《操作系统课件：第3章 处理机的调度和死锁》由会员分享，可在线阅读，更多相关《操作系统课件：第3章 处理机的调度和死锁（55页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章处理机的调度和死锁处理机的调度和死锁处理机调度与死锁处理机调度与死锁3.1 3.1 3.1 3.1 处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念v3.13.1高、中、低三级调度高、中、低三级调度 v1 1、高级调度（作业调度、长程调度、接纳调度）、高级调度（作业调度、长程调度、接纳调度）将外存作业调入内存，创建将外存作业调入内存，创建PCBPCB等，插入就绪等，插入就绪队列。队列。一般用于批处理系统，分一般用于批处理系统，分/ /实时系统一般直接实时系统一般直接入内存，无此环节。入内存，无此环节。调度特性调度特性1.1.接纳作业数（内存驻留数）接
2、纳作业数（内存驻留数）太多太多周转时间周转时间T T长长太少太少系统效率低系统效率低2.2.接纳策略：即采用何种调度算法：接纳策略：即采用何种调度算法：FCFSFCFS、短、短作业优先等作业优先等处理机调度与死锁处理机调度与死锁处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念（2 2 2 2）v2 2、低级调度（进程调度，短程调度）、低级调度（进程调度，短程调度）v主要是由分派程序（主要是由分派程序（DispatcherDispatcher）分派处理机。）分派处理机。1.1.非抢占方式：非抢占方式：简单，实时性差简单，实时性差 ( (如如win31)win31)
3、2.2.抢占方式抢占方式（1 1）时间片原则）时间片原则（2 2）优先权原则）优先权原则（3 3）短作业优先原则。）短作业优先原则。 vv3 3 3 3、中级调度（中程）、中级调度（中程）、中级调度（中程）、中级调度（中程）vv为提高系统吞吐量和内存利用率而引入的一内为提高系统吞吐量和内存利用率而引入的一内为提高系统吞吐量和内存利用率而引入的一内为提高系统吞吐量和内存利用率而引入的一内-外存外存外存外存对换功能（换出时，进程为挂起或就绪驻外状态）对换功能（换出时，进程为挂起或就绪驻外状态）对换功能（换出时，进程为挂起或就绪驻外状态）对换功能（换出时，进程为挂起或就绪驻外状态） v运行频率：低运
4、行频率：低 中中 高高。处理机调度与死锁处理机调度与死锁问？问？问？问？v三种调度被引发的事件？三种调度被引发的事件？v事件的表现方式？事件的表现方式？处理机调度与死锁处理机调度与死锁3.1.23.1.23.1.23.1.2调度的队列模型调度的队列模型调度的队列模型调度的队列模型v一、仅有进程调度的队列模型一、仅有进程调度的队列模型就绪队列就绪队列CPU阻塞队列阻塞队列交互用户交互用户时间片完时间片完进程调度进程调度进程完成进程完成等待事件等待事件事件出现事件出现处理机调度与死锁处理机调度与死锁3.1.23.1.23.1.23.1.2调度的队列模型调度的队列模型调度的队列模型调度的队列模型v二
5、、具有高二、具有高/ /低级模型低级模型就绪队列就绪队列CPU阻塞队列阻塞队列时间片完时间片完进程调度进程调度进程进程完成完成等待事件等待事件1事件事件1出现出现后备队列后备队列阻塞队列阻塞队列等待事件等待事件2事件事件2出现出现作业调度作业调度处理机调度与死锁处理机调度与死锁三、具有三级调度三、具有三级调度三、具有三级调度三、具有三级调度就绪队列就绪队列CPU就绪、挂起队列就绪、挂起队列时间片完时间片完进程调度进程调度进程进程完成完成后备队列后备队列阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作业调度阻塞队列阻塞队列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交
6、互型作业处理机调度与死锁处理机调度与死锁3.1.3.1.3.1.3.1.3 3 3 3选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 v一、面向用户的准则一、面向用户的准则1 1周转时间短（常用于批处理系统）周转时间短（常用于批处理系统）概念：作业从提交概念：作业从提交 完成的时间完成的时间. .分为：分为：（1 1）驻外等待调度时间）驻外等待调度时间（2 2）驻内等待调度时间）驻内等待调度时间（3 3）执行时间）执行时间（4 4）阻塞时间）阻塞时间处理机调度与死锁处理机调度与死锁v一、面向用户的准则一、面向用户的准则平均周转时
7、间平均周转时间 平均带权平均带权 可见带权可见带权w w越小越好越小越好,Ts,Ts为实际服务时间。为实际服务时间。3.1.3.1.3.1.3.1.3 3 3 3选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 处理机调度与死锁处理机调度与死锁v一、面向用户的准则一、面向用户的准则2 2响应时间快：（对交互性作业）响应时间快：（对交互性作业）概念：键盘提交请求到首次响应时间概念：键盘提交请求到首次响应时间（1 1）输入传送时间）输入传送时间（2 2）处理时间）处理时间（3 3）响应传送时间）响应传送时间3 3截止时间的保证（特别于
8、实时系统）截止时间的保证（特别于实时系统）4 4优先权准则：（即需要抢占调度）优先权准则：（即需要抢占调度）3.1.3.1.3.1.3.1.3 3 3 3选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 处理机调度与死锁处理机调度与死锁v二、面向系统的准则二、面向系统的准则1 1吞吐量高（特别于批处理）：单位时间完成作吞吐量高（特别于批处理）：单位时间完成作业数业数2 2处理机利用率好：（因处理机利用率好：（因CPUCPU贵，特别于大中型多贵，特别于大中型多用户系统）用户系统）3 3各类资源的平衡利用。（？折算标准）各类资源的平衡
9、利用。（？折算标准）3.1.3.1.3.1.3.1.3 3 3 3选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 处理机调度与死锁处理机调度与死锁3.23.23.23.2调度算法调度算法调度算法调度算法是一个资源分配问题是一个资源分配问题是一个资源分配问题是一个资源分配问题 v3.2.13.2.1先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法 1.FCFS1.FCFS特点：简单，有利于长作业特点：简单，有利于长作业 即即CPUCPU繁忙性作业繁忙性作业2.2.短作业进程优先调度算法：短作业进程优先调
10、度算法：SJ(P)FSJ(P)F提高了平均周转时间和平均带权周转时间（从而提提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）高了系统吞吐量）特点：对长作业不利，有可能得不到服务（饥饿）特点：对长作业不利，有可能得不到服务（饥饿）估计时间不易确定估计时间不易确定处理机调度与死锁处理机调度与死锁 例例例例进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99处理机调度与死锁处理机调度与死锁图图图图3.4FCFS3.4FCFS3.4FCFS3.4FCFS和和和和SJFSJFS
11、JFSJF比较比较比较比较进程名进程名 A B C D E平均平均到达时间到达时间 0 1 2 3 4服务时间服务时间 4 3 5 2 4FCFS完成时间完成时间 4 7 12 14 18周转时间周转时间 4 6 10 11 149带权周转时间带权周转时间 1 2 2 5.5 3.52.8SJF完成时间完成时间 4 9 18 6 13周转时间周转时间 4 8 16 3 98带权周转时间带权周转时间 1 2.67 3.1 1.5 2.252.1处理机调度与死锁处理机调度与死锁3.2.23.2.23.2.23.2.2高优先权优先调度算法高优先权优先调度算法高优先权优先调度算法高优先权优先调度算法v
12、1.1.优先权调度算法类型优先权调度算法类型非抢占式优先权算法非抢占式优先权算法抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。v2.2.优先权类型：优先权类型：1 1静态优先权：静态优先权：进程优先权在整个运行期不变。进程优先权在整个运行期不变。确定优先权依据确定优先权依据（1 1）进程类型）进程类型（2 2）进程对资源的需求；）进程对资源的需求；（3 3）根据用户需求。）根据用户需求。特点：简单，但低优先权作业可能长期不被特点：简单，但低优先权作业可能长期不被调度。调度。处理机调度与死锁处理机调度与死锁3.2.23.2.23.2.23.2.2高优先权优先调度算法高优先权优先调度
13、算法高优先权优先调度算法高优先权优先调度算法(2)(2)(2)(2)v2 2动态优先权：动态优先权：如：优先权随执行时间而下降，随等待时间而升高。如：优先权随执行时间而下降，随等待时间而升高。响应比响应比RpRp= =（等待时间服务时间）（等待时间服务时间）/ /服务时间服务时间 作为优作为优先权先权优点：长短兼顾优点：长短兼顾 缺点：需计算缺点：需计算RpRpv3.3.高响应比优先算法：高响应比优先算法：特点：特点：响应比响应比RpRp= =（tw+tstw+ts）/ /tsts（1 1）短作业）短作业R RP P大。大。（2 2）tsts（要求服务时间）相同的进程间相当于（要求服务时间）相
14、同的进程间相当于FCFSFCFS。（3 3）长作业等待一段时间仍能得到服务。）长作业等待一段时间仍能得到服务。处理机调度与死锁处理机调度与死锁3.2.33.2.33.2.33.2.3基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法v1.1.时间片轮转时间片轮转时间片大小的确定时间片大小的确定太大：退化为太大：退化为FCFSFCFS；太小：系统开销过大太小：系统开销过大系统对响应时间的要求；系统对响应时间的要求；T=T=nqnq就绪队列中进程的数目；就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用命令）系统的处理能力：（应保证一个
15、时间片处理完常用命令）处理机调度与死锁处理机调度与死锁3.2.33.2.33.2.33.2.3基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法v2.2.多级反馈队列调度多级反馈队列调度特点：长、短作业兼顾，有较好的响应时间特点：长、短作业兼顾，有较好的响应时间（1 1）短作业一次完成；）短作业一次完成；（2 2）中型作业周转时间不长；）中型作业周转时间不长；（3 3）大型作业不会长期不处理。）大型作业不会长期不处理。处理机调度与死锁处理机调度与死锁就绪队列就绪队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至
16、至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2S3图图35多级队列反馈调度算法多级队列反馈调度算法处理机调度与死锁处理机调度与死锁v3 3.3.1.3.1实现实时调度的基本条件实现实时调度的基本条件1 1提供必要的调度信息提供必要的调度信息（1 1）就绪时间；）就绪时间；（2 2）开始）开始/ /完成截止时间；完成截止时间；（3 3）处理时间；）处理时间；（4 4）资源要求；）资源要求；（5 5）优先级；）优先级；2 2系统处理能力强系统处理能力强3 3 3 3.3.3.3.3实时调度实时调度实时调度实时调度Ci为处理时间，为处理时间，Pi为周期时间（基于周期性实时任务）
17、为周期时间（基于周期性实时任务）处理机调度与死锁处理机调度与死锁v3 3.3.1.3.1实现实时调度的基本条件实现实时调度的基本条件3.3.采用抢占调度方式采用抢占调度方式剥夺方式：一般都采用此剥夺方式：一般都采用此非剥夺方式（实现简单）：一般应使实时任务较小，非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃以及时放弃CPUCPU。4.4.具有快速切换机制具有快速切换机制具有快速响应外部中断能力。具有快速响应外部中断能力。快速任务分派快速任务分派3 3 3 3.3.3.3.3实时调度实时调度实时调度实时调度处理机调度与死锁处理机调度与死锁3 3 3 3.3.2.3.2.3.2.3.2实
18、时调度算法的分类实时调度算法的分类实时调度算法的分类实时调度算法的分类v1 1非抢占式调度算法非抢占式调度算法时间片轮转时间片轮转 秒级秒级非抢占优先权（协同）非抢占优先权（协同） 秒秒 毫秒级毫秒级v2 2抢占式调度算法抢占式调度算法时钟中断抢占优先权时钟中断抢占优先权 毫秒级毫秒级基于抢占点抢占基于抢占点抢占立即抢占立即抢占immediate preemption immediate preemption 毫秒毫秒 微秒级微秒级只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间调度时间实时进程要求调度实时进程要求调度调度实时进程运行调度实时进
19、程运行a 非抢占轮转调度非抢占轮转调度当前进程实时进程实时进程要求调度实时进程要求调度当前进程运行完成当前进程运行完成b 非抢占优先权调度非抢占优先权调度调度时间调度时间c 基于时钟中断抢占的优先权抢占调度基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度实时进程要求调度抢占时刻（其它中断）抢占时刻（其它中断）b 立即抢占优先权调度立即抢占优先权调度当前进程实时进程实时进程要求调度实时进程要求调度时钟中断到达时时钟中断到达时调度时间调度时间调度时间调度时间处理机调度与死锁处理机调度与死锁3.3.33.3.33.3.33.3.3常用的几种实时调度算法常用的几种实时调度算法常用的几种
20、实时调度算法常用的几种实时调度算法v1.1.最早截止时间优先最早截止时间优先EDFEDF（earliest deadline first)earliest deadline first)算算法法根据任务的截止时间来确定任务的优先级根据任务的截止时间来确定任务的优先级截止时间越早，优先级越高截止时间越早，优先级越高可以是抢占式或非抢占式可以是抢占式或非抢占式处理机调度与死锁处理机调度与死锁最早截止时间优先最早截止时间优先最早截止时间优先最早截止时间优先EDFEDFEDFEDF例例例例1342134212 34t开始截止时间开始截止时间任务到达任务到达任务执行任务执行图图37 EDF算法用于非抢占
21、调度方式算法用于非抢占调度方式处理机调度与死锁处理机调度与死锁2 2 2 2. . . . 最低松弛度优先最低松弛度优先最低松弛度优先最低松弛度优先LLFLLFLLFLLF算法算法算法算法v松弛度：松弛度：若若A A进程进程需在需在200ms200ms时完成，其本身运行需要时完成，其本身运行需要100ms100ms，当，当前时刻是前时刻是10ms10ms，则，则A A的松弛度为：的松弛度为：20020010010010109090主要用于可抢占的调度方式中主要用于可抢占的调度方式中例：例：A1A2A3A4A5A6A7A8B1B2B3020406080 100120 140160t图图38 A/
22、B任务每次必须完成的时间任务每次必须完成的时间处理机调度与死锁处理机调度与死锁最低松弛度优先最低松弛度优先最低松弛度优先最低松弛度优先LLFLLFLLFLLF算法算法算法算法(2)(2)(2)(2)A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8处理机调度与死锁处理机调度与死锁3.43.43.43.4多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度v1.1.紧密耦合紧密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS紧密耦合紧密耦合共享共享R
23、AMRAM和和I/OI/O高速总线和交叉开关连接高速总线和交叉开关连接松弛耦合松弛耦合独立独立RAMRAM和和I/OI/O通道和通信线路连接通道和通信线路连接v2.2.对称多处理器系统和非对称多处理器系统对称多处理器系统和非对称多处理器系统处理器是否结构相同处理器是否结构相同处理机调度与死锁处理机调度与死锁3 3 3 3.4.2.4.2.4.2.4.2进程分配方式进程分配方式进程分配方式进程分配方式v1.1.SMPSMP中进程分配方式中进程分配方式静态分配静态分配动态分配动态分配可防止系统中多个处理器忙闲不均可防止系统中多个处理器忙闲不均v2.2.非非SMPSMP中进程分配方式中进程分配方式进
24、程调度在主处理器上执行进程调度在主处理器上执行有潜在的不可靠性有潜在的不可靠性处理机调度与死锁处理机调度与死锁3.4.33.4.33.4.33.4.3进程（线程）调度方式进程（线程）调度方式进程（线程）调度方式进程（线程）调度方式 v1.1.自调度自调度各个处理机自行在就绪队列中取任务。各个处理机自行在就绪队列中取任务。特点；简单，分布式调度，调度算法可采用特点；简单，分布式调度，调度算法可采用前述方法，多个前述方法，多个CPUCPU利用率都不错（不会闲）利用率都不错（不会闲）但：但：瓶颈问题，（单队列）瓶颈问题，（单队列）低效性；（需拷贝现场）低效性；（需拷贝现场）线程切换频繁（当线程合作时
25、线程切换频繁（当线程合作时, ,各线程并行各线程并行的条件不容易满足）的条件不容易满足） 处理机调度与死锁处理机调度与死锁2.2.2.2.成组调度成组调度成组调度成组调度 v优点：优点：（1 1）对相互合作的进（线）程组调度，可以减小切换，）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。减小系统开销。（2 2）每次分配一组）每次分配一组CPUCPU，减少了调度频率。，减少了调度频率。v分配时间分配时间（1 1）面向程序）面向程序（2 2）面向线程：使处理机利用率更高。）面向线程：使处理机利用率更高。 处理机调度与死锁处理机调度与死锁2.2.2.2.成组调度成组调度成组调度成组调度应
26、用程序应用程序A应用程应用程序序BCpu1线程线程1线程线程1Cpu2线程线程2空闲空闲Cpu3线程线程3空闲空闲Cpu4线程线程4空闲空闲时间时间1/21/2浪费浪费37.5%应用程序应用程序A应用程应用程序序BCpu1线程线程1线程线程1Cpu2线程线程2空闲空闲Cpu3线程线程3空闲空闲Cpu4线程线程4空闲空闲时间时间4/51/5浪费浪费15%处理机调度与死锁处理机调度与死锁3.3.3.3.专用处理机分配专用处理机分配专用处理机分配专用处理机分配 v引入：多处理机系统，每个处理已不再属宝贵资源。引入：多处理机系统，每个处理已不再属宝贵资源。v特点：每个进（线）程专用处理机，使其切换小，
27、特点：每个进（线）程专用处理机，使其切换小，提高效率。提高效率。v主要用于大型计算，实时系统主要用于大型计算，实时系统处理机调度与死锁处理机调度与死锁3.53.53.53.5产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件v3 3.5.5.1.1产生死锁的原因。产生死锁的原因。v一、竞争资源引起死锁。一、竞争资源引起死锁。1 1可剥夺（可剥夺（CPUCPU、内存，）和非剥夺性（打印机，磁、内存，）和非剥夺性（打印机，磁带机）资源带机）资源2 2竞争非剥夺性资源竞争非剥夺性资源可造成死锁可造成死锁 p1p2R1R2处理机调度与死锁处理机调度与死锁3
28、.53.53.53.5产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件v3 3竞争临时性资源竞争临时性资源临时性资源是指由一个进程产生，被另一个进程使用临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。一段时间后便无用的资源。处理机调度与死锁处理机调度与死锁二、进程推进顺序不当引起死锁。二、进程推进顺序不当引起死锁。二、进程推进顺序不当引起死锁。二、进程推进顺序不当引起死锁。213DP2Req(R2)P2Req(R1)P1Req(R1) P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1) P1Rel(R2
29、)4处理机调度与死锁处理机调度与死锁3.5.2 3.5.2 3.5.2 3.5.2 产生死锁的必要条件产生死锁的必要条件产生死锁的必要条件产生死锁的必要条件v1 1互斥条件（资源的临界性）互斥条件（资源的临界性）v2 2请求和保持条件请求和保持条件v3 3不剥夺条件不剥夺条件v4 4环路等待环路等待处理机调度与死锁处理机调度与死锁3.5.33.5.33.5.33.5.3处理死锁的基本方法处理死锁的基本方法处理死锁的基本方法处理死锁的基本方法 v1 1预防；破坏预防；破坏4 4个条件之一：有效，使资源个条件之一：有效，使资源利用率低。利用率低。v2 2避免：防止进入不安全态。避免：防止进入不安全
30、态。v3 3检测：检测到死锁再清除。检测：检测到死锁再清除。v4 4解除：与解除：与“检检”配套。配套。处理机调度与死锁处理机调度与死锁3.6 3.6 3.6 3.6 死锁预防和避免死锁预防和避免死锁预防和避免死锁预防和避免 v3.6.1 3.6.1 死锁预防死锁预防 一、互斥条件是资源固有属性，不能避免。一、互斥条件是资源固有属性，不能避免。二、摒弃请求和保持条件二、摒弃请求和保持条件全分配，全释放（全分配，全释放（ANDAND）缺点：（缺点：（1 1）延迟进程运行）延迟进程运行（2 2）资源严重浪费）资源严重浪费三、摒弃三、摒弃“不剥夺不剥夺”条件条件增加系统开销，且进程前段工作可能失效。
31、增加系统开销，且进程前段工作可能失效。处理机调度与死锁处理机调度与死锁3.6 3.6 3.6 3.6 死锁预防和避免死锁预防和避免死锁预防和避免死锁预防和避免 v3.6.1 3.6.1 死锁预防死锁预防 四、摒弃四、摒弃“环路环路”条件条件有序资源分配法：为资源编号，申请时需按编号进有序资源分配法：为资源编号，申请时需按编号进行。行。缺点：缺点：（1 1）新增资源不便，（原序号已排定）新增资源不便，（原序号已排定）（2 2）用户不自由）用户不自由（3 3）资源与进程使用顺序不同造成浪费）资源与进程使用顺序不同造成浪费处理机调度与死锁处理机调度与死锁3.6.2 3.6.2 3.6.2 3.6.2
32、 系统的安全状态系统的安全状态系统的安全状态系统的安全状态v在在“避免死锁避免死锁”方法中的判断条件方法中的判断条件 v1. 1. 安全状态安全状态按某种顺序并发进程都能达到获得最大资源而顺序按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。完成的序列为安全序列。能找到安全序列的状态为安全状态。能找到安全序列的状态为安全状态。处理机调度与死锁处理机调度与死锁3.6.2 3.6.2 3.6.2 3.6.2 系统的安全状态（系统的安全状态（系统的安全状态（系统的安全状态（2 2 2 2）v2.2.安全状态例安全状态例进程进程最大最大需求需求已分已分配配可用可用P11053P242P
33、392安全序列：安全序列：p2p2p1p1p3 p3 处理机调度与死锁处理机调度与死锁3.6.2 3.6.2 3.6.2 3.6.2 系统的安全状态（系统的安全状态（系统的安全状态（系统的安全状态（3 3 3 3）v3 3安全安全不安全的转换不安全的转换 上例中，若上例中，若P3P3再申请一台，则不安全再申请一台，则不安全 进程进程最大需求最大需求已分配已分配可用可用P11052P242P393处理机调度与死锁处理机调度与死锁3 3 3 3.6.3.6.3.6.3.6.3利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁 v1 1数据结构数据结构avail
34、ablejavailablej=k: =k: 系统现有系统现有RjRj类资源类资源k k个；个；maxi,jmaxi,j=k: =k: 进程进程i i需要需要RjRj的最大数的最大数k k个；个；alloci,jalloci,j=k: =k: 进程进程i i已得到已得到RjRj类资源类资源k k个；个； needi,jneedi,j=k:=k: 进程进程i i需要需要RjRj类资源类资源k k个个有：有：needi,jneedi,j= = maxi,jmaxi,j alloci,jalloci,j requestirequesti进程进程i i请求资源数请求资源数workiworki：进程：进
35、程i i执行完后系统应有资源数（也即可用数）执行完后系统应有资源数（也即可用数）finishifinishi ：布尔量，表进程：布尔量，表进程i i能否顺序完成。能否顺序完成。 处理机调度与死锁处理机调度与死锁3 3 3 3.6.3.6.3.6.3.6.3利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁 v2 2银行家算法银行家算法 reqi=needierrorreqi=availiblock处理机调度与死锁处理机调度与死锁3 3 3 3.6.3.6.3.6.3.6.3利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免
36、死锁 avail=avail-reqialloci=alloci+reqineedi=needi-reqifinishi=.F.needi=workwork=work+allocifinishi=.T.处理机调度与死锁处理机调度与死锁4 4 4 4实例实例实例实例 Max A B C Allocation A B C Need A B C Available A B C p0 7 5 3 0 1 0 7 4 3 3 3 2(2 3 0) p1 3 2 2 2 0 0(3 0 2) 1 2 2(0 2 0) p2 9 0 2 3 0 2 6 0 0 p3 2 2 2 2 1 1 0 1 1 p4
37、 4 3 3 0 0 2 4 3 1T0时刻的资源分配表时刻的资源分配表处理机调度与死锁处理机调度与死锁4 4 4 4实例实例实例实例Work A B CNeed A B C Alloc A B CWork+alloc A B C Finish p1 3 3 2 1 2 2 2 0 0 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p2 7 4 5 6 0 0 3 0 2 10 4 7 true p0 10 4 7 7 4 3 0 1 0 10 5 7 trueT0时刻的安全序列时刻的安全序
38、列处理机调度与死锁处理机调度与死锁4 4 4 4实例实例实例实例Work A B CNeed A B C Alloc A B CWork+alloc A B C Finish p1 2 3 0 0 2 0 3 0 2 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p0 7 4 5 7 4 3 0 1 0 7 5 5 true p2 7 5 5 6 0 0 3 0 2 10 5 7 trueP1申请资源申请资源(1,0,2)时安全性检查时安全性检查(安全安全)处理机调度与死锁处理机调度与死锁4
39、 4 4 4实例实例实例实例 Allocation A B C Need A B C Available A B C p0 0 3 0 7 2 3 2 1 0 p1 3 0 2 0 2 0 p2 3 0 2 6 0 0 p3 2 1 1 0 1 1 p4 0 0 2 4 3 1为为P0分配（分配（0，2，0）后的情况（不安全）后的情况（不安全）处理机调度与死锁处理机调度与死锁3.73.73.73.7死锁的检测和解除死锁的检测和解除死锁的检测和解除死锁的检测和解除 v3.7.13.7.1检测检测v1.1.资源分配图资源分配图p1p2处理机调度与死锁处理机调度与死锁3.73.73.73.7死锁的检
40、测和解除死锁的检测和解除死锁的检测和解除死锁的检测和解除 v2.2.死锁定理死锁定理简化资源分配图简化资源分配图若能完全简化则消去所有的边。若能完全简化则消去所有的边。定理：死锁状态的充分条件，资源分配图不可完全简化定理：死锁状态的充分条件，资源分配图不可完全简化v3.3.检测死锁的算法：检测死锁的算法：处理机调度与死锁处理机调度与死锁Work= availableL:=Li| alloci=0 reqi=0 (孤立进程点孤立进程点)For all Li L doBeginFor all reqi =work doBeginWork=work+allociL=LiLendEndDeadlock= (L=p1 pn)3.73.73.73.7死锁的检测和解除死锁的检测和解除死锁的检测和解除死锁的检测和解除 处理机调度与死锁处理机调度与死锁解除解除解除解除v检检测测到到死死锁锁后后，回回退退到到上上一一状状态态（要要进进行行资资源源剥剥夺夺，且且需需保保存存以以前前状状态态的的分分配配信信息息），重重新新分分配配，若若不不行，继续回退行，继续回退，
