计算机操作系统课件第三章教学教材.ppt

《计算机操作系统课件第三章教学教材.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统课件第三章教学教材.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机操作系统课件第三章 进程调度要解决的问题WHATWHAT：按什么原则分配按什么原则分配CPUCPU 进程调度算法进程调度算法WHENWHEN：何时分配何时分配CPUCPU 进程调度的时机进程调度的时机HOWHOW：如何分配如何分配CPUCPU CPU CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）1.高级、中级和低级调度l处理机是计算机系统中的重要资源处理机是计算机系统中的重要资源l处理机调度算法对整个计算机系统的综处理机调度算法对整个计算机系统的综合性能指标有重要影响合性能指标有重要影响l可把处理机调度分成三个层次：可把处理机调度分成三个层次：高级调度 中级调度 低级调

2、度高级调度高级调度也称为作业调度或长程调度或宏观调度也称为作业调度或长程调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天高级调度的时间尺度通常是分钟、小时或天中级调度中级调度涉及进程在内外存间的交换，从存储器涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问和数据必须在内存里才能被处理机直接访问低级调度低级调度也称进程

3、调度或短程调度或微观调度，也称进程调度或短程调度或微观调度，从处理机资源分配的角度来看，处理机需要经常从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效频繁使用，要求在实现时做到高效2.进程调度的任务 进程调度的任务是控制协进程调度的任务是控制协调进程对调进程对CPUCPU的竞争的竞争,即按一定即按一定的调度算法从就绪队列中选中的调度算法从就绪队列中选中一个进程，把一个进程，把CPUCPU的使用权交的使用权

4、交给被选中的进程。给被选中的进程。3.确定算法的原则具有公平性具有公平性资源利用率高（特别是资源利用率高（特别是CPUCPU利用利用率）率）在交互式系统情况下要追求响应在交互式系统情况下要追求响应时间（越短越好）时间（越短越好）在批处理系统情况下要追求系统在批处理系统情况下要追求系统吞吐量吞吐量4.进程调度方式非非抢抢占占方方式式：分分派派程程序序一一旦旦把把处处理理机机分分配配给给某某进进程程后后便便让让它它一一直直运运行行下下去去，直直到到进进程程完完成成或或发发生生某某事事件件而而阻阻塞塞时时，才才把把处处理理机分配给另一个进程。机分配给另一个进程。抢抢占占方方式式：当当一一个个进进程程

5、正正在在运运行行时时，系系统统可可以以基基于于某某种种原原则则，剥剥夺夺已已分分配配给给它它的的处处理理机机，将将之之分分配配给给其其它它进进程程。抢抢占占原原则则有有：优优先先权权原原则则、短短进进程程优优先先原原则则、时时间间片片原原则。则。5.进程调度性能衡量的指标周转时间周转时间响应时间响应时间CPU-I/OCPU-I/O执行期执行期6.进程调度模型 1)只有进程调度的调度队列模型图 3-1 仅具有进程调度的调度队列模型2)具有高低级调度的调度队列模型图 3-2 具有高、低两级调度的调度队列模型3)具有三级调度的调度队列模型图 3-3 具有三级调度时的调度队列模型7.选择进程调度方式的

6、准则面面向向用用户户的的准准则则：周周转转时时间间短短；响响应应时时间间快快；截截止止时时间间的的保保证证；优优先先权准则权准则面面向向系系统统的的准准则则：系系统统吞吞吐吐量量高高；处处理理机机利利用用率率好好；各各类类资资源源的的平平衡衡利用利用3.2 3.2 进程调度算法先进先出先进先出(FIFO)(FIFO)算法算法最短最短CPUCPU运行期优先调度算法运行期优先调度算法最高优先权优先调度算法最高优先权优先调度算法 轮转法轮转法 多级反馈队列多级反馈队列 1.先进先出(FIFO)算法 该该算算法法总总是是把把处处理理机机分分配配给给最最先先进进入入就就绪绪队队列列的的进进程程，一一个个

7、进进程程一一旦旦分分得得处处理理机机，便便执执行行下下去去，直到该进程完成或阻塞时，才释放处理机。直到该进程完成或阻塞时，才释放处理机。优点优点:实现简单实现简单.缺点缺点:没考虑进程的优先级没考虑进程的优先级 2.最短CPU运行期优先调度算法该该算算法法从从就就绪绪队队列列中中选选出出“下下一一个个CPUCPU执执行行期期”最最短短的的进进程程，为为之之分分配配处理机。处理机。该该算算法法虽虽可可获获得得较较好好的的调调度度性性能能，但但难难以以准准确确地地知知道道下下一一个个CPUCPU执执行行期期，而而只只能能根根据据每每一一个个进进行行的的执执行行历历史史来来预测。预测。4.最高优先权

8、优先调度算法 该该算算法法总总是是把把处处理理机机分分配配给给就就绪绪队队列列中中具具有有最最高高优优先先权权的的进进程程。常常用用以以下下两两种种方方法法来来确确定进程的优先权定进程的优先权(优先级根据优先数来决定优先级根据优先数来决定)静静态态优优先先数数法法：静静态态优优先先权权是是在在创创建建进进程程时时确确定定的的，在在整整个个运运行行期期间间不不再再改改变变。依依据据有有：进进程程类类型型、进进程程对对资资源源的的要要求求、用用户户要要求求的的优优先先权。权。动动态态优优先先数数法法：在在进进程程创创建建时时创创立立一一个个优优先先数数，但但在在其其生生命命周周期期内内优优先先数数

9、可可以以动动态态变变化化。如如等等待时间长优先数可改待时间长优先数可改变变图 3-4 FCFS和SJF调度算法的性能 3.FCFS和SJF的性能比较 优先权的变化规律可描述为：优先权的变化规律可描述为：由由于于等等待待时时间间与与服服务务时时间间之之和和，就就是是系系统统对对该该作作业业的的响响应应时时间间，故故该该优优先先权权又又相相当当于于响应比响应比R RP P。据此，又可表示为：。据此，又可表示为：5.高响应比优先调度算法6.轮转法 把把CPUCPU划划分分成成若若干干时时间间片片,并并且且按按顺顺序序赋赋给给就就绪绪队队列列中中的的每每一一个个进进程程，进进程程轮轮流流占占有有CPU

10、CPU，当当时时间间片片用用完完时时，即即使使进进程程未未执执行行完完毕毕，系系统统也也剥剥夺夺该该进进程程的的CPUCPU，将将该该进进程程排排在在就就绪绪队队列列末末尾尾。同同时时系系统统选选择择另另一一个个进进程程运行运行简简单单轮轮转转法法：系系统统将将所所有有就就绪绪进进程程按按FIFOFIFO规规则则排排队队，按按一一定定的的时时间间间间隔隔把把处处理理机机分分配配给给队队列列中中的的进进程程。这这样样，就就绪绪队队列列中中所所有有进进程程均可获得一个时间片的处理机而运行。均可获得一个时间片的处理机而运行。多多级级队队列列方方法法：将将系系统统中中所所有有进进程程分分成成若若干干类

11、，每类为一级。类，每类为一级。7.分时系统中常用时间片轮转法时间片选择问题：固定时间片固定时间片 可变时间片可变时间片与时间片大小有关的因素：系统响应时间系统响应时间 就绪进程个数就绪进程个数 CPU CPU能力能力 1)简单轮转法的调度模型2)多队列反馈调度算法 将就绪队列分为将就绪队列分为N N级，每个就绪队列级，每个就绪队列分配给不同的时间片，队列级别越高，分配给不同的时间片，队列级别越高，时间越小，级别越低，时间片越大，最时间越小，级别越低，时间片越大，最后一级采用时间片轮转，其他队列采用后一级采用时间片轮转，其他队列采用先进先出；先进先出；系统从第一级调度，当第一系统从第一级调度，当

12、第一级为空时，系统转向第二个队列，级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放当运行进程用完一个时间片，放弃弃CPUCPU时，进入下一级队列；等待进程时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列程第一次就绪时，进入第一级队列 *首先系统中设置多个就绪队列首先系统中设置多个就绪队列*每个就绪队列分配给不同时间片，优先级高的为每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，第一级队列，时间片最小，随着队列级别的降低，时间片加大时间片加大*各个队列按照先进先出调度算

13、法各个队列按照先进先出调度算法*一个新进程就绪后进入第一级队列一个新进程就绪后进入第一级队列*进程由于等待而放弃进程由于等待而放弃CPUCPU后，进入等待队列，一后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列旦等待的事件发生，则回到原来的就绪队列*当有一个优先级更高的进程就绪时，可以抢占当有一个优先级更高的进程就绪时，可以抢占CPUCPU，被抢占进程回到原来一级就绪队列末尾，被抢占进程回到原来一级就绪队列末尾*当第一级队列空时，就去调度第二级队列，如此当第一级队列空时，就去调度第二级队列，如此类推类推*当时间片到后，进程放弃当时间片到后，进程放弃CPUCPU，回到下一级队列，回到下

14、一级队列 3)多队列反馈调度算法8.进程调度的时机当一个进程运行完毕，或由于某种错误而当一个进程运行完毕，或由于某种错误而终止运行终止运行当一个进程在运行中处于等待状态（等待当一个进程在运行中处于等待状态（等待I/OI/O）分时系统中时间片到分时系统中时间片到当有一个优先级更高的进程就绪（可抢占当有一个优先级更高的进程就绪（可抢占式）式）例如：新创建一个进程，一个等待进程变例如：新创建一个进程，一个等待进程变成就绪成就绪在进程通信中，执行中的进程执行了某种在进程通信中，执行中的进程执行了某种原语操作（原语操作（P P操作，阻塞原语，唤醒原语）操作，阻塞原语，唤醒原语）何时切换进程 只要只要OS

15、OS取得对取得对CPUCPU的控制，进程切换就可的控制，进程切换就可能发生，如能发生，如:超级用户调用超级用户调用来自程序的显式请求来自程序的显式请求(如：打开文件如：打开文件)，该进程通常会被阻塞，该进程通常会被阻塞陷阱陷阱最末一条指令导致出错，会引起进程最末一条指令导致出错，会引起进程移至退出状态移至退出状态中断中断 外部因素影响当前指令的执行，控制外部因素影响当前指令的执行，控制被转移至被转移至IHIH（中断处理程序）（中断处理程序）9.引起进程调度的原因正正在在执执行行的的进进程程执执行行完完毕毕或或因因发发生生某某事事件件而不能再继续执行；而不能再继续执行；执行中的进程因提出执行中的

16、进程因提出I/OI/O请求而暂停执行；请求而暂停执行；在在进进程程通通信信或或同同步步过过程程中中执执行行了了某某种种原原语语操作如操作如P P操作、阻塞、挂起原语等；操作、阻塞、挂起原语等；在在可可抢抢占占式式调调度度中中，有有比比当当前前进进程程优优先先权权更高的进程进入就绪队列；更高的进程进入就绪队列；在时间片轮转法中，时间片完。在时间片轮转法中，时间片完。通通常常系系统统是是按按先先来来先先服服务务或或优优先先权权形形式式来来组织调度队列。组织调度队列。10.进程调度算法其其中中，RQRQ为为就就绪绪队队列列指指针针，EPEP为为运运行行队队列列指针指针。3.3 3.3 实实 时时 调

17、调 度度1.1.实现实时调度的基本条件实现实时调度的基本条件提供必要的信息提供必要的信息(就绪时间、截止时间、处理就绪时间、截止时间、处理时间、资源优先级时间、资源优先级)系统处理能力强系统处理能力强采用抢占式调度机制采用抢占式调度机制具有快速切换机制具有快速切换机制 2.实时调度算法的分类1)非抢占式调度算法:非抢占式轮转调度算法非抢占式优先调度算法2)抢占式调度算法:基于时钟中断的抢占优先调度算法 立即抢占优先权调度算法。图 3-5 实时进程调度 图 3-6 EDF算法用于非抢占调度方式 3.常用的几种实时调度算法1 1）最早截止时间优先即）最早截止时间优先即EDF(Earliest De

18、adline EDF(Earliest Deadline First)First)算法算法图 3-7 A和B任务每次必须完成的时间2）最低松弛度优先(LLF)算法 该该算算法法是是根根据据任任务务紧紧急急(或或松松弛弛)的的程程度度，来来确确定定任任务的优先级。该算法主要用于可抢占调度方式中。务的优先级。该算法主要用于可抢占调度方式中。假假如如在在一一个个实实时时系系统统中中，有有两两个个周周期期性性实实时时任任务务A A和和B B，任任务务A A要要求求每每 20 20 msms执执行行一一次次，执执行行时时间间为为 10 10 msms；任任务务B B只要求每只要求每50 ms50 ms执

19、行一次，执行时间为执行一次，执行时间为 25 ms 25 ms。在在刚刚开开始始时时(t t1 1=0)=0)，A A1 1必必须须在在20ms20ms时时完完成成，而而它它本本身身运运行行又又需需 10 10 msms，可可算算出出A A1 1的的松松弛弛度度为为10ms10ms；B B1 1必必须须在在50ms50ms时时完完成成，而而它它本本身身运运行行就就需需25 25 msms，可可算算出出B B1 1的的松松弛弛度度为为25 25 msms，故故调调度度程程序序应应先先调调度度A A1 1执执行行。在在t t2 2=10=10 msms时时，A A2 2的的松松弛弛度度可可按按下下

20、式式算算出出：A A2 2的的松松弛弛度度=必必须须完完成成时时间间-其其本本身身的的运运行行时时间间-当前时间当前时间=40 ms-10 ms-10 ms=20 ms=40 ms-10 ms-10 ms=20 ms 类类似似地地，可可算算出出B1B1的的松松弛弛度度为为15ms15ms，调调度度程程序序应应选选择择B2B2运运行行。t t3=30 3=30 msms时时，A2A2的的松松弛弛度度已已减减为为0 0，B1B1的的松松弛弛度度为为15 ms15 ms，于是调度程序应抢占，于是调度程序应抢占B1B1的处理机而调度的处理机而调度A2A2运行运行图 3-8 利用ELLF算法进行调度的情

21、况3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.5.1 3.5.1 死锁的概念死锁的概念1.1.死锁例子死锁例子:一个由于一个由于申请不同类型资源申请不同类型资源而产生死锁的例子而产生死锁的例子设设系系统统有有一一台台打打印印机机(R1)(R1)一一台台扫扫描描仪仪(R2)(R2)，两两进进程共享这两台设备。程共享这两台设备。用用信信号号量量S1S1表表示示R1R1是是否否可可用用，用用信信号号量量S2S2表表示示R2R2是否可用，是否可用，S1S1、S2 S2初值为初值为1 1。死锁例子死锁例子 这这两两个个进进程程在在并并发发执执行行过过程程中中，可可能能会会发发生生死死锁锁

22、。大大家家可可以以思思考考一一下下，如如何何修改，进程才不会发生死锁。修改，进程才不会发生死锁。2.死锁概念指指多多个个进进程程因因竞竞争争共共享享资资源源而而造造成成的的一一种种僵僵局局，若若无无外外力力作作用用，这这些些进进程程都都将将永永远远不不能能再向前推进。再向前推进。即即：一一组组进进程程中中，每每个个进进程程都都无无限限等等待待被被该该组组进进程程中中另另一一进进程程所所占占有有的的资资源源，因因而而永永远远无无法法得得到到的的资资源源，这这种种现现象象称称为为进进程程死死锁锁，这一组进程就称为死锁进程。这一组进程就称为死锁进程。3.关于死锁的一些结论关于死锁的一些结论参与死锁的

23、进程最少是两个参与死锁的进程最少是两个 参与死锁的进程至少有两个已经占有参与死锁的进程至少有两个已经占有资源资源参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进参与死锁的进程是当前系统中所有进程的子集程的子集注：如果死锁发生，会浪费大量系统资注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。源，甚至导致系统崩溃。4.永久性资源和临时性资源永久性资源：可以被多个进程多次使永久性资源：可以被多个进程多次使用（可再用资源）用（可再用资源）可抢占资源可抢占资源(如如CPUCPU和内存和内存)不可抢占资源（如打印机、磁带机）不可抢占资源（如打印机、磁带机

24、）临时性资源：只可使用一次的资源；临时性资源：只可使用一次的资源；如信号量如信号量,中断信号，同步信号等（可中断信号，同步信号等（可消耗性资源）消耗性资源）“申请申请-分配分配-使用使用-释放释放”模式模式3.5.2 产生死锁的原因1.1.竞争系统资源竞争系统资源2.2.进程的推进顺序不当进程的推进顺序不当 1.1.竞争系统资源 若若系系统统中中只只有有一一台台打打印印机机R1R1和和一一台台读读卡卡机机R2R2，可可供供进进程程P1P1和和P2P2共共享享。若若形形成成环路等待环路等待，这样会产生死锁，这样会产生死锁。2.2.进程的推进顺序不当在在进进程程P1P1和和P2P2并并发发执执行行

25、时时，按按照照左左图图曲曲线线所所示示顺顺序序推推进进时时，两两进进程程会会顺顺利利完完成成，我我们们称称这这种种推推进进顺顺序序是是合合法法的的。若若按按曲曲线线的的顺顺序序推推进进时时，进进入入不不安安全全区区D D内内，两进程再推进会产生死锁。两进程再推进会产生死锁。3.5.3 产生死锁的必要条件互斥条件互斥条件（资源独占）（资源独占）请请求求和和保保持持条条件件（部部分分分分配配，占有申请）占有申请）不剥夺条件（不剥夺条件（不可强占）不可强占）环路等待条件。环路等待条件。解决死锁的基本办法预防死锁避免死锁检测死锁解除死锁3.6 预防死锁的方法和避免死锁 1.1.预防死锁的方法预防死锁的

26、方法 在系统设计时确定资源分配算法，保证不发生死锁。具在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。体的做法是破坏产生死锁的四个必要条件之一。1)资源一次性分配；(破坏请求和保持条件破坏请求和保持条件)2)可剥夺资源；即即当当某某进进程程新新的的资资源源未未满满足足时时，释释放放已已占占有的资源有的资源(破坏不可剥夺条件破坏不可剥夺条件)3)资源有序分配法；做做法法：系系统统给给每每类类资资源源赋赋予予一一个个编编号号，每每一一个个进进程程按按编编号号递递增增的的顺顺序序请请求求资资源源，释释放放则则相相反反(破破坏坏环路等待条件环路等待条件)2.死

27、锁避免死锁避免定义:在系统运行过程中，对进程发出的在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。能发生死锁，则不予分配，否则予以分配。预预防防死死锁锁的的几几种种策策略略，会会严严重重地地损损害害了了系系统统性性能能。因因此此要要施施加加较较弱弱的的限限制制，从从而而获获得得较较满满意意得得系系统统性性能来避免死锁。能来避免死锁。由由于于在在避避免免死死锁锁的的策策略略中中，允允许许进进程程动动态态

28、地地申申请请资资源源。因因而而，系系统统在在进进行行资资源源分分配配之之前前预预先先计计算算资资源源分分配配的的安安全全性性。若若此此次次分分配配不不会会导导致致系系统统进进入入不不安安全全状状态态，则则将将资资源源分分配配给给进进程程；否否则则，进进程程等等待待。其中最具有代表性的避免死锁算法是银行家算法。其中最具有代表性的避免死锁算法是银行家算法。3.安全状态与不安全状态 安安全全状状态态指指系系统统能能按按某某种种进进程程顺顺序序来来为为每每个个进进程程分分配配其其所所需需资资源源，直直至至最最大大需需求求，使使每每个个进进程程都都可可顺顺序序完完成成。若若系系统统不不存存在在这这样样一

29、一个个序序列，则称系统处于不安全状态。列，则称系统处于不安全状态。1)安全序列 一个进程序列一个进程序列PP1 1，P Pn n 是安全的，是安全的，如果对于每一个进程如果对于每一个进程P Pi i(1(1i in n），它以），它以后尚需要的资源量不超过系统当前剩余资后尚需要的资源量不超过系统当前剩余资源量与所有进程源量与所有进程P Pj j(j i)(j i)当前占有资源当前占有资源量之和，系统处于安全状态。量之和，系统处于安全状态。(安全状态一定是没有死锁发生的安全状态一定是没有死锁发生的)进进 程程 最最 大大 需需 求求 已已 分分 配配 可可 用用 P1P2P3104952232)

30、2)安全状态之例安全状态之例 我们通过一个例子来说明安全性。假定系我们通过一个例子来说明安全性。假定系统中有三个进程统中有三个进程P P1 1、P P2 2和和P P3 3，共有，共有1212台磁带机。台磁带机。进程进程P P1 1总共要求总共要求1010台磁带机，台磁带机，P P2 2和和P P3 3分别要求分别要求4 4台和台和9 9台。假设在台。假设在T T0 0时刻，进程时刻，进程P P1 1、P P2 2和和P P3 3已分已分别获得别获得5 5台、台、2 2台和台和2 2台磁带机，尚有台磁带机，尚有3 3台空闲未台空闲未分配，如下表所示：分配，如下表所示：3)3)由安全状态向不安全

31、状态的转换由安全状态向不安全状态的转换 如果不按照安全序分配资源，则系统如果不按照安全序分配资源，则系统可能会由安全状态进入不安全状态。例如，可能会由安全状态进入不安全状态。例如，在在T T0 0时刻以后，时刻以后，P P3 3又请求又请求1 1台磁带机，若此台磁带机，若此时系统把剩余时系统把剩余3 3台中的台中的1 1台分配给台分配给P P3 3，则系，则系统便进入不安全状态。统便进入不安全状态。因为，此时也无因为，此时也无法再找到一个安全序列，法再找到一个安全序列，例如，把其余例如，把其余的的2 2台分配给台分配给P P2 2，这样，在，这样，在P P2 2完成后只能释完成后只能释放出放出

32、4 4台，既不能满足台，既不能满足P P1 1尚需尚需5 5台的要求，台的要求，也不能满足也不能满足P P3 3尚需尚需6 6台的要求，致使它们台的要求，致使它们都无法推进到完成，彼此都在等待对方释都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。放资源，即陷入僵局，结果导致死锁。安全状态与不安全状态 不安全状态不安全状态:不存在一个安全序列，不存在一个安全序列，不安全状态不一定导致死锁不安全状态不一定导致死锁4.利用银行家算法避免死锁1)1)银行家算法中的数据结构银行家算法中的数据结构 (1)(1)可可利利用用资资源源向向量量AvailableAvailable。这这是是

33、一一个个含含有有m m个个元元素素的的数数组组，其其中中的的每每一一个个元元素素代代表表一一类类可可利利用用的的资资源源数数目目，其其初初始始值值是是系系统统中中所所配配置置的的该该类类全全部部可可用用资资源源的的数数目目，其其数数值值随随该该类类资资源源的的 分分 配配 和和 回回 收收 而而 动动 态态 地地 改改 变变。如如 果果AvailableAvailablej j=K=K，则则表表示示系系统统中中现现有有R Rj j类类资资源源K K个。个。(2)(2)最最大大需需求求矩矩阵阵MaxMax。这这是是一一个个n nm m的的矩矩阵阵，它它定定义义了了系系统统中中n n个个进进程程中

34、中的的每每一一个个进进程程对对m m类类资资源源的的最最大大需需求求。如如果果MaxMaxi,ji,j=K=K，则表示进程，则表示进程i i需要需要R Rj j类资源的最大数目为类资源的最大数目为K K。(3)(3)分分配配矩矩阵阵AllocationAllocation。这这也也是是一一个个n nm m的的矩矩阵阵，它它定定义义了了系系统统中中每每一一类类资资源源当当前前已已分分配配给给每每一一进进程程的的资资源源数数。如如果果AllocationAllocationi,ji,j=K=K，则则表表示示进进程程i i当当前前已已分分得得R Rj j类类资资源源的数目为的数目为K K。(4)(4

35、)需需求求矩矩阵阵NeedNeed。这这也也是是一一个个n nm m的的矩矩阵阵，用用以以表表示示每每一一个个进进程程尚尚需需的的各各类类资资源源数数。如如果果NeedNeedi,ji,j=K K，则则表表示进程示进程i i还需要还需要R Rj j类资源类资源K K个，方能完成其任务。个，方能完成其任务。Need Needi,ji,j=Max=Maxi,ji,j-Allocation-Allocationi,ji,j 2)2)银行家算法银行家算法 设设RequestRequesti i是是进进程程P Pi i的的请请求求向向量量，如如果果RequestRequesti ij j=K K，表表示

36、示进进程程P Pi i需需要要K K个个R Rj j类类型型的的资资源源。当当P Pi i发发出出资资源源请请求求后后，系统按下述步骤进行检查：系统按下述步骤进行检查：(1)(1)如如果果RequestRequesti ij jNeedNeedi,ji,j，便便转转向向步步骤骤2 2；否否则则认认为为出出错错，因因为为它它所所需需要要的的资资源源数数已已超超过过它它所所宣宣布的最大值。布的最大值。(2)(2)如如果果RequestRequesti ij jAvailableAvailablej j，便便转转向步骤向步骤(3)(3)；否则，；否则，表示尚无足够资源，表示尚无足够资源，P Pi i

37、须等待。须等待。(3)(3)系系统统试试探探着着把把资资源源分分配配给给进进程程P Pi i，并并修修改改下下面面数数据据结结构构中的数值：中的数值：AvailableAvailable j j=Available=Available j j-Request-Requesti i j j;AllocationAllocationi,ji,j=Allocation=Allocationi,ji,j+Request+Requesti ij j;NeedNeedi,ji,j=Need=Needi,ji,j-Request-Requesti ij j;(4)(4)系系统统执执行行安安全全性性算算法法，

38、检检查查此此次次资资源源分分配配后后，系系统统是是否否处处于于安安全全状状态态。若若安安全全，才才正正式式将将资资源源分分配配给给进进程程P Pi i，以以完完成成本本次次分分配配；否否则则，将将本本次次的的试试探探分分配配作作废废，恢恢复复原原来来的的资资源分配状态，让进程源分配状态，让进程P Pi i等待。等待。3)3)安全性算法安全性算法(1)(1)设设置置两两个个向向量量：工工作作向向量量Work:Work:它它表表示示系系统统可可提提供供给给进进程程继继续续运运行行所所需需的的各各类类资资源源数数目目，它它含含有有m m个个元元素素，在在执执行行安安全全算算法法开开始始时时，Work

39、=Available;Work=Available;Finish:Finish:它它表表示示系系统统是是否否有有足足够够的的资资源源分分配配给给进进程程，使使之之运运行行完完成成。开开始始时时先先做做FinishFinishi i=false;=false;当当有有足足够够资资源源分分配配给进程时，给进程时，再令再令FinishFinishi i=true=true。(2)(2)从从进进程程集集合合中中找找到到一一个个能能满满足足下下述述条条件件的的进进程程：FinishFinishi i=false;=false;NeedNeedi,ji,jWorkWorkj j；若若找找到到，执执行行步步

40、骤骤(3)(3)，否否则则，执执行行步步骤骤(4)(4)。(3)(3)当当进进程程P Pi i获获得得资资源源后后，可可顺顺利利执执行行，直直至至完完成成，并并释释放放出分配给它的资源，故应执行：出分配给它的资源，故应执行：Work Workj j=WorkWorki i+Allocation+Allocationi,ji,j;Finish Finishi i=true;true;go to step 2;go to step 2;(4)(4)如如果果所所有有进进程程的的FinishFinishi i=true=true都都满满足足，则则表表示示系系统处于安全状态；否则，系统处于不安全状态。统

41、处于安全状态；否则，系统处于不安全状态。图图 3-8 3-8 T T0 0时刻的资源分配表时刻的资源分配表 4)4)银行家算法之例银行家算法之例 假定系统中有五个进程假定系统中有五个进程P P0 0,P,P1 1,P,P2 2,P,P3 3,P,P4 4和三类资源和三类资源A,B,CA,B,C，各种资源的数量分别为，各种资源的数量分别为1010、5 5、7 7，在，在T T0 0时刻的资源分配情况如图时刻的资源分配情况如图 3-15 3-15 所示。所示。(1)(1)T T0 0时刻的安全性：时刻的安全性：图 3-9 T0时刻的安全序列 (2)(2)P P1 1请请 求求 资资 源源：P P1

42、 1发发 出出 请请 求求 向向 量量RequestRequest1 1(1(1，0 0，2)2)，系统按银行家算法进行检查：，系统按银行家算法进行检查：Request Request1 1(1,0,2)Need(1,0,2)Need1 1(1,2,2)(1,2,2)Request Request1 1(1,0,2)Available(1,0,2)Available1 1(3,3,2)(3,3,2)系系 统统 先先 假假 定定 可可 为为 P P1 1分分 配配 资资 源源，并并 修修 改改Available,Available,AllocationAllocation1 1和和NeedNee

43、d1 1向向量量，由由此此形形成成的资源变化情况如图的资源变化情况如图 3-15 3-15 中的圆括号所示。中的圆括号所示。再利用安全性算法检查此时系统是否安全。再利用安全性算法检查此时系统是否安全。图图 3-10 P 3-10 P1 1申请资源时的安全性检查申请资源时的安全性检查 (3)(3)P P4 4请请求求资资源源：P P4 4发发出出请请求求向向量量RequestRequest4 4(3,3,0)(3,3,0)，系统按银行家算法进行检查：，系统按银行家算法进行检查：Request Request4 4(3,3,0)Need(3,3,0)Need4 4(4,3,1);(4,3,1);R

44、equest Request4 4(3,3,0)Available(2,3,0)(3,3,0)Available(2,3,0)，让，让P P4 4等待。等待。(4)(4)P P0 0请请求求资资源源：P P0 0发发出出请请求求向向量量RequstRequst0 0(0,2,0)(0,2,0)，系统按银行家算法进行检查：系统按银行家算法进行检查：Request Request0 0(0,2,0)Need(0,2,0)Need0 0(7,4,3);(7,4,3);Request Request0 0(0,2,0)Available(2,3,0);(0,2,0)Available(2,3,0);系

45、统暂时先假定可为系统暂时先假定可为P P0 0分配资源，并修改分配资源，并修改有关数据，如图有关数据，如图 3-11 3-11 所示。所示。图图 3-11 3-11 为为P P0 0分配资源后的有关资源数据分配资源后的有关资源数据 允许死锁发生，操作系统不断允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发监视系统进展情况，判断死锁是否发生生 一旦死锁发生则采取专门的措一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操施，解除死锁并以最小的代价恢复操作系统运行作系统运行3.7 死锁的检测和解除1.检测时机 当进程等待时检测死锁当进程等待时检测死锁 （其缺点是系统的开销大）（其缺

46、点是系统的开销大）定时检测定时检测 系统资源利用率下降时检测死锁系统资源利用率下降时检测死锁2.死锁检测算法每个进程和资源指定唯一编号每个进程和资源指定唯一编号设置一张资源分配表设置一张资源分配表 记录各进程与其占用资源之间的关系记录各进程与其占用资源之间的关系设置一张进程等待表设置一张进程等待表 记录各进程与要申请资源之间的关系记录各进程与要申请资源之间的关系1)资源分配表和进程等待表资源分配表资源分配表 进程等待表进程等待表r1 p2 p1 r1r1 p2 p1 r1r2 p5 p2 r3r2 p5 p2 r3r3 p4 p4 r4r3 p4 p4 r4r4 p1r4 p1 2)资源分配表

47、和进程等待表当进程当进程P4P4申请资源申请资源3 3时，会产生死锁吗？时，会产生死锁吗？3)检测算法3.死锁的解除 重要的是以最小的代价恢重要的是以最小的代价恢复系统的运行。方法如下：复系统的运行。方法如下：1 1）重新启动）重新启动 2 2）撤消进程）撤消进程 3 3）剥夺资源）剥夺资源 4 4）进程回退）进程回退4.资源分配图 用有向图描述进程的死锁用有向图描述进程的死锁 准确、形象准确、形象 系统由若干类资源构成，一类系统由若干类资源构成，一类资源称为一个资源类；每个资源类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源中包含若干个同种资源，称为资源实例实例资源分配图 二元

48、组二元组G=G=（V V，E E）V V：结点集，分为：结点集，分为P P，R R两部分两部分 P=p1,p2,pn,R=r1,r2,rm P=p1,p2,pn,R=r1,r2,rm E E：边的集合，其元素为有序二元组：边的集合，其元素为有序二元组:(pi,rj)(pi,rj)或或(rj,pi)(rj,pi)表示法:资源类:用方框表示（资源的不同类型）用方框表示（资源的不同类型）资源实例:用方框中的黑圆点表示（存在于每用方框中的黑圆点表示（存在于每个资源中）个资源中）进程:用圆圈中加进程名表示用圆圈中加进程名表示分配边：资源实例资源实例进程的一条有向边进程的一条有向边申请边：进程进程资源类的

49、一条有向边资源类的一条有向边 5.死锁定理 如果资源分配图中没有环路，如果资源分配图中没有环路，则系统中没有死锁，如果图中存在则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。环路则系统中可能存在死锁。如果每个资源类中只包含一个如果每个资源类中只包含一个资源实例，则环路是死锁存在的充资源实例，则环路是死锁存在的充分必要条件。分必要条件。有环有死锁有环有死锁有环无死锁有环无死锁2.2.死锁定理死锁定理 图图 3-12 3-12 资源分配图的简化资源分配图的简化 6.资源分配图化简方法如下方法如下:1 1）找一个非孤立点进程结点且只有）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为

50、孤分配边，去掉分配边，将其变为孤立结点立结点2 2）再把相应的资源分配给一个等待）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请该资源的进程，即将某进程的申请边变为分配边边变为分配边7.解除死锁 当当发发现现有有进进程程死死锁锁后后，便便应应立立即即把把它它从从死锁状态中解脱出来，常采用的方法有：死锁状态中解脱出来，常采用的方法有：剥剥夺夺资资源源：从从其其它它进进程程剥剥夺夺足足够够数数量量的的资资源源给死锁进程，以解除死锁状态；给死锁进程，以解除死锁状态；撤撤消消进进程程：可可以以直直接接撤撤消消死死锁锁进进程程或或撤撤消消代代价价最最小小的的进进程程，直直至至有有足足够够的的