《计算机操作系统(大学课程)第三章.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统(大学课程)第三章.ppt（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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)2.2.抢占方式抢占方式（1 1）时间片原则）时间片原则（2
3、 2）优先权原则）优先权原则（3 3）短作业优先原则。）短作业优先原则。vv3 3 3 3、中级调度（中程）、中级调度（中程）、中级调度（中程）、中级调度（中程）vv为提高系统吞吐量和内存利用率而引入的一内为提高系统吞吐量和内存利用率而引入的一内为提高系统吞吐量和内存利用率而引入的一内为提高系统吞吐量和内存利用率而引入的一内-外存外存外存外存对换功能（换出时，进程为挂起或就绪驻外状态）对换功能（换出时，进程为挂起或就绪驻外状态）对换功能（换出时，进程为挂起或就绪驻外状态）对换功能（换出时，进程为挂起或就绪驻外状态）v运行频率：低运行频率：低 中中 高高。3.1.23.1.23.1.23.1.2
4、调度的队列模型调度的队列模型调度的队列模型调度的队列模型v一、仅有进程调度的队列模型一、仅有进程调度的队列模型就绪队列就绪队列CPU阻塞队列阻塞队列交互用户交互用户时间片完时间片完进程调度进程调度进程完成进程完成等待事件等待事件事件出现事件出现3.1.23.1.23.1.23.1.2调度的队列模型调度的队列模型调度的队列模型调度的队列模型v二、具有高二、具有高/低级模型低级模型就绪队列就绪队列CPU阻塞队列阻塞队列时间片完时间片完进程调度进程调度进程进程完成完成等待事件等待事件1事件事件1出现出现后备队列后备队列阻塞队列阻塞队列等待事件等待事件2事件事件2出现出现作业调度作业调度三、具有三级调
5、度三、具有三级调度三、具有三级调度三、具有三级调度就绪队列就绪队列CPU就绪、挂起队列就绪、挂起队列时间片完时间片完进程调度进程调度进程进程完成完成后备队列后备队列阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作业调度阻塞队列阻塞队列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交互型作业3.1.33.1.33.1.33.1.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 v一、面向用户的准则一、面向用户的准则1 1周转时间短（常用于批处理系统）周转时间短（常用于批处理系统）概念：作业从提交概念：作业
6、从提交 完成的时间完成的时间.分为：分为：（1 1）驻外等待调度时间）驻外等待调度时间（2 2）驻内等待调度时间）驻内等待调度时间（3 3）执行时间）执行时间（4 4）阻塞时间）阻塞时间v一、面向用户的准则一、面向用户的准则平均周转时间平均周转时间 平均带权平均带权 可见带权可见带权w w越小越好越小越好,Ts,Ts为实际服务时间。为实际服务时间。3.1.33.1.33.1.33.1.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 v一、面向用户的准则一、面向用户的准则2 2响应时间快：（对交互性作业）响应时间快：（对交互性作
7、业）概念：键盘提交请求到首次响应时间概念：键盘提交请求到首次响应时间（1 1）输入传送时间）输入传送时间（2 2）处理时间）处理时间（3 3）响应传送时间）响应传送时间3 3截止时间的保证（特别于实时系统）截止时间的保证（特别于实时系统）4 4优先权准则：（即需要抢占调度）优先权准则：（即需要抢占调度）3.1.33.1.33.1.33.1.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 v二、面向系统的准则二、面向系统的准则1 1吞吐量高（特别于批处理）：单位时间完成作吞吐量高（特别于批处理）：单位时间完成作业数业数2 2处理
8、机利用率好：（因处理机利用率好：（因CPUCPU贵，特别于大中型多贵，特别于大中型多用户系统）用户系统）3 3各类资源的平衡利用。（？折算标准）各类资源的平衡利用。（？折算标准）3.1.33.1.33.1.33.1.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 3.23.23.23.2调度算法调度算法调度算法调度算法是一个资源分配问题是一个资源分配问题是一个资源分配问题是一个资源分配问题 v3.2.13.2.1先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法 1.FCFS1.FCFS特点：简单，有
9、利于长作业特点：简单，有利于长作业 即即CPUCPU繁忙性作业繁忙性作业2.2.短作业进程优先调度算法：短作业进程优先调度算法：SJ(P)FSJ(P)F提高了平均周转时间和平均带权周转时间（从而提提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）高了系统吞吐量）特点：对长作业不利，有可能得不到服务（饥饿）特点：对长作业不利，有可能得不到服务（饥饿）估计时间不易确定估计时间不易确定 例例例例进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99图图图图3.4FCFS3.4F
10、CFS3.4FCFS3.4FCFS和和和和SJFSJFSJFSJF比较比较比较比较进程名进程名 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.13.2.23.2.23.2.23.2.2高优先权优先调度算法高优先权优先调度算法高优先权优先调度算
11、法高优先权优先调度算法v1.1.优先权调度算法类型优先权调度算法类型非抢占式优先权算法非抢占式优先权算法抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。v2.2.优先权类型：优先权类型：1 1静态优先权：静态优先权：进程优先权在整个运行期不变。进程优先权在整个运行期不变。确定优先权依据确定优先权依据（1 1）进程类型）进程类型（2 2）进程对资源的需求；）进程对资源的需求；（3 3）根据用户需求。）根据用户需求。特点：简单，但低优先权作业可能长期不被特点：简单，但低优先权作业可能长期不被调度。调度。3.2.23.2.23.2.23.2.2高优先权优先调度算法高优先权优先调度算法高优
12、先权优先调度算法高优先权优先调度算法(2)(2)(2)(2)v2 2动态优先权：动态优先权：如：优先权随执行时间而下降，随等待时间而升高。如：优先权随执行时间而下降，随等待时间而升高。响应比响应比Rp=Rp=（等待时间服务时间）（等待时间服务时间）/服务时间服务时间 作为优作为优先权先权优点：长短兼顾优点：长短兼顾 缺点：需计算缺点：需计算RpRpv3.3.高响应比优先算法：高响应比优先算法：特点：特点：响应比响应比Rp=Rp=（tw+tstw+ts）/ts/ts（1 1）短作业）短作业 R RP P大。大。（2 2）tsts（要求服务时间）相同的进程间相当于（要求服务时间）相同的进程间相当于
13、FCFSFCFS。（3 3）长作业等待一段时间仍能得到服务。）长作业等待一段时间仍能得到服务。3.2.33.2.33.2.33.2.3基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法v1.1.时间片轮转时间片轮转时间片大小的确定时间片大小的确定太大：退化为太大：退化为FCFSFCFS；太小：系统开销过大太小：系统开销过大系统对响应时间的要求；系统对响应时间的要求；T=nqT=nq就绪队列中进程的数目；就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用命令）系统的处理能力：（应保证一个时间片处理完常用命令）3.2.33.2.33.2
14、.33.2.3基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法v2.2.多级反馈队列调度多级反馈队列调度特点：长、短作业兼顾，有较好的响应时间特点：长、短作业兼顾，有较好的响应时间（1 1）短作业一次完成；）短作业一次完成；（2 2）中型作业周转时间不长；）中型作业周转时间不长；（3 3）大型作业不会长期不处理。）大型作业不会长期不处理。就绪队列就绪队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2S3图图35多级队列反馈调度算法多级队列反馈
15、调度算法v3.3.13.3.1实现实时调度的基本条件实现实时调度的基本条件1 1提供必要的调度信息提供必要的调度信息（1 1）就绪时间；）就绪时间；（2 2）开始）开始/完成截止时间；完成截止时间；（3 3）处理时间；）处理时间；（4 4）资源要求；）资源要求；（5 5）优先级；）优先级；2 2系统处理能力强系统处理能力强3.33.33.33.3实时调度实时调度实时调度实时调度Ci为处理时间，为处理时间，Pi为周期时间（基于周期性实时任务）为周期时间（基于周期性实时任务）v3.3.13.3.1实现实时调度的基本条件实现实时调度的基本条件3.3.采用抢占调度方式采用抢占调度方式剥夺方式：一般都采
16、用此剥夺方式：一般都采用此非剥夺方式（实现简单）：一般应使实时任务较小，非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃以及时放弃CPUCPU。4.4.具有快速切换机制具有快速切换机制具有快速响应外部中断能力。具有快速响应外部中断能力。快速任务分派快速任务分派3.33.33.33.3实时调度实时调度实时调度实时调度3.3.23.3.23.3.23.3.2实时调度算法的分类实时调度算法的分类实时调度算法的分类实时调度算法的分类v1 1非抢占式调度算法非抢占式调度算法时间片轮转时间片轮转 秒级秒级非抢占优先权（协同）非抢占优先权（协同）秒秒 毫秒级毫秒级v2 2抢占式调度算法抢占式调度算法
17、时钟中断抢占优先权时钟中断抢占优先权 毫秒级毫秒级基于抢占点抢占基于抢占点抢占立即抢占立即抢占immediate preemption immediate preemption 毫秒毫秒 微秒级微秒级只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间调度时间实时进程要求调度实时进程要求调度调度实时进程运行调度实时进程运行a 非抢占轮转调度非抢占轮转调度当前进程实时进程实时进程要求调度实时进程要求调度当前进程运行完成当前进程运行完成b 非抢占优先权调度非抢占优先权调度调度时间调度时间c 基于时钟中断抢占的优先权抢占调度基于时钟中断抢占的优先权抢占调
18、度当前进程实时进程实时进程要求调度实时进程要求调度抢占时刻（其它中断）抢占时刻（其它中断）b 立即抢占优先权调度立即抢占优先权调度当前进程实时进程实时进程要求调度实时进程要求调度时钟中断到达时时钟中断到达时调度时间调度时间调度时间调度时间3.3.33.3.33.3.33.3.3常用的几种实时调度算法常用的几种实时调度算法常用的几种实时调度算法常用的几种实时调度算法v1.1.最早截止时间优先最早截止时间优先EDFEDF（earliest deadline first)earliest deadline first)算算法法根据任务的截止时间来确定任务的优先级根据任务的截止时间来确定任务的优先级截
19、止时间越早，优先级越高截止时间越早，优先级越高可以是抢占式或非抢占式可以是抢占式或非抢占式最早截止时间优先最早截止时间优先最早截止时间优先最早截止时间优先EDFEDFEDFEDF例例例例1342134212 34t开始截止时间开始截止时间任务到达任务到达任务执行任务执行图图37 EDF算法用于非抢占调度方式算法用于非抢占调度方式2.2.2.2.最低松弛度优先最低松弛度优先最低松弛度优先最低松弛度优先LLFLLFLLFLLF算法算法算法算法v松弛度：松弛度：若若A A进程需在进程需在200ms200ms时完成，其本身运行需要时完成，其本身运行需要100ms100ms，当，当前时刻是前时刻是10m
20、s10ms，则，则A A的松弛度为：的松弛度为：20020010010010109090主要用于可抢占的调度方式中主要用于可抢占的调度方式中例：例：A1A2A3A4A5A6A7A8B1B2B3020406080 100120 140160t图图38 A/B任务每次必须完成的时间任务每次必须完成的时间最低松弛度优先最低松弛度优先最低松弛度优先最低松弛度优先LLFLLFLLFLLF算法算法算法算法(2)(2)(2)(2)A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t83.43.
21、43.43.4多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度v1.1.紧密耦合紧密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS紧密耦合紧密耦合共享共享RAMRAM和和I/OI/O高速总线和交叉开关连接高速总线和交叉开关连接松弛耦合松弛耦合独立独立RAMRAM和和I/OI/O通道和通信线路连接通道和通信线路连接v2.2.对称多处理器系统和非对称多处理器系统对称多处理器系统和非对称多处理器系统处理器是否结构相同处理器是否结构相同3.4.23.4.23.4.23.4.2进程分配方式进程分配方式进程分配方式进程分配方式v1.SMP1.SMP中进程分配方式中进程分配
22、方式静态分配静态分配动态分配动态分配可防止系统中多个处理器忙闲不均可防止系统中多个处理器忙闲不均v2.2.非非SMPSMP中进程分配方式中进程分配方式进程调度在主处理器上执行进程调度在主处理器上执行有潜在的不可靠性有潜在的不可靠性3.4.33.4.33.4.33.4.3进程（线程）调度方式进程（线程）调度方式进程（线程）调度方式进程（线程）调度方式 v1.1.自调度自调度各个处理机自行在就绪队列中取任务。各个处理机自行在就绪队列中取任务。特点；简单，分布式调度，调度算法可采用特点；简单，分布式调度，调度算法可采用前述方法，多个前述方法，多个CPUCPU利用率都不错（不会闲）利用率都不错（不会闲
23、）但：但：瓶颈问题，（单队列）瓶颈问题，（单队列）低效性；（需拷贝现场）低效性；（需拷贝现场）线程切换频繁（当线程合作时线程切换频繁（当线程合作时,各线程并行各线程并行的条件不容易满足）的条件不容易满足）2.2.2.2.成组调度成组调度成组调度成组调度 v优点：优点：（1 1）对相互合作的进（线）程组调度，可以减小切换，）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。减小系统开销。（2 2）每次分配一组）每次分配一组CPUCPU，减少了调度频率。，减少了调度频率。v分配时间分配时间（1 1）面向程序）面向程序（2 2）面向线程：使处理机利用率更高。）面向线程：使处理机利用率更高。2
24、.2.2.2.成组调度成组调度成组调度成组调度应用程序应用程序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特点：每个进（线）程专用处理
25、机，使其切换小，特点：每个进（线）程专用处理机，使其切换小，提高效率。提高效率。v主要用于大型计算，实时系统主要用于大型计算，实时系统v例 考虑5个进程P1,P2,P3,P4,P5,见表1.规定进程的优先度越小,优先级越高.试描述在采用下述几种调度算法时各个进程的运行过程.并计算采用每种算法时的进程平均周转时间.假设忽略进程的调度时间.1、先来先服务调度算法2、时间片轮转调度算法(时间片为1ms)3、非剥夺式SJF调度算法4、剥夺式优先级调度算法表1进程创建时间运行时间(ms)优先级P1033P2265P3441P4652P5824解:(1)FCFS调度算法,进程的运行过程如图所示:(2)时间
26、片轮转调度算法,进程的运行情况如图所示:01:p112:p2p123:p1p234:p3p2p145:p3p256:p4p2p367:p3p4p278:p5p2p3p489:p4p5p2p3(3)非剥夺式SJF调度算法,进程的运行情况如图所示:(4)剥夺式优先级调度算法,进程的运行情况如图所示:表表表表2 2 进程的平均周转时间进程的平均周转时间进程的平均周转时间进程的平均周转时间算法进程名创建时间结束时间周转时间平均周转时间(ms)FCFSP1033(3+7+9+12+12)/5=8.60P2297P34139P461812P582012RRP1044(4+16+13+14+7)/5=10.
27、80P221816P341713P462014P58157非剥夺式优先级P1033(3+7+9+12+12)/5=8.60P2297P34139P461812P582012剥夺式优先级P1033(3+18+4+7+7)/5=7.8P222018P3484P46137P581573.53.53.53.5产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件v3.5.13.5.1产生死锁的原因。产生死锁的原因。v一、竞争资源引起死锁。一、竞争资源引起死锁。1 1可剥夺（可剥夺（CPUCPU、内存，）和非剥夺性（打印机，磁、内存，）和非剥夺性（打印机，磁带机
28、）资源带机）资源2 2竞争非剥夺性资源竞争非剥夺性资源可造成死锁可造成死锁 p1p2R1R23.53.53.53.5产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件v3 3竞争临时性资源竞争临时性资源临时性资源是指由一个进程产生，被另一个进程使用临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。一段时间后便无用的资源。二、进程推进顺序不当引起死锁。二、进程推进顺序不当引起死锁。二、进程推进顺序不当引起死锁。二、进程推进顺序不当引起死锁。213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(
29、R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)43.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避免：防止进入不安全态。避免：防止进入不安全态。v
30、3 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 避免死锁避免死锁避免死锁避免死锁v方法方法：（1）系统的状态：安全和不安全）系统的状态：安全和不安全
32、 （2）进程动态地申请资源，系统对资源预分配，进行安全性）进程动态地申请资源，系统对资源预分配，进行安全性的检测。的检测。v系统中描述资源所需的数据结构系统中描述资源所需的数据结构 某类资源：某类资源：Maxi：某进程所需的最大资源数：某进程所需的最大资源数 Allocationi：某进程已分配的资源数：某进程已分配的资源数 Needi：某进程还需要的资源数：某进程还需要的资源数 Available i：系统中可用的资源数：系统中可用的资源数 Maxi=Allocationi +Needi Available i比较比较v1.1.安全状态安全状态按某种顺序并发进程都能达到获得最大资源而顺按某种
33、顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。序完成的序列为安全序列。能找到安全序列的状态为安全状态。能找到安全序列的状态为安全状态。3.6.2 3.6.2 3.6.2 3.6.2 系统的安全状态（系统的安全状态（系统的安全状态（系统的安全状态（2 2 2 2）v2.2.安全状态例（安全状态例（共有共有1212个该类资源）个该类资源）进程进程最大需求最大需求已分配已分配可用可用P11053P242P392安全序列：安全序列：p2p2p1p1p3 p3 3.6.2 3.6.2 3.6.2 3.6.2 系统的安全状态（系统的安全状态（系统的安全状态（系统的安全状态（3 3 3 3）v
34、3 3 安全安全不安全的转换不安全的转换 上例中，若上例中，若P3P3再申请一台，则不安全再申请一台，则不安全 进程进程最大需求最大需求 已分配已分配可用可用P11052P242P393v安全状态安全状态 避免死锁避免死锁v不安全状态不安全状态 可能进入死锁可能进入死锁v不安全状态是否必然导致系统进入死锁？不安全状态是否必然导致系统进入死锁？3.6.33.6.33.6.33.6.3利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁 v1 1数据结构数据结构availablej=k:availablej=k:系统现有系统现有RjRj类资源类资源k k个；个；
35、maxi,j=k:maxi,j=k:进程进程i i需要需要RjRj的最大数的最大数k k个；个；alloci,j=k:alloci,j=k:进程进程i i已得到已得到RjRj类资源类资源k k个；个；needi,j=k:needi,j=k:进程进程i i需要需要RjRj类资源类资源k k个个有：有：needi,j=maxi,jneedi,j=maxi,jalloci,jalloci,jRequestiRequesti：进程：进程i i请求资源数请求资源数workiworki：进程：进程i i执行完后系统应有资源数（也即执行完后系统应有资源数（也即可用数）可用数）finishifinishi：布
36、尔量，表进程：布尔量，表进程i i能否顺序完成。能否顺序完成。3.6.33.6.33.6.33.6.3利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁 v2 2银行家算法银行家算法 reqi=needierrorreqi=availiblock3.6.33.6.33.6.33.6.3利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁 avail=avail-reqialloci=alloci+reqineedi=needi-reqifinishi=.F.needi0(对所有i)Maxim+n 若系统已因竞争该类资源而
37、进入死锁状态,则意味着已有一个以上的进程因申请不到该类资源而无限阻塞,而m个资源肯定已全部分配出去,即 Allocationi=m因此 Needi=Maxi-Allocationim+n-m即 Needin 这样,至少必须存在一个进程,其Needi0,这显然与题意不符,所以该系统不可能因竞争该类资源而进入死锁状态.(3)此时系统可能发生死锁,如n=4,m=3时,若P1的Max为0,而其余三个进程的Max都为2,则任然满足最大需求量之和(即6)小于m+n(即7)的要求,但当除P1以外的其余三个进程各得到一个资源时.这三个进程将进入死锁状态.3.73.73.73.7死锁的检测和解除死锁的检测和解除
38、死锁的检测和解除死锁的检测和解除 v3.7.13.7.1检测检测v1.1.资源分配图资源分配图p1p23.73.73.73.7死锁的检测和解除死锁的检测和解除死锁的检测和解除死锁的检测和解除 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检检测测到到死死锁锁后后，回回退退到到上上一一状状态态（要要进进行行资资源源剥剥夺夺，且且需需保保存存以以前前状状态态的的分分配配信信息息），重重新新分分配配，若若不不行，继续回退行，继续回退，