ZGSOS(-)处理机调度与死锁

1、12022年7月4日星期一北京交通大学计算机学院 翟高寿主讲教师：翟高寿翟高寿（副教授）联系电话(办) 电子邮件：制作人：翟高寿翟高寿制作单位：北京交通大学计算机学院北京交通大学计算机学院操作系统操作系统22022年7月4日星期一北京交通大学计算机学院 翟高寿第三章第三章 处理机调度与死锁处理机调度与死锁3.1 高级、中级与低级调度3.2 调度队列模型3.3 调度方式与算法选择准则3.4 调度算法3.5 死锁产生及处理策略3.6 死锁避免与银行家算法32022年7月4日星期一北京交通大学计算机学院 翟高寿多道程序环境与处理机调度q作业类型与处理机获得过程批量型作业、

2、终端型作业q基于操作系统类型的调度分类批处理/分时/实时调度及多处理机调度q调度是多道程序系统的关键所在系统运行性能（如吞吐量大小、周转时间长短、响应及时性等）在很大程度上都取决于调度，特别是处理机调度一个作业从提交到执行，通常都要经历高级、中级、低级及I/O等多级调度多级调度42022年7月4日星期一北京交通大学计算机学院 翟高寿多级调度示意图52022年7月4日星期一北京交通大学计算机学院 翟高寿高级调度（作业/长程/宏观调度）q概念用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程和分配必要资源；然后，再将新创建进程插入到就绪队列上准备执行q操作系统配置作业调度机制分析批

3、处理系统分时系统、实时系统及时性要求q作业调度机制要领作业量确定多道程序度(Degree of Multiprogramming)作业选择调度算法62022年7月4日星期一北京交通大学计算机学院 翟高寿低级调度（进程/短程调度）q概念用来决定就绪队列中的哪个进程将获得处理机，然后再由分派程序（Dispatcher）执行把处理机分配给该进程的具体操作q操作系统配置进程调度机制分析基本调度，所有类型操作系统均需配置q调度方式分类非抢占方式（仅适用于批处理系统）抢占方式（分时、实时及批处理系统均可）72022年7月4日星期一北京交通大学计算机学院 翟高寿非抢占与抢占调度方式比较q非抢占调度方式(No

4、n-preemptive Mode)处理机分配给进程直至完成或阻塞引起进程调度的因素：当前进程执行完毕或因发生事件、提出I/O请求、执行原语操作而阻塞实现简单、系统开销小，但难以满足紧急任务要求，故不宜在实时系统中采用q抢占调度方式(Preemptive Mode)允许暂停正在执行进程和重新分配处理机抢占原则（优先权/短作业优先/时间片原则）82022年7月4日星期一北京交通大学计算机学院 翟高寿中级调度（中程调度）q概念为提高内存利用率和系统吞吐量，应使那些暂时不能运行的进程放弃占用内存资源，即调至外存上去等待；当内存稍有空闲时，可将外存中那些重又具备运行条件的就绪进程重新调入内存，修改其状

5、态和挂到就绪进程队列等待进程调度q实质存储器管理中的对换功能92022年7月4日星期一北京交通大学计算机学院 翟高寿第三章第三章 处理机调度与死锁处理机调度与死锁3.1 高级、中级与低级调度3.2 调度队列模型3.3 调度方式与算法选择准则3.4 调度算法3.5 死锁产生及处理策略3.6 死锁避免与银行家算法102022年7月4日星期一北京交通大学计算机学院 翟高寿仅有进程调度的调度队列模型就绪队列阻塞队列交互作业进程调度CPU进程完成等待事件时间片完事件出现112022年7月4日星期一北京交通大学计算机学院 翟高寿具有高级和低级调度的调度队列模型就绪队列阻塞队列1作业调度进程调度CPU进程完

6、成等待事件1时间片完事件1出现后备队列阻塞队列2等待事件2事件2出现阻塞队列n等待事件n事件n出现批量作业交互作业122022年7月4日星期一北京交通大学计算机学院 翟高寿同时具有三级调度的调度队列模型就绪队列就绪挂起队列作业调度进程调度CPU进程完成事件出现时间片完中级调度后备队列阻塞挂起队列挂起阻塞队列等待事件事件出现批量作业交互作业挂起132022年7月4日星期一北京交通大学计算机学院 翟高寿第三章第三章 处理机调度与死锁处理机调度与死锁3.1 高级、中级与低级调度3.2 调度队列模型3.3 调度方式与算法选择准则3.4 调度算法3.5 死锁产生及处理策略3.6 死锁避免与银行家算法14

7、2022年7月4日星期一北京交通大学计算机学院 翟高寿选择调度方式和算法的若干准则q面向用户的准则（与操作系统类型有关）周转时间周转时间短（平均周转平均周转/带权周转带权周转时间时间）响应时间响应时间快截至时间截至时间的保证优先权准则q面向系统的准则系统吞吐量吞吐量高处理机利用率好各类资源的平衡利用niiTnT11niSiiTTnW11152022年7月4日星期一北京交通大学计算机学院 翟高寿第三章第三章 处理机调度与死处理机调度与死锁锁3.1 高级、中级与低级调度3.2 调度队列模型3.3 调度方式与算法选择准则3.4 调度算法3.5 死锁产生及处理策略3.6 死锁避免与银行家算法16202

8、2年7月4日星期一北京交通大学计算机学院 翟高寿3.4 调度算法（资源分配算法）3.4.1 先来先服务调度算法3.4.2 短作业（进程）优先调度算法3.4.3 高优先权优先调度算法3.4.4 高响应比优先调度算法3.4.5 时间片轮转调度算法3.4.6 多级队列调度算法3.4.7 多级反馈队列调度算法172022年7月4日星期一北京交通大学计算机学院 翟高寿先来先服务调度算法FCFSq基本思想先来先服务作业调度算法先来先服务进程调度算法q算法特点有利于长作业（进程）而不利于短作业（进程）有利于CPU繁忙型作业（进程）而不利于I/O繁忙型作业（进程）182022年7月4日星期一北京交通大学计算机

9、学院 翟高寿先来先服务调度算法举例分析进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间ABCD0123110011000110110211011022021100100199111001.99192022年7月4日星期一北京交通大学计算机学院 翟高寿3.4 调度算法（资源分配算法）3.4.1 先来先服务调度算法3.4.2 短作业（进程）优先调度算法3.4.3 高优先权优先调度算法3.4.4 高响应比优先调度算法3.4.5 时间片轮转调度算法3.4.6 多级队列调度算法3.4.7 多级反馈队列调度算法202022年7月4日星期一北京交通大学计算机学院 翟高寿短进程优先调度算法举例分

10、析进程名ABCDE平均到达时间01234服务时间43524完成时间47121418周转时间461011149带权周转时间1225.53.52.8完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.1作业情况先来先服务先来先服务短进程优先短进程优先212022年7月4日星期一北京交通大学计算机学院 翟高寿短作业(进程)优先调度算法SJ(P)Fq基本思想短作业优先调度算法短进程优先调度算法q算法特点能有效降低作业（进程）平均等待时间和提高系统吞吐量不利于长作业（进程）完全未考虑作业（进程）的紧迫程度作业（进程）执行时间估计的不准确性222022年7月4日星期一

11、北京交通大学计算机学院 翟高寿3.4 调度算法（资源分配算法）3.4.1 先来先服务调度算法3.4.2 短作业（进程）优先调度算法3.4.3 高优先权优先调度算法3.4.4 高响应比优先调度算法3.4.5 时间片轮转调度算法3.4.6 多级队列调度算法3.4.7 多级反馈队列调度算法232022年7月4日星期一北京交通大学计算机学院 翟高寿高优先权优先调度算法FPFq基本思想照顾紧迫型作业（进程）q算法分类非抢占式优先权算法抢占式优先权调度算法q优先权类型静态优先权动态优先权进程优先权确定依据：进程类型、资源需求及用户要求242022年7月4日星期一北京交通大学计算机学院 翟高寿3.4 调度算

12、法（资源分配算法）3.4.1 先来先服务调度算法3.4.2 短作业（进程）优先调度算法3.4.3 高优先权优先调度算法3.4.4 高响应比优先调度算法3.4.5 时间片轮转调度算法3.4.6 多级队列调度算法3.4.7 多级反馈队列调度算法252022年7月4日星期一北京交通大学计算机学院 翟高寿高响应比优先调度算法q基本思想短作业优先调度算法+动态优先权机制q优先权（响应比RP）（等待时间+要求服务时间）/要求服务时间q算法特点短作业与先后次序的兼顾，且不会使长作业长期得不到服务响应比计算系统开销262022年7月4日星期一北京交通大学计算机学院 翟高寿3.4 调度算法（资源分配算法）3.4

13、.1 先来先服务调度算法3.4.2 短作业（进程）优先调度算法3.4.3 高优先权优先调度算法3.4.4 高响应比优先调度算法3.4.5 时间片轮转调度算法3.4.6 多级队列调度算法3.4.7 多级反馈队列调度算法272022年7月4日星期一北京交通大学计算机学院 翟高寿时间片轮转调度算法q基本思想按先来先服务原则排队时间片及时钟中断q时间片大小的确定系统对响应时间的要求就绪队列中进程的数目系统的处理能力282022年7月4日星期一北京交通大学计算机学院 翟高寿时间片轮转调度算法举例分析待续0 1 2 3 4 5 6 7 8 910 11 12 13 14 15 16 17ABCDEABCD

14、EABCEACEtABCDEq=1q=4292022年7月4日星期一北京交通大学计算机学院 翟高寿时间片轮转调度算法举例分析续完进程名ABCDE平均到达时间01234服务时间43424完成时间151216917周转时8带权周转时间3.753.673.533.253.43完成时间47111317周转时间46910138.4带权周转时间122.2553.252.61q=4q=1作业情况302022年7月4日星期一北京交通大学计算机学院 翟高寿3.4 调度算法（资源分配算法）3.4.1 先来先服务调度算法3.4.2 短作业（进程）优先调度算法3.4.3 高优先权优先调度算法

15、3.4.4 高响应比优先调度算法3.4.5 时间片轮转调度算法3.4.6 多级队列调度算法3.4.7 多级反馈队列调度算法312022年7月4日星期一北京交通大学计算机学院 翟高寿多级队列调度算法q引入的必要性多操作系统类型配置批量型作业和交互性作业性质的不同q基本思想作业性质分类排列，不同队列不同调度算法q队列间关系处理优先权方式前/后台比例方式322022年7月4日星期一北京交通大学计算机学院 翟高寿3.4 调度算法（资源分配算法）3.4.1 先来先服务调度算法3.4.2 短作业（进程）优先调度算法3.4.3 高优先权优先调度算法3.4.4 高响应比优先调度算法3.4.5 时间片轮转调度算

16、法3.4.6 多级队列调度算法3.4.7 多级反馈队列调度算法332022年7月4日星期一北京交通大学计算机学院 翟高寿多级反馈队列调度算法q引入的必要性各类进程调度算法均有一定的局限性q基本思想设置多个就绪队列并赋予各个队列不同优先权不同队列中进程执行的时间片大小各不相同先来先服务调度算法与时间片轮转调度算法相结合队列间调度准则和抢占式优先权调度q算法性能能较好地满足各种类型用户（终端型作业用户、短批处理作业用户、长批处理作业用户）的要求342022年7月4日星期一北京交通大学计算机学院 翟高寿3.4 调度算法（资源分配算法）3.4.1 先来先服务调度算法3.4.2 短作业（进程）优先调度算

17、法3.4.3 高优先权优先调度算法3.4.4 高响应比优先调度算法3.4.5 时间片轮转调度算法3.4.6 多级队列调度算法3.4.7 多级反馈队列调度算法352022年7月4日星期一北京交通大学计算机学院 翟高寿作业题作业题q3.1 谈谈你对处理机调度模型及各级调度机制的认识与理解。q3.2 选择调度方式和调度算法时，应遵循哪些准则？并请分析比较各种调度算法的基本思想、关键要领、优缺点及适用场合。362022年7月4日星期一北京交通大学计算机学院 翟高寿操作系统实践实验4q调度算法实现与比较：I.先来先服务调度算法、短作业（/进程）优先调度算法、高优先权优先调度算法、高响应比优先调度算法、时

18、间片轮转调度算法、多级反馈队列调度算法II.随机发生作业到达（或进程创建）事件，并显示调度过程明细III.撰写实验报告，阐述实验目的、实验目标、实验步骤、技术难点及解决方案、关键数据结构和算法流程、测试方案与过程及运行效果、结论与体会等。372022年7月4日星期一北京交通大学计算机学院 翟高寿第三章第三章 处理机调度与死锁处理机调度与死锁3.1 高级、中级与低级调度3.2 调度队列模型3.3 调度方式与算法选择准则3.4 调度算法3.5 死锁产生及处理策略3.6 死锁避免与银行家算法382022年7月4日星期一北京交通大学计算机学院 翟高寿3.5 死锁产生及处理策略3.5.1 死锁的基本概念

19、3.5.2 死锁产生的原因3.5.3 死锁产生的必要条件3.5.4 处理死锁的基本方法3.5.5 死锁的预防3.5.6 死锁的检测与解除392022年7月4日星期一北京交通大学计算机学院 翟高寿死锁的基本概念q死锁（Deadlock）在多道程序系统中，并发执行的多个进程因争夺资源而造成的一种若无外力作用有关进程都将永远不能向前推进的僵持状态或僵局q资源分类可剥夺资源可剥夺资源与不可剥夺资源不可剥夺资源永久性资源永久性资源与临时性资源临时性资源402022年7月4日星期一北京交通大学计算机学院 翟高寿3.5 死锁产生及处理策略3.5.1 死锁的基本概念3.5.2 死锁产生的原因3.5.3 死锁产

20、生的必要条件3.5.4 处理死锁的基本方法3.5.5 死锁的预防3.5.6 死锁的检测与解除412022年7月4日星期一北京交通大学计算机学院 翟高寿死锁产生原因之一：竞争资源I/O设备共享时的死锁情况（A）竞争非剥夺性资源进程间通信时的死锁情况（ B ）竞争临时性资源P1P2R1R2P1P3S1S3P2S2422022年7月4日星期一北京交通大学计算机学院 翟高寿死锁产生原因之二：进程推进次序非法P1Request(R1) P1Request(R2)P1Release(R1) P1Release(R2)P2Request(R2)P2Request(R1)P2Release(R2)P2Rele

21、ase(R1)1234432022年7月4日星期一北京交通大学计算机学院 翟高寿3.5 死锁产生及处理策略3.5.1 死锁的基本概念3.5.2 死锁产生的原因3.5.3 死锁产生的必要条件3.5.4 处理死锁的基本方法3.5.5 死锁的预防3.5.6 死锁的检测与解除442022年7月4日星期一北京交通大学计算机学院 翟高寿产生死锁的必要条件q互斥条件资源排它性使用q请求和保持条件请求资源未果进程虽阻塞但保持占有资源不放q不剥夺条件进程已获资源未使用完之前不能被剥夺q环路等待条件进程-资源环形链P0, P1, P2, , Pn452022年7月4日星期一北京交通大学计算机学院 翟高寿3.5 死

22、锁产生及处理策略3.5.1 死锁的基本概念3.5.2 死锁产生的原因3.5.3 死锁产生的必要条件3.5.4 处理死锁的基本方法3.5.5 死锁的预防3.5.6 死锁的检测与解除462022年7月4日星期一北京交通大学计算机学院 翟高寿处理死锁的基本方法q预防死锁设置某些限制前提以破坏产生死锁必要条件q避免死锁资源动态分配过程中，利用某种方法去防止系统进入不安全状态q检测死锁运行过程中通过系统设置的检测机构及时检测死锁的发生，并精确确定相关进程和资源q解除死锁撤销或挂起一些进程以回收资源和再分配472022年7月4日星期一北京交通大学计算机学院 翟高寿3.5 死锁产生及处理策略3.5.1 死锁

23、的基本概念3.5.2 死锁产生的原因3.5.3 死锁产生的必要条件3.5.4 处理死锁的基本方法3.5.5 死锁的预防3.5.6 死锁的检测与解除482022年7月4日星期一北京交通大学计算机学院 翟高寿死锁的预防策略之一q摒弃“请求和保持”条件系统要求所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源和进行一次性分配简单、安全且易于实现资源浪费、进程延迟492022年7月4日星期一北京交通大学计算机学院 翟高寿死锁的预防策略之二q摒弃“不剥夺”条件进程在需要资源时才提出请求，且得不到满足时应释放其已占有资源实现复杂，代价很大（反复地申请与释放资源、进程周转时间延长、系统

24、吞吐量降低、系统开销增加）502022年7月4日星期一北京交通大学计算机学院 翟高寿死锁的预防策略之三q摒弃“环路等待”条件所有资源按类型进行线性排队，所有进程对资源的请求严格按资源序号递增次序提出资源次序的不灵活性（新设备、程序逻辑设计与编程限制及资源浪费）512022年7月4日星期一北京交通大学计算机学院 翟高寿3.5 死锁产生及处理策略3.5.1 死锁的基本概念3.5.2 死锁产生的原因3.5.3 死锁产生的必要条件3.5.4 处理死锁的基本方法3.5.5 死锁的预防3.5.6 死锁的检测与解除522022年7月4日星期一北京交通大学计算机学院 翟高寿资源分配图qG=(PR, E)资源请

25、求边 e = 资源分配边 e = P1P2R1R2P1P2R2R1532022年7月4日星期一北京交通大学计算机学院 翟高寿死锁定理q系统状态S为死锁状态的充要条件是当且仅当该状态下的资源分配图是不可完全化简不可完全化简的P1P2R2R1P1P2R2R1P1P2R2R1542022年7月4日星期一北京交通大学计算机学院 翟高寿死锁检测算法1 令Work = Available IsolatedSet=Pi Allocationi = 0Requesti = 0 2 for all Pi IsolatedSet do begin for all Requesti Work do begin Wo

26、rk = Work + Allocationi ; IsolatedSet = IsolatedSet Pi end end3 deadlock = (IsolatedSet = = P1 , P2 , , Pn);552022年7月4日星期一北京交通大学计算机学院 翟高寿死锁的解除q基本方法剥夺其它进程足够数量资源给死锁进程撤消死锁进程（全部撤销或逐个撤销）q死锁解除策略评价指标为解除死锁所需撤消的进程数目最小撤消死锁进程所付出的代价最小562022年7月4日星期一北京交通大学计算机学院 翟高寿死锁解除策略实例评析SP1(CU1)U1U2UkP2(CU2)Pk(CUk)P1V21V23V2k

27、P3PkP1Vk1Vk2Vkk-1P2Pk-1P2V12V13V1kP3PkP3W123W124W12kP4PkP1W231W234W23kP4PkP1Wkk-11Wkk-12Wkk-1k-2P2Pk-2q两种死锁解除策略评析Cost = AverageCostForCancelProcess KCost = minCostForCancelProcessi572022年7月4日星期一北京交通大学计算机学院 翟高寿3.5 死锁产生及处理策略3.5.1 死锁的基本概念3.5.2 死锁产生的原因3.5.3 死锁产生的必要条件3.5.4 处理死锁的基本方法3.5.5 死锁的预防3.5.6 死锁的检测

28、与解除582022年7月4日星期一北京交通大学计算机学院 翟高寿第三章第三章 处理机调度与死锁处理机调度与死锁3.1 高级、中级与低级调度3.2 调度队列模型3.3 调度方式与算法选择准则3.4 调度算法3.5 死锁产生及处理策略3.6 死锁避免与银行家算法592022年7月4日星期一北京交通大学计算机学院 翟高寿死锁避免q基本思想允许进程动态地申请资源，但系统在进行资源分配之前，应首先就资源分配的安全性进行检查，且仅当确认此次分配不会导致系统进入不安全状态时才可分配，否则予以拒绝602022年7月4日星期一北京交通大学计算机学院 翟高寿死锁避免基本概念q安全状态指系统可按某种进程序列（称之为

29、安全分配序列）来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程均能顺利完成q不安全状态系统无法找到一个安全分配序列的系统状态q死锁与状态安全性之间的关系并非所有不安全状态都是死锁状态当系统进入不安全状态后，便可能陷入死锁只要保证系统处于安全状态，便可避免死锁612022年7月4日星期一北京交通大学计算机学院 翟高寿安全状态及向不安全状态的转换qT0时刻存在安全分配序列 q若在若在T T0 0时刻应进程请求将所剩磁带机中的时刻应进程请求将所剩磁带机中的1 1台台分配给分配给P3，则系统进入不安全状态，则系统进入不安全状态资源名称资源名称 资源总数资源总数可用资源量可用

30、资源量可用资源量可用资源量磁带机1232进程进程最大需求最大需求已分配已分配(尚需尚需)已分配已分配(尚需尚需)P1105（5）5（5）P242（2）2（2）P392（7）3（6）622022年7月4日星期一北京交通大学计算机学院 翟高寿银行家算法之数据结构q可利用资源向量/请求向量mAvailablej=k表示系统现有k个Rj类资源Requestij=k表示进程Pi请求k个Rj类资源q最大需求矩阵/分配矩阵/需求矩阵n,mMaxi,j=k表示进程Pi最多需要k个Rj类资源Allocationi,j=k表示进程Pi已有k个Rj类资源Needi,j=k表示进程Pi尚需k个Rj类资源q工作向量 m

31、 / Finish布尔向量 nWorkj=k表示系统“可”提供k个Rj类资源Finishi 表示进程Pi可否拥有足够资源完成运行632022年7月4日星期一北京交通大学计算机学院 翟高寿银行家算法之主体算法1 进程Pi发出资源请求Requesti2 若非RequestiNeedi，出错返回3 若非Requesti Available，则应使Pi等待并返回4 系统试探性地满足Pi请求，并作以下修改：Available = Available RequestiAllocationi = Allocationi + RequestiNeedi = Needi Requesti5 系统调用安全性算法安

32、全性算法进行资源分配检查，若安全则执行分配，否则恢复试探分配前状态，并使Pi等待642022年7月4日星期一北京交通大学计算机学院 翟高寿银行家算法之安全性子算法1 令Work = Available， Finish=FALSE2 从进程集合中查找一个满足Finishi=FALSE且 Needi = Work 的进程Pi 。若找到，则可假定Pi能获得所需资源并顺利执行，故有：Work = Work + Allocationi Finishi = True 然后重复执行第2步；否则转至第3步执行3 如果Finish=TRUE，则表示系统处于安全状态；否则系统处于不安全状态652022年7月4日星

33、期一北京交通大学计算机学院 翟高寿银行家算法应用举例之一A(待续)q系统资源总量 AvailableA,B,C = 10, 5, 7qT0时刻 AvailableA,B,C = 3, 3, 2q安全分配序列 ? 进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4 3P13 2 2 2 0 0 1 2 2P29 0 2 3 0 2 6 0 0P32 2 2 2 1 1 0 1 1P44 3 3 0 0 2 4 3 1662022年7月4日星期一北京交通大学计算机学院 翟

34、高寿银行家算法应用举例之一B(待续)q系统资源总量 AvailableA,B,C = 10, 5, 7qT0时刻 AvailableA,B,C = 3, 3, 2q安全分配序列 ? 进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4 3P13 2 2 2 0 0 1 2 2 3 3 25 3 2TrueP29 0 2 3 0 2 6 0 0P32 2 2 2 1 1 0 1 1P44 3 3 0 0 2 4 3 1672022年7月4日星期一北京交通大学计算机学院 翟

35、高寿银行家算法应用举例之一C(待续)q系统资源总量 AvailableA,B,C = 10, 5, 7qT0时刻 AvailableA,B,C = 3, 3, 2q安全分配序列 ? 进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4 3P13 2 2 2 0 0 1 2 2 3 3 25 3 2TrueP29 0 2 3 0 2 6 0 0P32 2 2 2 1 1 0 1 1 5 3 27 4 3TrueP44 3 3 0 0 2 4 3 1682022年7月4日星

36、期一北京交通大学计算机学院 翟高寿银行家算法应用举例之一D(待续)q系统资源总量 AvailableA,B,C = 10, 5, 7qT0时刻 AvailableA,B,C = 3, 3, 2q安全分配序列 ? 进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4 3P13 2 2 2 0 0 1 2 2 3 3 25 3 2TrueP29 0 2 3 0 2 6 0 0P32 2 2 2 1 1 0 1 1 5 3 27 4 3TrueP44 3 3 0 0 2 4

37、3 1 7 4 37 4 5True692022年7月4日星期一北京交通大学计算机学院 翟高寿银行家算法应用举例之一E(待续)q系统资源总量 AvailableA,B,C = 10, 5, 7qT0时刻 AvailableA,B,C = 3, 3, 2q安全分配序列 ? 进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4 3 7 4 57 5 5TrueP13 2 2 2 0 0 1 2 2 3 3 25 3 2TrueP29 0 2 3 0 2 6 0 0P32 2

38、 2 2 1 1 0 1 1 5 3 27 4 3TrueP44 3 3 0 0 2 4 3 1 7 4 37 4 5True702022年7月4日星期一北京交通大学计算机学院 翟高寿银行家算法应用举例之一F(待续)q系统资源总量 AvailableA,B,C = 10, 5, 7qT0时刻 AvailableA,B,C = 3, 3, 2q安全分配序列进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4 3 7 4 57 5 5TrueP13 2 2 2 0 0 1

39、2 2 3 3 25 3 2TrueP29 0 2 3 0 2 6 0 0 7 5 5 10 5 7TrueP32 2 2 2 1 1 0 1 1 5 3 27 4 3TrueP44 3 3 0 0 2 4 3 1 7 4 37 4 5True712022年7月4日星期一北京交通大学计算机学院 翟高寿银行家算法应用举例之二A(待续)q进程P1发出资源请求Request1(1,0,2)2, 3, 0q安全分配序列 ? 进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4

40、3P13 2 22+1 0+0 0+2 1-1 2-0 2-2P29 0 2 3 0 2 6 0 0P32 2 2 2 1 1 0 1 1P44 3 3 0 0 2 4 3 1722022年7月4日星期一北京交通大学计算机学院 翟高寿银行家算法应用举例之二B(待续)q进程P1发出资源请求Request1(1,0,2)2, 3, 0q安全分配序列 ? 进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4 3P13 2 22+1 0+0 0+2 1-1 2-0 2-22 3

41、 05 3 2TrueP29 0 2 3 0 2 6 0 0P32 2 2 2 1 1 0 1 1P44 3 3 0 0 2 4 3 1732022年7月4日星期一北京交通大学计算机学院 翟高寿银行家算法应用举例之二C(待续)q进程P1发出资源请求Request1(1,0,2)2, 3, 0q安全分配序列 ? 进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4 3P13 2 22+1 0+0 0+2 1-1 2-0 2-22 3 05 3 2TrueP29 0 2 3

42、 0 2 6 0 0P32 2 2 2 1 1 0 1 1 5 3 27 4 3TrueP44 3 3 0 0 2 4 3 1742022年7月4日星期一北京交通大学计算机学院 翟高寿银行家算法应用举例之二D(待续)q进程P1发出资源请求Request1(1,0,2)2, 3, 0q安全分配序列 ? 进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4 3P13 2 22+1 0+0 0+2 1-1 2-0 2-22 3 05 3 2TrueP29 0 2 3 0 2

43、6 0 0P32 2 2 2 1 1 0 1 1 5 3 27 4 3TrueP44 3 3 0 0 2 4 3 1 7 4 37 4 5True752022年7月4日星期一北京交通大学计算机学院 翟高寿银行家算法应用举例之二E(待续)q进程P1发出资源请求Request1(1,0,2)2, 3, 0q安全分配序列 ? 进程进程MAXA B CAllocationA B CNeedA B CWorkA B CAllocation+ WorkA B CFinishP07 5 3 0 1 0 7 4 3 7 4 57 5 5TrueP13 2 22+1 0+0 0+2 1-1 2-0 2-22 3 05 3 2TrueP29 0 2 3 0 2 6 0 0P32 2 2 2 1 1 0 1 1 5 3 27 4 3TrueP44 3 3 0 0 2 4 3 1 7 4 37 4