—B调算法实用教案

《—B调算法实用教案》由会员分享，可在线阅读，更多相关《—B调算法实用教案（55页珍藏版）》请在金锄头文库上搜索。

1、1.1.先来先服务First-Come-First-Served First-Come-First-Served （FCFSFCFS）（作业进程）调度算法 FCFSFCFS是一种最简单的调度算法，可用于作业或进程调度。此算法的原则(yunz)(yunz)是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。FCFSFCFS算法属于非抢占方式，一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。FCFSFCFS算法易于实现，表面上很公平。CPU就绪就绪(jix)队列队列123后备后备(hubi)队列队列内存第1页/共54

2、页第一页，共55页。例题: 在单道环境下，某批处理有四道作业，已知他们的进入系统的时刻、估计运算时间(shjin)如下：作业(zuy)进入(jnr)时刻(h)运行时间(h)12348.008.509.009.502.000.500.100.20用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间 第2页/共54页第二页，共55页。8.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.301.004.0016.006.50平均平均(pngjn)周转时间周转时间T平均平均(pngjn)带权周转时间带权周转时间T作业作业进入时刻进入时刻

3、运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻周转时间周转时间12348.008.509.009.502.000.500.100.20带权周转 用FCFS算法:计算作业(zuy)的运行情况、平均周转时间和平均带权周转时间完成时间(shjin)=开始时间(shjin)+运行时间(shjin)周转时间=完成时间 进入时间带权周转时间=周转时间 / 运行时间6.875（h）1.725（h）第3页/共54页第三页，共55页。FCFS算法(sunf)调度例2作业名进入时间运行时间（分）需内存量KBA 8:06 4215B 8:18 3060C 8:302450D 8:36 2410E 8:42 1

4、220有用户空间100KB，并规定(gudng)作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法第4页/共54页第四页，共55页。有用户空间100KB，并规定作业相应程序装入内存连续(linx)区域，并不能被移动，作业与进程均采用FCFS算法作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20100K15K60K10K15K第5页/共54页第五页，共55页。 FCFS FCFS总结：总结： FCFSFCFS根根据据进进程程到到达达就就绪绪队队列列的

5、的时时间间来来分分配配中中央央处处理理机机，一一旦旦一一个个进进程程获获得得了了中中央央处处理理机机，就就一一直直运运行行到到结结束束，先先来来先先服服务务是是非非剥剥夺调度。夺调度。 这这种种调调度度从从形形式式上上讲讲是是公公平平的的，但但它它使使短短作作业业要要等等待待长长作作业业的的完完成成，重重要要的的作作业业要要等等待待不不重重要要作作业业的的完完成成。从从这这个个意意义义上上讲讲又又是是不公平的。不公平的。 先先进进先先出出调调度度使使响响应应时时间间的的变变化化(binhu)(binhu)较较小小，因因此此它它比比其其它它大大多多数数调调度度都都可可预预测测。由由于于这这种种调

6、调度度方方法法不不能能保保证证良良好好的的响响应应时时间间，在在处处理理交交互互式式用用户户时时很很少少用用这这种种方方法法。在在当当今今系系统统中中，先先进进先先出出很很少少作作为为调调度度模模式式，而而是是常常常常嵌嵌套套在在其其它它的的调调度度模模式式中中。例例如如，许许多多调调度度模模式式根根据据优优先先级级将将处处理理机机分分配配给给进进程程，但但具具有有相相同同优优先先级级的的进进程却按先进先出进行分配。程却按先进先出进行分配。第6页/共54页第六页，共55页。2.2.短作业进程优先(SJF/Shortest (SJF/Shortest Process Next)Process N

7、ext)调度算法 这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间(shjin)(shjin)（估计值）最短的作业进入主存运行。这一算法有利于短作业，对长作业不利。采用SJFSJF有利于系统减少平均周转时间(shjin)(shjin)和平均带权周转时间(shjin)(shjin)。第7页/共54页第七页，共55页。作业作业进入时刻进入时刻(h)运行时间运行时间(h)12348.008.509.009.502.000.500.100.20例题(lt)(lt)： 用 SJF 算法计算作业的运行情况、平均(pngjn)周转时间和平均(pngjn)带权周转时间第8页/共54页第八页，共

8、55页。该算法总是优先该算法总是优先(yuxin)(yuxin)调度要求运行时间最短的作业调度要求运行时间最短的作业作业作业 进入时刻进入时刻(shk) 运行时间运行时间 开始时刻开始时刻(shk) 完成时刻完成时刻(shk) 周转周转时间时间 带权周转带权周转 1 8.00 2.00 2 8.50 0.50 3 9.00 0.10 4 9.50 0.20平均平均(pngjn)周转时间周转时间 T平均平均(pngjn)带权周转时间带权周转时间T 最短作业优先法（SJFSJF）第9页/共54页第九页，共55页。该算法总是优先调度要求运行时间该算法总是优先调度要求运行时间(shjin)(shjin

9、)最最短的作业短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始开始(kish)时刻时刻 完成时刻完成时刻 周转时间周转时间 带带权周转权周转 1 8.00 2.00 8.00 2 8.50 0.50 3 9.00 0.10 4 9.50 0.20平均周转平均周转(zhuzhun)时间时间 T平均带权周转平均带权周转(zhuzhun)时间时间T 最短作业优先法（SJFSJF）第10页/共54页第十页，共55页。该算法总是优先调度要求运行时间该算法总是优先调度要求运行时间(shjin)(shjin)最短的作业最短的作业作业作业(zuy) 进入时刻进入时刻 运行时间运行时间 开始时刻开始时

10、刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 3 9.00 0.10 4 9.50 0.20平均周转平均周转(zhuzhun)时间时间 T平均带权周转平均带权周转(zhuzhun)时间时间T 最短作业优先法（SJFSJF）第11页/共54页第十一页，共55页。该算法总是优先调度该算法总是优先调度(diod)(diod)要求运行时间最短的要求运行时间最短的作业作业作业作业 进入时刻进入时刻 运行时间运行时间(shjin) 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间(shjin) 带权周转带权周转 1 8.

11、00 2.00 8.00 10.00 2 8.50 0.50 3 9.00 0.10 10.00 4 9.50 0.20平均平均(pngjn)周转时间周转时间 T平均平均(pngjn)带权周转时间带权周转时间T 最短作业优先法（SJFSJF）第12页/共54页第十二页，共55页。该算法总是优先调度要求运行该算法总是优先调度要求运行(ynxng)(ynxng)时间时间最短的作业最短的作业作业作业 进入进入(jnr)时刻时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 3 9.00

12、0.10 10.00 10.10 4 9.50 0.20平均周转平均周转(zhuzhun)时间时间 T平均带权周转平均带权周转(zhuzhun)时间时间T 最短作业优先法（SJFSJF）第13页/共54页第十三页，共55页。该算法总是优先该算法总是优先(yuxin)(yuxin)调度要求运行时间调度要求运行时间最短的作业最短的作业作业作业 进入时刻进入时刻 运行时间运行时间(shjin) 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间(shjin) 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 3 9.00 0.10 10.00 10.10 4

13、9.50 0.20 10.10平均周转平均周转(zhuzhun)时间时间 T平均带权周转平均带权周转(zhuzhun)时间时间T 最短作业优先法（SJFSJF）第14页/共54页第十四页，共55页。该算法总是该算法总是(zn sh)(zn sh)优先调度要求运行时间最优先调度要求运行时间最短的作业短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始开始(kish)时刻时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 3 9.00 0.10 10.00 10.10 4 9.50 0.20 10.10 10.30

14、平均平均(pngjn)周转时间周转时间 T平均平均(pngjn)带权周转时间带权周转时间T 最短作业优先法（SJFSJF）第15页/共54页第十五页，共55页。该算法总是优先调度要求该算法总是优先调度要求(yoqi)(yoqi)运行时间最短的运行时间最短的作业作业作业作业(zuy) 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 10.30 3 9.00 0.10 10.00 10.10 4 9.50 0.20 10.10 10.30平均周转平均周转(zhuzhun

15、)时间时间 T平均带权周转平均带权周转(zhuzhun)时间时间T 最短作业优先法（SJFSJF）第16页/共54页第十六页，共55页。该算法该算法(sun f)(sun f)总是优先调度要求运行时间最总是优先调度要求运行时间最短的作业短的作业作业作业 进入时刻进入时刻 运行时间运行时间(shjin) 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间(shjin) 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 10.30 10.80 3 9.00 0.10 10.00 10.10 4 9.50 0.20 10.10 10.30平均平均(pngjn)

16、周转时间周转时间 T平均平均(pngjn)带权周转时间带权周转时间T 最短作业优先法（SJFSJF）第17页/共54页第十七页，共55页。该算法总是优先调度要求运行时间该算法总是优先调度要求运行时间(shjin)(shjin)最短的作业最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成完成(wn chng)时刻时刻 周转时间周转时间 带带权周转权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 10.30 10.80 3 9.00 0.10 10.00 10.10 4 9.50 0.20 10.10 10.30平均平均(pngjn)周转时间

17、周转时间 T平均平均(pngjn)带权周转时间带权周转时间T 最短作业优先法（SJFSJF）第18页/共54页第十八页，共55页。该算法总是优先调度要求运行该算法总是优先调度要求运行(ynxng)(ynxng)时间最短的作业时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间(shjin) 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间(shjin) 带权周转带权周转 1 8.00 2.00 8.00 10.00 2.00 2 8.50 0.50 10.30 10.80 2.30 3 9.00 0.10 10.00 10.10 1.10 4 9.50 0.20 10.10 10.3

18、0 0.80平均周转平均周转(zhuzhun)时间时间 T平均带权周转平均带权周转(zhuzhun)时间时间T 最短作业优先法（SJFSJF）第19页/共54页第十九页，共55页。该算法总是优先调度该算法总是优先调度(diod)(diod)要求运行时间最短的作业要求运行时间最短的作业作业作业 进入时刻进入时刻 运行运行(ynxng)时间时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带带权周转权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.30 10.80 2.30 4.60 3 9.00 0.10 10.00 10.10 1

19、.10 11.00 4 9.50 0.20 10.10 10.30 0.80 4.00 平均周转平均周转(zhuzhun)时间时间 T平均带权周转平均带权周转(zhuzhun)时间时间T 最短作业优先法（SJFSJF）第20页/共54页第二十页，共55页。该算法总是优先该算法总是优先(yuxin)(yuxin)调度要求运行时间最短的作业调度要求运行时间最短的作业作业作业(zuy) 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.30 10.

20、80 2.30 4.60 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.10 10.30 0.80 4.00 平均周转平均周转(zhuzhun)时间时间 T1.55h平均带权周转平均带权周转(zhuzhun)时间时间T5.15h 最短作业优先法（SJFSJF）第21页/共54页第二十一页，共55页。该算法总是优先该算法总是优先(yuxin)(yuxin)调度要求运行时间最短的作业调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间(shjin) 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间(shjin) 带权周转带

21、权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.30 10.80 2.30 4.60 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.10 10.30 0.80 4.00 平均周转平均周转(zhuzhun)时间时间 T1.55h平均带权周转平均带权周转(zhuzhun)时间时间T5.15h 最短作业优先法（SJFSJF）运行顺序 1 342第22页/共54页第二十二页，共55页。作业作业 进入时刻进入时刻(shk) 运行时间运行时间 开始时刻开始时刻(shk) 完成时刻完成时刻(shk)

22、 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.30 10.80 2.30 4.60 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.10 10.30 0.80 4.00 作业作业进入时刻进入时刻运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间12348.008.509.009.502.000.500.100.208.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.301.004.0

23、016.006.50带权周转缺点(qudin)：1 有利于短作业，不利于长作业； 2 未考虑作业紧迫程度;第23页/共54页第二十三页，共55页。图 3-4 FCFS和SJF调度(diod)算法的性能 第24页/共54页第二十四页，共55页。SJF算法(sunf)例作业名进入时间运行时间（分）需内存量KBA 8:064215B 8:183060C 8:302450D 8:362410E 8:421220有用户空间100KB，并规定作业相应(xingyng)程序装入内存连续区域，并不能被移动，作业与进程均采用SJf算法第25页/共54页第二十五页，共55页。作业名 进入(jnr)时间 运行时间（

24、分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20100K15K60K10K15K第26页/共54页第二十六页，共55页。例：A请求系统服务时间5s，B请求系统服务时间为100s，设第0到第5秒前，CPU运行C进程。第1秒时B进入系统内存，第2秒时A进入内存当CPU空闲，需要调度进程时根据不同的算法(sunf)选择A或B问：分别计算FCFS算法(sunf)下和SJF算法(sunf)下，A和B的周转时间，带权周转时间和系统平均周转时间B BA A调度(diod)算法比较例题第27页/共54页第二十七

25、页，共55页。FCFS算法先来先服务B：周转时间为4100104s带权周转时间为104/1001.04A：周转时间为3+100+5108s带权周转时间为108/521.6平均带权周转时间为(21.6+1.04)211.32SJF算法短进程(jnchng)优先A：周转时间为3+58s带权周转时间为8/51.6B：周转时间为4+5+100109s带权周转时间为109/1001.09平均带权周转时间为(1.6+1.09)21.345调度算法(sunf)比较例先调度先调度(diod)B后调度后调度(diod)A先调度先调度A后调度后调度B调度顺序调度顺序调度顺序调度顺序调度顺序调度顺序调度顺序调度顺序

26、第28页/共54页第二十八页，共55页。短作业(zuy)（进程）优先算法SJ（P）F不一定能真正做到短作业优先调度未考虑作业的紧迫程度，因而不能保证紧迫性作业被及时处理不利于长作业，当不断(bdun)有短进程到达时，不保证长进程响应的及时性，甚至可能得不到调度第29页/共54页第二十九页，共55页。3.3.高响应比优先 Highest Response Highest Response Ratio Next (HRRN)(Ratio Next (HRRN)(作业) )调度算法 按照高响应比优先的原则，在每次选择作业投入运行时，先计算此时后备(hubi)(hubi)作业队列中每个作业的响应比RP

27、RP，然后选择其值最大的作业投入运行。 RP RP值定义为： RP RP（已等待时间要求运行时间）要求运行时间 1 1已等待时间要求运行时间 HRNHRN算法实际上是FCFSFCFS算法和SJFSJF算法的折衷。第30页/共54页第三十页，共55页。 响响应应比比R R不不仅仅是是要要求求运运行行时时间间(shjin)(shjin)的的函函数，而且还是等待时间数，而且还是等待时间(shjin)(shjin)的函数。的函数。 由由于于R R与与要要求求运运行行时时间间(shjin)(shjin)成成反反比比，故故对对短短作作业业是是有有利利的的，另另一一方方面面，因因R R与与等等待待时时间间(

28、shjin)(shjin)成成正正比比，故故长长作作业业随随着着其其等等待待时时间间(shjin)(shjin)的的增增长长，也也可可获获的的较较高高的的响响应应比比。这这就就克克服服了了短短作作业业优优先先的的缺缺点点，既既照照顾顾了了先先来来者者，又又优优待待了了短短作作业业，是是上上述述两两种种算算法法的的一一种种较较好好的的折中。折中。第31页/共54页第三十一页，共55页。(3)最高响应比作业(zuy)优先算法（HRN）作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转周转(zhuzhun)时间时间 带权周转带权周转(zhuzhun) 1 8.00

29、 2.00 2 8.50 0.50 3 9.00 0.10 4 9.50 0.20 平均周转平均周转(zhuzhun)时间时间= 带权周转带权周转(zhuzhun)时间时间= 8.0010.002.001.0010.1010.602.104.2010.0010.101.1011.0010.6010.801.306.501.625h5.675h第32页/共54页第三十二页，共55页。4.4.时间(shjin)(shjin)片轮转Round-Round-RobinRobin（RRRR）调度算法 进程调度程序总是选择就绪队列中第一个进程，允许其占有处理机一个时间片的时间。当执行(zhxng)的时间片

30、用完时，调度程序便停止该进程的执行(zhxng)，并将它送就绪队列的末尾，等待分配下一时间片再执行(zhxng)。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行(zhxng)一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片处理机执行(zhxng)时间。 在RR算法中，时间片的大小对系统性能有很大的影响。第33页/共54页第三十三页，共55页。 时时间间片片轮轮转转策策略略特特别别适适合合于于分分时时系系统统中中使使用用，当当多多个个进进程程驻驻留留在在主主存存中中时时，在在进进程程间间转转接接处处理理机机的开销一般是不大的。的开销一般是不大的。 在在

31、轮轮转转法法中中，时时间间片片长长度度的的选选取取非非常常重重要要，时时间间片片长长度度的的选选择择会会直直接接影影响响系系统统开开销销和和响响应应时时间间，如如果果时时间间片片长长度度过过短短，则则调调度度程程序序剥剥夺夺处处理理机机的的次次数数增增多多，这这将将使使进进程程上上下下文文交交换换次次数数也也大大大大增增加加，加加重重了了系系统统开开销销。如如果果时时间间片片长长度度选选择择过过长长（大大）。大大到到一一个个进进程程足足以以完完成成其其全全部部运运行行工工作作所所需需的的时时间间，那那么么时时间间片片轮轮转转法法就就退退化化为为先先来来先先服服务务策策略略了了。最最佳佳的的时时

32、间间片片量量值值应应能能使使分分时时用用户户(yngh)(yngh)得得到到好好的的响应时间。响应时间。第34页/共54页第三十四页，共55页。 时间片 SRT/Nmax RT响应时间 Nmax最大进程(jnchng)数 每当一轮调度开始时，系统便根据就绪队列中已有进程(jnchng)数目计算一次值。作为新一轮调度的时间片。这种方法得到的时间片是随就绪队列中的进程(jnchng)数变化的。第35页/共54页第三十五页，共55页。例：假定在一个处理机上执行以下五个作业： 作业号 A B C D E A B C D E 到达(dod)(dod)时间 0 1 2 3 4 0 1 2 3 4 运行时间

33、 4 3 5 2 4 4 3 5 2 4分别采用FCFSFCFS、SJFSJF、RRRR（时间片1 1）和HRN(HRN(响应比高者优先) )四种调度算法时，试做：（1 1）画出调度图；（2 2）计算每个作业的周转时间和带权周转时间 ；（3 3）计算平均周转时间和平均带权周转时间。调度图： T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1815 16 17 18 FCFS A A A A B B B C C C C C D D FCFS A A A A B B B C C C

34、 C C D D E E E EE E E E SJF A A A A D D B B B E E E E C SJF A A A A D D B B B E E E E C C C C CC C C C RR A B C D E A B C D E A B C E RR A B C D E A B C D E A B C E A C E CA C E C HRN A A A A B B B D D C C C C C HRN A A A A B B B D D C C C C C E E E EE E E E第36页/共54页第三十六页，共55页。例解：第37页/共54页第三十七页，共55页

35、。例解-1第38页/共54页第三十八页，共55页。例解-2高响应比优先(HRRN)(作业)调度算法计算： T=0：只有作业A已到达(dod)，调度作业A运行。 T=4：作业A完成，作业B、C、D、E已到达(dod)，计算作业B、C、D、E响应比RP分别为： 1+3/3、1+2/5、1+1/2、1+0/4，作业B响应比最大调度运行。 T=7：作业B完成，作业C、D、E已到达(dod)，计算作业C、D、E响应比RP分别为： 1+5/5、1+4/2、1+3/4，作业D响应比最大调度运行。 T=9：作业D完成，作业C、E已到达(dod)，计算作业C、E响应比RP分别为： 1+7/5、1+5/4，作业C

36、响应比最大调度运行。 T=14：作业C完成，只有作业E未完成，调度作业E运行。第39页/共54页第三十九页，共55页。 按照(nzho)进程的优先权大小来调度，使高优先权进程得到优先处理的调度策略称为优先权调度算法。 进程的优先权的设置可以是静态的，也可以是动态的。5.高优先(yuxin)权(Priority)优先(yuxin)调度算法第40页/共54页第四十页，共55页。静态(jngti)(jngti)优先权 在进程创建时确定，且在整个生命期中保持不变。确定进程优先权的依据有：进程类型，通常系统进程（例如对换进程）的优先权高于一般用户态进程的优先权； 进程对资源的需求，如进程执行(zhxng

37、)时间及内存需要的进程应赋予较高的优先权；根据用户要求，由用户的紧迫程度及用户所付费用的多少来确定进程的优先权。第41页/共54页第四十一页，共55页。动态(dngti)(dngti)优先权 是指在创建进程时所赋予(fy)的优先权，可以随进程的推进而改变，以便获得更好的调度性能。改变优先权的因数，随系统不同而不同，最常考虑的因素的进程的等待时间，已使用处理机的时间，或者资源使用情况等。第42页/共54页第四十二页，共55页。 在UNIX系统中处于核心态和用户态的优先权不同。进程处于核心态的优先权高，处于核心态的进程优先权又分二类，一类是因等待磁盘I/O、等待缓冲器等不可中断优先权最高，而另一类

38、因等待TTY输入输出等可中断优先权其次。处于用户态的优先权相对(xingdu)较低，用户态优先权又分为n+1级优先权。优先数为0级的优先权最高，优先数为n级的优先权最低。 用户态优先权是可变的，它随着占用CPU时间的增加而降低。核心每隔1秒钟便按下述公式对各进程重新计算其用户优先数（优先数与优先权成反比关系）。 优先数最近使用CPU的时间2基本用户优先数。第43页/共54页第四十三页，共55页。例题(lt)：假定要在处理机上执行如下(rxi)作业：作业执行时间优先级123410121313455225134作业(zuy)的执行顺序为：第44页/共54页第四十四页，共55页。6 6多级队列(du

39、li)(duli)调度算法 多队列调度是根据作业的性质和类型的不同，将就绪队列再分为若干个子队列，所有(suyu)的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法。 例如前后台系统可以建立两个就绪队列，批处理作业所建立进程进入后台就绪队列；交互型作业所建立的进程进入前台就绪队列。前台采用时间片轮转算法，进程按FCFS等策略排序，后台采用高优先权的调度算法或者短作业优先的调度算法。第45页/共54页第四十五页，共55页。 对多级就绪(jix)队列调度策略有两种，一种是各就绪(jix)队列按进程性质赋予不同的优先权，优先权高的就绪(jix)队列的进程优先被调度，例如上例

40、中前台就绪(jix)队列的优先权比后台就绪(jix)队列的优先权高，所以前台队列中的进程优先被调度。而只有当优先权高的就绪(jix)队列空时，方才调度优先权其次的就绪(jix)队列进程，在上例中只有前台队列空时，才调度后台就绪(jix)队列。这样，只有较高优先权的就绪(jix)队列都空时才调度最低优先权就绪(jix)队列的进程。 另一种调度就绪(jix)队列的方式是为每个队列分配一定的占用CPU时间的比例。如在上例中为前台队列分配80的CPU时间，给后台队列分配20的CPU时间。第46页/共54页第四十六页，共55页。1.优先级逐渐降低优先级逐渐降低2.优先级高的时间片短优先级高的时间片短3.

41、新进程进入内存后，首先新进程进入内存后，首先将它放入第一队列的末尾，将它放入第一队列的末尾，按按FCFS原则原则(yunz)排队排队等待调度。等待调度。6） 多级反馈队列多级反馈队列(duli)调度算法调度算法 4.在第在第n队列队列(duli)中便采取按时间片轮转的方式运行。中便采取按时间片轮转的方式运行。5.仅当第一队列仅当第一队列(duli)空闲时，调度程序才调度第二队列空闲时，调度程序才调度第二队列(duli)中的进程运行；如果处中的进程运行；如果处理机正在第理机正在第i队列队列(duli)中为某进程服务时，又有新进程进入优先权较高的队列中为某进程服务时，又有新进程进入优先权较高的队列

42、(duli)(第第1(i-1)中的任何一个队列中的任何一个队列(duli)，则此时新进程将抢占正在运行进程的处理机，即由，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第调度程序把正在运行的进程放回到第i队列队列(duli)的末尾，把处理机分配给新到的高优先的末尾，把处理机分配给新到的高优先权进程。权进程。 第47页/共54页第四十七页，共55页。 WindowsNT采用可抢占动态(dngti)优先级多级就绪队列调度算法。NT执行体支持32级优先级，并将它们分成两类，实时优先级（1631）和可变优先级（115），0级为系统保留。每个优先级一个就绪队列，高序号队列为高

43、优先级，调度程序从高优先级的队列开始往下找，如高优先级队列为空时才再往下找，直至找到一个进程。 第48页/共54页第四十八页，共55页。 各个就绪队列中进程执行(zhxng)时间片的大小也各不相同，在优先级越高的队列中，每个进程的执行(zhxng)时间片就规定得越小。 当一个进程执行(zhxng)完一个完整的时间片后被中断抢占处理器，而被抢占的进程优先级降低一级而进入下级就绪队列，如此继续，直至降到进程的基本优先级。而一个进程从阻塞态变为就绪态时要提高优先级，提高的幅度与等待的事件有关。如等待键盘输入所提高的幅度要大于等待磁盘I/O。第49页/共54页第四十九页，共55页。图：多级反馈(fnk

44、u)队列就绪队列1 时间片S1时间片完时间片完时间片完时间片完就绪队列2 时间片S2S1运行运行运行就绪队列n 时间片SnSn-1完成完成完成完成完成完成时间片完时间片完阻塞队列i阻塞阻塞阻塞阻塞阻塞阻塞事件发生事件发生第50页/共54页第五十页，共55页。感谢您的观赏(gunshng)第54页/共54页第五十四页，共55页。内容(nirng)总结1.先来先服务First-Come-First-Served （FCFS）（作业进程）调度算法。由于这种调度方法不能保证良好的响应时间，在处理交互式用户时很少用这种方法。FCFS算法先来先服务。SJF算法短进程优先。RT响应时间。Nmax最大进程数。在UNIX系统中处于核心态和用户态的优先权不同。如等待键盘输入所提高的幅度(fd)要大于等待磁盘I/O。感谢您的观赏第五十五页，共55页。