典型的调度算法
标签: 操作系统
学习人数: 9892

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

1.先来先服务调度算法(FCFS)

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

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

 

2.短作业优先调度算法(SJF)

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

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

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

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

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

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

 

3.优先级调度算法

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

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

2.优先级的类型

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

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

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

 

4.高响应比优先调度算法(HRRN)

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

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

响应比的计算公式:

 

根据公式可知:

 

5.时间片轮转调度算法(RR)

时间片轮转调度算法主要适用于分时系统。该算法采取了非常公平的处理机分配方式,即让就绪队列上的每个进程每次仅运行一个时间片。

在轮转法中,系统根据FCFS策略,将所有的就绪进程排成一个就绪队列,并可设置每隔一定时间便产生一次中断,去激活进程调度程序进行调度,完成一次调度,把CPU分配给队首进程,并令其执行。

在 RR 调度算法中,应在何时进行进程的切换,可分为两种情况:

 ① 若一个时间片尚未用完,正在运行的进程便已经完成,就立即激活调度程序,将它从就绪队列中删除,再调度就绪队列中队首的进程运行,并启动一个新的时间片。

② 在一个时间片用完时,计时器中断处理程序被激活。如果进程尚未运行完毕,调度程序将把它送往就绪队列的末尾。

在时间片轮转调度算法中,时间片的大小对系统性能的影响很大。若时间片足够大,以至于所有进程都能在一个时间片内执行完毕,则时间片轮转调度算法就退化为先来先服务调度算法。若时间片很小,则处理机将在进程间过于频繁地切换,使处理机的开销增大,而真正用于运行用户进程的时间将减少。因此,时间片的大小应选择适当。时间片的长短通常由以下因素确定:系统的响应时间、就绪队列中的进程数目和系统的处理能力。

 

6.多队列调度算法

如前所述的各种调度算法,尤其在应用于进程调度时,由于系统中仅设置一个进程的就绪队列,即低级调度算法是固定的、单一的,无法满足系统中不同用户对进程调度策略的不同要求,在多处理机系统中,这种单一调度策略实现机制的缺点更显突出,由此,多级队列调度算法能够在一定程度上弥补这一缺点。

该算法将系统中的进程就绪队列从一个拆分为若干个,将不同类型或性质的进程固定分配在不同的就绪队列,不同的就绪队列采用不同的调度算法,一个就绪队列中的进程可以设置不同的优先级,不同的就绪队列本身也可以设置不同的优先级。

 

7.多级反馈队列调度算法

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展,通过动态调整进程优先级和时间片大小,多级反馈队列调度算法可以兼顾多方面的系统目标。

(1) 设置多个就绪队列:在系统中设置多个就绪队列,并为每个队列赋予不同的优先级。第一个队列的优先级最高,第二个次之,其余队列的优先级逐个降低。该算法为不同队列中的进程所赋予的执行时间片的大小也各不相同,在优先级越高的队列中,其时间片就越小。

(2) 每个队列都采用FCFS算法:当新进程进入内存后,首先将它放入第一队列的末尾,按 FCFS 原则等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可撤离系统。否则,即它在一个时间片结束时尚未完成,调度程序将其转入第二队列的末尾等待调度;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……,依此类推。当进程最后被降到第 n 队列后,在第 n 队列中便采取按 RR 方式运行。

(3) 按队列优先级调度:调度程序首先调度最高优先级队列中的诸进程运行,仅当第一队列空闲时才调度第二队列中的进程运行。

在多级反馈队列调度算法中,如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时,便能较好地满足各种类型用户的需要。

(1)终端型用户:短作业优先

(2)短批处理作业用户:周转时间短

(3)长批处理作业用户:不必担心长时间得不到处理。

 



课后作业

课后习题

 

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。


登录后发布评论

暂无评论,来抢沙发