第三章处理机调度与死锁2ppt课件

1、第三章第三章 处理机调处理机调度与死锁度与死锁内容提要内容提要处理机调度及调度算法处理机调度及调度算法产生死锁的原因和必要条件产生死锁的原因和必要条件预防死锁的方法，死锁的检测与解除预防死锁的方法，死锁的检测与解除 银行家算法银行家算法第三章第三章 处理机调度与死锁处理机调度与死锁 处理机调度：按一定方法动态地把处理处理机调度：按一定方法动态地把处理机分配给就绪队列中的一个进程机分配给就绪队列中的一个进程WHAT：按什么原则分配：按什么原则分配CPU进程调度算法进程调度算法WHEN：何时分配：何时分配CPU 进程调度的时机进程调度的时机 HOW：如何分配：如何分配CPU CPU调度过程进程调度

2、过程进程 的上下文切换）的上下文切换）第三章第三章 处理机调度与死锁处理机调度与死锁3.1 3.1 处理机调度的基本概念处理机调度的基本概念 1)1)调度类型调度类型 高级调度：即作业调度，选择后备作业进入高级调度：即作业调度，选择后备作业进入内存，为其建立进程内存，为其建立进程, ,分配资源并排在就绪分配资源并排在就绪队列。队列。 中级调度：即对换调度，将暂不运行的进程中级调度：即对换调度，将暂不运行的进程调到外存等待，从而提高内存利用率和系调到外存等待，从而提高内存利用率和系统吞吐量统吞吐量 低级调度：即进程调度，决定哪个进程可以低级调度：即进程调度，决定哪个进程可以占用占用CPUCPU，

3、进入运行状态。，进入运行状态。输入程序输入程序就就绪绪阻阻塞塞就就绪绪运运行行完完成成阻阻塞塞后后备备外存外存中级调度中级调度对换对换低级调度低级调度作业调度作业调度2)2)进程调度方式进程调度方式 调度方式是指但某一个进程正在处理机上执行调度方式是指但某一个进程正在处理机上执行时如果有时如果有个更重要更紧迫的进程需要处理此时应该如何分配处个更重要更紧迫的进程需要处理此时应该如何分配处理机。理机。非抢占方式非抢占方式 进程一旦被调度执行，除非进程完成或发生某事进程一旦被调度执行，除非进程完成或发生某事件被阻塞，否则不允许其他进程抢夺其执行权。件被阻塞，否则不允许其他进程抢夺其执行权。抢占方式抢

4、占方式 允许按某种策略原则剥夺正在执行的进程的执允许按某种策略原则剥夺正在执行的进程的执行权行权 -优先权原则优先权原则-短作业短作业( (进程进程) )优先原则优先原则-时间片原则时间片原则3)3)调度类型与调度类型与O.SO.S类型的关系类型的关系多道批处理系统：存在作业调度、进程调度多道批处理系统：存在作业调度、进程调度分时分时/ /实时系统：只有进程调度实时系统：只有进程调度 共同点：均存在进程调度分配共同点：均存在进程调度分配CPUCPU）4) 4) 调度队列模型调度队列模型( (三种三种) )调度队列模型调度队列模型n 仅有进程调度的调度队列模型仅有进程调度的调度队列模型就就 绪绪

5、队队 列列阻阻 塞塞队队列列进程调度进程调度CPU进程完成进程完成等待事件等待事件交互用户交互用户事事件件出出现现时间片完时间片完进程调度进程调度CPU进程完成进程完成时间片完时间片完就就 绪绪队队列列12等待事件等待事件等待事件等待事件等待事件等待事件n12n事件事件 呈现呈现事件事件 呈现呈现事件事件 呈现呈现后后备备 队队列列作业作业调度调度与上一模型的主要区别：就绪队列的形式；与上一模型的主要区别：就绪队列的形式； 设置多个阻塞队列设置多个阻塞队列阻阻队队列列塞塞2 2阻阻队队列列塞塞n n阻阻队队列列塞塞1 1n具有高级和低级的调度队列模型具有高级和低级的调度队列模型n同时具有三级调

6、度的调度队列模型同时具有三级调度的调度队列模型就绪队列就绪队列进程调度进程调度就绪，挂起队列就绪，挂起队列中级调度中级调度阻塞，挂起队列阻塞，挂起队列阻塞队列阻塞队列等待事件等待事件进程完成进程完成时间片完时间片完作业调度作业调度交互型作业交互型作业后备队列后备队列批量作业批量作业挂起挂起事件出现事件出现事事件件出出现现事件出现事件出现CPU5) 5) 调度性能评价调度性能评价 作业调度算法的评价因素作业调度算法的评价因素 CPUCPU利用率：越高越好利用率：越高越好 吞吐量：单位时间内吞吐量：单位时间内CPUCPU完成作业的数量完成作业的数量 周转时间：通常与带权周转时间一起作为评价批周转时

7、间：通常与带权周转时间一起作为评价批处理系统的性能指标，定义如下：处理系统的性能指标，定义如下：,1,2,.,/,1,2,.,ioisiiiriTttinWT tin n个作业的平均周转时间T和平均周转系数W分别为1111niniTTinWW inn 对于每个用户来说，总是希望作业提交后立即执行，这样周转时间等于执行时间；而对于一个计算机系统来说，不可能满足每个用户的这种要求，只能使系统的平均周转时间最短。3.2 3.2 调度算法调度算法l 先来先服务调度算法先来先服务调度算法l 短作业进程优先调度算法短作业进程优先调度算法l 高优先权者优先调度算法高优先权者优先调度算法l 时间片轮转调度算法

8、时间片轮转调度算法l 多队列反馈轮转调度算法多队列反馈轮转调度算法l 实时调度算法实时调度算法相关术语相关术语n调度算法：根据系统的资源分配策略所规定的资源调度算法：根据系统的资源分配策略所规定的资源n 分配算法分配算法n几个术语几个术语n 到达时间、服务时间、开始时间到达时间、服务时间、开始时间n 完成时间、等待时间完成时间、等待时间n 周转时间：完成时间周转时间：完成时间-到达时间到达时间n 带权周转时间：周转时间带权周转时间：周转时间/服务时间服务时间1 1先来先服务调度算法先来先服务调度算法战略：先进入后备队列就绪队列的作业战略：先进入后备队列就绪队列的作业进进 程先被调度程先被调度优

9、点：算法简单易实现优点：算法简单易实现缺点：不分轻重缓急，对短作业进程不利缺点：不分轻重缓急，对短作业进程不利2 2短作业进程优先调度算法短作业进程优先调度算法战略：启动要求运行时间最短的作业。战略：启动要求运行时间最短的作业。优点：有效降低作业平均等待时间提高系统的优点：有效降低作业平均等待时间提高系统的吞吞 吐量吐量缺点：长作业进程可能长期得不到服务缺点：长作业进程可能长期得不到服务进程名进程名到达时到达时间间服务时服务时间间开始时开始时间间完成时完成时间间周转时周转时间间带权周带权周转时间转时间平均平均04A13B25C32D44E044476例：先来先服务算法例：先来先服务算法FCFS

10、） 712101214111418141225.53.592.8A A A A B B B C C C C C D D E E E E05101518t进程名进程名到达时到达时间间服务时服务时间间开始时开始时间间完成时完成时间间周转时周转时间间带权周带权周转时间转时间平均平均04A13B25C32D44E0441例：短作业例：短作业/短进程优先短进程优先SJF/SPF）4633/26988/391399/413181616/540/52.1A A A AB B BC C C C CD DE E E E05101518t3 3高优先权者优先调度算法高优先权者优先调度算法 优先权：反映作业进程重要

11、性和调度级别的权优先权：反映作业进程重要性和调度级别的权值，又称优先数。通常分为：值，又称优先数。通常分为：静态优先数：进程创建时确定运行过程中保持不变。静态优先数：进程创建时确定运行过程中保持不变。一般根据进程的类型，资源需求情况，估计的运一般根据进程的类型，资源需求情况，估计的运行时间等因素确定。一般用一整数进行表示如行时间等因素确定。一般用一整数进行表示如0 0至至3232）动态优先数：创建进程时确定一个优先级，进程运动态优先数：创建进程时确定一个优先级，进程运行过程中可以根据情况的变化调整优先级，调整行过程中可以根据情况的变化调整优先级，调整一般是根据进程占用的一般是根据进程占用的CP

12、UCPU的时间长短、进程等待的时间长短、进程等待CPUCPU时间长短来进行如高响应比优先）。时间长短来进行如高响应比优先）。 调度类型非抢占式优先权调度：处理机一旦分配给就绪队列中优先权最高的进程后，该进程就一直运行下去直到自动放弃或完成，这时才可把处理机分配给另一优先级最高的进程。抢占式优先权调度：进程在运行时一旦出现了另一个优先级更高的进程，调度程序就停止该进程而把处理机分配给新出现的高优先权进程。进程进程名名到达到达时间时间服务服务时间时间静态静态优先优先权权开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间平均平均例：静态优先权，非抢占式例：静态优先权，非抢占式1

13、为高优先权）为高优先权）04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考虑一下抢占式，情况如何？考虑一下抢占式，情况如何？ 高响应比优先调度算法高响应比优先调度算法HRPHRP）：优先调度响）：优先调度响应比高的作业应比高的作业 时间务时间响应时间权务时间务时间等等待待+ +要要求求服服优优先先= = =要要求求服服要要求求服服对短作业有利对短作业有利是先来先服务是先来先服务对长作业有利对长作业有利缺点：要进行响应比计算，增加了系统开销缺点：要进行响应比计算，增加了系统开销小结：小结：等待时间相同的作业，则要求服

14、务的时间愈短，等待时间相同的作业，则要求服务的时间愈短，其优先权愈高其优先权愈高要求服务的时间相同的作业，则等待时间愈长，要求服务的时间相同的作业，则等待时间愈长，其优先权愈高其优先权愈高长作业，优先权随等待时间的增加而提高，其等长作业，优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高，待时间足够长时，其优先权便可升到很高， 从从而也可获得处理机而也可获得处理机4 4时间片轮转调度算法适合于分时系统）时间片轮转调度算法适合于分时系统） 战略战略 系统将所有的就绪进程按先来先服务的原则排系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把成一个队列，每次调度时

15、，把CPUCPU分配给队首进程，分配给队首进程，并令其执行一个时间片并令其执行一个时间片 当执行的时间片用完时，由一个计时器发出时当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便停止该进程的执行，并钟中断请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配给就将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首绪队列中新的队首 优、缺点：简单易实现，但不分轻重缓急优、缺点：简单易实现，但不分轻重缓急 关键：时间片大小的选择关键：时间片大小的选择例：基于时间片的轮转调度算法例：基于时间片的轮转调度算法进程名进程名到达时到达时间间服务时服务时间间开始时开始

16、时间间完成时完成时间间周转时周转时间间带权周带权周转时间转时间平均平均A B C D E A B C D E A B C E A C E C05101518t04A03B05C02D04E012349121517181515/41111/31616/566/21313/412.22.12若到达时间若到达时间为为0 0、1 1、2 2、3 3、4 4，又如，又如何？何？5 5多级队列反馈轮转调度算法多级队列反馈轮转调度算法 战略：将时间片与优先级调度相结合。战略：将时间片与优先级调度相结合。 -设置多个就绪队列，分别赋予不同的优先级。设置多个就绪队列，分别赋予不同的优先级。 优先级越低则时间片越

17、长优先级越低则时间片越长 -新进程进入内存后，先投入第一队列的末尾，新进程进入内存后，先投入第一队列的末尾， 按按FCFSFCFS算法调度；若按第一队列一个时间片算法调度；若按第一队列一个时间片未能未能 执行完，则降低投入到第二队列的末尾，同执行完，则降低投入到第二队列的末尾，同样按样按 FCFSFCFS算法调度；如此下去，降低到最后的队算法调度；如此下去，降低到最后的队列，列， 则按则按“时间片轮转算法调度直到完成时间片轮转算法调度直到完成 -仅当较高优先级的队列为空，才调度较低优仅当较高优先级的队列为空，才调度较低优先级先级 的队列中的进程执行。如果进程执行时有新的队列中的进程执行。如果进

18、程执行时有新进程进程 进入较高优先级的队列，则抢先执行新进程，进入较高优先级的队列，则抢先执行新进程，并并 把被抢先的进程投入原队列的末尾把被抢先的进程投入原队列的末尾就绪队列就绪队列1 1就绪队列就绪队列2 2就绪队列就绪队列3 3就绪队列就绪队列n nS1S2S3至至CPU至至CPU至至CPU至至CPU( (时间片：时间片：S1 S2 S3) )高高低低优先级优先级时间片时间片小小大大Sn按按FIFO原则原则排队等待调排队等待调度度尚未完成转入第二尚未完成转入第二队列的末尾，按队列的末尾，按FIFO原则等待调原则等待调度度采取按时间片轮采取按时间片轮转的方式运行转的方式运行因等待而放弃因等

19、待而放弃CPU后，进入阻塞队列，后，进入阻塞队列，一旦等待的事件发一旦等待的事件发生，则回到原来的生，则回到原来的就绪队列就绪队列调度算法性能分析调度算法性能分析设有四个作业，其提交时刻、执行时间如下表所示，分别采用FCFS、SJF、FPF调度方法，计算平均周转时间T和平均周转系数W。作业号提交时刻运行时间18.002.0028.500.5039.000.1049.500.20先来先服务调度算法： 顺序为1 2 3 4，平均周转时间和平均周转系数的计算结果如下表所示： 作业 提交时间 执行时间开始时间完成时间周转时间周转系数 1 8.00 2.00 2 8.50 0.50 3 9.00 0.1

20、0 4 9.50 0.208.0010.002.001.0010.0010.502.004.0010.5010.601.6016.0010.6010.801.306.506.9027.50 平均周转时间T1.725小时，平均周转系数W6.875 最短作业优先调度算法：最短作业优先调度算法：由于在由于在8.008.00开始执行作业，当时仅有开始执行作业，当时仅有1 1，而作业，而作业2 2，3 3，4 4尚未到达，故作业尚未到达，故作业1 1是最短作业。作业是最短作业。作业1 1执行执行完成后是完成后是10.0010.00，此时作业，此时作业2 2，3 3，4 4均已经到达，均已经到达，故选最短

21、作业故选最短作业3 3，然后是，然后是4 4，2 2。所以顺序为。所以顺序为1,3,4,21,3,4,2。平均周转时间和平均周转系数的计算。平均周转时间和平均周转系数的计算结果如下表所示：结果如下表所示： 作业 提交时间执行时间开始时间 完成时间 周转时间 周转系数 1 8.00 2.00 2 8.50 0.50 3 9.00 0.10 4 9.50 0.208.0010.002.001.0010.0010.101.1011.0010.1010.300.804.0010.3010.802.304.606.2020.60 平均周转时间T1.55小时，平均周转系数W5.15响应比高者优先算法：响应

22、比高者优先算法：在作业在作业1 1执行完成，计算作业执行完成，计算作业2 2，3 3，4 4的响应比分别的响应比分别为：为：4 4，1111，3.53.5，因此作业，因此作业1 1执行完成后选中作业执行完成后选中作业3 3完成。完成。执行顺序执行顺序为为1 1，3 3，2 2，4 4。按此算法求得的平均周转时间和平。按此算法求得的平均周转时间和平均周转系均周转系数如下表所示：数如下表所示： 作业 提交时间执行时间开始时间 完成时间 周转时间 周转系数 1 8.00 2.00 2 8.50 0.50 3 9.00 0.10 4 9.50 0.208.0010.002.001.0010.0010.

23、101.1011.0010.1010.602.104.2010.6010.801.306.506.5022.70 平均周转时间T1.625小时，平均周转系数W5.675总结：就其平均周转时间和平均周转系数来说，最短作业优先算法最小，先来先服务算法最大，响应比高者优先算法居中。6 6两种常见的实时调度算法两种常见的实时调度算法最早截止时间优先算法最早截止时间优先算法(EDF)(EDF) 选择就绪队列中开始截止时间最早的实时任务选择就绪队列中开始截止时间最早的实时任务对应的进程先执行一般非抢占方式）对应的进程先执行一般非抢占方式）最低松弛度优先算法最低松弛度优先算法(LLF)(LLF)松弛度松弛度

24、= =规定完成时间规定完成时间- -所需执行时间所需执行时间- -当前时间当前时间选择松弛度最小的实时任务对应的就绪进程选择松弛度最小的实时任务对应的就绪进程先执行，一般采用抢占方式，当某进程松弛度为先执行，一般采用抢占方式，当某进程松弛度为零时，必须立即抢占执行。零时，必须立即抢占执行。EDF例：例：进程到达时刻执行所需时间 开始截止时间P1042P22310P3324P4537t=0只有P1进程，P1执行4个单位时间t=4P2、P3均到达，P3截止时间早于P2截止时间 P3执行两个单位时间t=6P2和P4就绪，P4截止时间早于P2，P4执行t=9只剩P2，P2执行LLFLLF例：两个周期性

25、实时任务例：两个周期性实时任务A A和和B B， A A：每：每20ms20ms执行一次，每次执行时间为执行一次，每次执行时间为10ms10ms B B：每：每50ms50ms执行一次，每次执行时间为执行一次，每次执行时间为25ms25mst (ms)0102030405060708090100110120A1A2A3A4A5A6B1B2调度调度（执行）（执行）抢占抢占抢占抢占松弛度松弛度t (ms)0102030405060708090100110120A1(10)A2(10)A3(10)A4(10)A5(10)B1(20)B2(10)B1(5)B2(15)A1=10未进入未进入A2A2=0

26、A3=10 A3=5未进入未进入A4A4=0A5=10B1=25 B1=15B1=15B1=5未进入未进入B2B2=20 B2=20 B2=10A1B1A2B1A3B2A4B23.3 3.3 死锁死锁 死锁：多个进程竞争系统资源，造成一种僵死锁：多个进程竞争系统资源，造成一种僵局，使得这些进程在无外力的作用下，均局，使得这些进程在无外力的作用下，均无法继续向前推进。无法继续向前推进。 讨论问题讨论问题死锁的产生原因死锁的产生原因产生死锁的必要条件产生死锁的必要条件死锁的预防死锁的预防死锁的避免死锁的避免死锁的检测和解除死锁的检测和解除1 1产生死锁的原因产生死锁的原因死锁主要是由两个或多个进程

27、对资源需求的冲突引死锁主要是由两个或多个进程对资源需求的冲突引起的起的进程A请求资源R2进程B请求资源R1请求资源R1请求资源R2R1分配R2分配（阻塞）（阻塞）死锁产生的原因： 资源竞争 进程推进顺序不当资源竞争引起死锁情况独占资源分为可剥夺式和不可剥夺式，死锁与不 可剥夺式有关。P1P2R1Rn进程的推进顺序不当导致死锁请求打印机请求读卡机释放打印机释放读卡机进程P1请求读卡机请求打印机释放读卡机释放打印机进程P2打印机读卡机Req(R1)Req(R2)Rel(R1)Rel(R2)Req(R2)Req(R1)Rel(R2)Rel(R1)进程的推进顺序非法将导致死锁续）P2Rel(R1)P2

28、Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2) 进程推进顺序合法进程的推进顺序非法将导致死锁续）P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2) 进程推进顺序合法进程的推进顺序非法将导致死锁续）P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2) 进程推进顺序合法进程的推进顺序非法将导致死锁续）P2Rel(R1)P2Rel(R2)P2

29、Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2) 进程推进顺序不合法D:不安全区2 2死锁产生的四个必要条件死锁产生的四个必要条件n 互斥条件n 请求和保持条件n 不剥夺条件n 环路等待条件n上述条件是产生死锁的必有条件，并非充分条件。如n果破坏上述4个条件之一，就可以预防死锁的产生。3.4 3.4 死锁的处理死锁的处理用于处理死锁的主要方法：预防死锁：通过设置限制条件破坏死锁的四个必要条件 中的一个或几个来防止死锁发生避免死锁：资源分配过程中用某种方法防止系统进入不 安全状态来防止死锁发生检测死锁：通过系统的检测机构来检测死锁发生解除死

30、锁：通过撤销或挂起一些进程恢复系统正常运行1 1预防死锁预防死锁战略：从破坏死锁的必要条件入手战略：从破坏死锁的必要条件入手, ,破坏摒弃四破坏摒弃四 个必要条件之一个必要条件之一 摒弃摒弃“互斥条件互斥条件” 由设备的固有属性决定，只能通过某种技术由设备的固有属性决定，只能通过某种技术加以利用，但一般来说这种方法不是很有效。加以利用，但一般来说这种方法不是很有效。 摒弃摒弃“请求和保持条件请求和保持条件” 进程创建时，一次性将全部所需资源均分配进程创建时，一次性将全部所需资源均分配给进程，其在运行过程中不会产生新的请求。给进程，其在运行过程中不会产生新的请求。 摒弃摒弃“不剥夺条件不剥夺条件

31、” 进程因请求新资源而得不到满足，造进程因请求新资源而得不到满足，造成阻塞时，暂时释放已占有的所有资源成阻塞时，暂时释放已占有的所有资源剥夺）。剥夺）。 摒弃摒弃“环路等待条件环路等待条件” 按序分配资源。系统依据一定的策略按序分配资源。系统依据一定的策略给资源由低到高编号，进程必须按从小到给资源由低到高编号，进程必须按从小到大顺序申请资源，并规定进程占有的资源大顺序申请资源，并规定进程占有的资源号小于申请的资源号才能得到申请资源。号小于申请的资源号才能得到申请资源。使之资源分配图不会形成环路。使之资源分配图不会形成环路。2 2避免死锁避免死锁 避免死锁：用动态方法判断资源的使用情避免死锁：用

32、动态方法判断资源的使用情况和系统状态，在分配资源之前，系统将况和系统状态，在分配资源之前，系统将判断如果满足进程的请求是否可能会发生判断如果满足进程的请求是否可能会发生死锁。如果会，就不分配资源，从而避免死锁。如果会，就不分配资源，从而避免死锁。系统状态分为安全状态和不安全状死锁。系统状态分为安全状态和不安全状态：态：安全状态：存在一个状态序列能够使所有安全状态：存在一个状态序列能够使所有的进程均得到它们所需的资源并执行结束。的进程均得到它们所需的资源并执行结束。不安全状态：如果不存在一个状态序列能不安全状态：如果不存在一个状态序列能够使所有的进程均执行结束，即为不安全够使所有的进程均执行结束

33、，即为不安全状态。状态。安全状态示例：安全状态示例： 假定系统有三个进程P1、P2和P3，共有12台磁带机。T0时刻资源分配状况为图1，T1时刻P3又申请到了一台磁带机其资源分配状况如图2：进程最大需求已分配可用P1P2P310495223进程最大需求已分配可用P1P2P310495232安安全全不不安安全全避免死锁的方法：银行家算法避免死锁的方法：银行家算法银行家算法银行家算法( (由由DijkstraDijkstra提出提出) )：在资源分配时进：在资源分配时进行判断，分析系统状态是否安全。行判断，分析系统状态是否安全。 基本思想：将系统资源比作贷款，申请资源的基本思想：将系统资源比作贷款

34、，申请资源的进程比作借款人，操作系统比作银行家。银行家进程比作借款人，操作系统比作银行家。银行家不可能满足所有借款人所要求借款的总额，所以不可能满足所有借款人所要求借款的总额，所以当某借款人提出借款时，银行家必须判断如果将当某借款人提出借款时，银行家必须判断如果将款借出，会不会导致资金周转不灵。若会，则不款借出，会不会导致资金周转不灵。若会，则不借；否则，就借。借；否则，就借。n单项资源的银行家算法n假设系统中有10台磁带机，有3个进程A、B、C对磁带机占有及需求情况如下表所示。系统剩余磁带机2台。进程名已分配数尚需申请数最大需求数A224B336C358此时，若A申请1台，或B申请1台，或C

35、申请2台分配不分配不分配银行家算法银行家算法n银行家算法过程：n对每一个资源申请进行检查，看如果满足该申请是否会导致不安全状态。若是，则不满足该申请，否则就满足。检查状态是否安全的方法是看是否有足够的资源满足一个距最大需求最近的进程。如果可以，则认为这些资源是可以收回的，然后检查下一个距最大需求最近的进程，如此反复下去。如果所有资源最终都被收回，则该状态是安全的，最初的申请可以满足。银行家算法银行家算法n单项资源的银行家算法n系统中某一资源总量为10，4个进程申请，初始状态如下图所示。进程名已有数目最大需求尚需数目a044b055c066d077剩余资源10银行家算法银行家算法n单项资源的银行

36、家算法n某一时刻，系统状态如下图所示。进程名已有数目最大需求尚需数目a143b253c165d275剩余资源4先满足进程a银行家算法银行家算法n单项资源的银行家算法n满足进程a后，系统状态如下图所示：进程名已有数目最大需求尚需数目a-b253c165d275剩余资源5状态是安全的银行家算法银行家算法n单项资源的银行家算法n但如果先满足进程c后，系统状态如下图所示。进程名已有数目最大需求尚需数目a143b253c561d275剩余资源0状态是不安全的银行家算法银行家算法n多项资源的银行家算法：设置资源的已分配矩阵allocation、尚需资源矩阵need以及可分配资源向量available。n如

37、果某一进程对某一种资源提出申请，就假定预先分配给它，然后修改已分配矩阵allocation、尚需资源矩阵need和向量available；n在矩阵need中找出一行，使该行向量小于等于available。若不存在这样的向量，就说明没有进程能够获得全部资源运行到完成，将会引起死锁；n假设被选中的那一行的进程获得资源并运行结束，把它占有的资源全部加入向量available；n反复(2)(3)步骤，直到下述情况之一出现：或者所有进程都完成，则系统是安全的，可以分配；或者发生死锁，则预先分配是不安全的，应不予分配。银行家算法银行家算法n多项资源的银行家算法n假设系统中有4类资源：打印机5个、手写板7个、扫描仪8个和读卡器9个，分别表示为R1，R2，R3，R4；共有5个进程a，b，c，d，e，某时刻系统状态如下所