处理机调度算法的比较
计算机科学学院 计算机科学与技术 2009
摘要：处理机调度基本概念、调度算法优劣的评价准则、多种处理机调度算法的介绍 引言
操作系统是处理计算机硬件的一层软件和作为计算机用户与计算机硬件的中间的协调者。操作系统的CPU调度器负责给各个任务分发CPU带宽资源。调度算法负责管理当前执行任务等额顺序和性能
3 内容：
3.1 处理机调度的基本概念
高/中/低级调度
1. 高级调度（作业调度）
决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，准备执行。
2. 低级调度（进程调度）
决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。 非抢占方式和抢占方式
3. 中级调度
决定把又具备运行条件的挂起进程重新调入内存，挂到就绪队列上，准备执行。
3.2 调度算法优劣的评价准则
衡量和比较调度算法性能优劣主要有一下几个因素：
（1）CPU利用率。CPU是计算机系统中最重要的资源，所以应尽可能使CPU保持忙，使这一资源利用率最高。
（2）吞吐量。CPU运行时表示系统正处于工作状态，工作量的大小是以每单位时间所完成的作业数目来描述的，这就叫吞吐量。
（3）周转时间。指从作业提交到作业完成所经过的时间，包括作业等待，在就绪队列中排队，在处理机上运行以及进行输入/输出操作所花时间的总和。
（4）等待时间。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法优劣常常简单的考察等待时间。
（5）响应时间。指从作业提交到系统作出相应所经过的时间。在交互式系统中，作业的周转时间并不一定是最好的衡量准则，因此，常常使用另一种度量准则，即相应时间。从用户观点看，响应时间应该快一点好，但这常常要牺牲系统资源利用率为代价。
（6）公平性——确保每个用户每个进程获得合理的 CPU 份额或其他资源份额，不会出现饿死情况。 当然，这些目标本身就存在着矛盾之处，操作系统在设计时必须根据其类型的不
同进行权衡，以达到较好的效果。下面着重看一下批处理系统的调度性能指标。
批处理系统的调度性能主要用作业周转时间和作业带权周转时间来衡量，此时间
越短，则系统效率越高，作业吞吐能率越强。如果作业i 提交给系统的时刻是ts，完成 时刻是tf，那么，作业的周转时间ti 为：
ti =tf - ts
实际上，它是作业在系统里的等待时间与运行时间之和。从操作系统来说，为了
提高系统的性能，要让若干个用户的平均作业周转时间和平均带权作业周转时间最小。 平均作业周转时间 T = （Σti） / n
如果作业i 的周转时间为ti，所需运行时间为tk，则称wi=ti /tk 为该作业的带权周
转时间。因为，ti 是等待时间与运行时间之和，故带权周转时间总大于1。
平均作业带权周转时间W = （Σwi） / n
通常，用平均作业周转时间来衡量对同一作业流施行不同作业调度算法时，它们
呈现的调度性能；用平均作业带权周转时间来衡量对不同作业流施行同一作业调度算
法时，它们呈现的调度性能。这两个数值均越小越好。
3.3几种处理机调度算法详细介绍
3.3.1作业调度
1、先来先服务算法
先来先服务FCFS（First Come，First Served）算法是按照作业进入系统的作业
后备队列的先后次序来挑选作业，先进入系统的作业优先被挑选。这是一种非剥夺式
算法，容易实现，但效率不高，只顾及到作业等候时间，而没考虑作业要求服务时间
的长短。显然这不利于短作业而优待了长作业，或者说有利于CPU 繁忙型作业而不利
于I/O 繁忙型作业。有时为了等待长作业的执行，而使短作业的周转时间变得很大。
从而，平均周转时间也变大。
2、最短作业优先算法
最短作业优先SJF（Shortest Job First ）算法是以进入系统的作业所要求的CPU
时间长短为标准，总是选取估计计算时间最短的作业投入运行。这是一种非剥夺式调
度算法，它克服了FCFS 偏爱长作业的缺点，易于实现，但效率也不高。它的主要弱
点：一是需要预先知道作业所需的CPU 时间，这个估计值很难精确，如果程序员估计
过低，系统就可能提前终止该作业；二是忽视了作业等待时间，由于系统不断地接受
新作业，而作业调度又总是选择计算时间短的作业投入运行，因此，使进入系统时间
早但计算时间长的作业等待时间过长，会出现饥饿现象；三是尽管减少了对长作业的
偏爱，但由于缺少剥夺机制，对分时、实时处理仍然很不理想。
3、响应比最高者优先（HRRF）算法
先来先服务算法与最短作业优先算法都是比较片面的调度算法。先来先服务算法
只考虑作业的等候时间而忽视了作业的计算时间，而最短作业优先算法恰好与之相反，
它只考虑用户估计的作业计算时间而忽视了作业的等待时间。响应比最高者优先算法
（Highest Response Ratio First）是介乎这两种算法之间的一种折衷的策略，既考虑作
业等待时间，又考虑作业的运行时间，这样既照顾了短作业又不使长作业的等待时间
过长，改进了调度性能。缺点是每次计算各道作业的响应比会有一定的时间开销，需
要估计期待的服务时间，性能要比SJF 略差。这里把作业进入系统后的等待时间与估
计计算时间之和称为作业的响应时间，作业的响应时间除以作业估计计算时间称作响
应比，现定义：
响应比＝作业响应时间/作业估计计算时间=1+作业等待时间/作业估计计算时间
每当调度一个作业运行时，都要计算后备作业队列中每个作业的响应比，选择响
应比最高者投入运行。显然，计算时间短的作业容易得到较高的响应比，因为，这时
分母较小，使得HRRF 较高，因此，本算法是优待短作业的。但是，如果一个长作业
在系统中等待的时间足够长后，由于，它的年龄较大使得分子足够大，则HRRF 较大，
那么，它也将获得足够高的响应比，从而，可以被选中执行，不至于长时间地等待下
去，饥饿的现象不会发生。
4、优先数法
这种算法是根据确定的优先数来选取作业，每次总是选择优先数高的作业。规定
用户作业优先数的方法是多种多样的。一种是由用户自己提出作业的优先数，称作外
部优先数法。有的用户为了自己的作业尽快的被系统选中就设法提高自己作业的优先
数，这时系统可以规定优先数越高则需付出的计算机使用费就越多，以作限制。另一
种是由系统综合考虑有关因素来确定用户作业的优先数，称作内部优先数法。
5、分类调度算法
分类调度算法预先按一定的原则把作业划分成若干类，以达到均衡使用操作系统
资源和兼顾大小作业的目的。分类原则包括：作业计算时间、对内存的需求、对外围
设备的需求等。作业调度时还可以为每类作业设置优先级，从而，照顾到同类作业中
的轻重缓急。
6、用磁带与不用磁带的作业搭配
这种算法将需要使用磁带机的作业分开来。在作业调度时，把使用磁带机的作业
和不使用磁带机的作业搭配挑选。在不使用磁带机的作业执行时，可预先通知操作员
将下一批作业要用的磁带预先装上，这样可使要用磁带机的作业在执行时省去等待装
磁带的时间。显然，这对缩短系统的平均周转时间是有益的。
3.3.2 低级调度
1、先来先服务算法
先来先服务算法是按照进程进入就绪队列的先后次序来分配处理器。先进入就绪
队列的进程优先被挑选，运行进程一旦占有处理器将一直运行下去直到运行结束或被
阻塞，这是一种非剥夺式调度。这种算法容易实现，但效率不高，显然，不利于I/O
频繁的进程。
2、时间片轮转调度
轮转法调度也称之为时间片调度，具体做法是调度程序每次把CPU 分配给就绪队
列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个这样
的时间片。当这个时间片结束时，就强迫一个进程让出处理器，让它排列到就绪队列
的尾部，等候下一轮调度。实现这种调度要使用一个间隔时钟。当一个进程开始运行
时，就将时间片的值置入间隔时钟内，当发生间隔时钟中断时，就表明该进程连续运
行的时间已超过一个规定的时间片。此时，中断处理程序就通知处理器调度进行处理
器的切换工作。这种调度策略可以防止那些很少使用外围设备的进程过长的占用处理
器，导致要使用外围设备的那些进程没有机会去启动外围设备。
最常用的轮转法是基本轮转法。它要求每个进程轮流地运行相同的一个时间片。
在分时系统中，这是一种较简单又有效的调度策略。—个分时系统有许多终端设备，
终端用户在各自的终端设备上同时使用计算机，如果某个终端用户的程序长时间的占
用处理器，势必使其他终端用户的要求不能得到及时响应。一般说分时系统的终端用
户提出要求后到计算机响应给出回答的时间只能是几秒钟，这样才能使终端用户感到
满意。采用基本轮转的调度策略可以使系统及时响应。例如，一个分时系统有10 个终
端，如果每个终端用户进程的时间片为100ms，那么，粗略地说，每个终端用户在每
秒钟内可以得到大约100ms 的处理器时间，如果对于终端用户的每个要求，处理器花
费300ms 的时间就可以给出回答时，那么，终端响应的时间大致就在3 秒左右，这样
可算得上及时响应了。
基本轮转法的策略可以略加修改。例如，对于不同的进程给以不同的时间片；时
间片的长短可以动态地修改等等，这些做法主要是为了进一步提高效率。
轮转法调度是一种剥夺式调度，系统耗费在进程切换上的开销比较大，这个开销
与时间片的大小很有关系。如果时间片取值太小，以致于大多数进程都不可能在一个
时间片内运行完毕，切换就会频繁，系统开销显著增大，所以，从系统效率来看，时
间片取大一点好。另一方面，时间片长度较大，那么，随着就绪队列里进程数目的增
加，轮转一次的总时间增大，亦即对每个进程的响应速度放慢了，甚至时间片大到让
每个进程足以完成其所有任务，这一算法便退化成先来先服务算法。为了满足用户对
响应时间的要求，要么限制就绪队列中的进程数量，要么采用动态时间片法，根据当
前负载状况，及时调整时间片的大小。所以，时间片大小的确定要从进程个数、切换
开销、系统效率和响应时间等多方面考虑。
3、优先数调度
给每一个进程确定一个优先数，处理器调度每次选择就绪进程中优先数最大者，
让它占用处理器运行称优先数调度。怎样确定优先数呢?可以有以下几种考虑，使用外
围设备频繁者优先数大，这样有利于提高效率；重要算题进程的优先数大，这样有利
于用户更早得到计算结果；进入计算机时间长的进程优先数大，这样有利于缩短作业
的周转时间；交互式用户的进程优先数大，这样有利于终端用户的响应时间等等，以
上采用了静态优先数法。效率高性能好的低级调度可采用动态优先数法，在创建一个
进程时，根括进程类型和资源使用情况确定一个优先数，而当进程耗尽时间片或重新
被调度时，再次计算并调整所有进程的优先数。基本原则是：①根据进程占有CPU 时
间多少来决定，当一个进程占有CPU 时间愈长，那么，在它被阻塞之后再次获得调度
的优先数就越低，反之，进程获得调度的可能性越大；②根据进程等待CPU 时间多少
来决定，一个进程在队列中等待CPU 的时间愈长，那么，在它再次获得调度时的优先
数就越高，反之，进程获得调度的可能性越小。基于优先数的低级调度算法可以按调
度方式不同分为剥夺式和非剥夺式优先数调度算法。
4、多级反馈队列调度
多级反馈队列调度这种方法又称反馈循环队列或多队列策略。其主要思想是将就
绪进程或线程分为两级或多级，系统相应建立两个或多个就绪队列，较高优先级的队
列一般分配给较短的时间片。处理器调度每次先从高一级的就绪进程队列中选取可占
有处理器的进程，同一队列中按先来先服务原则排队，只有在选不到时，才从较低一
级的就绪进程队列中选取。
5、保证调度算法
一种完全不同的调度算法是向用户做出明确的性能保证，然后去实现它，称保证
调度算法。一种很实际并很容易实现的保证是：当你工作时己有n 个用户登录在系统，
则你将获得CPU 处理能力的1/n。类似地，如果在一个有n 个进程运行的用户系统中，
每个进程将获得CPU 处理能力的1/n。
为了实现所作的保证，系统必须跟踪各个进程自创建以来已经使用了多少CPU 时
间。然后，计算各个进程应获得的CPU 时间，即自创建以来的时间除以n。由于各个
进程实际获得的CPU 时间已知，所以，很容易计算出实际获得的CPU 时间和应获得
的CPU 时间之比，于是调度将转向比率最低的进程。
6、彩票调度算法
尽管向用户做出承诺并履行它是一个好主意，但实现却很困难。不过有另一种可
以给出类似的可预见结果，而且实现起来简单许多，这种算法称为彩票调度算法。
3.3.3 实时调度
1）单比率调度算法
单比率调度事先为每个进程分配一个与事件发生频率成正比的优先数，运行频率
越高的进程其优先就数越高。例如，周期为20ms 的进程优先数为50，周期为100ms
的进程优先数为10，运行时调度程序总是调度优先数最高的就绪进程，并采取抢占式
分配策略。可以证明该算法是最优的。
2）限期调度算法
限期调度的基本思想是：当一个事件发生时，对应的进程就被加入就绪进程队列。
该就绪队列按照截止期限排序，对于一个周期性事件，其截止期限即为事件下一次发
生的时间。该调度算法首先运行队首进程，即截止时间最近的那个进程。
3）最少裕度法
最少裕度法的基本思想是：首先计算各个进程的富裕时间，即裕度（laxity），然
后选择裕度最少的进程执行。计算公式为：裕度=截止时间-(就绪时间+计算时间) ,裕度
小说明很紧迫了，就绪后让它尽快运行。
3.3.4 多处理系统调度
1）负载共享调度算法
2）群调度算法
3）处理器专派调度算法
4）动态调度算法
结语：综上所述，本文简单的介绍了处理机调度基本概念、调度算法优劣的评价准则、多种处理机调度算法的介绍。本文重点讲述了作业调度和低级调度并作出分析。
参考文献：
【1】孙钟秀主编 费翔林 骆斌 谢立参编 操作系统教程.北京：高等教育出版社,2003
处理机调度算法的比较
计算机科学学院 计算机科学与技术 2009
摘要：处理机调度基本概念、调度算法优劣的评价准则、多种处理机调度算法的介绍 引言
操作系统是处理计算机硬件的一层软件和作为计算机用户与计算机硬件的中间的协调者。操作系统的CPU调度器负责给各个任务分发CPU带宽资源。调度算法负责管理当前执行任务等额顺序和性能
3 内容：
3.1 处理机调度的基本概念
高/中/低级调度
1. 高级调度（作业调度）
决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，准备执行。
2. 低级调度（进程调度）
决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。 非抢占方式和抢占方式
3. 中级调度
决定把又具备运行条件的挂起进程重新调入内存，挂到就绪队列上，准备执行。
3.2 调度算法优劣的评价准则
衡量和比较调度算法性能优劣主要有一下几个因素：
（1）CPU利用率。CPU是计算机系统中最重要的资源，所以应尽可能使CPU保持忙，使这一资源利用率最高。
（2）吞吐量。CPU运行时表示系统正处于工作状态，工作量的大小是以每单位时间所完成的作业数目来描述的，这就叫吞吐量。
（3）周转时间。指从作业提交到作业完成所经过的时间，包括作业等待，在就绪队列中排队，在处理机上运行以及进行输入/输出操作所花时间的总和。
（4）等待时间。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法优劣常常简单的考察等待时间。
（5）响应时间。指从作业提交到系统作出相应所经过的时间。在交互式系统中，作业的周转时间并不一定是最好的衡量准则，因此，常常使用另一种度量准则，即相应时间。从用户观点看，响应时间应该快一点好，但这常常要牺牲系统资源利用率为代价。
（6）公平性——确保每个用户每个进程获得合理的 CPU 份额或其他资源份额，不会出现饿死情况。 当然，这些目标本身就存在着矛盾之处，操作系统在设计时必须根据其类型的不
同进行权衡，以达到较好的效果。下面着重看一下批处理系统的调度性能指标。
批处理系统的调度性能主要用作业周转时间和作业带权周转时间来衡量，此时间
越短，则系统效率越高，作业吞吐能率越强。如果作业i 提交给系统的时刻是ts，完成 时刻是tf，那么，作业的周转时间ti 为：
ti =tf - ts
实际上，它是作业在系统里的等待时间与运行时间之和。从操作系统来说，为了
提高系统的性能，要让若干个用户的平均作业周转时间和平均带权作业周转时间最小。 平均作业周转时间 T = （Σti） / n
如果作业i 的周转时间为ti，所需运行时间为tk，则称wi=ti /tk 为该作业的带权周
转时间。因为，ti 是等待时间与运行时间之和，故带权周转时间总大于1。
平均作业带权周转时间W = （Σwi） / n
通常，用平均作业周转时间来衡量对同一作业流施行不同作业调度算法时，它们
呈现的调度性能；用平均作业带权周转时间来衡量对不同作业流施行同一作业调度算
法时，它们呈现的调度性能。这两个数值均越小越好。
3.3几种处理机调度算法详细介绍
3.3.1作业调度
1、先来先服务算法
先来先服务FCFS（First Come，First Served）算法是按照作业进入系统的作业
后备队列的先后次序来挑选作业，先进入系统的作业优先被挑选。这是一种非剥夺式
算法，容易实现，但效率不高，只顾及到作业等候时间，而没考虑作业要求服务时间
的长短。显然这不利于短作业而优待了长作业，或者说有利于CPU 繁忙型作业而不利
于I/O 繁忙型作业。有时为了等待长作业的执行，而使短作业的周转时间变得很大。
从而，平均周转时间也变大。
2、最短作业优先算法
最短作业优先SJF（Shortest Job First ）算法是以进入系统的作业所要求的CPU
时间长短为标准，总是选取估计计算时间最短的作业投入运行。这是一种非剥夺式调
度算法，它克服了FCFS 偏爱长作业的缺点，易于实现，但效率也不高。它的主要弱
点：一是需要预先知道作业所需的CPU 时间，这个估计值很难精确，如果程序员估计
过低，系统就可能提前终止该作业；二是忽视了作业等待时间，由于系统不断地接受
新作业，而作业调度又总是选择计算时间短的作业投入运行，因此，使进入系统时间
早但计算时间长的作业等待时间过长，会出现饥饿现象；三是尽管减少了对长作业的
偏爱，但由于缺少剥夺机制，对分时、实时处理仍然很不理想。
3、响应比最高者优先（HRRF）算法
先来先服务算法与最短作业优先算法都是比较片面的调度算法。先来先服务算法
只考虑作业的等候时间而忽视了作业的计算时间，而最短作业优先算法恰好与之相反，
它只考虑用户估计的作业计算时间而忽视了作业的等待时间。响应比最高者优先算法
（Highest Response Ratio First）是介乎这两种算法之间的一种折衷的策略，既考虑作
业等待时间，又考虑作业的运行时间，这样既照顾了短作业又不使长作业的等待时间
过长，改进了调度性能。缺点是每次计算各道作业的响应比会有一定的时间开销，需
要估计期待的服务时间，性能要比SJF 略差。这里把作业进入系统后的等待时间与估
计计算时间之和称为作业的响应时间，作业的响应时间除以作业估计计算时间称作响
应比，现定义：
响应比＝作业响应时间/作业估计计算时间=1+作业等待时间/作业估计计算时间
每当调度一个作业运行时，都要计算后备作业队列中每个作业的响应比，选择响
应比最高者投入运行。显然，计算时间短的作业容易得到较高的响应比，因为，这时
分母较小，使得HRRF 较高，因此，本算法是优待短作业的。但是，如果一个长作业
在系统中等待的时间足够长后，由于，它的年龄较大使得分子足够大，则HRRF 较大，
那么，它也将获得足够高的响应比，从而，可以被选中执行，不至于长时间地等待下
去，饥饿的现象不会发生。
4、优先数法
这种算法是根据确定的优先数来选取作业，每次总是选择优先数高的作业。规定
用户作业优先数的方法是多种多样的。一种是由用户自己提出作业的优先数，称作外
部优先数法。有的用户为了自己的作业尽快的被系统选中就设法提高自己作业的优先
数，这时系统可以规定优先数越高则需付出的计算机使用费就越多，以作限制。另一
种是由系统综合考虑有关因素来确定用户作业的优先数，称作内部优先数法。
5、分类调度算法
分类调度算法预先按一定的原则把作业划分成若干类，以达到均衡使用操作系统
资源和兼顾大小作业的目的。分类原则包括：作业计算时间、对内存的需求、对外围
设备的需求等。作业调度时还可以为每类作业设置优先级，从而，照顾到同类作业中
的轻重缓急。
6、用磁带与不用磁带的作业搭配
这种算法将需要使用磁带机的作业分开来。在作业调度时，把使用磁带机的作业
和不使用磁带机的作业搭配挑选。在不使用磁带机的作业执行时，可预先通知操作员
将下一批作业要用的磁带预先装上，这样可使要用磁带机的作业在执行时省去等待装
磁带的时间。显然，这对缩短系统的平均周转时间是有益的。
3.3.2 低级调度
1、先来先服务算法
先来先服务算法是按照进程进入就绪队列的先后次序来分配处理器。先进入就绪
队列的进程优先被挑选，运行进程一旦占有处理器将一直运行下去直到运行结束或被
阻塞，这是一种非剥夺式调度。这种算法容易实现，但效率不高，显然，不利于I/O
频繁的进程。
2、时间片轮转调度
轮转法调度也称之为时间片调度，具体做法是调度程序每次把CPU 分配给就绪队
列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个这样
的时间片。当这个时间片结束时，就强迫一个进程让出处理器，让它排列到就绪队列
的尾部，等候下一轮调度。实现这种调度要使用一个间隔时钟。当一个进程开始运行
时，就将时间片的值置入间隔时钟内，当发生间隔时钟中断时，就表明该进程连续运
行的时间已超过一个规定的时间片。此时，中断处理程序就通知处理器调度进行处理
器的切换工作。这种调度策略可以防止那些很少使用外围设备的进程过长的占用处理
器，导致要使用外围设备的那些进程没有机会去启动外围设备。
最常用的轮转法是基本轮转法。它要求每个进程轮流地运行相同的一个时间片。
在分时系统中，这是一种较简单又有效的调度策略。—个分时系统有许多终端设备，
终端用户在各自的终端设备上同时使用计算机，如果某个终端用户的程序长时间的占
用处理器，势必使其他终端用户的要求不能得到及时响应。一般说分时系统的终端用
户提出要求后到计算机响应给出回答的时间只能是几秒钟，这样才能使终端用户感到
满意。采用基本轮转的调度策略可以使系统及时响应。例如，一个分时系统有10 个终
端，如果每个终端用户进程的时间片为100ms，那么，粗略地说，每个终端用户在每
秒钟内可以得到大约100ms 的处理器时间，如果对于终端用户的每个要求，处理器花
费300ms 的时间就可以给出回答时，那么，终端响应的时间大致就在3 秒左右，这样
可算得上及时响应了。
基本轮转法的策略可以略加修改。例如，对于不同的进程给以不同的时间片；时
间片的长短可以动态地修改等等，这些做法主要是为了进一步提高效率。
轮转法调度是一种剥夺式调度，系统耗费在进程切换上的开销比较大，这个开销
与时间片的大小很有关系。如果时间片取值太小，以致于大多数进程都不可能在一个
时间片内运行完毕，切换就会频繁，系统开销显著增大，所以，从系统效率来看，时
间片取大一点好。另一方面，时间片长度较大，那么，随着就绪队列里进程数目的增
加，轮转一次的总时间增大，亦即对每个进程的响应速度放慢了，甚至时间片大到让
每个进程足以完成其所有任务，这一算法便退化成先来先服务算法。为了满足用户对
响应时间的要求，要么限制就绪队列中的进程数量，要么采用动态时间片法，根据当
前负载状况，及时调整时间片的大小。所以，时间片大小的确定要从进程个数、切换
开销、系统效率和响应时间等多方面考虑。
3、优先数调度
给每一个进程确定一个优先数，处理器调度每次选择就绪进程中优先数最大者，
让它占用处理器运行称优先数调度。怎样确定优先数呢?可以有以下几种考虑，使用外
围设备频繁者优先数大，这样有利于提高效率；重要算题进程的优先数大，这样有利
于用户更早得到计算结果；进入计算机时间长的进程优先数大，这样有利于缩短作业
的周转时间；交互式用户的进程优先数大，这样有利于终端用户的响应时间等等，以
上采用了静态优先数法。效率高性能好的低级调度可采用动态优先数法，在创建一个
进程时，根括进程类型和资源使用情况确定一个优先数，而当进程耗尽时间片或重新
被调度时，再次计算并调整所有进程的优先数。基本原则是：①根据进程占有CPU 时
间多少来决定，当一个进程占有CPU 时间愈长，那么，在它被阻塞之后再次获得调度
的优先数就越低，反之，进程获得调度的可能性越大；②根据进程等待CPU 时间多少
来决定，一个进程在队列中等待CPU 的时间愈长，那么，在它再次获得调度时的优先
数就越高，反之，进程获得调度的可能性越小。基于优先数的低级调度算法可以按调
度方式不同分为剥夺式和非剥夺式优先数调度算法。
4、多级反馈队列调度
多级反馈队列调度这种方法又称反馈循环队列或多队列策略。其主要思想是将就
绪进程或线程分为两级或多级，系统相应建立两个或多个就绪队列，较高优先级的队
列一般分配给较短的时间片。处理器调度每次先从高一级的就绪进程队列中选取可占
有处理器的进程，同一队列中按先来先服务原则排队，只有在选不到时，才从较低一
级的就绪进程队列中选取。
5、保证调度算法
一种完全不同的调度算法是向用户做出明确的性能保证，然后去实现它，称保证
调度算法。一种很实际并很容易实现的保证是：当你工作时己有n 个用户登录在系统，
则你将获得CPU 处理能力的1/n。类似地，如果在一个有n 个进程运行的用户系统中，
每个进程将获得CPU 处理能力的1/n。
为了实现所作的保证，系统必须跟踪各个进程自创建以来已经使用了多少CPU 时
间。然后，计算各个进程应获得的CPU 时间，即自创建以来的时间除以n。由于各个
进程实际获得的CPU 时间已知，所以，很容易计算出实际获得的CPU 时间和应获得
的CPU 时间之比，于是调度将转向比率最低的进程。
6、彩票调度算法
尽管向用户做出承诺并履行它是一个好主意，但实现却很困难。不过有另一种可
以给出类似的可预见结果，而且实现起来简单许多，这种算法称为彩票调度算法。
3.3.3 实时调度
1）单比率调度算法
单比率调度事先为每个进程分配一个与事件发生频率成正比的优先数，运行频率
越高的进程其优先就数越高。例如，周期为20ms 的进程优先数为50，周期为100ms
的进程优先数为10，运行时调度程序总是调度优先数最高的就绪进程，并采取抢占式
分配策略。可以证明该算法是最优的。
2）限期调度算法
限期调度的基本思想是：当一个事件发生时，对应的进程就被加入就绪进程队列。
该就绪队列按照截止期限排序，对于一个周期性事件，其截止期限即为事件下一次发
生的时间。该调度算法首先运行队首进程，即截止时间最近的那个进程。
3）最少裕度法
最少裕度法的基本思想是：首先计算各个进程的富裕时间，即裕度（laxity），然
后选择裕度最少的进程执行。计算公式为：裕度=截止时间-(就绪时间+计算时间) ,裕度
小说明很紧迫了，就绪后让它尽快运行。
3.3.4 多处理系统调度
1）负载共享调度算法
2）群调度算法
3）处理器专派调度算法
4）动态调度算法
结语：综上所述，本文简单的介绍了处理机调度基本概念、调度算法优劣的评价准则、多种处理机调度算法的介绍。本文重点讲述了作业调度和低级调度并作出分析。
参考文献：
【1】孙钟秀主编 费翔林 骆斌 谢立参编 操作系统教程.北京：高等教育出版社,2003