第三章 处理机调度

《第三章 处理机调度》由会员分享，可在线阅读，更多相关《第三章 处理机调度（102页珍藏版）》请在文档大全上搜索。

1、第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 3.1 处理机调度的基本概念处理机调度的基本概念 3.2 3.2 调度算法调度算法 3.3 3.3 实时调度实时调度 3.4 3.4 多处理机系统中的调度多处理机系统中的调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 第三章 处理机调度与死锁 3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 高级、中级和低级调度高级、中级和低级调度 1.高级调度高级调度(High Scheduling)-作业调度作业调度 决

2、定把外存上处于后备队列中的哪些作决定把外存上处于后备队列中的哪些作业调入内存业调入内存,并为它们创建进程、分配必要的并为它们创建进程、分配必要的资源，然后将资源，然后将 新创建的进程排在就绪队列上，新创建的进程排在就绪队列上，准备执行准备执行第三章 处理机调度与死锁 接纳多少个作业接纳哪些作业2. 低级调度低级调度(Low Level Scheduling)-进程调度进程调度 决定就绪队列中的哪个进程应获得处理决定就绪队列中的哪个进程应获得处理机，由分派程序执行把处理机分配给该进程机，由分派程序执行把处理机分配给该进程的具体操作的具体操作 1) 非抢占方式(Non-preemptive Mod

3、e) 2) 抢占方式(Preemptive Mode) 第三章 处理机调度与死锁 引入的主要目的：为了提高内存利用率和系统吞吐量 使暂时不能运行的进程不再占用宝贵的内存资源，将它们调至外存上暂时等待（就绪驻外存状态或挂起状态），当这些进程重又具备运行条件、且内存又有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上3. 中级调度中级调度(Intermediate-Level Scheduling) 中程调度中程调度第三章 处理机调度与死锁 3.1.2 调度队列模型调度队列模型 1. 仅有进程调度的调度队列模型仅有进程调度的调度队

4、列模型 图 3 - 1 仅具有进程调度的调度队列模型 第三章 处理机调度与死锁 就 绪队 列阻 塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完CPU进程进程i进程调度进程调度进程进程j进程进程k进程进程p就绪队列时间片完时间片完进程进程f进程进程b进程进程n进程进程l阻塞队列等待事件等待事件事件出现事件出现进程完成进程完成进程进程X第三章 处理机调度与死锁 2. 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 图 3-2 具有高、低两级调度的调度队列模型 第三章 处理机调度与死锁 就 绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件

5、2出现等待事件n事件n出现后备 队列作业3作业2作业1作业调度作业调度进程2就绪队列CPU阻 塞 队 列 1阻 塞 队 列 n阻 塞 队 列 2进程调度进程调度等待事件等待事件1进程1等待事件等待事件2等待事件等待事件n事件事件1出现出现事件事件2出现出现事件事件n出现出现第三章 处理机调度与死锁 3. 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 图 3-3 具有三级调度时的调度队列模型 第三章 处理机调度与死锁 就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现3.1.3 选择调度

6、方式和调度算法的若干准则选择调度方式和调度算法的若干准则 1. 面向用户的准则面向用户的准则 (1) 周转时间短。周转时间短。 周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔 niSiiTTnW11作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间第三章 处理机调度与死锁 作业在外存后备队列上的等待时间进程在就绪队列上等待进程调度的时间进程在CPU上执行的时间进程等待I/O操作完成的时间(2) 响应时间快。 (3) 截止时间的保证。 (4) 优先权准则。 第三章 处理机调度与死锁 2. 面向系统的准则面向系统的准则 (1) 系统吞吐量高。(2)

7、处理机利用率好。 (3) 各类资源的平衡利用。 第三章 处理机调度与死锁 第三章 处理机调度与死锁 3.2 调 度 算 法 先来先服务调度算法FCFS 短作业(进程)优先调度算法SJ(P)F 高优先权优先调度算法 基于时间片的轮转调度算法3.2.1 先来先服务和短作业先来先服务和短作业(进程进程)优先调度算法优先调度算法 第三章 处理机调度与死锁 1先来先服务（FCFS）调度算法作业调度：从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存运行；进程调度：就绪队列按进入的先后次序排列，调度时，选队首进程投入运行。 A0t1020503040BC515352545D进程名ABCD

8、就绪时间051015要求服务时间1025510先来先服务先来先服务FCFS周转时间带权周转时间101301.2306353.526.252.9252 2、短作业（进程）优先调度算法（、短作业（进程）优先调度算法（SJ(P)FSJ(P)F） 短作业优先SJF调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 短进程SPF优先调度算法是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。A0t1020503040BC515352545D进程名ABCD就绪时间051015要求服务时间1

9、025510短作业优先短作业优先SJ(P)F周转时间带权周转时间101451.85110117.51.2进程名ABCD平均就绪时间051015要求服务时间1025510先来先服务（FCFS）周转时间1030303526.25带权周转时间11.263.52.925短进程优先（SPF）周转时间104551017.5带权周转时间11.8111.2FCFS和SPF调度算法的性能比较作业情况调度算法进程名ABCD平均到达时间051025要求服务时间20503540FCFS完成时间周转时间带权周转时间SJF完成时间周转时间带权周转时间3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法 1.

10、优先权调度算法的类型 非抢占式优先权算法 抢占式优先权调度算法2. 优先权的类型优先权的类型 1) 静态优先权 第三章 处理机调度与死锁 确定进程优先权的依据有如下三个方面：(1) 进程类型。 (2) 进程对资源的需求。 (3) 用户要求。 A0t1020503040BC515352545D进程名ABCD就绪时间051015要求服务时间1025510优先权0132高优先权优先高优先权优先(静态静态)非抢占式优先权调度A0t1020503040BC515352545D进程名ABCD就绪时间051015要求服务时间1025510优先权0132高优先权优先高优先权优先(静态静态)抢占式优先权调度 2

11、) 动态优先权 动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。 第三章 处理机调度与死锁 进程名ABCD就绪时间051015要求服务时间1025510优先权0132高优先权优先高优先权优先(动态动态)非抢占式优先权调度(优先权以速率0.2/5ms提高)1.21.4A0t1020503040BC515352545D3) 高响应比优先调度算法

12、优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 第三章 处理机调度与死锁 要求服务时间要求服务时间等待时间优先权+要求服务时间响应时间要求服务时间要求服务时间等待时间优先权+3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法 1. 时间片轮转法时间片轮转法RR 在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停

13、止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。第三章 处理机调度与死锁 A0t1020503040BC515352545D进程名ABCD就绪时间051015要求服务时间1025510时间片轮转法时间片轮转法RR时间片为5个单位时间2. 多级反馈队列调度算法多级反馈队列调度算法 第三章 处理机调度与死锁 就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CPU(时间片：S1S 2S3)图 3-5 多级反馈队列调度算

14、法 3. 多级反馈队列调度算法的性能多级反馈队列调度算法的性能 (1) 终端型作业用户。 (2) 短批处理作业用户。 (3) 长批处理作业用户。第三章 处理机调度与死锁 假定在单CPU条件下有下列要执行的作业:作业ABCDE到达时间01234运行时间61215优先级31342（1）用一个执行时间图描述在下列算法时各自执行这些作业的情况：FCFS、RR（时间片1）和非抢占式优先级。（2）对于上述每种算法，各个作业的周转时间是多少？平均周转时间是多少？（3）对于上述每种算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？作业ABCDE到达时间01234运行时间61215优先级31342FC

15、FS周转时间带权周转时间RR周转时间带权周转时间非抢占式优先周转时间带权周转时间123456789 1011 12 13 14 15t3.3 实实 时时 调调 度度 3.3.1 实现实时调度的基本条件实现实时调度的基本条件 1. 提供必要的信息提供必要的信息2. 系统处理能力强系统处理能力强3. 采用抢占式调度机制采用抢占式调度机制4. 具有快速切换机制具有快速切换机制第三章 处理机调度与死锁 3.3.2 实时调度算法的分类实时调度算法的分类 1. 非抢占式调度算法非抢占式调度算法 (1) 非抢占式轮转调度算法。 (2) 非抢占式优先调度算法。 第三章 处理机调度与死锁 2. 抢占式调度算法抢

16、占式调度算法 (1) 基于时钟中断的抢占式优先权调度算法。(2) 立即抢占(Immediate Preemption)的优先权调度算法。 图 3-6 实时进程调度 第三章 处理机调度与死锁 (a) 非抢占轮转调度当前进程实时进程实时进程请求调度实时进程枪占当前进程，并立即执行(d) 立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b) 非抢占优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间当前进程实时进程请求调度时钟中断到来时调度时间(c) 基于时钟中断抢占的优先权抢占调度调度时间实时进程.3.3.3 常用的几种实时调度算法常用的

17、几种实时调度算法 1. 最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)算法算法 开始截止时间2. 最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)算法算法 松驰度=完成截止时间-其本身运行时间-当前时间 第三章 处理机调度与死锁 进程名ABCD就绪时间051015要求服务时间1025510开始截止时间5152520最早截止时间优先最早截止时间优先EDF抢占式调度A0t1020503040BC515352545D进程名ABCD就绪时间051015要求服务时间1025510完成截止时间30403555松驰度最低松驰度优先最

18、低松驰度优先LLF抢占式调度A0t1020503040BC515352545D201020301510 1510505 020151003.4 多处理机系统中的调度 3.3.1 3.3.1 多处理器系统的类型多处理器系统的类型 3.3.2 3.3.2 进程分配方式进程分配方式 3.3.3 3.3.3 进程（线程）调度方式进程（线程）调度方式3.3.1 多处理器系统的类型多处理系统MPS（MultiProcessor System） 从多处理器之间耦合的紧密程度可以把MPS分为两类：紧密耦合MPS和松弛耦合MPS 根据系统中所用处理器的相同与否可分为两类：对称MPS和非对称MPS1 1、紧密耦合

19、、紧密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS 紧密耦合（Tightly Coupted）通常通过高速总线或高速交叉开关来实现多个处理器之间的互连。共享主存储器系统和I/O设备。系统中所有进程和资源由OS统一控制管理。 松散耦合（Loosely Coupted）通常通过通道或通信线路来实现多台计算机之间互连。每台计算机都有自己的存储器和I/O设备，可以独立工作。2 2、对称、对称MPSMPS和非对称和非对称MPSMPS 对称多处理系统SMPS（Symmetric MultiProcessor System）在系统中所包含的各处理器单元在功能上和结构上都相同。当前的绝大多数MPS属于此类

20、。 非对称多处理器系统。系统中有多种类型的处理单元，它们的功能和结构各不相同，其中只有一个主处理器，其余为从处理器。3.3.2 进程分配方式 在多处理器系统中，进程的调度与系统结构有关。 在同构性系统中，由于所有的处理器都是相同的，因而可将进程分配到任一处理器上运行； 在非对称MPS，对任一进程而言，都只能将其分配到某一适合于其运行的处理机上去执行。 下面分别介绍对称MPS和非对称MPS中的进程分配方式。1 1、对称、对称MPSMPS中的进程分配方式中的进程分配方式 静态分配静态分配（Static Assignment）方式：一个进程从开始执行直至其完成都被固定的分配到一个处理器上去执行。优点

21、是进程调度开销小，缺点是各处理器可能出现忙闲不均。 动态分配动态分配（Dynamic Assignment）方式：在系统中仅设置一个公共的就绪队列，分配进程总是给空闲处理器且对某一进程的执行来讲也可能曾在不同的处理器上。优点是消除忙闲不均现象。缺点是对松散耦合系统增大开销。2、非对称MPS中的进程分配方式 对于非对称MPS，其OS大多是采用主-从式OS,即OS的核心部分驻留在一台主机上，而从机上只是用户程序，进程调度只由主机执行。每当从机空闲时向主机发一索求进程信号，然后等待主机分配进程。主机中保持有一个就绪队列。此种方式优点是系统处理比较简单，缺点是不可靠性。（克服缺点的方法是利用多台而非一

22、台管理系统）3.3.3 进程（线程）调度方式 自调度自调度（Self-SchedulingSelf-Scheduling）方式）方式 成组调度成组调度（Gang SchedulingGang Scheduling）方式）方式 专用处理器专用处理器（Dedicated Processor Dedicated Processor AssignmentAssignment）分配方式）分配方式1、自调度（Self-Scheduling）方式 均衡调度均衡调度(balanced scheduling)(balanced scheduling) 一个就绪队列一个就绪队列( (多处理机互斥访问多处理机互斥访

23、问) ) 优点优点 不需要专门的处理机从事任务分派工作不需要专门的处理机从事任务分派工作 任务分配均衡任务分配均衡 缺点缺点 当当CPUCPU较多时较多时, ,就绪队列成为瓶颈就绪队列成为瓶颈 线程两次调度可能处于不同处理机线程两次调度可能处于不同处理机 不能保证同组线程同时调度不能保证同组线程同时调度自调度(self scheduling)就绪队列就绪队列进程进程(线程线程)进程进程(线程线程)进程进程(线程线程)CPUCPUCPU自调度(self scheduling) 例子例子: : Mach, Mach, 改进的自调度改进的自调度 全局队列全局队列 局部队列局部队列 调度时调度时 首先

24、考虑局部队列首先考虑局部队列 然后考虑全局队列然后考虑全局队列2、成组调度（Gang Scheduling）方式 将一组相关(合作)的线程同时分派到多个处理机上运行 避免合作线程之间的相互等待 降低开销,提高运行效率2、成组调度（Gang Scheduling）方式1.1. 面向所有应用程序平均分配处理器时间面向所有应用程序平均分配处理器时间2.2. 面向所有线程平均分配处理器时间面向所有线程平均分配处理器时间 按线程平均分配处理器时间按线程平均分配处理器时间的方法更有效。的方法更有效。两种分配处理器时间的方法两种分配处理器时间的方法3、专用处理器（Dedicated Processor As

25、signment）方式对系统的性能和效率来讲，单个处理器对系统的性能和效率来讲，单个处理器的利用率已不太重要。的利用率已不太重要。由于每个进（线）程专用一台处理器，由于每个进（线）程专用一台处理器，可避免进（线）程的切换，从而大大加可避免进（线）程的切换，从而大大加速了程序运行。速了程序运行。最新版最新版TOP500TOP500超级计算机排行榜超级计算机排行榜2007年6月27日下午，在德国德累斯顿举行的ISC07（国际超级计算大会）上，第29届TOP500超级计算机名单正式对外公布。本届排行榜的最大特点表现在：前十位的系统排名几乎全面洗牌，入选TOP500、TOP100的门槛大幅提升。排行榜

26、还反映了一些新的变化，如双核处理器已占据主流地位，InfiniBand份额大幅增加，欧洲HPC应用开始恢复，HP和IBM分列数量和性能两大赢家等。 全球最快的10台超级计算机排名排名所在地所在地厂商及计算机名称厂商及计算机名称1DOE/NNSA/LLNL United States IBM BlueGene/L 2Oak Ridge National LaboratoryUnited StatesCray Jaguar 3NNSA/Sandia National LaboratoriesUnited States Cray Red Storm4IBM Thomas J. Watson Rese

27、arch CenterUnited States IBM BGW5Stony Brook/BNL, New York Center for Computional SciencesUnited States IBM New York Blue6DOE/NNSA/LLNLUnited States IBM ASC Purple 7Rensselaer Polytechnic Institute, Computional Center for Nanotechnology InnovationsUnited States IBM eServer Blue Gene Solution8NCSAUni

28、ted States Dell Abe 9Barcelona Supercomputing CenterSpain IBM MareNostrum 10Leibniz RechenzentrumGermany SGI HLRB-II 关于死锁死锁（死锁（DeadlockDeadlock）, ,是指多个进程是指多个进程在运行过程中因争夺资源而造成的在运行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时，一种僵局，当进程处于这种状态时，若无外力作用，它们都将无法再向若无外力作用，它们都将无法再向前推进。前推进。3.5 产生死锁的原因和必要条件 3.5.1 3.5.1 产生死锁的原因产生死锁的

29、原因 3.5.2 3.5.2 产生死锁的必要条件产生死锁的必要条件 3.5.3 3.5.3 处理死锁的基本方法处理死锁的基本方法3.5.1 产生死锁的原因产生死锁的原因可归结为如下两点：产生死锁的原因可归结为如下两点：1.1. 竞争资源。竞争资源。2.2. 进程间推进顺序非法。进程间推进顺序非法。可剥夺和非剥夺性资源可剥夺和非剥夺性资源永久性资源和临时性资源永久性资源和临时性资源. Request(B); Request(A); Release(A); Release(B);P2. Request(A); Request(B); Release(B); Release(A);P1v例如：例如：

30、死锁发生：双方都拥有部分资源，同时在请求对方已死锁发生：双方都拥有部分资源，同时在请求对方已占有的资源。如次序：占有的资源。如次序：P1 P2 P1 P2竞争非剥夺性资源竞争非剥夺性资源P1:P2:v(consumable resource)：可以动态生成和消耗，可以动态生成和消耗，一般不限制数量。如硬件中断、信号、消息、缓冲一般不限制数量。如硬件中断、信号、消息、缓冲区内的数据。区内的数据。. Receive(P1,N); Send(P1,R);P2. Receive(P2,R); Send(P2,N);P1死锁发生：双方都等待对方去生成资源，死锁发生：双方都等待对方去生成资源，如次序：如次

31、序：P1 P2竞争临时性资源竞争临时性资源P1:P2:正确的进程推进顺序正确的进程推进顺序 P1: Release(S1); Request(S3); P2: Release(S2); Request(S1); P3: Release(S3); Request(S2); 死锁的进程推进顺序死锁的进程推进顺序 P1: Request(S3); Release(S1); P2: Request(S1); Release(S2); P3: Request(S2); Release(S3);进程推进顺序不当引起死锁进程推进顺序不当引起死锁S3S1S2P1P3P2P2Rel(R1)P2Rel(R2)P2

32、Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D进程推进顺序对死锁的影响进程推进顺序对死锁的影响3.5.2 产生死锁的必要条件虽然进程在运行过程中可能发生死锁，虽然进程在运行过程中可能发生死锁，但死锁的发生也必须具备一定的条件。但死锁的发生也必须具备一定的条件。可以看出，必须具备以下四个条件。可以看出，必须具备以下四个条件。3.5.2 产生死锁的必要条件 1 1. .互斥条件互斥条件：指进程对所分配到的资源指进程对所分配到的资源进行排他性使用，即在一段时间内某进行排他性使用，即在一段时间内某资源只由一个进程占用。如果此时还资源只由一个进

33、程占用。如果此时还有其他进程请求该资源，则请求者只有其他进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕能等待，直至占有该资源的进程用毕释放。释放。3.5.2 产生死锁的必要条件 2.2.请求和保持条件：请求和保持条件：指进程已经保持指进程已经保持了至少一个资源，但又提出了新的了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但又对占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放。自己已获得的其他资源保持不放。3.5.2 产生死锁的必要条件 3.3.不剥夺条件：不剥夺条件：指进程已获得的资源，指进程已获得的资源

34、，在未使用完之前，不能被剥夺，只在未使用完之前，不能被剥夺，只能在使用完时由自己释放。能在使用完时由自己释放。3.5.2 产生死锁的必要条件4.4.环路等待条件：环路等待条件：指在发生死锁时，必然指在发生死锁时，必然存在一个存在一个“进程进程资源资源”的环形链，的环形链，即进程集合即进程集合P0,P1,P2,P0,P1,P2,Pn,Pn中的中的P0P0正在等待一个正在等待一个P1P1占用的资源；占用的资源；P1P1正在正在等待一个等待一个P2P2占用的资源，占用的资源，PnPn正正在等待一个已被在等待一个已被P0P0占用的资源。占用的资源。3.5.3 处理死锁的基本方法一、预防死锁消除产生死锁

35、的必要条件二、避免死锁分配资源时防止进入不安全状态三、检测死锁不预防死锁，出现死锁就解除四、解除死锁与检测死锁配合使用思考题思考题 一台计算机共8台磁带机，由N个进程共享，每个进程最多要3台，问N为多少时不会有死锁，为什么？ 3.6 预防与避免死锁的方法 3.6.1 3.6.1 预防死锁预防死锁 3.6.2 3.6.2 系统安全状态系统安全状态 3.6.3 3.6.3 利用银行家算法避免死锁利用银行家算法避免死锁3.6.1 预防死锁 预防死锁的方法是使四个必要条件中的第2、3、4条件之一不能成立，来避免发生死锁。至于必要条件1，因为它是由设备的固有条件所决定的，不仅不能改变，还应加以保证。下面

36、分别对三种情况加以说明：1、摒弃“请求和保持”条件静态资源分配法静态资源分配法优点优点：算法简单、易于实现且很安全：算法简单、易于实现且很安全缺点缺点：资源浪费严重，进程延迟运行。：资源浪费严重，进程延迟运行。2、摒弃“不剥夺”条件 系统规定，进程是逐个地提出对资源的要求的。当一个已经保持了某些资源的进程，提出新的要求不被满足时必须释放它已经保持的所有资源，待以后需要时再重新申请。从而摒弃了“不剥夺”条件。 该方法实现起来比较复杂且付出很大代价。可能会造成前功尽弃，反复申请和释放(抖动)情况。3、摒弃“环路等待”条件 有序资源分配法： 与前两种策略比较，资源利用率和系统吞吐量都有较明显的改善。

37、 但也存在严重问题：为资源编号限制新设备的增加；进程使用设备顺序与申请顺序相反；限制用户编程自由。r1r2rkrm.申请次序申请次序3.6.2 系统安全状态 在避免死锁的方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可避免发生死锁。检测检测可满足请求可满足请求 分配分配 不分配不分配安全安全不安全不安全系统处于安全状态系统处于安全状态：存在安全进程序列：存在安全进程序列进程序列进程序列安全安全，p1,p2,pn可依次进行完。可依次进行完。安全安全不安全不安全死锁死锁1、安全状态2、安全状态之例 假定系统中有三个进程A、B和C，共有12台磁带机。进程A总共要求10

38、台，B和C分别要求4台和9台。假设在T0时刻，进程A、B和C已分别获得5台、2台和2台，尚有3台未分配，如下表所示：进程进程最大需求最大需求已分配已分配可用可用A1053B42C92233.6.3 利用银行家算法避免死锁1.1. 银行家算法中的数据结构银行家算法中的数据结构（1）可利用资源向量）可利用资源向量Available。这是一个含有。这是一个含有m个元素的个元素的数组，其中的每一个元素代表一类可利用的资源数目数组，其中的每一个元素代表一类可利用的资源数目;（2）最大需求矩阵）最大需求矩阵Max。这是一个。这是一个n*m的矩阵，它定义了系的矩阵，它定义了系统中统中n个进程中的每一个进程对

39、个进程中的每一个进程对m类资源的最大需求。类资源的最大需求。（3）分配矩阵）分配矩阵Allocation。这也是一个。这也是一个n*m的矩阵，它定义的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。了系统中每一类资源当前已分配给每一进程的资源数。（4）需求矩阵）需求矩阵Need。这也是一个。这也是一个n*m的矩阵，用以表示每的矩阵，用以表示每一个进程尚需的各类资源数。一个进程尚需的各类资源数。可利用资源向量Available(A B C)2 5 3最大需求矩阵 Max(A B C)P1 3 2 2P2 5 2 2P3 7 4 5分配矩阵Allocation(A B C) 2 0 0

40、 2 1 1 3 0 2需求矩阵Need(A B C) 1 2 2 3 1 1 4 4 3- -= =3.6.3 利用银行家算法避免死锁2.银行家算法银行家算法 设设Requesti是进程是进程Pi的请求向量，如果的请求向量，如果Requesti j=K，表示进程，表示进程Pi需要需要K个个Rj类型的资源。类型的资源。当当Pi发出资源请求后，系统按下述步骤进行发出资源请求后，系统按下述步骤进行检查：检查：Pi请求资源请求资源RequestI NeedI请求超量，错返请求超量，错返RequestI Available不满足，等待不满足，等待Available:=Available-Request

41、IAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI安全安全确认，分配完确认，分配完成成Available:=Available+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等待等待FTFTTF银行家算法案例3.6.3 利用银行家算法避免死锁3.安全性算法（1）设置两个向量： 工作向量work：表示系统可提供给进程继续运行的各类资源数目，在执行安全算法开始时，work:=Available; Finish:它表示系统是否有足够的资源分配进程，使之运行完成

42、。开始时先做Finishi:=false;当有足够资源分配给进程时，再令Finishi:=true。安全性检测算法FWork:=Available;Finish:=false; 有满足条件的有满足条件的j:Finishj=falseNeedj WorkFinishj=true;Work:=Work+AllocationjT j ,finishj=trueTF安全安全不安全不安全4、银行家算法之例 假定系统中有四个进程P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、4、7，在T0时刻的资源分配情况如下所示: 资源情况进程MaxA B CAllocationA B CNeed

43、A B C AvailableA B CP1P2P3P43 2 2 9 0 22 2 24 3 32 0 03 0 22 1 10 0 21 2 26 0 0 0 1 14 3 13 3 2 资源情况进程WorkA B CAllocationA B CAllocation+WorkFinish(1)T0时刻的安全性：4、银行家算法之例 资源情况进程MaxA B CAllocationA B CNeedA B C AvailableA B CP1P2P3P43 2 2 9 0 22 2 24 3 32 0 03 0 22 1 10 0 21 2 26 0 0 0 1 14 3 13 3 2Wor

44、k P1 3 3 22 0 0 5 3 2true P3 5 3 22 1 1 7 4 3true P4 7 4 30 0 2 7 4 5true P2 7 4 53 0 2 10 4 7trueT0时刻系统是安全的，存在安全序列P1,P3,P4,P2Request1(1,0,2)=Need1(1,2,3)；Request1(1,0,2)=Available(3,3,2)；试探性把资源分配给P1,并修改相应的数据,形成的资源变化情况上表所示；由所执行安全性检查得知:可以找到一个安全序列P1,P3,P4,P2,即此时系统是安全的,可以满足请求。 资源情况进程WorkA B CAllocation

45、A B CAllocation+WorkFinish(2)P1请求资源，发出请求向量 Request1(1,0,2)；4、银行家算法之例 资源情况进程MaxA B CAllocationA B CNeedA B C AvailableA B CP1P2P3P43 2 2 9 0 22 2 24 3 32 0 03 0 22 1 10 0 21 2 26 0 0 0 1 14 3 13 3 2Request1(1,0,2) P1 2 3 03 0 2 5 3 2true P3 5 3 22 1 1 7 4 3true P4 7 4 30 0 2 7 4 5true P2 7 4 53 0 2 1

46、0 4 7true2 3 03 0 20 2 0WorkRequest4(3,3,0)Need4(4,3,1)；Request4(3,3,0)Available(2,3,0)；(3)P4请求资源，发出请求向量 Request4(3,3,0)；4、银行家算法之例 资源情况进程MaxA B CAllocationA B CNeedA B C AvailableA B CP1P2P3P43 2 2 9 0 22 2 24 3 33 0 23 0 22 1 10 0 20 2 06 0 0 0 1 14 3 12 3 0Request4(3,3,0)当前系统资源不能满足P4的请求，不予分配；Reque

47、st4(0,2,0)Need4(4,3,1)；Request4(0,2,0)Available(2,3,0)；(4)P4请求资源，发出请求向量 Request4(0,2,0)；4、银行家算法之例 资源情况进程MaxA B CAllocationA B CNeedA B C AvailableA B CP1P2P3P43 2 2 9 0 22 2 24 3 33 0 23 0 22 1 10 0 20 2 06 0 0 0 1 14 3 12 3 0Request4(0,2,0)系统试探性为P4分配资源，并修改相应的数据，开成的资源分配情况如上所示；2 1 00 2 24 1 1Work进行安全

48、性检查：可用资源Available(2,1,0)已不能满足任何进程的需要，系统进入不安全状态，故系统不能满足P4的请求3.7 死锁的检测与解除 3.7.1 3.7.1 死锁的检测死锁的检测 3.7.2 3.7.2 死锁的解除死锁的解除3.7.1 死锁的检测当系统为进程分配资源时，若未采取任当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和何限制性措施，则系统必须提供检测和解除死锁的手段，为此系统必须：解除死锁的手段，为此系统必须：1.1. 保存有关资源的请求和分配信息；保存有关资源的请求和分配信息；2.2. 提供一种算法，以利用这些信息来检测提供一种算法，以利用这些信息来检测

49、系统是否已进入死锁状态。系统是否已进入死锁状态。1 资源分配图定义定义: G=(V,E), V=P R, P=p1,p2,pn, R=r1,r2,rm, E=(pi,rj) (rj,pi), pi P, rj R. 申请边申请边(pi,rj): pi申请申请rj； 分配边分配边(rj,pi): rj分配分配pi;图示：图示： 进程：进程： 资源：资源： 申请边：由进程到资源类；申请边：由进程到资源类； 分配边：由资源实例到进程。分配边：由资源实例到进程。r2 P2P1r11 资源分配图申请：申请：pi申请申请rj中的一个资源实例，由中的一个资源实例，由pi向向rj画一申画一申请边，如可满足，改

50、为分配边。请边，如可满足，改为分配边。释放：去掉分配边。释放：去掉分配边。例子（无环路，无死锁）p1p2p3r1r3r2r4例子（有环路，有死锁）p1p2p3r1r3r2r4例子（有环路，无死锁）p1p2p3p4r1r22、资源分配图的简化简化方法如下：1.在资源分配图中找出一个既不阻塞又非独立的进程结点Pi，在顺利的情况下运行完毕，释放其占有的全部资源。2.由于释放了资源，这样能使其它被阻塞的进程获得资源继续运行。3.在经过一系列简化后若能消去图中的所有的边，使所有进程结点都孤立，则称该图是可完全简化的，反之是不可完全简化的。3、死锁定理可以证明：可以证明：S S状态为死锁状态的充分条状态为

51、死锁状态的充分条件是当且仅当件是当且仅当S S状态的资源分配图是状态的资源分配图是不不可完全简化的可完全简化的。 例：根据死锁定理判断如下所示的资源分配图是否存在死锁。P1P2P3R1R2R3P1P3P2R1R2图图1图图23.7.2 死锁的解除当发现进程死锁时，便应立即把它们从死当发现进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用的方法是：锁状态中解脱出来。常采用的方法是：1.1. 剥夺资源。剥夺资源。从其他进程剥夺足够数量的资从其他进程剥夺足够数量的资源给死锁进程以解除死锁状态。源给死锁进程以解除死锁状态。2.2. 撤销进程。撤销进程。最简单的是让全部进程都死掉；最简单的是让全部进

52、程都死掉；温和一点的是按照某种顺序逐个撤销进程，温和一点的是按照某种顺序逐个撤销进程，直至有足够的资源可用，使死锁状态消除直至有足够的资源可用，使死锁状态消除为止。为止。本章基础要点1.1. 要使当前运行进程总是优先级最高的进程，要使当前运行进程总是优先级最高的进程，则应选择：则应选择：抢占优先级调度算法。抢占优先级调度算法。2.在分时系统中，进程调度经常采用：在分时系统中，进程调度经常采用：时间片轮转调度算法。时间片轮转调度算法。3.进程运行结束、进入阻塞状态、时间片用进程运行结束、进入阻塞状态、时间片用完、有更高优先级的进程进入就绪队列等完、有更高优先级的进程进入就绪队列等原因均可引起：原

53、因均可引起：进程调度。进程调度。本章基础要点本章基础要点4.进程调度采用时间片轮转法时，时间片过进程调度采用时间片轮转法时，时间片过大，就会使轮转法转化为：大，就会使轮转法转化为：先来先服务调度算法。先来先服务调度算法。5.进程的调度方式有两种：进程的调度方式有两种：抢占式调度和非抢占式调度。抢占式调度和非抢占式调度。6.死锁产生的四个必要条件是：死锁产生的四个必要条件是：互斥、请求和保持、不剥夺和环路等待。互斥、请求和保持、不剥夺和环路等待。7.在有在有m个进程的系统中出现死锁时，死锁进个进程的系统中出现死锁时，死锁进程的个数程的个数k应满足的条件是：应满足的条件是：2 k m。本章基础要点

54、本章基础要点8.不让死锁发生的策略可分为静态和动态两不让死锁发生的策略可分为静态和动态两种，死锁避免属于：种，死锁避免属于：动态策略。动态策略。9.某系统中有某系统中有3个并发进程，都需要同类资源个并发进程，都需要同类资源4个，该系统绝对不会发生死锁的最少资源个个，该系统绝对不会发生死锁的最少资源个数是：数是：10。10.资源的按序分配策略可以破坏：资源的按序分配策略可以破坏：环路等待条件环路等待条件。11.预先静态分配法可以破坏：预先静态分配法可以破坏：请求和保持条件请求和保持条件。课堂练习课堂练习一个系统具有150个存储单元，在T0时刻按下表所示分配给3个进程。 资源资源进程进程Maxallocationp17025P26040P36045对下列请求应用银行家算法分别分析判断是否安全？1) 第4个进程P4到达，最大需求60个存储单元，当前分配25个单元。2) 第4个进程P4到达，最大需求50个存储单元，当前分配35个单元。如果是安全的，请给出一个可能的安全序列；如果不是安全的，请说明原因。