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

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

分级调度作业调度进程调度死锁小结4．1分级调度作业的状态及转换处理机调度：如何从众多的作业队列中选择一道或几道进入内存，进入内存的若干进程又如何去竞争CPU的使用权，这称为处理机调度。处理机调度分4级：作业调度、交换调度、进程调度、线程调度。作业调度：负责从后备队列中选择作业投入运行。将作业从运行状态变成完成状态。进程调度：则将进程从就绪状态变为运行状态。交换调度：负责将外存交换区中的进程调入内存。将内存进程调入外存交换区。四者关系作业调度提交收容外存内存就绪就绪执行交换调度等待等待进程调度完成线程调度作业调度：又称高级调度，

宏观调度。其主要任务是对大量的后备作业以一定的原则进行挑选，给选中的作业分配内存、I/O设备等必要的资源，建立相应的进程，这时该作业所对应的进程具有使用CPU的权力。作业完成时负责收回资源进程调度：又称低级调度，微观调度。其任务是按照某种原则将CPU分配给某一就绪进程，即确定哪个进程在什么时候获得处理机，使用多长时间。二者联系：作业调度创建进程调度所需要进程。二者区别：①处理对象不同；②完成任务不同。交换调度：又称中级调度，

其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪进程或等待进程调入内存，或者把内存中的就绪进程或等待进程交换到外存中。4．2作业调度一、作业调度功能1.数据结构：JCB用于记录作业相关信息2.从后备队列中挑选一部分作业投入运行3.为被选中的作业做好执行前的准备工作：建立进程分配资源4.作业完成后做善后处理工作：收回资源，输出执行时间等作业管理信息二、作业调度目标及性能衡量标准1.调度目标：对所有的作业应该是公平合理的设备利用率高单位时间内执行尽可能多的作业每个作业有尽可能快的响应时间2.调度衡量标准：周转时间Ti=Tfi-TsiTi=Twi+Tri

平均周转时间T=

带权周转时间wi=带权平均周转时间w===1+三、作业调度算法1.先到先服务FCFS：优先选择最先到达的作业作业提交时间运行时间开始时刻完成时间周转时间带权周转时间18:002528:201038:202048:302058:3515T=175/5=35W=10.2/5≈2.04

2.短作业优先SJF：优先选择最少运行时间的作业作业提交时间运行时间开始时刻完成时间周转时间带权周转时间18:002528:201038:202048:302058:3515T=33W=1.8

3.响应比高者优先考虑：作业提交时间运行时间开始时刻完成时间周转时间带权周转时间18:002528:201038:202048:302058:3515T=34W=1.91

响应比=等待时间/运行时间4．3进程调度一、进程调度功能1.记录系统中所有进程的执行情况

2.从就绪进程中选择占有处理机的进程

3.进行进程上下文（进程状态、有关变量、数据结构的值、硬件寄存器值、PCB等）切换二、进程调度的时机1.正在执行的进程运行完毕2.执行中的进程变成阻塞状态3.分时系统中时间片用完4.可剥夺调度方式中有优先级高的进程进入就绪队列三、进程调度性能衡量标准1.定性标准：（1）可靠性：一次进程调度是否能引起数据结构的破坏（2）简洁性：调度程序的国度繁琐将引起较大的系统开销2.定量标准（1）CPU的利用率（2）进程在就绪队列中的等待时间与执行时间之比四、进程调度调度方式1.可剥夺：2.不可剥夺：五、进程调度算法1.先到先服务FCFS：优先调度最先进入就绪队列的进程2.轮转法（RoundRobin）：将CPU的处理时间分成固定大小的时间片，一个进程在被调度程序选中后用完了系统规定的时间片但未完成要求的任务，自动到就绪队列队尾3.多级反馈队列法（RoundRobinwithMultipleFeedback）：优先级

高

低

RL1

RL2

RLn

时间片

短

长

4.优先数法：优先调度优先级最高的进程动态优先数：优先数随着进程的执行而发生变化5.SCBF(ShortCPUBurstFirst)静态优先数：进程的执行期间优先数不变六、进程调度与作业调度的比较对象分配资源使用频率调度算法作业后备作业内存、设备低FCFS，SJC优先数响应比高者优先进程就绪进程CPU高FCFS，轮转法，优先数，多级反馈队列法4.4进程死锁例：P1打印机绘图仪

P2绘图仪打印机Pi思考P（S(i+1)mod5）拿左叉P（S(i)）拿右叉；吃饭；放左叉；V（S(i+1)mod5）放右叉V（S(i)）;例：哲学家就餐问题01234思考吃饭01234例：P2、P1都需3台打印机，系统中有4台打印机，其中P1和P2各分得2台。P2P1

一、死锁的定义：死锁：指各并发过程彼此互相等待对方所使用的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源，从而造成了一种僵局。如果无外力作用，这些进程永远不能再向前推进。二、死锁产生的原因竞争资源

进程推进顺序不当

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）打破互斥和不剥夺条件：一个已保持了某些资源的进程。若新的资源要求不能立即得到满足，它必须释放已保持的所有资源，以后需要时再重新申请，这意味着一个进程已占有的资源，在运行过程中可能暂时地释放或说被剥夺。2）打破部分分配条件：系统要求所有进程一次性申请所需的全部资源。若系统有足够的资源分配给一个进程时，便一次把所需资源分配给该进程。这样，进程在整个运行期间为会提出任何要求，但系统浪费严重，降低了并发性。3）打破环路条件：将所有资源编号，申请时按顺序申请，先申请小号，再申请大号，这样，能保证申请到最大号者，肯定运行完成。2、死锁的避免1）安全与不安全状态：允许进程动态申请资源，系统进行资源分配前先计算资源分配的安全性，若此次分配不会导致进入不安全状态，则将资源分配给进程，否则进程等待。安全状态：指将系统按照某种顺序如<p1,p2,p3,…pn>来为每一个进程分配其所需资源，直到最大需求使每个进程可顺序完成，若系统不存在这样一个安全系列，则系统处于不安全状态。只要系统处于安全状态，便可避免进死锁状态。例：三个进程P1,P2,和P3所需要磁带机10，4，9系统中其12台。T0时刻 最大需求 P1 10 P2 4 P3 9 T0时刻存在一个安全序列<P2,P1,P3>所以系统安全。如果P3请求1台,状态发生变化.已分配5 22可用3

还需5 27找不到一个安全序列.状态不安全.请求不能满足。如果P1请求1台,状态发生变化.结果如何？如果P2请求1台,状态发生变化.结果又如何？2）数据结构（1）可用资源向量available[m]:available[i]

代表资源i的可用资源数。初值为系统中所配置的该类资源的全部可用资源数。available[j]=k;Rj类资源有k个。(2)Max[m,n]:max[i,j]=k表示进程i最多需要k个Rj资源。(3)Allocation[m,n]:allocation[i,j]=k表示进程i已分得k个Rj资源。(4)Need[m,n]:need[i,j]=k表示进程i还需要k个Rj资源。存在关系：Need=Max-Allocation3)银行家算法requesti进程Pi的请求向量。requesti[j]=k进程Pi申请k个Rj，Pi发出请求后，系统按如下方法做.(1)ifrequesti<=Needi,thengoto(b)elseerror(2)ifrequesti<=Available,thengoto(c)elsePiwaits(3)系统试分配,修改数据结构。Available=Available-requestiNeedi=Needi-requestiallocationi=allocationi+requesti(4)系统执行安全性算法，若安全，正式分配，否则，试探作废，Pi等待,恢复原来的数据结构。4)安全性算法

设置两个向量：工作向量work,表示系统能够提供给进程的资源数；Finish，表示系统是否有足够的资源满足每个进程，初始时Work=Available，Finish=false(2)从进程集合中找满足下列条件的进程：

Finish[i]=false且Needi<=work,(3)如果找到：Work=work+allocationiFinish[i]=trueGotob)(4)如果对所有进程都有finish[i]=true则系统安全，否则系统不安全。5)银行家算法的例进程{p0,p1,p2,p3,p4}资源{A,B,C}最大可用资源{10,5,7}AtthemomentT0: Max allocation need available ABC ABC ABC ABCP0 753 010 743 332P1322 200 122P2 902 302 600P3 222 211 011 P4 433 002 431RT0时刻的安全性:workneed allocation work+allocation finishABC ABC ABC ABCP1 332 122 200 532trueP3 532 011 211 743trueP4 743 431 002 745 trueP0745 743 010 755 trueP2 755 600 302 1057true找到了安全序列<p1,p3,p4,p0,p2>，所以该时刻系统安全P1请求：request1(1,0,2) Max allocation need available ABC ABC ABC ABCP0 753 010 743 230P1 322 302

020P2 902 302 600P3 222 211 011 P4 433 002 431（1）request1<=need1（4）运行安全性算法.（2）request1<=available（3）试分配，修改数据结构122332RT1时刻的安全性:work need allocation work+allocation finishABC ABC ABC ABCP1 230 020 302 532 trueP3 532 011 211 743 trueP4 743 431 002 745 trueP0 745 743 010 755 trueP2 755 600 302 1057true找到了安全序列<p1,p3,p4,p0,p2>，所以该时刻系统安全P4请求request4(3,3,0)（1）request4<=need4（2）request4<=availableisnotsatisfied.431230P4wait

P0请求request0(0,2,0) Max allocation need available ABC ABC ABC ABCP0 753 030

723

210P1 322 302 020P2 902 302 600P3 222 211 011 P4 433 002 431（1）request0<=need0（2）request0<=available.（3）试分配，修改数据结构.743230（4）运行安全性算法.找不到安全序列，所以不安全，恢复数据结构，P0等待五、死锁的检测和恢复当系统为进程分配资源时，若未采取任何限制性措施保证不进入死锁状态，则系统必须提供解除死锁的手段。1.资源分配图R1R2P1P2R1R2P1P2R1R2

P1P2R1R2P1P22死锁定理当且仅当S的资源分配图是不可完全简化的，S为死锁状态。死的解除：1.终止死锁进程；2.按一定顺序中止进程直至释放到有足够的资源来完成剩下的进程为止；3.从被锁住进程中强迫剥夺资源以解除死锁。4．5小结处理机调度定义、层次、四者所在位置作业调度与进程调度的任务、功能、关系作业调度功能、衡量标准作业调度算法进程调度功能、时机、衡量标准、方式进程调度算法两类调度算法的比较死锁定义死锁产生原因；产生死锁的四个必要条件；死锁的解决：预防、避免、检测和恢复1.银行家算法中出现下述资源分配：作业 allocation need available ABCD ABCD ABCDP0 0032 0012 1622P1 1000 1750P2 1354 2356P3 0332 0652 P4 0014 0656（1）该状态是否安全？（2）如果P2提出请求Request2（1，2，2，2）后，系统能否将资源分配给它？2.有相同类型的5个资源被4个进程所共享，且每个进程最多需要2个这样的资源才可以运行完毕，试问系统是否会由于