资源分配与处理机调度第四章

第四章资源分配与处理机调度1资源分配与处理机调度第四章共34页，您现在浏览的是第1页!本章要点（1）一、资源分配两种资源分配方式静态分配动态分配死锁定义、起因、产生死锁的必要条件、不产生死锁的最小资源数规避死锁的方法预防避免检测与恢复

银行家算法2资源分配与处理机调度第四章共34页，您现在浏览的是第2页!本章要点（2）二、处理机调度处理机的二级调度作业级调度进程级调度作业调度作业状态：提交、后备、执行、完成作业控制块JCB作业调度的性能评价－平均周转时间、平均带权周转时间作业调度算法（FCFS、SJF、HRRN、优先数、RR等）进程调度的主要任务Unix进程调度：基于优先数的多级反馈轮转算法

静态设置动态计算3资源分配与处理机调度第四章共34页，您现在浏览的是第3页!4.1资源分配2、资源分配的两种方式静态分配：在作业级实施

当一个作业运行前，将它要求的所有资源一次性分配给该作业，直到该作业完成时释放其占用的所有资源，分配给作业的资源伴随作业的整个运行过程。

缺点：效率太低动态分配：在进程级实施

当一个进程要求使用某个（类）资源时，向系统提出资源的请求，系统响应进程的请求将某种资源分配给进程，进程使用完毕后立即释放该资源

优点：系统资源的利用率提高 缺点：有可能造成死锁4资源分配与处理机调度第四章共34页，您现在浏览的是第4页!4.2死锁分配分配请求请求P1P2R1R2一种死锁状态[例1]：假设系统中有P1、P2两个进程并发执行，P1和P2在执行中都同时需要资源R1和R2，R1和R2都是一次只能给一个进程使用的临界资源，如左图所示。而右图则标示了系统在某种资源分配方式下产生的死锁状态。5资源分配与处理机调度第四章共34页，您现在浏览的是第5页!4.2死锁产生死锁的根本原因：系统资源不足

死锁是资源竞争和资源分配不合理两个因素同时作用所产生的可能结果

资源不足资源共享资源竞争合理分配不合理分配提高资源利用率死锁6资源分配与处理机调度第四章共34页，您现在浏览的是第6页!4.2死锁产生死锁的四个必要条件：1、互斥条件：并发进程所请求的资源是互斥使用的独占资源，即一次只能被一个进程使用的资源，具有排它性。

2、不可剥夺条件（请求和保持）进程所占有的资源在没有使用完之前不能被其它进程强行占用，只能由占有该资源的进程自己释放。

3、部分分配：进程对于自己所需要的资源每次只请求一部分，操作系统允许部分资源的分配。4、环路条件：系统中各并发进程对于资源的占有和请求形成环路，即请求箭头方向和占有箭头方向形成环路

7资源分配与处理机调度第四章共34页，您现在浏览的是第7页!4.2死锁1.死锁的预防（针对发生死锁的4个必要条件）条件1（互斥）：是资源本身固有的特性，很难改变和破坏的，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备；条件2（不可剥夺）：较难否定，但可制定相应的规则，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请；对CPU还可进行可剥夺分配。条件3（部分分配）：容易否定，只要分配策略上规定每个进程一次性将所需资源全部申请到位，用完后释放。（静态分配）条件4（环路）：容易否定，采用有序分配，将资源编号，各进程对于资源的请求只能按号的递增进行，比如请求了R1才能请求R2，从而破坏环路条件预防死锁。8资源分配与处理机调度第四章共34页，您现在浏览的是第8页!4.2死锁2、死锁的避免

指操作系统在动态分配过程中对每一次的分配都要采取某种策略去判断一下当前的分配有没有导致死锁的可能性，没有则实施分配，有则拒绝分配，从而动态地避免死锁的产生。

最有代表性的死锁避免算法是DijkstraE.W于1968年提出的银行家算法，该算法借鉴了银行家对于项目投资的管理经验到，银行家总是希望：1、使用最多的项目同时开工，以获取最大的回报。2、保证至少有一个项目能完成，避免所有项目都在进行之中而手中却无钱周转（即进入死锁）。9资源分配与处理机调度第四章共34页，您现在浏览的是第9页!4.2死锁3、死锁的检测与恢复

死锁的检测与恢复是指系统设置专门机构，在死锁发生时该机构能够及时检测出死锁发生的位置和原因，并能够通过外力破坏死锁产生的一个必要条件，从而使并发进程能够从死锁状态中恢复出来。

死锁检测算法类似于银行家算法，如果某时刻所有进程不能全部进入安全序列，它们将死锁。10资源分配与处理机调度第四章共34页，您现在浏览的是第10页!4.3处理机的多级调度1、处理机调度的目标：公平：确保每个进程都能公平地占有处理机高效：使处理机尽可能忙响应时间快：与用户交互快捷周转时间短：用户等待输出的时间短系统吞吐量大：相同时间内完成的作业尽可能多11资源分配与处理机调度第四章共34页，您现在浏览的是第11页!4.4作业调度

1、作业的4个状态：提交状态：用户将程序提交给系统，等待输入。后备状态：系统响应用户请求，将作业输入到磁盘上，等待作业调度。执行状态：该作业被调度进入内存，并创建相应的进程，插入进程就绪队列。完成状态：作业执行结束，并释放其占用的所有系统资源。12资源分配与处理机调度第四章共34页，您现在浏览的是第12页!4.4作业调度2、作业控制块JCB（JobControlBlock)，它是存放作业控制和管理信息的数据结构，是作业存在的唯一标识，是操作系统调度的依据。主要信息见右图。13资源分配与处理机调度第四章共34页，您现在浏览的是第13页!4.4作业调度4、作业调度算法先来先服务FCFS:按作业提交的先后次序进行调度的短作业优先SJF：选择运行时间最小的作业进行调度响应比高优先HRRN：响应比＝优先数调度时间片轮转RR最短剩余时间优先SRT多级反馈队列FB

运行时间等待时间14资源分配与处理机调度第四章共34页，您现在浏览的是第14页!4.5进程调度作业调度：长程调度进程调度： 中程调度（就绪且换出－>就绪 阻塞且换出－>阻塞）

涉及到内存和交换区的切换 短程调度（就绪－>运行）

涉及到处理机的直接分配15资源分配与处理机调度第四章共34页，您现在浏览的是第15页!4.5进程调度1、进程上下文进程上下文指发生进程切换时的运行现场，它由进程的正文段、数据段、CPU的寄存器以及有关的数据结构组成。对于处理机而言，进程上下文是当前终止执行的进程现场（上文）与即将运行的进程现场（下文），上下文切换的主要任务是保存当前进程的现场信息，加载或恢复新进程的现场信息，使处理机实现在进程之间的切换。

16资源分配与处理机调度第四章共34页，您现在浏览的是第16页!4.5进程调度调度进程：组织和维护就绪进程队列。包括确定调度算法、按调度算法管理就绪进程队列。分派进程：是指当处理机空闲时，从就绪队列中选取队列头的一个进程实施处理机的分配，并负责进行处理机上下文的切换。

进程调度与进程控制和进程通信的功能有密切的联系，当一个进程阻塞时，这个进程将被调度进程调度到相应的等待队列中，并让出CPU，由分派进程选择一个就绪进程占用CPU；当一进程被唤醒时，调度进程也会将其插入到就绪进程队列中。17资源分配与处理机调度第四章共34页，您现在浏览的是第17页!4.5进程调度3、进程调度的时机：进程执行了终止函数，进入僵死状态。进程执行了阻塞原语将自己阻塞，放弃了处理机。进程执行了请求I/O操作后进入阻塞态，放弃了处理机。进程执行了P操作，因为条件不满足而阻塞，放弃了处理机。在分时系统中执行进程的时间片用完。在执行完用户请求的系统调用后，由系统调用返回时。在可剥夺方式下，当就绪进程的优先级高于执行进程时。18资源分配与处理机调度第四章共34页，您现在浏览的是第18页!4.1资源分配1、操作系统对资源管理和分配的目标保证资源有高的利用率；在合理的时间内使所有用户进程具有获得所需资源的机会；对不可共享的资源实施互斥使用；防止由于资源分配不合理而引起的死锁。19资源分配与处理机调度第四章共34页，您现在浏览的是第19页!4.2死锁5.2.1死锁的概念死锁：系统中所有的并发进程彼此互相等待对方所拥有的资源，且它们在得到对方资源之前不会释放自己所拥有的资源，从而造成互相死等，却永远等不到的一种任一进程都不能继续运行的系统状态。

在死锁状态下，进程都处于阻塞态，解除它们阻塞的事件或条件永远也不会发生20资源分配与处理机调度第四章共34页，您现在浏览的是第20页!4.2死锁可能产生死锁的情况：当缓冲区满时，若生产者先到，它可顺利执行p(mutex)操作取得对缓冲区的使用权，但是当它执行p(empty)时，由于没有空缓冲区而被挂起。能将这个生产者唤醒的只能是有一个消费者从缓冲区中取走一个产品，并执行v(empty)操作，但由于缓冲区已被不能存放产品的生产者占用，任何消费者都进不去，因而出现了死锁。反之，当缓冲区空时消费者先到也会出现死锁。[例2]：在前面学过的生产者－消费者问题中，如果将两个p操作的次序颠倒，如图所示，会不会发生死锁？如果会，在什么样的情况下发生？颠倒后的：P生产者（）{P(mutex)；P(empty)；送一个产品到缓冲区；V(mutex)；V(full)；}21资源分配与处理机调度第四章共34页，您现在浏览的是第21页!4.2死锁如果不考虑资源分配的合理性，若要不产生死锁，则资源的个数必须满足以下条件（即系统不会产生死锁的最小资源数）：设系统所拥有的资源总数为M，共享该资源的进程数为P，每个进程所需使用该资源的最大需求为N，则

M≥P*(N-1)+1时无论如何分配都不会产生死锁。22资源分配与处理机调度第四章共34页，您现在浏览的是第22页!4.2死锁规避死锁的3种方法1、预防－－－静态（执行前保证）2、避免－－－动态（执行中保证）3、检测与恢复23资源分配与处理机调度第四章共34页，您现在浏览的是第23页!4.2死锁预防死锁的缺陷：

1.用户进程必须事先列出所有需要的资源，以便系统一次性分配； 2.系统一次性分配给进程的资源在很多时间内是处于空闲状态的； 3.用户进程必须得到所有资源才能运行，减低了并发度，增加了等待时间。总结：

采用静态预防的方式来解决死锁问题牺牲了资源的利用率，而资源利用率的降低直接导致并发度的降低。

24资源分配与处理机调度第四章共34页，您现在浏览的是第24页!4.2死锁2个概念——安全序列和安全状态：安全序列——在该序列中所有的进程都可以因为之前进程的完成所释放的资源使得它们一个接一个的完成。 表示为<Pi,Pj,……Pm>，其中Pi,Pj…Pm代表系统中的进程安全状态——如果系统中的所有进程至少能找到一个安全序列，则称系统当前处于安全状态。注意：安全序列必须包括当前系统中所有进程，如果某个进程因资源不够而不能完成，则不存在安全序列，当前系统就处于不安全状态，可能导致死锁；如果系统在任意时刻都处于安全状态，则系统就是安全的，不会有死锁发生。

25资源分配与处理机调度第四章共34页，您现在浏览的是第25页!4.2死锁死锁排除的方法：1、撤消陷于死锁的全部进程；2、逐个撤消陷于死锁的进程，直到死锁不存在；3、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失。26资源分配与处理机调度第四章共34页，您现在浏览的是第26页!4.3处理机的多级调度2、处理机的两级调度宏观调度：作业调度微观调度：进程调度（在作业处于执行状态下） 线程调度（在进程处于运行状态下）27资源分配与处理机调度第四章共34页，您现在浏览的是第27页! 作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。作业调度功能：1.分配作业控制块JCB；2.按一定的调度算法，从后备作业中选择一个或几个作业进入系统内存；3.为被选中的作业创建进程，并且为其申请系统资源；4.作业结束后作善后处理工作。4.4作业调度

28资源分配与处理机调度第四章共34页，您现在浏览的是第28页!4.4作业调度3、作业调度的性能衡量指标：

平均周转时间和带权平均周转时间周转时间＝完成时间－提交时间＝等待时间＋执行时间平均周转时间T＝周转时间总和÷作业数带权周转＝周转时间÷执行时间平均