《计算机操作系统》课件OS-chapter 4.ppt

1、第四章第四章 处理机调度与死锁处理机调度与死锁 v掌握调度的层次及进程调度与作业调度的关系掌握调度的层次及进程调度与作业调度的关系v掌握各种作业调度算法及每种算法的作业周转时掌握各种作业调度算法及每种算法的作业周转时间和带权平均周转时间间和带权平均周转时间v死锁的原因，产生死锁的四个必要条件以及死锁死锁的原因，产生死锁的四个必要条件以及死锁的解决。的解决。本章重点：本章重点：各种作业调度算法及每种算法的作业周转时间和各种作业调度算法及每种算法的作业周转时间和带权平均周转时间带权平均周转时间死锁的解决死锁的解决本章难点本章难点：v分级调度分级调度v作业调度作业调度v进程调度进程调度v死锁死锁v小

2、结小结41分级调度作业的状态及转换作业的状态及转换处理机调度：如何处理机调度：如何从众多的作业队列中选择一道或几道从众多的作业队列中选择一道或几道进入内存进入内存，进入内存的若干进程又如何去，进入内存的若干进程又如何去竞争竞争CPU的使的使用权用权，这称为处理机调度。，这称为处理机调度。处理机调度分处理机调度分4级：作业调度、交换调度、进程调度、级：作业调度、交换调度、进程调度、线程调度。线程调度。作业调度：负责从后备队列中选择作业投入运行。作业调度：负责从后备队列中选择作业投入运行。将作业从运行状态变成完成状态。将作业从运行状态变成完成状态。进程调度：则将进程从就绪状态变为运行状态。进程调度

3、：则将进程从就绪状态变为运行状态。交换调度：负责将外存交换区中的进程调入内存。交换调度：负责将外存交换区中的进程调入内存。将内存进程调入外存交换区。将内存进程调入外存交换区。v四者关系作业调度作业调度提交提交收容收容外存外存内存内存就绪就绪就绪就绪执行执行交换调度交换调度等待等待等待等待进程调度进程调度完成完成线程调度线程调度作业调度：作业调度：又称高级调度，又称高级调度，宏观调度。宏观调度。其主要任务是对大量的后备作业以一定的原则进行挑选，其主要任务是对大量的后备作业以一定的原则进行挑选，给选中的作业分配内存、给选中的作业分配内存、I/O设备等必要的资源，建立相设备等必要的资源，建立相应的进

4、程，这时该作业所对应的进程具有使用应的进程，这时该作业所对应的进程具有使用CPU的权力。作业完成时负责收回资源的权力。作业完成时负责收回资源 进程调度：进程调度：又称低级调度，又称低级调度，微观调度。微观调度。其任务是按照某种原则将其任务是按照某种原则将CPU分配给某一就绪进程，即分配给某一就绪进程，即确定哪个进程在什么时候获得处理机，使用多长时间。确定哪个进程在什么时候获得处理机，使用多长时间。二者联系：作业调度创建进程调度所需要进程。二者联系：作业调度创建进程调度所需要进程。二者区别：二者区别：处理对象不同；处理对象不同；完成任务不同。完成任务不同。交换调度：交换调度：又称中级调度，又称中

5、级调度，其主要任务是按照给定的原则和策略，将处于外存交换其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪进程或等待进程调入内存，或者把内存中的区中的就绪进程或等待进程调入内存，或者把内存中的就绪进程或等待进程交换到外存中。就绪进程或等待进程交换到外存中。42作业作业调度一、作业调度功能一、作业调度功能1.数据结构：数据结构：JCB用于记录作业相关信息用于记录作业相关信息 2.从后备队列中挑选一部分作业投入运行从后备队列中挑选一部分作业投入运行 3.为被选中的作业做好执行前的准备工作：建立进程为被选中的作业做好执行前的准备工作：建立进程分配资源分配资源4.作业完成后做善后处理工作：收回

6、资源，输出执行作业完成后做善后处理工作：收回资源，输出执行时间等作业管理信息时间等作业管理信息二、作业调度目标及性能衡量标准二、作业调度目标及性能衡量标准 1.调度目标：调度目标：对所有的作业应该是公平合理的对所有的作业应该是公平合理的设备利用率高设备利用率高单位时间内执行尽可能多的作业单位时间内执行尽可能多的作业每个作业有尽可能快的响应时间每个作业有尽可能快的响应时间 2.调度衡量标准：调度衡量标准：周转时间周转时间 Ti=Tfi-Tsi Ti=Twi+Tri 平均周转时间T=带权周转时间wi=带权平均周转时间w=niTin11TriTiTriTriTwiTriTwiniWin11=1+三、

7、作业调度算法三、作业调度算法1.先到先服务先到先服务FCFS：优先选择最先到达的作业：优先选择最先到达的作业作业提交时间运行时间开始时刻完成时间周转时间带权周转时间18:002528:201038:202048:302058:3515T=175/5=35W=10.2/52.04 2.短作业优先短作业优先SJF：优先选择最少运行时间的作业：优先选择最少运行时间的作业作业提交时间运行时间开始时刻完成时间周转时间带权周转时间18:002528:201038:202048:302058:3515T=33W=1.8 3.响应比高者优先考虑响应比高者优先考虑：作业提交时间运行时间开始时刻完成时间周转时间带

8、权周转时间18:002528:201038:202048:302058:3515T=34W=1.91 响应比响应比=等待时间等待时间/运行时间运行时间 43进程调度进程调度一、进程调度功能一、进程调度功能1.记录系统中所有进程的执行情况 2.从就绪进程中选择占有处理机的进程 3.进行进程上下文（进程状态、有关变量、数据结构的值、硬件寄存器值、PCB等）切换二、进程调度的时机二、进程调度的时机1.正在执行的进程运行完毕正在执行的进程运行完毕2.执行中的进程变成阻塞状态执行中的进程变成阻塞状态3.分时系统中时间片用完分时系统中时间片用完4.可剥夺调度方式中有优先级高的进程进入就绪队列可剥夺调度方式

9、中有优先级高的进程进入就绪队列三、进程调度性能衡量标准三、进程调度性能衡量标准 1.定性标准：定性标准：（1）可靠性：一次进程调度是否能引起数据结构的破坏）可靠性：一次进程调度是否能引起数据结构的破坏（2）简洁性：调度程序的国度繁琐将引起较大的系统开销）简洁性：调度程序的国度繁琐将引起较大的系统开销2.定量标准定量标准（1）CPU的利用率的利用率（2）进程在就绪队列中的等待时间与执行时间之比）进程在就绪队列中的等待时间与执行时间之比 四、进程调度调度方式四、进程调度调度方式 1.可剥夺可剥夺：2.不可剥夺：不可剥夺：五、进程调度算法1.先到先服务先到先服务FCFS：优先调度最先进入就绪队列的进

10、程：优先调度最先进入就绪队列的进程2.轮转法轮转法（Round Robin）：将）：将CPU的处理时间分成固定的处理时间分成固定大小的时间片，一个进程在被调度程序选中后用完了系统大小的时间片，一个进程在被调度程序选中后用完了系统规定的时间片但未完成要求的任务，自动到就绪队列队尾规定的时间片但未完成要求的任务，自动到就绪队列队尾3.多级反馈队列法（多级反馈队列法（Round Robin with Multiple Feedback）：）：优先级 高 低 RL1 RL2 RLn 时间片 短 长 4.优先数法优先数法：优先调度优先级最高的进程：优先调度优先级最高的进程动态优先数：优先数随着进程的执行

11、而发生变化动态优先数：优先数随着进程的执行而发生变化 5.SCBF(Short CPU Burst First)静态优先数：进程的执行期间优先数不变静态优先数：进程的执行期间优先数不变 六、进程调度与作业调度的比较对象分配资源使用频率调度算法作业后备作业内存、设备低FCFS，SJC优先数响应比高者优先进程就绪进程CPU高FCFS，轮转法，优先数，多级反馈队列法4.4进程死锁进程死锁例：P1 打印机 绘图仪 P2 绘图仪 打印机Pi思考思考P（S(i+1)mod 5）拿左叉拿左叉P（S(i)）拿右叉；拿右叉；吃饭；吃饭；放左叉；放左叉；V（S(i+1)mod 5）放右叉放右叉V（S(i)）;例：

12、哲学家就餐问题例：哲学家就餐问题01234思考思考吃饭吃饭01234例：例：P2、P1都需都需3台打印机台打印机，系统中有，系统中有4台打印机，台打印机，其中其中P1和和P2各分得各分得2台。台。P2 P1 一、死锁的定义：一、死锁的定义：死锁：死锁：指各并发过程彼此互相等待对方所使用的资源，指各并发过程彼此互相等待对方所使用的资源，且这些并发进程在得到对方的资源之前不会释放自己所且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源，从而造成了一种僵局。如果无外力作用，拥有的资源，从而造成了一种僵局。如果无外力作用，这些进程永远不能再向前推进。这些进程永远不能再向前推进。二、死二、死锁锁

13、产生的原因产生的原因竞争资源竞争资源 进程推进顺序不当进程推进顺序不当 DP2(Rel(R1)P2(Rel(R2)P2(Req(R1)P2(Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)三、产生死锁的四个必要条件三、产生死锁的四个必要条件1.互斥条件互斥条件2.部分分配部分分配 3.不剥夺条件（不可抢占）不剥夺条件（不可抢占）4.环路条件环路条件四、死锁的解决四、死锁的解决1.死锁的预防：死锁的预防：打破死锁存在条件中的一个或几个打破死锁存在条件中的一个或几个有三种方法：有三种方法：1）打破互斥和不剥夺条件打破互斥和不剥夺条件：一个已保持了某些资源的进：

14、一个已保持了某些资源的进程。若新的资源要求不能立即得到满足，它必须释放程。若新的资源要求不能立即得到满足，它必须释放已保持的所有资源，以后需要时再重新申请，这意味已保持的所有资源，以后需要时再重新申请，这意味着一个进程已占有的资源，在运行过程中可能暂时地着一个进程已占有的资源，在运行过程中可能暂时地释放或说被剥夺。释放或说被剥夺。2）打破部分分配条件：打破部分分配条件：系统要求所有进程一次性申请所系统要求所有进程一次性申请所需的全部资源。若系统有足够的资源分配给一个进程需的全部资源。若系统有足够的资源分配给一个进程时，便一次把所需资源分配给该进程。这样，进程在时，便一次把所需资源分配给该进程。

15、这样，进程在整个运行期间为会提出任何要求，但系统浪费严重，整个运行期间为会提出任何要求，但系统浪费严重，降低了并发性。降低了并发性。3）打破环路条件：打破环路条件：将所有资源编号，申请时按顺序申请，将所有资源编号，申请时按顺序申请，先申请小号，再申请大号，这样，能保证申请到最大先申请小号，再申请大号，这样，能保证申请到最大号者，肯定运行完成。号者，肯定运行完成。2、死锁的避免、死锁的避免1）安全与不安全状态：允许进程动态申请资源，系统进）安全与不安全状态：允许进程动态申请资源，系统进行资源分配前先计算资源分配的安全性，若此次分配行资源分配前先计算资源分配的安全性，若此次分配不会导致不会导致 进

16、入不安全状态，则将资源分配给进程，否进入不安全状态，则将资源分配给进程，否则进程等待。则进程等待。安全状态：安全状态：指将系统按照某种顺序如指将系统按照某种顺序如来为每一个进程分配其所需资源，直到最大需求使每来为每一个进程分配其所需资源，直到最大需求使每个进程可顺序完成，若系统不存在这样一个安全系列，个进程可顺序完成，若系统不存在这样一个安全系列，则系统处于不安全状态。只要系统处于安全状态，便则系统处于不安全状态。只要系统处于安全状态，便可避免进死锁状态。可避免进死锁状态。例：三个进程例：三个进程P1,P2,和和P3所需要磁带机所需要磁带机10，4，9系统中系统中其其12台。台。T0时刻时刻

17、最大需求最大需求P110P24P39T0时刻存在一个安全序列时刻存在一个安全序列 所以系统安全。所以系统安全。如果如果 P3 请求请求 1 台台,状态发生变化状态发生变化.已分配已分配 522可用可用3还需还需527找不到一个安全序列找不到一个安全序列.状态不安全状态不安全.请求不能满足。请求不能满足。如果如果 P1 请求请求 1 台台,状态发生变化状态发生变化.结果如何？结果如何？如果如果 P2 请求请求 1 台台,状态发生变化状态发生变化.结果又如何？结果又如何？2）数据结构）数据结构（1）可用资源向量可用资源向量 availablem:availablei 代表资代表资源源i的可用资源数

18、。初值为系统中所配置的该类资源的的可用资源数。初值为系统中所配置的该类资源的全部可用资源数。全部可用资源数。availablej=k;Rj类资源有类资源有k个。个。(2)Maxm,n:maxi,j=k 表示进程表示进程i最多需要最多需要k个个Rj资源。资源。(3)Allocationm,n:allocationi,j=k 表示进程表示进程i已分得已分得k个个Rj资源。资源。(4)Needm,n:needi,j=k 表示进程表示进程i还需要还需要k个个Rj资源。资源。存在关系：存在关系：Need=Max-Allocation 3)银行家算法银行家算法requesti 进程进程Pi的请求向量。的请

19、求向量。requesti j=k 进程进程Pi申申请请k个个Rj，Pi发出请求后，系统按如下方法做发出请求后，系统按如下方法做.(1)if requesti=Needi,then go to(b)else error(2)if requesti=Available,then go to(c)else Pi waits(3)系统试分配系统试分配,修改数据结构。修改数据结构。Available=Available-requestiNeedi=Needi-requestiallocationi=allocationi+requesti(4)系统执行安全性算法，若安全，正式分配，系统执行安全性算法，若

20、安全，正式分配，否则，试探作废，否则，试探作废，Pi等待等待,恢复原来的数据结构。恢复原来的数据结构。4)安全性算法安全性算法(1)设置两个向量：工作向量设置两个向量：工作向量work,表示系统能够提供表示系统能够提供给进程的资源数；给进程的资源数；Finish，表示系统是否有足够的资源，表示系统是否有足够的资源满足每个进程，初始时满足每个进程，初始时Work=Available，Finish=false(2)从进程集合中找满足下列条件的进程：从进程集合中找满足下列条件的进程：Finishi=false 且且 Needi=work,(3)如果找到：如果找到：Work=work+allocati

21、oniFinishi=trueGoto b)(4)如果对所有进程都有如果对所有进程都有 finishi=true 则系统安全，则系统安全，否则系统不安全。否则系统不安全。5)银行家算法的例银行家算法的例进程进程 p0,p1,p2,p3,p4 资源资源A,B,C 最大可用资源最大可用资源 10,5,7At the moment T0:Maxallocationneedavailable ABCABCABCABCP0 7 5 30 1 07 4 33 3 2P1 3 2 22 0 01 2 2P2 9 0 23 0 26 0 0P3 2 2 22 1 10 1 1P4 4 3 30 0 24 3

22、1RT0时刻的安全性时刻的安全性:work needallocation work+allocation finishABC ABC ABCABCP1 3 3 2 1 2 22 0 05 3 2 trueP3 5 3 2 0 1 12 1 17 4 3 trueP4 7 4 3 4 3 10 0 27 4 5 trueP0 7 4 5 7 4 30 1 07 5 5 trueP2 7 5 5 6 0 03 0 210 5 7 true找到了安全序列找到了安全序列，所以该时刻系统安全，所以该时刻系统安全P1 请求：请求：request1(1,0,2)Maxallocationneedavaila

23、bleABCABCABCABCP07 5 30 1 07 4 32 3 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1（1）request1=need1（4）运行安全性算法.（2）request1=available（3）试分配，修改数据结构1 2 23 3 2RT1时刻的安全性时刻的安全性:work need allocation work+allocationfinishABCABCABCABCP12 3 00 2 03 0 25 3 2 trueP35 3 20 1 12 1 17 4 3 tru

24、eP47 4 34 3 10 0 27 4 5 trueP07 4 57 4 30 1 07 5 5 trueP27 5 56 0 03 0 210 5 7 true找到了安全序列找到了安全序列，所以该时刻系统安全，所以该时刻系统安全P4 请求请求 request4(3,3,0)（1）request4=need4（2）request4=available is not satisfied.4 3 12 3 0P4 wait P0 请求请求 request0(0,2,0)MaxallocationneedavailableABCABCABCABCP07 5 30 3 07 2 32 1 0P13

25、 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1（1）request0=need0（2）request0=available.（3）试分配，修改数据结构.7 4 32 3 0（4）运行安全性算法.找不到安全序列，所以不安全，恢复数据结构，P0等待五、死锁的检测和恢复五、死锁的检测和恢复当系统为进程分配资源时，若未采取任何限制性措施保当系统为进程分配资源时，若未采取任何限制性措施保证不进入死锁状态，则系统必须提供解除死锁的手段。证不进入死锁状态，则系统必须提供解除死锁的手段。1.资源分配图资源分配图R1 R2 P1

26、P2R1 R2 P1P2R1 R2 P1P2R1 R2 P1P22死锁定理死锁定理当且仅当当且仅当S的资源分配图是不可完全简化的，的资源分配图是不可完全简化的，S为死锁状为死锁状态。态。死的解除：死的解除：1.终止死锁进程；终止死锁进程；2.按一定顺序中止进程直至释放到有足够的资源来完成按一定顺序中止进程直至释放到有足够的资源来完成剩下的进程为止；剩下的进程为止；3.从被锁住进程中强迫剥夺资源以解除死锁。从被锁住进程中强迫剥夺资源以解除死锁。45 小结小结v处理机调度定义、层次、四者所在位置处理机调度定义、层次、四者所在位置v作业调度与进程调度的任务、功能、关系作业调度与进程调度的任务、功能、

27、关系 v作业调度功能、衡量标准作业调度功能、衡量标准v作业调度算法作业调度算法 v进程调度功能、时机、衡量标准、方式进程调度功能、时机、衡量标准、方式v进程调度算法进程调度算法v两类调度算法的比较两类调度算法的比较v死锁定义死锁定义 v死锁产生原因；死锁产生原因；v产生死锁的四个必要条件；产生死锁的四个必要条件；v死锁的解决：死锁的解决：预防、预防、避免避免、检测和恢复、检测和恢复1.银行家算法中出现下述资源分配：银行家算法中出现下述资源分配：作业作业allocationneedavailableABCDABCDABCDP0003200121622P110001750P213542356P30

28、3320652P400140656（1）该状态是否安全？）该状态是否安全？（2）如果）如果P2提出请求提出请求Request2（1，2，2，2）后，）后，系统能否将资源分配给它系统能否将资源分配给它？2.有相同类型的有相同类型的5个资源被个资源被4个进程所共享，且每个进个进程所共享，且每个进程最多需要程最多需要2个这样的资源才可以运行完毕，试问个这样的资源才可以运行完毕，试问系统是否会由于这种资源的竞争而产生死锁。系统是否会由于这种资源的竞争而产生死锁。3.已知某系统中的所有资源都是相同的，系统中的进已知某系统中的所有资源都是相同的，系统中的进程严格按照一次一个的方式申请或者释放资源。程严格按

29、照一次一个的方式申请或者释放资源。在此系统中，没有进程所需要的资源数超过系统在此系统中，没有进程所需要的资源数超过系统的资源总拥有量，试对下面列出的各种情况说明的资源总拥有量，试对下面列出的各种情况说明是否会发生死锁，为什么是否会发生死锁，为什么？情况序号情况序号系统中进程数系统中进程数 资源总量资源总量A12B21C22D234.系统中有系统中有3种资源种资源A、B、C，5个进程个进程P1、P2、P3、P4、P5，系统中有，系统中有A、B、C的数量分别是的数量分别是17、5、20，T0时刻系统状态如下：时刻系统状态如下：MaxAlocationABCABCP15 5 92 1 2P25 3

30、64 0 2P34 0 114 0 5P44 2 52 0 4P54 2 43 1 4（1）该状态是否安全？为什么？）该状态是否安全？为什么？（2）如果）如果P2提出请求提出请求Request2（0，3，4）后，）后，系统能否将资源分配给它系统能否将资源分配给它？为什么？为什么？（3）在（）在（2）的基础上，如果）的基础上，如果P4提出请求提出请求Request4（2，0，1）后，系统能否实施分配）后，系统能否实施分配？为什么？为什么？（4）在（）在（3）的基础上，如果）的基础上，如果P1提出请求提出请求Request1（0，2，0）后，系统能否实施分配）后，系统能否实施分配？为什么？为什么？JOBtCtRtStFTiWi18:00 228:00 6038:01 448:02 3求求FCFS,SJF和和HRN三种算法的三种算法的T和和W。二、批处理作业 submit作业完成 队列输入设备后 备 作业 队 列输出设备键盘作业调度程序作业终止程序输出程序OS中输入程序 作业注册程序后备状态后备状态运行状态运行状态完成状态完成状态