调度是分层次的，在操作系统中，一般将调度分为高级调度、中级调度和低级调度。 高级调度也称作业调度，其主要任务是按一定的原则，对磁盘中的处于后备状态的作业进行选择并创建为进程。 中级调度的主要任务是按照给定的原则和策略，将处在磁盘对换区中切具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到对换区。

低级调度即进程（线程）调度，是决定就绪队列中哪个进程将获得处理机，并使即将处理及分配给该进程的操作。

进程（线程）调度即处理机调度。任务是控制、协调进程（线程）对CPU的竞争，按照一定的调度算法，使某一就绪进程获得CPU的控制权，转换成运行状态。

概述

进程（线程）调度的主要功能

记录系统中所有进程（线程）的执行状况，根据一定的调度算法，从就绪队列中选出一个进程（线程）来，准备把CPU分配给它，把CPU分配给进程（线程），即把选中进程（线程）的进程（线程）控制块内有关的现场信息，让它占用CPU运行。

进程（线程）调度的时机

• 正在执行的进程（线程）运行完毕。
• 调用阻塞原语将自己阻塞起来进入等待状态。
• 调用阻塞原语操作，并且因为资源不足而被阻塞；或调用唤醒原语操作激活了等待资源的进程（线程）。
• 时间片用完。
• 就绪队列中的某个就绪队列中一旦有优先级高于当前运行进程（线程）优先级时，引发进程（线程）调度。

抢占方式：就绪队列中一旦由优先级高于当前运行进程（线程）优先级的进程（线程）存在时，便立即进行调度，转让CPU。

不可抢占方式：一旦把CPU分配给一个进程（线程），它就一直占用CPU，直到该进程（线程）自己因调用原语操作或等待I/O而进入阻塞状态或时间片用完时才让出CPU，重新执行进程（线程）调度。

调度算法设计原则

进程行为

几乎所有的进程的（磁盘）I/O请求或计算都是交替完成的。某些I/O活动可以看作是计算，在CPU向视频RAM复制数据以更新屏幕时，因为使用了CPU，所以这是计算，而不是I/O，当一个进程等待外部设备完成工作而被阻塞的行为属于I/O。

计算密集型：进程花费了绝大多数时间在计算上。

I/O密集型：进程在等待I/O上花费了绝大多数时间。

系统分类

通常分为三类环境：批处理、交互式和实时系统。

批处理系统：减少了进程的切换从而改善了性能。

交互式：避免一个进程霸占CPU拒绝为其他进程服务，抢占是必需的。服务器也归于此类，因为通常他们要服务多个突发的（远程）用户。

实时限制：只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的非协作甚至是有恶意程序。

调度算法的设计目标

运行大量批处理作业的大型计算中心的管理者们为了掌握其系统的工作状态，通常是检查各个指标：吞吐量、周转时间以及CPU利用率。

吞吐量：是系统每小时完成的作业数量。

周转时间：从一个批处理作业提交时间开始直到该作业完成时刻为止的统计平均时间。

CPU利用率：用于对批处理系统的度量，系统每小时可完成多少作业（吞吐量），以及完成作业需要多长时间（周转时间）。

进程（线程）调度算法

进程（线程）调度算法解决以何中次序对各就绪进程（线程）进程处理机的分配以及按何种时间比例让进程（线程）占用处理机。

先来先服务FCFS算法

进程按照他们请求CPU的顺序使用CPU。

最短作业优先SJF算法

当输入队列中有若干同等重要的作业被启动时，调度程序应使用最短作业优先算法。

有4个作业A、B、C、D，运行时间分别是8、4、4、4分钟。

先到先服务：若按图A，B，C，D 的次序运行，则A的周转时间为8分钟，B为12分钟，C为16分钟，D为20分钟，平均为14分钟。

最短作业优先：运行顺序为BCDA，则周转时间分别为4、8、12、20分钟，平均时间为11分钟。

最短剩余时间优先SRTN算法

调度程序总是选择其剩余运行时间最短的那个进程运行。

最高响应比优先HRRF算法

响应比Rp=（等待时间+预计运行时间）/预计运行时间=周期时间/预计运行时间。

轮转法RR算法

基本思想：将CPU的处理时间划分为一个个的时间片，就绪队列中的诸程序轮流运行一个时间片。当时间片结束时，就强迫运行的进程让出CPU，该进程机内就绪队列，等待下一次调度。同时，进程调度又去选择就绪队列中的一个进程，分配给它一个时间片，以投入运行。

影响时间片值设置的几个主要因素：

1. 系统响应时间：当进程数目一定时，时间片Q值的大小占比于系统对响应时间的要求，例如进程数目为N，要求响应时间为T，则Q=T/N，Q值随T值的大或小而大或小。
2. 就绪进程的数目：当系统响应时间T一定时，时间片Q值的大小反比于就绪进程数。
3. 计算机的处理能力：计算机的处理能力直接决定了每道程序的处理时间，显然，处理速度越高，时间片值就可以越小。

结论：时间片设置的太短会导致过多的进程切换，降低了CPU效率；而设的太长有可能引起对短的交互请求的响应时间变长，将时间片设置为20~50ms通常是一个比较合理的折中。

最高优先级HPF算法

最高优先级调度每次将处理及分配给具有最高优先级的就绪进程（线程）。进程（线程）的优先级由进程（线程）优先数决定的。

进程（线程）优先数的设置可以是静态的也可以是动态的。

静态优先数是在进程（线程）创建时根据进程（线程）初始特性或用户要求而确定的，在进程（线程）运行期间不能再改变。

动态优先数是指在进程（线程）创建时先确定一个初始优先数，以后在进程（线程）运行中随着进程（线程）特性的改变（如等待时间增长），不断修改优先数。优先数小的进程（线程）优先级高。

如果不对优先级进行调整，则低优先级进程很有可能产生饥饿现象。

多级反馈队列算法

以最高优先级算法作为主要的调度模式，但对于具有相同优先数的进程（线程）按先进先出调度算法处理。

多级队列反馈法就是综合了先进先出调度算法、时间片轮转法和可抢占式最高优先级算法的一种进程（线程）调度算法。

被调度队列的设置：系统按优先级别设置若干个就绪队列，不同优先级别的队列有不同的时间片，对级别较高的队列分配较小的时间片Si（i=1，2…..，n）。 在同一个队列之间的调度原则：除了第n级队列是按照RR算法调度之外，其他各级队列均按照先进先出调度算法调度。 在不同队列之间的调度原则：西戎总是先调度级别比较高的队列，仅当级别较高的队列为空是才去调度次一级队列中的就绪队列。当等待进程（线程）被唤醒时，它进入与其优先级相同的就绪队列，若该进程（线程）优先级高于正在执行的的进程（线程），便抢占CPU。

最短进程优先

如何从当前可运行进程中找出最短的那一个进程。

根据进程过去的行为进行推测，并执行估计运行时间最短的哪一个。

老化：通过当前测量值和向前估计值进程加权平均而得到下一个估计值的技术。

实时系统中的调度算法

实时系统是一种时间起着主导作用的系统，即系统的正确性不及取决于计算的逻辑结果，而且还依赖于产生结果的时间。

实时系统应用的例子包括实验控制、过程控制设备、机器人、空中交通管制、电信、军事指挥与控制系统。

硬实时任务值必须满足最后期限的限制，否则会给系统带来不可接受的破坏或者致命的错误。

软实时任务也有一个与之关联的最后期限，并希望能满足这个期限的要求，但并不是强制的，即使超过了最后期限，调度和完成这个任务仍是有意义的。

1. 速率单调调度算法：适用于可抢先的周期性进程的经典静态实时调度算法是速率单调调度RMS。
   • 每个周期性进程必须在其周期内完成。
   • 没有进程依赖于任何其他进程。
   • 每一进程在一次有突发中需要相同的CPu时间量。
   • 任何非周期性进程都没有最终时限。
   • 进程抢先即刻发生而没有系统开销。
2. 最早最终时限优先调度：EDF算法是一个动态算法，它不像速率单调算法那样要求进程是周期性的，他也不详RMS那样要求CPU突发有相同的运行时间。