操作系统中存在多种调度算法，有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的调度算法两者都适用。

1.先来先服务调度算法（FCFS）

该算法既可用于作业调度，也可用于进程调度。在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存,为他们分配必要的资源，创建进程并放入就绪队列。

先来先服务算法在单处理机系统中已很少作为主调度算法，但经常把它与其它调度算法相结合使用，形成一种更为有效的调度算法。

 

2.短作业优先调度算法（SJF）

SJF 算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF 算法可以分别用于作业调度和进程调度。

但仍然存在不容忽视的缺点：

①必须预知作业的运行时间。

②对长作业非常不利，长作业的周转时间会明显地增长。更严重的是，该算法完全忽视作业的等待时间，可能使作业等待时间过长，出现饥饿现象。

③在采用SJF算法时，人——机无法实现交互。

④该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。

 

3.优先级调度算法

在优先级调度算法中，则是基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的。这样就可以保证紧迫性作业优先运行。优先级调度算法可作为作业调度算法，也可作为进程调度算法。

1.优先级调度算法的类型

• 非剥夺式优先级调度算法：当一个进程正在处理机上运行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让该进程一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，才把处理机分配给另一优先级最高的进程。
• 剥夺式优先级调度算法：当一个进程正在处理机上运行时，若有某个优先级更高的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给优先级更高的进程。

2.优先级的类型

优先级调度算法的关键在于：应如何确定进程的优先级，以及确定是使用静态优先级还是动态优先级。

• 静态优先级：优先级是在创建进程时确定的，在进程的整个运行期间保持不变。确定静态优先级大小的主要依据有进程类型、进程对资源的要求、用户要求。

• 动态优先级：动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。动态调整优先级的主要依据有进程占有CPU时间的长短、就绪进程等待CPU时间的长短。

一般，进程优先级的设置可以参考以下原则：

①系统进程>用户进程 ②交互型进程>交互型进程 ③I/O型进程>计算型进程

 

4.高响应比优先调度算法（HRRN）

FCFS 算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。SJF 算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。

高响应比优先调度算法主要用于作业调度。其基本思想是每次进行作业调度时，先计算就绪队列中的每个作业的响应比，挑选响应比最高的作业投入运行。

响应比的计算公式：

 

根据公式可知：

• 作业的等待时间相同时，要求服务...

课后习题

 

1. 【2013统考真题】某系统正在执行三个进程P1、P2、P3，各进程的计算（CPU）时间和I/O时间比例如下表所示。

为提高系统资源利用率，合理的进程优先级设置应为（ ）。
A. P1 > P2 > P3         B.P3 > P2 > P1
C.    P2 > P1 = P3            D.   P1 > P2 = P3 

【答案】B

【解析】为了合理地设置进程优先级，应综合考虑进程的CPU时间和I/O时间。对于优先级调度算法，一般来说，I/O型作业的优先权高于计算型作业的优先权，这是由于I/O操作需要及时完成，它没有办法长时间地保存所要输入/输出的数据，所以考虑到系统资源利用率，要选择I/O繁忙型作业有更高的优先级。

 

2.下列调度算法中，（  ）调度算法是绝对可抢占的。

A. 先来先服务             B.时间片轮转
C.优先级                  D.短进程优先

【答案】B

【解析】时间片轮转算法是按固定的时间配额来运行的，时间一到，不管是否完成，当前的进程必须撤下，调度新的进程，因此它是由时间配额决定的、是绝对可抢占的。而优先级算法和短进程优先算法都可分为抢占式和不可抢占式。

 

3. 【2009统考真题】下列进程调度算法中，综合考虑进程等待时间和执行时间的是（  ）。

A. 时间片轮转调度算法            B. 短进程优先调度算法
C.先来先服务调度算法             D. 高响应比优先调度算法

【答案】D

【解析】响应比R = （等待时间+ 执行时间）/执行时间。它综合考虑了每个进程的等待时间和执行时间，对于同时到达的长进程和短进程，短进程会优先执行，以提高系统吞吐量；而长进程的响应比可以随等待时间的增加而提高，不会产生进程无法调度的情况。

 

4. 【2017统考真题】假设4个作业到达系统的时刻和运行时间如下表所示。

系统在t=2时开始作业调度，若分别采用先来先服务和短作业优先调度算法，则选中的作业分别是（ ）。
A.  J2、J3                          B.J1、J4    
C.  J2、J4                          D. J1、J3    

【答案】D

【解析】先来先服务调度算法是作业来得越早，优先级越高，因此会选择Ji。短作业优先调度算法是 作业运行时间越短，优先级越高，因此会选择所以选项D 正确。

 

5.【2012统考真题】一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达，它的计算和I/O操作顺序如下：

P1：计算60ms，I/O80ms，计算20ms

P2：计算120ms，I/O40ms，计算40ms

若不考虑调度和切换时间，则完成两个作业需要的时间最少是（  ）。

A. 240ms                         B. 260ms

C.340ms                          D. 360ms

【答案】B

【解析】由于比晚 5ms到达，Pi先占用CPU ,作业运行的甘特图如下。

 

6.【2016统考真题】某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms，3ms和4ms，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是（  ）。

A. 15ms                         B. 17ms

C.22ms                          D. 27ms

【答案】B

【解析】这类调度题目最好画图。因CPU、输入设备、输出设备都只有一个，因此各操作步骤不能重叠，画出运行时的甘特图后，就能清楚地看到不同作业间的时序关系，如下图所示。

 

7. 【2017统考真题】下列有关基于时间片的进程调度的叙述中，错误的是（  ）。

A. 时间片越短，进程切换的次数越多，系统开销越大

B. 当前进程的时间片用完后，该进程状态由执行态变为阻塞态

C. 时钟中断发生后，系统会修改当前进程在时间片内的剩余时间

D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等

【答案】B

【解析】进程切换带来系统开销，切换次数越多，开销越大，选项A 正确。当前进程的时间片用完后,其状态由执行态变为就绪态，选项B 错误。时钟中断是系统中特定的周期性时钟节拍，操作系统通过它来确定时间间隔，实现时间的延时和任务的超时，选项C 正确。现代操作系统为了保证性能最优，通常根据响应时间、系统开销、进程数量、进程运行时间、进程切换开销等因素确定时间片大小，选项D 正确。

 

8. 【2012统考真题】若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（  ）。

A. 在进程结束时能进行处理机调度

B. 创建新进程后能进行处理机调度

C. 在进程处于临界区时不能进行处理机调度

D. 在系统调用完成并返回用户态时能进行处理机调度

【答案】C

【解析】选项A、B、D 显然属于可以进行处理机调度的情况。对于选项C，当进程处于临界区时，说明进程正在占用处理机，只要不破坏临界资源的使用规则，就不会影响处理机的调度。比如，通常访问的临界资源可能是慢速的外设（如打印机），若在进程访问打印机时，不能进行处理机调度，则系统的性能将非常差。

 

9. 【2011统考真题】下列选项中，满足短作业优先且不会发生饥饿现象的是（  ）调度算法。

A. 先来先服务

B. 高响应比优先

C. 时间片轮转

D. 非抢占式短作业优先

【答案】B

【解析】响应比= （等待时间+ 执行时间）/执行时间。高响应比优先算法在等待时间相同的情况下，作业执行时间越短，响应比越高，满足短任务优先。随着长作业等待时间的增加，响应比会变大，执行机会也会增大，因此不会发生饥饿现象。先来先服务和时间片轮转不符合短任务优先，非抢占式短任务优先会产生饥饿现象。

 

10. 【2014统考真题】下列调度算法中，不可能导致饥饿现象的是（  ）。

A. 时间片轮转

B. 静态优先数调度

C. 非抢占式短作业优先

D. 抢占式短作业优先

【答案】A

【解析】采用静态优先级调度且系统总是出现优先级高的任务时，优先级低的任务总是得不到处理机而产生饥饿现象；而短任务优先调度不管是抢占式的还是非抢占的，当系统总是出现新来的短任务时，长任务会总是得不到处理机，产生饥饿现象，因此选项B、C、D 都错误。

 

11. 【2018统考真题】某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1μs。在T时刻就绪队列中有3个进程、和，其在就绪队列中的等待时间，需要的CPU时间和优先权如下表所示。

若优先权值大的进程优先权获得CPU，从T时刻起系统开始进程调度，则系统的平均周转时间为（  ）。

A. 54μs           B. 73μs             C. 74μs            D. 75μs

【答案】D

【解析】由优先权可知,进程的执行顺序为 P2->P3->P1。P2的周转时间为1 + 15 + 24 = 40μs； P3的周转时间为 18 + 1 +24+ 1 + 36 = 80μs； Pi 的周转时间为 30 + 1 + 24 + 1 + 36 + 1 + 12 = 105μs；平均周转时间为（40 + 80+ 105）/3 = 225/3 = 75μs, 因此选 D。

 

12.【2019统考真题】系统采用二级反馈队列调度算法进行进程调度。就绪队列Q1采用时间片轮转调度算法，时间片为10ms；就绪队列Q2采用短进程优先调度算法；系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程；新创建的进程首先进入Q1；Q1中的进程执行一个时间片后，若未结束，则转入Q2，若当前Q1、Q2为空，系统依次创建进程P1、P2需要的CPU时间分别为30ms和20ms，则进程P1、P2在系统中的平均等待时间为（  ）。

A. 25ms           B. 20ms             C. 15ms            D. 10ms

【答案】C

【解析】进程P1、P2依次创建后进入队列Q1，根据时间片调度算法的规则，进程P1、P2将依次被分配 10ms的CPU时间，两个进程分别执行完一个时间片后都会被转入队列Q2，就绪队列Q2采用短进程优先调度算法，此时P1还需要20ms的 CPU时间，P2还需要10ms的 CPU时间，所以P2会被优先调度执行，10ms后进程P2执行完成，之后P1再调度执行，再过20ms后P1也执行完成。

进程P1、P2的等待时间分别为图中的虚横线部分，平均等待时间=（P1等待时间+P2等待时间）/2 = （ 20 + 10）/2 = 15 ,因此答案选C。

 

13. 有一个CPU和两台外设D1、D2, 且在能够实现抢占式优先级调度算法的多道程序环境中， 同时进入优先级由高到低的P1、P2、P3，三个作业，每个作业的处理顺序和使用资源的时间如下:

P1：D2（30ms），CPU（10ms），D1（30ms），CPU（10ms）

P2：D1（20ms），CPU（20ms），D2（40ms）

P3：CPU（30ms），D1（20ms）

假设忽略不计其他辅助操作的时间，每个作业的周转时间T1、T2、T3分别为多少？ CPU和D1的利用率各是多少？

【解析】抢占式优先级调度算法，三个作业执行的顺序如下图所示。

作业P1的优先级最高，周转时间等于运行时间， T1 = 80ms；作业P2的等待时间为10ms，运

行时间为80ms，周转时间T2 = (10 + 80)ms = 90ms；作业P3的等待时间为40ms，运行时间为50ms，因此周转时间T3 = 90ms。

三个作业从进入系统到全部运行结束，时间为90ms。CPU与外设都是独占设备，运行时间分别为各作业的使用时间之和。CPU运行时间为[(10 +10) + 20 + 30]ms = 70ms,，D1为(30 + 20 + 20)ms = 70ms，D2为(30 + 40)ms = 70 ms，因此利用率均为70/90 = 77.8%。

 

14. 假定要在一台处理器上执行下表所示的作业，且假定这些作业在时刻。以 1, 2, 3, 4, 5 的顺序到达。说明分别使用FCFS、RR (时间片= 1 )、SJF及非剥夺式优先级调度算法时，这些作业的执行情况(优先级的高低顺序依次为1到5 ) 。

针对上述每种调度算法，给出平均周转时间和平均带权周转时间。

【解析】

1) 作业执行情况可以用如下的甘特图来表示。

2）各个作业对应于各个算法的周转时间和加权周转时间见下表。

所以，FCFS的平均周转时间为13.4，平均加权周转时间为7.26。

RR的平均周转时间为9.2 ，平均加权周转时间为2.84。

SJF的平均周转时间为7 , 平均加权周转时间为1.74。

非剥夺式优先级调度算法的平均周转时间为12 ,平均加权周转时间为6.36。

 

15. 有一个具有两道作业的批处理系统，作业调度采用短作业优先调度算法，进程调度采用抢占式优先级调度算法。作业的运行情况见下表，其中作业的优先数即进程的优先数，优先数越小，优先级越高。

1） 列出所有作业进入内存的时间及结束的时间（以分为单位）。

2） 计算平均周转时间。

【解析】

1） 具有两道作业的批处理系统，内存只存放两道作业，它们采用抢占式优先级调度算法竞争 CPU，而将作业调入内存采用的是短作业优先调度。8：0 0 ，作业1到来，此时内存和处理机空闲，作业1进入内存并占用处理机；8：2 0 ，作业2到来，内存仍有一个位置空闲，因此将作业2调入内存，又由于作业2的优先数高，相应的进程抢占处理机，在此期间8：30作业3到来，但内存此时已无空闲，因此等待。直至8：5 0 ，作业2 执行完毕，此时作业3、4竞争空出的一道内存空间，作业4 的运行时间短，因此先调入，但它的优先数低于作业1 ,因此作业1先执行。到9：10时，作业1执行完毕，再将作业3调入内存，且由于作业3 的优先数高而占用CPU。所有作业进入内存的时间及结束的时间见下表。

2 ) 平均周转时间为(70 + 30 + 90 + 90)/4 = 70min。

 

16. 【2016统考真题】某进程调度程序采用基于优先数（priority） 的调度策略，即选择优先 数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数,引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1 , 且waitTime置0 ; 进程处于就绪态时，cpuTime置0， waitTime定时加1。请回答下列问题：

1）若调度程序只将nice的值作为进程的优先数，即priority = nice，则可能会出现饥饿现象。为什么？

2 ）使用nice，cpuTime和 waitTime设计一种动态优先数计算方法，以避免产生饥饿现象,并说明waitTime的作用。

【解析】

1) 由于采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进程一直没有机会运行，因而会出现饥饿现象。

2) 优先数priority 的计算公式为 priority = nice + K1 * cpuTime - K2 * waitTime，其中K1 > 0，K2 >0, 用于分别调整cpuTime和 waitTime在 priority中所占的比例。waitTime可使长时间等待的进程优先数减少，从而避免出现饥饿现象。

 

17. 设有4个作业J1、J2、J3、J4, 它们的到达时间和计算时间见下表。若这4个作业在一台处 理器上按单道方式运行，采用高响应比优先调度算法，试写出各作业的执行顺序、各作业的周转时间及平均周转时间。

【解析】

作业的响应比可表示为

在时刻8：00，系统中只有一个作业J1，因此系统将它投入运行。在J1完成 (即 10： 0 0 )时，J2、J3、J4的响应比分别为(90 + 40)/40，(60 + 25)/25，(30 + 30 )/30，即 3.25，3.4，2，因此应先将J3投入运行。在J3完成 (即10：2 5 ) 时，J2、J4的响应比分别为(115 + 40)/40,，(55 + 30)/30，即 3.875，2.83，因此应先将J2投入运行，待它运行完毕时(即11：05 ), 再将J4投入运行，J4的结束时间为11：35。

可见作业的执行次序为J1、J3、J2、J4农扁各作业的运行情况见下表，它们的周转时间分别为120min，155min，85min，125min，平均周转时间为121.25min。

 

18. 在一个有两道作业的批处理系统中，有一作业序列，其到达时间及估计运行时间见下表。系统作业采用最高响应比优先调度算法［响应比= （等待时间+ 估计运行时间）/估计运行时间］。进程的调度采用短进程优先的抢占式调度算法。

1 ）列出各作业的执行时间（即列出每个作业运行的时间片段，如作业i的运行时间序列10：00—10：40, 11：00—11：20, 11：30—11：50 结束）。

2） 计算这批作业的平均周转时间。

【解析】

上述5个作业的运行情况如下图所示。

在 10：00，因为只有J1到达，因此将它调入内存，并将CPU调度给它。

在 10：10，到达，因此将J2调入内存，但由于J1只需再执行25min，因此继续执行。

虽然J3、J4、J5分别在10：15，10：20和 10：30到达，但因当时内存中已存放了两道作业，因此不能马上将它们调入内存。

在 10：35，J1结束。此时J3、J4、J5的响应比［根据题意，响应比=（等待时间+估计运行时间）/ 估计运行时间］分别为65/45， 35/20,，35/30，因此将J4调入内存，并将CPU分配给内存中运行时间最短者，即J4。

在 10：55，J4结束。此时J3、J5的响应比分别为85/45，55/30，因此将J3调入内存，并将CPU分配给估计运行时间较短的J2。

在 11：25，J2结束，作业调度程序将J5调入内存，并将CPU分配给估计运行时间较短的J5。

在 11：55，J5结束，将 CPU分配给J3。

在 12：40，J3结束。

通过上述分析，可知：

1） 作业1 的执行时间片段为10：00—10：35 （结束）。

作业2 的执行时间片段为10：55—11：25 （结束）。

作业3 的执行时间片段为11：55—12：40 （结束）。

作业4 的执行时间片段为10：35—10：55 （结束）。

作业5 的执行时间片段为11：25—11：55 （结束）。

2） 它们的周转时间分别为35min，75min，145min，35min，85min，因此它们的平均周转时间为 75min。