操作系统原理第五章-资源分配与调度优秀PPT.ppt

《操作系统原理第五章-资源分配与调度优秀PPT.ppt》由会员分享，可在线阅读，更多相关《操作系统原理第五章-资源分配与调度优秀PPT.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5.1 资源管理概述资源管理概述o1.资源管理的目的和任务资源管理的目的和任务o资源的静态安排和动态安排资源的静态安排和动态安排o资源的静态安排资源的静态安排o系统对作业一级接受资源静态安排方法。系统对作业一级接受资源静态安排方法。o系统在调度作业时，依据作业所需资源进行安系统在调度作业时，依据作业所需资源进行安排；并在作业运行完毕时，收回所安排的全部排；并在作业运行完毕时，收回所安排的全部资源。称为资源的静态安排。资源。称为资源的静态安排。o资源的动态安排资源的动态安排 o系统对进程一级接受资源动态安排方法。系统对进程一级接受资源动态安排方法。o系统在进程运行中，依据进程提出的资源需求，系统

2、在进程运行中，依据进程提出的资源需求，进行资源的动态安排和回收。称为资源的动态进行资源的动态安排和回收。称为资源的动态安排。安排。15.1 资源管理概述资源管理概述o资源管理的目的资源管理的目的o目的：为用户供应一种简洁而有效地运用资源目的：为用户供应一种简洁而有效地运用资源的方法，充分发挥各资源的作用。的方法，充分发挥各资源的作用。o应达到的目标：应达到的目标：o保证资源的高利用率；保证资源的高利用率；o在在“合理合理”时间内使全部顾客有获得所需资源时间内使全部顾客有获得所需资源的机会；的机会；o对不行共享的资源实施互斥运用；对不行共享的资源实施互斥运用；o防止由资源安排不当而引起死锁。防止

3、由资源安排不当而引起死锁。25.1 资源管理概述资源管理概述o资源管理的任务资源管理的任务o任务：解决资源安排问题，防止死锁；解决对任务：解决资源安排问题，防止死锁；解决对资源的存取、运用方法问题资源的存取、运用方法问题o资源管理的功能资源管理的功能o 资源数据结构的描述资源数据结构的描述o 确定资源的安排原则和调度原则确定资源的安排原则和调度原则o 执行资源安排执行资源安排 o 存取限制和平安爱护存取限制和平安爱护35.1 资源管理概述资源管理概述o2.资源的分类方法资源的分类方法o物理资源和程序资源物理资源和程序资源(处理器、外设等；消息或文件等处理器、外设等；消息或文件等)o单一访问入口

4、资源（不行重入，只能为一个进程运用）和单一访问入口资源（不行重入，只能为一个进程运用）和多访问入口资源（可以为多个进程共享运用）多访问入口资源（可以为多个进程共享运用）o等同资源（多个完全相同的设备）等同资源（多个完全相同的设备）o虚拟资源（虚拟资源（cpu、确定容量的主存、数量有限的外设），、确定容量的主存、数量有限的外设），如虚拟存储器如虚拟存储器o3.资源管理的机构和策略资源管理的机构和策略o机构：进行资源安排的必需的基本设施和部件，它包括描机构：进行资源安排的必需的基本设施和部件，它包括描述资源状态的数据结构、保证资源互斥的同步机构及资源述资源状态的数据结构、保证资源互斥的同步机构及资

5、源恳求排队的手段。恳求排队的手段。o策略：这些机构所运用的方法，资源安排的原则策略：这些机构所运用的方法，资源安排的原则45.2 资源安排机制资源安排机制o1.资源描述器资源描述器o什么是资源描述器什么是资源描述器o描述各类资源的最小安排单位的数据结构称为资描述各类资源的最小安排单位的数据结构称为资源描述器源描述器 RD(resource descriptor)。o如：主存最小安排单位：如：主存最小安排单位：o在分区安排中在分区安排中主存分区主存分区 o磁盘最小安排单位：磁盘最小安排单位：o磁盘面中的一个扇区磁盘面中的一个扇区o描述器的组织方式取决于资源安排单位的数量和描述器的组织方式取决于资

6、源安排单位的数量和这一数量是固定不变的、还是可以变更的这一特这一数量是固定不变的、还是可以变更的这一特征。征。5o资源描述器的内容资源描述器的内容o资源名资源名o资源类型资源类型o最小安排单位的大小最小安排单位的大小o最小安排单位的地址最小安排单位的地址o安排标记安排标记o描述器链接信息描述器链接信息o存取权限存取权限o密级密级o最终一次存取时间最终一次存取时间o记账信息记账信息20KB 0 os 作业1 作业3 作业4 52KB66KB130KB230KB256KB1主存5.2 资源安排机制资源安排机制6o 2.资源信息块资源信息块o什么是资源信息块（什么是资源信息块（rib）o描述某类资源

7、的恳求者、可用资源和该类资源描述某类资源的恳求者、可用资源和该类资源安排程序等必要信息的数据结构。安排程序等必要信息的数据结构。o对于每一类可利用的资源，可将其组织成可利对于每一类可利用的资源，可将其组织成可利用资源队列。在资源信息块中有指向这两个队用资源队列。在资源信息块中有指向这两个队列的队列指针，另外还有一项为该类资源安排列的队列指针，另外还有一项为该类资源安排程序的入口地址程序的入口地址。o资源安排程序是接收安排吩咐把资源安排给恳资源安排程序是接收安排吩咐把资源安排给恳求者的例程。求者的例程。o资源安排程序包括：安排程序和回收程序。资源安排程序包括：安排程序和回收程序。5.2 资源安排

8、机制资源安排机制7等待队列头指针可利用资源队列头指针资源分配程序入口地址pcb1pcb2pcbkrd1rd2rdn资源分配程序5.2 资源安排机制资源安排机制n资源信息块的内容资源信息块的内容85.3 资源安排策略资源安排策略o资源安排的方式取决于设计者所选择的目标，以及与应用每一类资源相联系的特定限制。o目的是使吞吐率尽可能地高，响应时间尽可能地短，即既要充分地利用系统各种资源，又要尽可能地满足用户要求。o一个资源进行安排的问题，在一般状况下，是由这样两个方面组成的：管理恳求的排队站（安排策略）与在等同资源间选择资源。o安排程序可以用不同的策略选择进程恳求；o依据恳求来到的次序进行查看；o将

9、进程恳求者的优先权结合到每一个恳求中；o满足能更合理地应用这一资源的那个恳求。9o1.常用的资源安排策略常用的资源安排策略o(1)先恳求先服务先恳求先服务(FIFO(First In First Out)策略策略)o排序原则：按恳求的先后次序排序。排序原则：按恳求的先后次序排序。o每一个新产生的恳求均排在队尾，而当资源可用时，每一个新产生的恳求均排在队尾，而当资源可用时，资源安排程序则从队列中选取第一个恳求，并满足资源安排程序则从队列中选取第一个恳求，并满足其须要。其须要。o这种策略可用于对进程或作业的调度，或外设、主存这种策略可用于对进程或作业的调度，或外设、主存安排安排 表头按请求的先后次

10、序先后按自然顺序排列的队列5.3 资源安排策略资源安排策略10o(2)优先调度优先调度o在优先调度策略下，对于每一个进程要指定一个优先在优先调度策略下，对于每一个进程要指定一个优先级，优先级反映了进程要求处理的紧迫程度。级，优先级反映了进程要求处理的紧迫程度。o排序原则：按优先级的凹凸排序。排序原则：按优先级的凹凸排序。o每一个新产生的恳求，按其优先级的凹凸插到相应的每一个新产生的恳求，按其优先级的凹凸插到相应的位置上。而当资源可用时，选取队列中第一个恳求，位置上。而当资源可用时，选取队列中第一个恳求，并满足其须要。并满足其须要。表头按优先级的高低排序高低 按优先级高低排列的就绪队列5.3 资

11、源安排策略资源安排策略11o一一.死锁的概念死锁的概念o1.死锁的例子死锁的例子o（1）同类资源的死锁）同类资源的死锁o（2）非同类资源的死锁）非同类资源的死锁o进程进程p1、p2 共享一台打印机和一台光标记阅读机共享一台打印机和一台光标记阅读机o时刻时刻t1，进程，进程 p1占用打印机占用打印机o 进程进程 p2占用光标记阅读机。占用光标记阅读机。o时刻时刻t2，进程，进程 p1又恳求光标记阅读机又恳求光标记阅读机o 进程进程 p2又恳求打印机又恳求打印机5.3 死锁死锁125.3 死锁死锁n(2)用信号灯的用信号灯的P、V操作描述死锁操作描述死锁n设进程设进程A与进程与进程B共享一台打印机

12、共享一台打印机(R1)和一台光标和一台光标记阅读机记阅读机(R2)。n用信号灯的用信号灯的P、V操作表示资源的申请和释放。操作表示资源的申请和释放。n信号灯设置信号灯设置 s1：表示：表示R1可用，初值为可用，初值为1。n s2：表示：表示R2可用，初值为可用，初值为1。n探讨两种资源恳求序列，哪种状况可能产生相互死探讨两种资源恳求序列，哪种状况可能产生相互死等的局面。等的局面。13 进程进程A 进程进程B A进程进程 进程进程B p(s1)；p(s2)；p(s1)p(s2)；占用R1 占用R2 占用R1 占用R2 v(s1)；v(s2)；p(s2)；p(s1)；又占用R2 又占用R1 p(s

13、2)；p(s1)；占用R2 占用R1 v(s1)v(s2)；v(s2)；v(s1)；v(s2)；v(s1)；5.3 死锁死锁14o2.什么是死锁什么是死锁o在两个或多个并发进程中，假如每个进程持有某种资在两个或多个并发进程中，假如每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推动，称这一组进程产生了死资源，否则就不能向前推动，称这一组进程产生了死锁。锁。o死锁是两个或多个进程被无限期地堵塞、相互等待的死锁是两个或多个进程被无限期地堵塞、相互等待的一种状态。一种状态。o二二.死锁的起因和条件死锁的起因和条件o1.

14、引起死锁的缘由引起死锁的缘由o系统资源不足；系统资源不足；o进程推动依次非法。进程推动依次非法。5.3 死锁死锁15o2.死锁图解死锁图解 A1：p1 request(r1)A2：p2 request(r2)B1：p1 request(r2)B2：p2 request(r1)C1：p1 release(r1)C2：p2 release(r2)D1：p1 release(r2)D2：p2 release(r1)N0A1B1C1D1A2B2C2D2P1进程进程P2进程进程5.3 死锁死锁16o3.产生死锁的必要条件产生死锁的必要条件o(1)互斥条件互斥条件o涉及的资源是非共享的，即为临界资源。涉及

15、的资源是非共享的，即为临界资源。o(2)不剥夺条件（非抢夺）不剥夺条件（非抢夺）o进程所获得的资源在未运用完毕之前，不能被其他进程强行进程所获得的资源在未运用完毕之前，不能被其他进程强行夺走。夺走。o(3)占用并等待（部分安排）占用并等待（部分安排）o进程每次申请它所须要的一部分资源。在等待一新资源的同进程每次申请它所须要的一部分资源。在等待一新资源的同时，进程接着占用已安排到的资源。时，进程接着占用已安排到的资源。o(4)环路条件（循环等待）环路条件（循环等待）o存在一种进程的循环链，链中的每一个进程已获得的资源同存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所恳求。

16、时被链中下一个进程所恳求。5.3 死锁死锁17o三三.解决死锁问题的策略解决死锁问题的策略o破坏产生死锁的四个必要条件之一破坏产生死锁的四个必要条件之一o互斥条件、不剥夺条件、占用并等待、循环等待互斥条件、不剥夺条件、占用并等待、循环等待o解决死锁的策略解决死锁的策略o接受静态资源安排方法接受静态资源安排方法预防死锁预防死锁o接受资源动态安排、有控安排方法接受资源动态安排、有控安排方法动态避开动态避开死锁死锁o当死锁发生时检测出死锁，并设法修复；当死锁发生时检测出死锁，并设法修复；o忽视死锁，认为死锁不会发生。（大多数操作系忽视死锁，认为死锁不会发生。（大多数操作系统接受）统接受）5.3 死锁

17、死锁18o四四.死锁的预防死锁的预防o预防死锁的方法分为静态预防和动态避开。预防死锁的方法分为静态预防和动态避开。o静态预防死锁的方法静态预防死锁的方法o其方法是预先安排全部共享的资源。（批处理）其方法是预先安排全部共享的资源。（批处理）o缺点：缺点：o一个用户在作业运行之前可能提不出他的作业一个用户在作业运行之前可能提不出他的作业将要运用的全部设备。将要运用的全部设备。o用户作业必需等待，直到全部资源满足时才能用户作业必需等待，直到全部资源满足时才能投入运行。事实上某些资源可能要到运行后期才投入运行。事实上某些资源可能要到运行后期才会用到。会用到。o一个作业运行期间，对某些设备的运用时间很一

18、个作业运行期间，对某些设备的运用时间很少，甚至不会用到。少，甚至不会用到。5.3 死锁死锁195.3 死锁死锁o五、死锁的避开（动态预防死锁的方法）五、死锁的避开（动态预防死锁的方法）o预防死锁和避开死锁的区分：预防死锁和避开死锁的区分：o前者所接受的安排策略本身就否定了必要条件之一，前者所接受的安排策略本身就否定了必要条件之一，这样来保证死锁不行能发生；而后者是在动态安排这样来保证死锁不行能发生；而后者是在动态安排资源的策略下接受某种算法来预防可能发生的死锁，资源的策略下接受某种算法来预防可能发生的死锁，从而拒绝可能引起死锁的某个资源恳求。从而拒绝可能引起死锁的某个资源恳求。o(1)有序资源

19、安排法有序资源安排法o系统中全部资源都给定一个唯一的编号，全部安排系统中全部资源都给定一个唯一的编号，全部安排恳求必需以上升的次序进行。当遵守上升次序的规恳求必需以上升的次序进行。当遵守上升次序的规则时，若资源可用，安排程序则予以安排；否则，则时，若资源可用，安排程序则予以安排；否则，恳求者等待。（线性方式破坏了死锁的环路条件）恳求者等待。（线性方式破坏了死锁的环路条件）o缺点：进程实际须要资源的依次不确定与资源的编缺点：进程实际须要资源的依次不确定与资源的编号相一样，因而仍旧会造成资源的奢侈。号相一样，因而仍旧会造成资源的奢侈。o对资源进行合理的排序，这种方法是有确定好用价对资源进行合理的排

20、序，这种方法是有确定好用价值的。值的。205.3 死锁死锁n(2)银行家算法n避开死锁的方法是否有效与接受的算法有很大的关系。它能在死锁发生前察觉它们的存在，代表算法是Dijkstra E W于1968年提出的银行家算法（可用于银行系统）。n申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时，由系统审查系统现有该类资源的数目是否能满足当前进程的最大需求量，如能满足就予以安排，否则进程等待。n按银行算法来安排资源是不会产生死锁的。因为，按该算安排资源时，每次安排后总存在着一个进程，假如让它单独进行下去，必定可以获得它所需的全部资源。n这种算法的主要问题是，要求每个进程必需先知道资源的最大需求量，过于谨慎及所花费的开销较大是运用银行算法的主要障碍。215.3 死锁死锁o例：系统拥有某类资源10个。现有进程P、Q、R共享该类资源。它们申请该类资源的最大需求量如下，当这些进程动态申请资源时，按银行家算法应如何安排，能保证不发生死锁。22一.资源管理功能 资源静态安排、动态安排二.资源的安排机制 资源描述器 资源信息块三.常用的资源安排策略 先恳求先服务 优先调度四.死锁 1.定义 举例 2.引起死锁的缘由 3.产生死锁的必要条件 4.死锁预防 5.死锁避开：有序资源安排方法、银行家算法 第五章第五章 小结小结23