操作系统原理第五章资源分配及调度课件.ppt

1、1. . .25.1 资源管理概述资源管理概述o1. 资源管理的目的和任务资源管理的目的和任务n资源的静态分配和动态分配o资源的静态分配n系统对作业一级采用资源静态分配方法。n系统在调度作业时，根据作业所需资源进行分配；并在作业运行完毕时，收回所分配的全部资源。称为资源的静态分配。 o资源的动态分配 n系统对进程一级采用资源动态分配方法。n系统在进程运行中，根据进程提出的资源需求，进行资源的动态分配和回收。称为资源的动态分配。. . .35.1 资源管理概述资源管理概述o资源管理的目的资源管理的目的n目的：为用户提供一种简单而有效地使用资源的方法，充分发挥各资源的作用。n应达到的目标：o保证资

2、源的高利用率；o在“合理”时间内使所有顾客有获得所需资源的机会；o对不可共享的资源实施互斥使用；o防止由资源分配不当而引起死锁。. . .45.1 资源管理概述资源管理概述o资源管理的任务资源管理的任务n任务：解决资源分配问题，防止死锁；解决对资源的存取、使用方法问题n资源管理的功能o 资源数据结构的描述o 确定资源的分配原则和调度原则o 执行资源分配 o 存取控制和安全保护. . .55.1 资源管理概述资源管理概述o2. 资源的分类方法资源的分类方法n物理资源和程序资源(处理器、外设等；消息或文件等)n单一访问入口资源（不可重入，只能为一个进程使用）和多访问入口资源（可以为多个进程共享使用

3、）n等同资源（多个完全相同的设备）n虚拟资源（cpu、一定容量的主存、数量有限的外设），如虚拟存储器o3. 资源管理的机构和策略资源管理的机构和策略n机构：进行资源分配的必需的基本设施和部件，它包括描述资源状态的数据结构、保证资源互斥的同步机构及资源请求排队的手段。n策略：这些机构所使用的方法，资源分配的原则. . .65.2 资源分配机制资源分配机制o1. 资源描述器资源描述器n什么是资源描述器什么是资源描述器o描述各类资源的最小分配单位的数据结构称为资源描述器 RD (resource descriptor)。n如：主存最小分配单位：在分区分配中主存分区 n磁盘最小分配单位：磁盘面中的一个

4、扇区n描述器的组织方式取决于资源分配单位的数量和这一数量是固定不变的、还是可以变化的这一特征。. . .7o资源描述器的内容资源描述器的内容n资源名n资源类型n最小分配单位的大小n最小分配单位的地址n分配标志n描述器链接信息n存取权限n密级n最后一次存取时间n记账信息20KB 0 os 作业1 作业3 作业4 52KB66KB130KB230KB256KB1主存5.2 资源分配机制资源分配机制. . .8o 2. 资源信息块资源信息块n什么是资源信息块（什么是资源信息块（rib）o描述某类资源的请求者、可用资源和该类资源分配程序等必要信息的数据结构。n对于每一类可利用的资源，可将其组织成可利用

5、资源队列。在资源信息块中有指向这两个队列的队列指针，另外还有一项为该类资源分配程序的入口地址 。n资源分配程序是接收分配命令把资源分配给请求者的例程。o资源分配程序包括：分配程序和回收程序。 5.2 资源分配机制资源分配机制. . .9等待队列头指针可利用资源队列头指针资源分配程序入口地址pcb1pcb2pcbkrd1rd2rdn资源分配程序5.2 资源分配机制资源分配机制n资源信息块的内容资源信息块的内容. . .105.3 资源分配策略资源分配策略o资源分配的方式取决于设计者所选择的目标，以及与应用每一类资源相联系的特定限制。n目的是使吞吐率尽可能地高，响应时间尽可能地短，即既要充分地利用

6、系统各种资源，又要尽可能地满足用户要求。 o一个资源进行分配的问题，在一般情况下，是由这样两个方面组成的：管理请求的排队站（分配策略）与在等同资源间选择资源。 o分配程序可以用不同的策略选择进程请求； n按照请求来到的次序进行查看； n将进程请求者的优先权结合到每一个请求中； n满足能更合理地应用这一资源的那个请求。 . . .11o1. 常用的资源分配策略常用的资源分配策略n(1) 先请求先服务先请求先服务(FIFO(First In First Out)策略)o排序原则：按请求的先后次序排序。o每一个新产生的请求均排在队尾，而当资源可用时，资源分配程序则从队列中选取第一个请求，并满足其需要

7、。o这种策略可用于对进程或作业的调度，或外设、主存分配 表头按请求的先后次序先后按自然顺序排列的队列5.3 资源分配策略资源分配策略. . .12o(2) 优先调度优先调度n在优先调度策略下，对于每一个进程要指定一个优先级，优先级反映了进程要求处理的紧迫程度。n排序原则：按优先级的高低排序。n每一个新产生的请求，按其优先级的高低插到相应的位置上。而当资源可用时，选取队列中第一个请求，并满足其需要。 表头按优先级的高低排序高低 按优先级高低排列的就绪队列5.3 资源分配策略资源分配策略. . .13o一一. 死锁的概念死锁的概念n1. 死锁的例子死锁的例子n（1）同类资源的死锁）同类资源的死锁n

8、（2）非同类资源的死锁）非同类资源的死锁o进程p1、p2 共享一台打印机和一台光标记阅读机o时刻t1，进程 p1占用打印机 进程 p2占用光标记阅读机。o时刻t2，进程 p1又请求光标记阅读机 进程 p2又请求打印机5.3 死锁死锁. . .145.3 死锁死锁n(2) 用信号灯的用信号灯的P、V操作描述死锁操作描述死锁o设进程A与进程B共享一台打印机(R1) 和一台光标记阅读机(R2) 。o用信号灯的P、V操作表示资源的申请和释放。 o信号灯设置 s1：表示R1可用，初值为1。 s2：表示R2可用，初值为1。o讨论两种资源请求序列，哪种情况可能产生互相死等的局面。. . .15 进程进程A

9、进程进程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(s2)； p(s1)； 占用R2 占用R1 v(s1 ) v(s2)； v(s2)； v(s1)； v(s2)； v(s1)； 5.3 死锁死锁. . .16o2. 什么是死锁什么是死锁n在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进，称这一组进程产生了死锁。n死锁是两个或多个进程被无限期地阻塞、相互等待的一种状态

10、。o二二. 死锁的起因和条件死锁的起因和条件n1. 引起死锁的原因引起死锁的原因o系统资源不足；o进程推进顺序非法。5.3 死锁死锁. . .17o2. 死锁图解死锁图解 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 死锁死锁. . .18o3. 产生死锁的必要条件

11、产生死锁的必要条件n(1) 互斥条件o涉及的资源是非共享的，即为临界资源。n(2) 不剥夺条件（非抢夺）o进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。 n(3) 占用并等待（部分分配）o进程每次申请它所需要的一部分资源。在等待一新资源的同时，进程继续占用已分配到的资源。n(4) 环路条件（循环等待）o存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求。 5.3 死锁死锁. . .19o三三. 解决死锁问题的策略解决死锁问题的策略n破坏产生死锁的四个必要条件之一破坏产生死锁的四个必要条件之一o互斥条件、不剥夺条件、占用并等待、循环等待n解决死锁的策略解决死

12、锁的策略o采用静态资源分配方法预防死锁o采用资源动态分配、有控分配方法动态避免死锁o当死锁发生时检测出死锁，并设法修复；o忽略死锁，认为死锁不会发生。（大多数操作系统采用）5.3 死锁死锁. . .20o四四. 死锁的预防死锁的预防n预防死锁的方法分为静态预防和动态避免。n静态预防死锁的方法静态预防死锁的方法o其方法是预先分配所有共享的资源。（批处理）o缺点：n一个用户在作业运行之前可能提不出他的作业将要使用的全部设备。 n用户作业必须等待，直到所有资源满足时才能投入运行。实际上某些资源可能要到运行后期才会用到。 n一个作业运行期间，对某些设备的使用时间很少，甚至不会用到。5.3 死锁死锁.

13、. .215.3 死锁死锁o五、死锁的避免（动态预防死锁的方法）五、死锁的避免（动态预防死锁的方法）n预防死锁和避免死锁的区别：o前者所采用的分配策略本身就否定了必要条件之一，这样来保证死锁不可能发生；而后者是在动态分配资源的策略下采用某种算法来预防可能发生的死锁，从而拒绝可能引起死锁的某个资源请求。 n(1) 有序资源分配法o系统中所有资源都给定一个唯一的编号，所有分配请求必须以上升的次序进行。当遵守上升次序的规则时，若资源可用，分配程序则予以分配；否则，请求者等待。（线性方式破坏了死锁的环路条件） o缺点：进程实际需要资源的顺序不一定与资源的编号相一致，因而仍然会造成资源的浪费。 o对资源

14、进行合理的排序，这种方法是有一定实用价值的。 . . .225.3 死锁死锁n(2) 银行家算法o避免死锁的办法是否有效与采用的算法有很大的关系。它能在死锁发生前察觉它们的存在，代表算法是Dijkstra E W于1968年提出的银行家算法（可用于银行系统）。o申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时，由系统审查系统现有该类资源的数目是否能满足当前进程的最大需求量，如能满足就予以分配，否则进程等待。o按银行算法来分配资源是不会产生死锁的。因为，按该算分配资源时，每次分配后总存在着一个进程，如果让它单独进行下去，必然可以获得它所需的全部资源。 o这种算法的主要问题是

15、，要求每个进程必须先知道资源的最大需求量，过于谨慎及所花费的开销较大是使用银行算法的主要障碍。 . . .235.3 死锁死锁o例：系统拥有某类资源10个。现有进程P、Q、R共享该类资源。它们申请该类资源的最大需求量如下，当这些进程动态申请资源时，按银行家算法应如何分配，能保证不发生死锁。 . . .24一. 资源管理功能 资源静态分配、动态分配二. 资源的分配机制 资源描述器 资源信息块三. 常用的资源分配策略 先请求先服务 优先调度四. 死锁 1. 定义 举例 2. 引起死锁的原因 3. 产生死锁的必要条件 4. 死锁预防 5. 死锁避免：有序资源分配方法、银行家算法 第五章第五章 小结小结. . .