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

1、12一、资源分配一、资源分配 两种资源分配方式两种资源分配方式 静态分配 动态分配 死锁死锁 定义、起因、产生死锁的必要条件、不产生死锁的最小资源数 规避死锁的方法规避死锁的方法预防避免检测与恢复 银行家算法银行家算法3二、处理机调度处理机调度 处理机的二级调度处理机的二级调度 作业级调度 进程级调度 作业调度作业调度 作业状态：提交、后备、执行、完成 作业控制块jcb 作业调度的性能评价平均周转时间、平均带权周转时间 作业调度算法（fcfs、sjf、hrrn、优先数、rr等） 进程调度的主要任务进程调度的主要任务 unix进程调度：进程调度：基于优先数的多级反馈轮转算法基于优先数的多级反馈轮

2、转算法 静态设置 动态计算41、操作系统对资源管理和分配的目标操作系统对资源管理和分配的目标保证资源有高的利用率；保证资源有高的利用率；在合理的时间内使所有用户进程具有获得所在合理的时间内使所有用户进程具有获得所需资源的机会；需资源的机会；对不可共享的资源实施互斥使用；对不可共享的资源实施互斥使用；防止由于资源分配不合理而引起的死锁。防止由于资源分配不合理而引起的死锁。52 2、资源分配的两种方式、资源分配的两种方式静态分配静态分配：在在作业级作业级实施实施当一个作业运行前，将它要求的所有资源一次性分配给该作业，直到该作业完成时释放其占用的所有资源，分配给作业的资源伴随作业的整个运行过程。缺点

3、：效率太低缺点：效率太低动态分配动态分配：在在进程级进程级实施实施当一个进程要求使用某个（类）资源时，向系统提出资源的请求，系统响应进程的请求将某种资源分配给进程，进程使用完毕后立即释放该资源优点：系统资源的利用率提高优点：系统资源的利用率提高缺点：有可能造成死锁缺点：有可能造成死锁65.2.15.2.1死锁的概念死锁的概念 死锁：死锁：系统中所有的系统中所有的并发进程彼此互相等待对方所拥有的资源，且它们在得到对方资源之前不会释放自己所拥有的资源，从而造成互相死等，却永远等不到的一种任一进程都不能继续运行的系统系统状态。在死锁状态下，进程都处于阻塞态，解在死锁状态下，进程都处于阻塞态，解除它们

4、阻塞的事件或条件永远也不会发生除它们阻塞的事件或条件永远也不会发生7分配分配请求请求p1p2r1r2一种死锁状态例1：假设系统中有p1、p2两个进程并发执行，p1和p2在执行中都同时需要资源r1和r2，r1和r2都是一次只能给一个进程使用的临界资源，如左图所示。而右图则标示了系统在某种资源分配方式下产生的死锁状态。8 可能产生死锁的情况：可能产生死锁的情况：当缓冲区满时当缓冲区满时，若生产者先到，若生产者先到，它可，它可顺利执行顺利执行p(mutex)p(mutex)操作取得对缓冲操作取得对缓冲区的使用权，区的使用权，但是但是当它执行当它执行p(empty)p(empty)时，由于没有空缓冲区

5、而被挂起。时，由于没有空缓冲区而被挂起。能将这个生产者唤醒的只能是有一能将这个生产者唤醒的只能是有一个消费者从缓冲区中取走一个产品，个消费者从缓冲区中取走一个产品，并执行并执行v(empty)v(empty)操作，操作，但由于缓冲但由于缓冲区已被不能存放产品的生产者占用，区已被不能存放产品的生产者占用，任何消费者都进不去，因而任何消费者都进不去，因而出现了出现了死锁。死锁。反之，反之，当缓冲区空时当缓冲区空时消费者先到也会消费者先到也会出现死锁出现死锁。例2：在前面学过的生产者消费者问题中，如果将两个p操作的次序颠倒，如图所示，会不会发生死锁？如果会，在什么样的情况下发生？颠倒后的：p生产者（

6、）p(mutex)；p(empty)；送一个产品到缓冲区； v(mutex)； v(full)；9产生死锁的根本原因：产生死锁的根本原因：系统资源不足系统资源不足 死锁是死锁是资源竞争资源竞争和和资源分配不合理资源分配不合理两两个因素同时作用所产生的可能结果个因素同时作用所产生的可能结果资源不足资源共享资源竞争合理分配不合理分配提高资源利用率死锁10 如果不考虑资源分配的合理性，若要不产如果不考虑资源分配的合理性，若要不产生死锁，则资源的个数必须满足以下条件生死锁，则资源的个数必须满足以下条件（即（即系统不会产生死锁的最小资源数系统不会产生死锁的最小资源数）：）：设系统所拥有的资源总数为设系统

7、所拥有的资源总数为m m，共享该资源的，共享该资源的进程数为进程数为p p，每个进程所需使用该资源的最，每个进程所需使用该资源的最大需求为大需求为n n，则，则 mpmp* *(n-1)+1(n-1)+1 时时无论如何分配都不会产生死锁。无论如何分配都不会产生死锁。11产生死锁的四个产生死锁的四个必要条件必要条件：1 1、互斥条件：、互斥条件：并发进程所请求的资源是并发进程所请求的资源是互斥使用的独占资源，即一次只能被一互斥使用的独占资源，即一次只能被一个进程使用的资源，具有排它性。个进程使用的资源，具有排它性。2 2、不可剥夺条件（请求和保持、不可剥夺条件（请求和保持）进程所进程所占有的资源

8、在没有使用完之前不能被其占有的资源在没有使用完之前不能被其它进程强行占用，只能由占有该资源的它进程强行占用，只能由占有该资源的进程自己释放。进程自己释放。3 3、部分分配：、部分分配：进程对于自己所需要的资进程对于自己所需要的资源每次只请求一部分，操作系统允许部源每次只请求一部分，操作系统允许部分资源的分配。分资源的分配。4 4、环路条件：、环路条件：系统中各并发进程对于资系统中各并发进程对于资源的占有和请求形成环路，即请求箭头源的占有和请求形成环路，即请求箭头方向和占有箭头方向形成环路方向和占有箭头方向形成环路12规避死锁的规避死锁的3 3种方法种方法1 1、预防静态（执行前保证）、预防静态

9、（执行前保证）2 2、避免动态（执行中保证）、避免动态（执行中保证）3 3、检测与恢复、检测与恢复131.1.死锁的预防（针对发生死锁的死锁的预防（针对发生死锁的4 4个必要条件）个必要条件）条件条件1 1（互斥）：（互斥）：是是资源本身固有的特性，很难改变和破资源本身固有的特性，很难改变和破坏的坏的，但可采用相应的技术，如利用，但可采用相应的技术，如利用假脱机技术假脱机技术，即，即用可共享使用的设备模拟非共享的设备；用可共享使用的设备模拟非共享的设备；条件条件2 2（不可剥夺）：（不可剥夺）：较难否定，但可制定相应的规则，较难否定，但可制定相应的规则，例如，当一个进程（程序）申请某资源被拒绝

10、，则必例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起须释放已占用的资源，如需要再与其它所需资源一起申请；对申请；对cpucpu还可进行可剥夺分配。还可进行可剥夺分配。条件条件3 3（部分分配）：（部分分配）：容易否定，只要分配策略上规定每容易否定，只要分配策略上规定每个进程一次性将所需资源全部申请到位，用完后释放。个进程一次性将所需资源全部申请到位，用完后释放。（静态分配）（静态分配）条件条件4 4（环路）：（环路）：容易否定，采用容易否定，采用有序分配有序分配，将资源编号，将资源编号，各进程对于资源的请求只能按号的递增进行，比如请各进程对于资源的

11、请求只能按号的递增进行，比如请求了求了r1r1才能请求才能请求r2r2，从而破坏环路条件预防死锁。，从而破坏环路条件预防死锁。 14预防死锁的缺陷：预防死锁的缺陷：1.1.用户进程必须事先列出所有需要的资源，以用户进程必须事先列出所有需要的资源，以便系统一次性分配；便系统一次性分配；2.2.系统一次性分配给进程的资源在很多时间内系统一次性分配给进程的资源在很多时间内是处于空闲状态的；是处于空闲状态的；3.3.用户进程必须得到所有资源才能运行，减低用户进程必须得到所有资源才能运行，减低了并发度，增加了等待时间。了并发度，增加了等待时间。总结：总结：采用静态预防的方式来解决死锁问题采用静态预防的方

12、式来解决死锁问题牺牲牺牲了资源的利用率了资源的利用率，而资源利用率的降低直接导，而资源利用率的降低直接导致并发度的降低。致并发度的降低。152 2、死锁的避免、死锁的避免指操作系统在动态分配过程中对每一次的分指操作系统在动态分配过程中对每一次的分配都要采取配都要采取某种策略某种策略去判断一下当前的分配有去判断一下当前的分配有没有导致死锁的可能性，没有则实施分配，有没有导致死锁的可能性，没有则实施分配，有则拒绝分配，从而动态地避免死锁的产生则拒绝分配，从而动态地避免死锁的产生。最有代表性的死锁避免算法是最有代表性的死锁避免算法是dijkstra e.w 于于1968年提出的年提出的银行家算法银行

13、家算法，该算法借，该算法借鉴了银行家对于项目投资的管理经验到，银行鉴了银行家对于项目投资的管理经验到，银行家总是希望：家总是希望：1、使用最多的项目同时开工，以获取最大的回、使用最多的项目同时开工，以获取最大的回报。报。2、保证至少有一个项目能完成，避免所有项目、保证至少有一个项目能完成，避免所有项目都在进行之中而手中却无钱周转（即进入死都在进行之中而手中却无钱周转（即进入死锁）。锁）。 162 2个概念个概念安全序列和安全状态安全序列和安全状态： 安全序列安全序列在该序列中所有的进程都可以在该序列中所有的进程都可以因为之前进程的完成所释放的资源使得它们因为之前进程的完成所释放的资源使得它们一

14、个接一个的完成。一个接一个的完成。表示为表示为pi,pj,pm，其中，其中pi,pj pi,pj pmpm代表系统中的进程代表系统中的进程 安全状态安全状态如果系统中的如果系统中的所有进程至少能所有进程至少能找到一个安全序列，则称系统当前处于安全找到一个安全序列，则称系统当前处于安全状态状态。注意：安全序列必须包括当前系统中所有进程，注意：安全序列必须包括当前系统中所有进程，如果某个进程因资源不够而不能完成，则不如果某个进程因资源不够而不能完成，则不存在安全序列，当前系统就处于不安全状态，存在安全序列，当前系统就处于不安全状态，可能导致死锁；如果系统在任意时刻都处于可能导致死锁；如果系统在任意

15、时刻都处于安全状态，则系统就是安全的，不会有死锁安全状态，则系统就是安全的，不会有死锁发生。发生。173 3、死锁的检测与恢复、死锁的检测与恢复死锁的检测与恢复是指系统设置专门机构，在死锁发生时该机构能够及时检测出死锁发生的位置和原因，并能够通过外力破坏死锁产生的一个必要条件，从而使并发进程能够从死锁状态中恢复出来。死锁检测算法类似于银行家算法，如果某时刻所有进程不能全部进入安全序列，它们将死锁。18死锁排除的方法：死锁排除的方法：1 1、撤消陷于死锁的全部进程；、撤消陷于死锁的全部进程；2 2、逐个撤消陷于死锁的进程，直到死锁不存、逐个撤消陷于死锁的进程，直到死锁不存在；在；3 3、从陷于死

16、锁的进程中逐个强迫放弃所占用、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失。的资源，直至死锁消失。191、处理机调度的目标：、处理机调度的目标： 公平公平：确保每个进程都能公平地占有处理机 高效高效：使处理机尽可能忙 响应时间快响应时间快：与用户交互快捷 周转时间短周转时间短：用户等待输出的时间短 系统吞吐量大系统吞吐量大：相同时间内完成的作业尽可能多202 2、处理机的两级调度、处理机的两级调度宏观调度：作业调度宏观调度：作业调度微观调度：进程调度（在作业处于执行状态下）微观调度：进程调度（在作业处于执行状态下） 线程调度（在进程处于运行状态下）线程调度（在进程处于运行状态下）2

17、11 1、作业的、作业的4 4个状态：个状态： 提交状态提交状态：用户将程序提交给系统，等：用户将程序提交给系统，等待输入。待输入。 后备状态后备状态：系统响应用户请求，将作业：系统响应用户请求，将作业输入到磁盘上，等待作业调度。输入到磁盘上，等待作业调度。 执行状态执行状态：该作业被调度进入内存，并：该作业被调度进入内存，并创建相应的进程，插入进程就绪队列。创建相应的进程，插入进程就绪队列。 完成状态完成状态：作业执行结束，并释放其占：作业执行结束，并释放其占用的所有系统资源。用的所有系统资源。22作业调度的作业调度的主要任务主要任务是完成作业从是完成作业从后后备备状态到状态到执行执行状态和

18、从状态和从执行执行状态到状态到完成完成状态的转变。状态的转变。作业调度功能：作业调度功能：1.1.分配作业控制块分配作业控制块jcbjcb；2.2.按一定的调度算法，从后备作业中选择按一定的调度算法，从后备作业中选择一个或几个作业进入系统内存；一个或几个作业进入系统内存；3.3.为被选中的作业创建进程，并且为其申为被选中的作业创建进程，并且为其申请系统资源；请系统资源；4.4.作业结束后作善后处理工作。作业结束后作善后处理工作。23 2、作业控制块作业控制块jcbjcb（job control block)，它是存放作业控制和管理信息的数据结构，是作业存在的唯一标识，是操作系统调度的依据。 主

19、要信息见右图。243 3、作业调度的性能衡量指标：、作业调度的性能衡量指标：平均周转时间平均周转时间和和带权平均周转时间带权平均周转时间u周转时间完成时间提交时间等待周转时间完成时间提交时间等待 时间执行时间时间执行时间u平均周转时间平均周转时间t t周转时间总和周转时间总和作业数作业数u带权周转周转时间带权周转周转时间执行时间执行时间u平均带权周转时间平均带权周转时间w w带权周转总和带权周转总和作作业数业数 254 4、作业调度算法、作业调度算法 先来先服务先来先服务fcfs:fcfs:按作业提交的先后次序按作业提交的先后次序进行调度的进行调度的 短作业优先短作业优先sjfsjf：选择运行

20、时间最小的作业进选择运行时间最小的作业进行调度行调度 响应比高优先响应比高优先hrrnhrrn：响应比响应比 优先优先数调度数调度 时间片轮转时间片轮转rrrr 最短剩余时间优先最短剩余时间优先srt srt 多级反馈队列多级反馈队列fbfb运行时间等待时间2627 作业调度：长程调度作业调度：长程调度 进程调度进程调度：中程调度（就绪且换出中程调度（就绪且换出 就绪就绪 阻塞且换出阻塞且换出 阻塞）阻塞）涉及到内存和交换区的切换涉及到内存和交换区的切换 短程调度（就绪短程调度（就绪 运行）运行）涉及到处理机的直接分配涉及到处理机的直接分配28新新建建就就绪绪就绪就绪且换且换出出运运行行长程调

21、度长程调度长程调度长程调度短程调度短程调度中程调度中程调度阻塞阻塞且换且换出出阻阻塞塞中程调度中程调度图 处理机的长程、中程和短程调度之间的关系291 1、进程上下文、进程上下文 进程上下文指发生进程切换时的运行现场，它由进程上下文指发生进程切换时的运行现场，它由进程的正文段、数据段、进程的正文段、数据段、cpucpu的寄存器以及有关的的寄存器以及有关的数据结构组成。数据结构组成。 对于处理机而言，进程上下文是对于处理机而言，进程上下文是当前终止执行的当前终止执行的进程现场进程现场（上文）与（上文）与即将运行的进程现场即将运行的进程现场（下（下文），上下文切换的主要任务是保存当前进程的文），上

22、下文切换的主要任务是保存当前进程的现场信息，加载或恢复新进程的现场信息，使处现场信息，加载或恢复新进程的现场信息，使处理机实现在进程之间的切换。理机实现在进程之间的切换。302 2、进程调度的功能、进程调度的功能 记录系统中所有进程的执行情况记录系统中所有进程的执行情况 选择进程，对其实施处理机的分配选择进程，对其实施处理机的分配 进行进程上下文的切换进行进程上下文的切换进程调度涉及到进程调度涉及到就绪队列的管理就绪队列的管理和和处处理机分配理机分配的双重任务，很多操作系统将的双重任务，很多操作系统将这两个任务分别用两个系统进程来完成：这两个任务分别用两个系统进程来完成：调度进程调度进程和和分派进程分派进程。31调度进程调度进程：组织和维护就绪进程队列。组织和维护就绪进程队列。包括确定调度算法、按调度算法管理包括确定调度算法、按调度算法管理就绪进程队列。就绪进程队列。分派进程分派进程：是指当处理机空闲时，从就是指当处理机空闲时，从就绪队列中选取队列头的一个进程实施绪队列中选取队列头的一个进程实施处理机的分配，并负责进行处理机上处理机的分配，并负责进行处理机上下文的切换。下文的切换。 进程调度与进程控制和进程通信的功能进程调度与进程控制和进程通信的功能有密切的联系，当一个