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

《资源分配与处理机调度第四章.ppt》由会员分享，可在线阅读，更多相关《资源分配与处理机调度第四章.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 资源分配与资源分配与处理机调度处理机调度1本本章要点（章要点（1）一、资源分配一、资源分配两种资源分配方式两种资源分配方式静态分配动态分配死锁死锁定义、起因、产生死锁的必要条件、不产生死锁的最小资源数规避死锁的方法规避死锁的方法预防避免检测与恢复银行家算法银行家算法2本本章要点（章要点（2）二、处理机调度处理机调度处理机的二级调度处理机的二级调度作业级调度进程级调度作业调度作业调度作业状态：提交、后备、执行、完成作业控制块JCB作业调度的性能评价平均周转时间、平均带权周转时间作业调度算法（FCFS、SJF、HRRN、优先数、RR等）进程调度的主要任务进程调度的主要任务Unix进程

2、调度：进程调度：基于优先数的多级反馈轮转算法基于优先数的多级反馈轮转算法静态设置动态计算34 4.1.1资源分配资源分配1、操作系统对资源管理和分配的目标操作系统对资源管理和分配的目标保证资源有高的利用率；保证资源有高的利用率；在合理的时间内使所有用户进程具有获得所需在合理的时间内使所有用户进程具有获得所需资源的机会；资源的机会；对不可共享的资源实施互斥使用；对不可共享的资源实施互斥使用；防止由于资源分配不合理而引起的死锁。防止由于资源分配不合理而引起的死锁。44 4.1.1资源分配资源分配2 2、资源分配的两种方式、资源分配的两种方式静态分配静态分配：在在作业级作业级实施实施当一个作业运行前

3、，将它要求的所有资源一次性分配给该作业，直到该作业完成时释放其占用的所有资源，分配给作业的资源伴随作业的整个运行过程。缺点：效率太低缺点：效率太低动态分配动态分配：在在进程级进程级实施实施当一个进程要求使用某个（类）资源时，向系统提出资源的请求，系统响应进程的请求将某种资源分配给进程，进程使用完毕后立即释放该资源优点：系统资源的利用率提高优点：系统资源的利用率提高缺点：有可能造成死锁缺点：有可能造成死锁54 4.2.2死锁死锁5.2.15.2.1死锁的概念死锁的概念死锁：死锁：系统中所有的系统中所有的并发进程彼此互相等待对方所拥有的资源，且它们在得到对方资源之前不会释放自己所拥有的资源，从而造

4、成互相死等，却永远等不到的一种任一进程都不能继续运行的系统系统状态。在死锁状态下，进程都处于阻塞态，解在死锁状态下，进程都处于阻塞态，解除它们阻塞的事件或条件永远也不会发生除它们阻塞的事件或条件永远也不会发生64 4.2.2死锁死锁分配分配请求请求P1P2R1R2一种死锁状态例1：假设系统中有P1、P2两个进程并发执行，P1和P2在执行中都同时需要资源R1和R2，R1和R2都是一次只能给一个进程使用的临界资源，如左图所示。而右图则标示了系统在某种资源分配方式下产生的死锁状态。74 4.2.2死锁死锁可能产生死锁的情况：可能产生死锁的情况：当当缓缓冲冲区区满满时时，若若生生产产者者先先到到，它它

5、可可顺顺利利执执行行p(mutexp(mutex)操操作作取取得得对对缓缓冲冲区区 的的 使使 用用 权权，但但 是是 当当 它它 执执 行行p(empty)p(empty)时时，由由于于没没有有空空缓缓冲冲区区而而被被挂挂起起。能能将将这这个个生生产产者者唤唤醒醒的的只只能能是是有有一一个个消消费费者者从从缓缓冲冲区区中中取取走走一一个个产产品品，并并执执行行v(empty)v(empty)操操作作，但但由由于于缓缓冲冲区区已已被被不不能能存存放放产产品品的的生生产产者者占占用用，任任何何消消费费者者都都进进不不去去，因而因而出现了死锁。出现了死锁。反反之之，当当缓缓冲冲区区空空时时消消费费

6、者者先先到到也也会会出现死锁出现死锁。例2：在前面学过的生产者消费者问题中，如果将两个p操作的次序颠倒，如图所示，会不会发生死锁？如果会，在什么样的情况下发生？颠倒后的：P生产者（）P(mutex)；P(empty)；送一个产品到缓冲区；V(mutex)；V(full)；84 4.2.2死锁死锁产生死锁的根本原因：产生死锁的根本原因：系统资源不足系统资源不足 死锁是死锁是资源竞争资源竞争和和资源分配不合理资源分配不合理两两个因素同时作用所产生的可能结果个因素同时作用所产生的可能结果资源不足资源共享资源竞争合理分配不合理分配提高资源利用率死锁94.24.2死锁死锁如果不考虑资源分配的合理性，若要

7、不产如果不考虑资源分配的合理性，若要不产生死锁，则资源的个数必须满足以下条件生死锁，则资源的个数必须满足以下条件（即（即系统不会产生死锁的最小资源数系统不会产生死锁的最小资源数）：）：设系统所拥有的资源总数为设系统所拥有的资源总数为M M，共享该资源的共享该资源的进程数为进程数为P P，每个进程所需使用该资源的最每个进程所需使用该资源的最大需求为大需求为N N，则则 MP*(N-1)+1MP*(N-1)+1 时时无论如何分配都不会产生死锁。无论如何分配都不会产生死锁。104 4.2.2死锁死锁产生死锁的四个产生死锁的四个必要条件必要条件：1 1、互互斥斥条条件件：并并发发进进程程所所请请求求的

8、的资资源源是是互互斥斥使使用用的的独独占占资资源源，即即一一次次只只能能被被一一个进程使用的资源，具有排它性。个进程使用的资源，具有排它性。2 2、不不可可剥剥夺夺条条件件（请请求求和和保保持持）进进程程所所占占有有的的资资源源在在没没有有使使用用完完之之前前不不能能被被其其它它进进程程强强行行占占用用，只只能能由由占占有有该该资资源源的的进程自己释放。进程自己释放。3 3、部部分分分分配配：进进程程对对于于自自己己所所需需要要的的资资源源每每次次只只请请求求一一部部分分，操操作作系系统统允允许许部部分资源的分配。分资源的分配。4 4、环环路路条条件件：系系统统中中各各并并发发进进程程对对于于

9、资资源源的的占占有有和和请请求求形形成成环环路路，即即请请求求箭箭头头方向和占有箭头方向形成环路方向和占有箭头方向形成环路114 4.2.2死锁死锁规避死锁的规避死锁的3 3种方法种方法1 1、预防静态（执行前保证）、预防静态（执行前保证）2 2、避免动态（执行中保证）、避免动态（执行中保证）3 3、检测与恢复、检测与恢复124 4.2.2死锁死锁1.1.死锁的预防（针对发生死锁的死锁的预防（针对发生死锁的4 4个必要条件）个必要条件）条条件件1 1（互互斥斥）：是是资资源源本本身身固固有有的的特特性性，很很难难改改变变和和破破坏坏的的，但但可可采采用用相相应应的的技技术术，如如利利用用假假脱

10、脱机机技技术术，即即用可共享使用的设备模拟非共享的设备；用可共享使用的设备模拟非共享的设备；条条件件2 2（不不可可剥剥夺夺）：较较难难否否定定，但但可可制制定定相相应应的的规规则则，例例如如，当当一一个个进进程程（程程序序）申申请请某某资资源源被被拒拒绝绝，则则必必须须释释放放已已占占用用的的资资源源，如如需需要要再再与与其其它它所所需需资资源源一一起起申请；对申请；对CPUCPU还可进行可剥夺分配。还可进行可剥夺分配。条条件件3 3（部部分分分分配配）：容容易易否否定定，只只要要分分配配策策略略上上规规定定每每个个进进程程一一次次性性将将所所需需资资源源全全部部申申请请到到位位，用用完完后

11、后释释放放。（静态分配）（静态分配）条条件件4 4（环环路路）：容容易易否否定定，采采用用有有序序分分配配，将将资资源源编编号号，各各进进程程对对于于资资源源的的请请求求只只能能按按号号的的递递增增进进行行，比比如如请请求了求了R1R1才能请求才能请求R2R2，从而破坏环路条件预防死锁。从而破坏环路条件预防死锁。134 4.2.2死锁死锁预防死锁的缺陷：预防死锁的缺陷：1.1.用用户户进进程程必必须须事事先先列列出出所所有有需需要要的的资资源源，以以便系统一次性分配；便系统一次性分配；2.2.系系统统一一次次性性分分配配给给进进程程的的资资源源在在很很多多时时间间内内是处于空闲状态的；是处于空

12、闲状态的；3.3.用用户户进进程程必必须须得得到到所所有有资资源源才才能能运运行行，减减低低了并发度，增加了等待时间。了并发度，增加了等待时间。总结：总结：采采用用静静态态预预防防的的方方式式来来解解决决死死锁锁问问题题牺牺牲牲了了资资源源的的利利用用率率，而而资资源源利利用用率率的的降降低低直直接接导导致致并发度的降低。并发度的降低。144 4.2.2死锁死锁2 2、死锁的避免、死锁的避免指指操操作作系系统统在在动动态态分分配配过过程程中中对对每每一一次次的的分分配配都都要要采采取取某某种种策策略略去去判判断断一一下下当当前前的的分分配配有有没没有有导导致致死死锁锁的的可可能能性性，没没有有

13、则则实实施施分分配配，有有则拒绝分配，从而动态地避免死锁的产生则拒绝分配，从而动态地避免死锁的产生。最最有有代代表表性性的的死死锁锁避避免免算算法法是是Dijkstra E.W 于于1968年年提提出出的的银银行行家家算算法法，该该算算法法借借鉴鉴了了银银行行家家对对于于项项目目投投资资的的管管理理经经验验到到，银银行行家总是希望：家总是希望：1、使使用用最最多多的的项项目目同同时时开开工工，以以获获取取最最大大的的回回报。报。2、保保证证至至少少有有一一个个项项目目能能完完成成，避避免免所所有有项项目目都在进行之中而手中却无钱周转（即进入死锁）。都在进行之中而手中却无钱周转（即进入死锁）。1

14、54 4.2.2死锁死锁2 2个概念个概念安全序列和安全状态安全序列和安全状态：安全序列安全序列在该序列中所有的进程都可以在该序列中所有的进程都可以因为之前进程的完成所释放的资源使得它们因为之前进程的完成所释放的资源使得它们一个接一个的完成。一个接一个的完成。表示为表示为,Pm，其中其中Pi,PjPi,Pj PmPm代表系统中的进程代表系统中的进程安全状态安全状态如果系统中的如果系统中的所有进程至少能所有进程至少能找到一个安全序列，则称系统当前处于安全找到一个安全序列，则称系统当前处于安全状态状态。注意：安全序列必须包括当前系统中所有进程，注意：安全序列必须包括当前系统中所有进程，如果某个进程

15、因资源不够而不能完成，则不如果某个进程因资源不够而不能完成，则不存在安全序列，当前系统就处于不安全状态，存在安全序列，当前系统就处于不安全状态，可能导致死锁；如果系统在任意时刻都处于可能导致死锁；如果系统在任意时刻都处于安全状态，则系统就是安全的，不会有死锁安全状态，则系统就是安全的，不会有死锁发生。发生。164.24.2死锁死锁3 3、死锁的检测与恢复、死锁的检测与恢复死锁的检测与恢复是指系统设置专门机构，在死锁发生时该机构能够及时检测出死锁发生的位置和原因，并能够通过外力破坏死锁产生的一个必要条件，从而使并发进程能够从死锁状态中恢复出来。死锁检测算法类似于银行家算法，如果某时刻所有进程不能

16、全部进入安全序列，它们将死锁。174.24.2死锁死锁死锁排除的方法：死锁排除的方法：1 1、撤消陷于死锁的全部进程；、撤消陷于死锁的全部进程；2 2、逐个撤消陷于死锁的进程，直到死锁不存、逐个撤消陷于死锁的进程，直到死锁不存在；在；3 3、从陷于死锁的进程中逐个强迫放弃所占用、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失。的资源，直至死锁消失。184.34.3处理机的多级调度处理机的多级调度1、处理机调度的目标：、处理机调度的目标：公平公平：确保每个进程都能公平地占有处理机高效高效：使处理机尽可能忙响应时间快响应时间快：与用户交互快捷周转时间短周转时间短：用户等待输出的时间短系统

17、吞吐量大系统吞吐量大：相同时间内完成的作业尽可能多194.34.3处理机的多级调度处理机的多级调度2 2、处理机的两级调度、处理机的两级调度宏观调度：作业调度宏观调度：作业调度微观调度：进程调度（在作业处于执行状态下）微观调度：进程调度（在作业处于执行状态下）线程调度（在进程处于运行状态下）线程调度（在进程处于运行状态下）204 4.4.4作业调度作业调度1 1、作业的、作业的4 4个状态：个状态：提交状态提交状态：用户将程序提交给系统，等：用户将程序提交给系统，等待输入。待输入。后备状态后备状态：系统响应用户请求，将作业：系统响应用户请求，将作业输入到磁盘上，等待作业调度。输入到磁盘上，等待

18、作业调度。执行状态执行状态：该作业被调度进入内存，并：该作业被调度进入内存，并创建相应的进程，插入进程就绪队列。创建相应的进程，插入进程就绪队列。完成状态完成状态：作业执行结束，并释放其占：作业执行结束，并释放其占用的所有系统资源。用的所有系统资源。21作作业业调调度度的的主主要要任任务务是是完完成成作作业业从从后后备备状状态态到到执执行行状状态态和和从从执执行行状状态态到到完完成成状态的转变。状态的转变。作业调度功能：作业调度功能：1.1.分配作业控制块分配作业控制块JCBJCB；2.2.按按一一定定的的调调度度算算法法，从从后后备备作作业业中中选选择择一个或几个作业进入系统内存；一个或几个

19、作业进入系统内存；3.3.为为被被选选中中的的作作业业创创建建进进程程，并并且且为为其其申申请系统资源；请系统资源；4.4.作业结束后作善后处理工作。作业结束后作善后处理工作。4 4.4.4作业调度作业调度224.44.4作业调度作业调度 2、作作业业控控制制块块JCBJCB（Job Control Block)，它是存放作业控制和管理信息的数据结构，是作业存在的唯一标识，是操作系统调度的依据。主要信息见右图。234 4.4.4作业调度作业调度3 3、作业调度的性能衡量指标：、作业调度的性能衡量指标：平均周转时间平均周转时间和和带权平均周转时间带权平均周转时间u周周转转时时间间完完成成时时间间

20、提提交交时时间间等等待待 时间执行时间时间执行时间u平均周转时间平均周转时间T T周转时间总和周转时间总和作业数作业数u带权周转周转时间带权周转周转时间执行时间执行时间u平平均均带带权权周周转转时时间间W W带带权权周周转转总总和和作作业数业数 244 4.4.4作业调度作业调度4 4、作业调度算法、作业调度算法先先来来先先服服务务FCFS:FCFS:按按作作业业提提交交的的先先后后次次序序进进行调度的行调度的短短作作业业优优先先SJFSJF：选选择择运运行行时时间间最最小小的的作作业业进进行调度行调度响应比高优先响应比高优先HRRNHRRN：响应比响应比优先优先数调度数调度时间片轮转时间片轮

21、转RRRR最短剩余时间优先最短剩余时间优先SRT SRT 多级反馈队列多级反馈队列FBFB运行时间等待时间255.45.4作业调度作业调度264.54.5进程调度进程调度作业调度：长程调度作业调度：长程调度进程调度进程调度：中程调度（就绪且换出中程调度（就绪且换出 就绪就绪 阻塞且换出阻塞且换出 阻塞）阻塞）涉及到内存和交换区的切换涉及到内存和交换区的切换 短程调度（就绪短程调度（就绪 运行）运行）涉及到处理机的直接分配涉及到处理机的直接分配274.54.5进程调度进程调度新新建建就就绪绪就绪就绪且换且换出出运运行行长程调度长程调度长程调度长程调度短程调度短程调度中程调度中程调度阻塞阻塞且换且

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

23、加载或恢复新进程的现场信息，使处理机信息，加载或恢复新进程的现场信息，使处理机实现在进程之间的切换。实现在进程之间的切换。294.54.5进程调度进程调度2 2、进程调度的功能、进程调度的功能记录系统中所有进程的执行情况记录系统中所有进程的执行情况选择进程，对其实施处理机的分配选择进程，对其实施处理机的分配 进行进程上下文的切换进行进程上下文的切换进程调度涉及到进程调度涉及到就绪队列的管理就绪队列的管理和和处处理机分配理机分配的双重任务，很多操作系统将的双重任务，很多操作系统将这两个任务分别用两个系统进程来完成：这两个任务分别用两个系统进程来完成：调度进程调度进程和和分派进程分派进程。304

24、4.5.5进程调度进程调度调调度度进进程程：组组织织和和维维护护就就绪绪进进程程队队列列。包包括括确确定定调调度度算算法法、按按调调度度算算法法管管理理就绪进程队列。就绪进程队列。分分派派进进程程：是是指指当当处处理理机机空空闲闲时时，从从就就绪绪队队列列中中选选取取队队列列头头的的一一个个进进程程实实施施处处理理机机的的分分配配，并并负负责责进进行行处处理理机机上上下文的切换。下文的切换。进进程程调调度度与与进进程程控控制制和和进进程程通通信信的的功功能能有有密密切切的的联联系系，当当一一个个进进程程阻阻塞塞时时，这这个个进进程程将将被被调调度度进进程程调调度度到到相相应应的的等等待待队队列

25、列中中，并并让让出出CPUCPU，由由分分派派进进程程选选择择一一个个就就绪绪进进程程占占用用CPUCPU；当当一一进进程程被被唤唤醒醒时时，调调度度进进程程也会将其插入到就绪进程队列中。也会将其插入到就绪进程队列中。314.54.5进程调度进程调度总而言之，进程调度包括：调度算法的选择（调度算法）调度算法的选择（调度算法）调度时机的选择（调度时机）调度时机的选择（调度时机）实施进程调度（调度程序）实施进程调度（调度程序）324.54.5进程调度进程调度3 3、进程调度的时机：、进程调度的时机：进程执行了终止函数，进入僵死状态。进程执行了终止函数，进入僵死状态。进程执行了阻塞原语将自己阻塞，放

26、弃了处进程执行了阻塞原语将自己阻塞，放弃了处理机。理机。进程执行了请求进程执行了请求I/OI/O操作后进入阻塞态，放弃操作后进入阻塞态，放弃了处理机。了处理机。进程执行了进程执行了P P操作，因为条件不满足而阻塞，操作，因为条件不满足而阻塞，放弃了处理机。放弃了处理机。在分时系统中执行进程的时间片用完。在分时系统中执行进程的时间片用完。在执行完用户请求的系统调用后，由系统调在执行完用户请求的系统调用后，由系统调用返回时。用返回时。在可剥夺方式下，当就绪进程的优先级高于在可剥夺方式下，当就绪进程的优先级高于执行进程时。执行进程时。334.54.5进程调度进程调度4 4、进程调度策略、进程调度策略调度方式调度方式非剥夺式调度：进程自动放弃非剥夺式调度：进程自动放弃CPUCPU可剥夺式调度：系统强迫进程放弃可剥夺式调度：系统强迫进程放弃CPUCPU调度算法调度算法FCFSFCFS循环法循环法最短进程优先最短进程优先最短剩余时间优先最短剩余时间优先反馈队列反馈队列34