第5章 资源分配与调度.ppt

1、第五章 资源分配与调度,5.1 资源管理概述 5.2 资源分配的机构和策略 5.3 死锁概念,5.1 资源管理概述,5.1.1 资源管理功能(任务) 1. 资源数据结构的描述 构造资源分配所需的数据结构，应包含该资源的物理名、逻辑名、类型、地址、分配状态等信息。 2. 确定资源的分配原则 (调度原则) 确定资源分配原则，即决定资源应分给谁，何时分配，分配多少等问题。,3. 实施资源分配 根据所确定的资源分配原则以及用户的要求，执行资源分配。当资源使用完毕后，收回资源以便重新分配给其他作业和进程使用。 4. 存取控制和安全保护 对资源的存取进行控制并对资源实施安全保护措施。,5.1.2 资源的静

2、态分配和动态分配 1. 资源的静态分配 系统对作业一级采用资源静态分配方法。 系统在调度作业时，根据作业所需资源进行分配；并在作业运行完毕时，收回所分配的全部资源。这种分配通常称为资源的静态分配。 2. 资源的动态分配 系统对进程一级采用资源动态分配方法。 系统在进程运行中，根据进程提出的资源需求，进行资源的动态分配和回收。这种分配通常称为资源的动态分配。,5.1.3 资源的分类 1.物理资源和程序资源 机器的组成部件如CPU、主存等是物理资源，程序设计与程序执行过程中形成的如消息、服务程序或文件等是程序资源。 2.单一访问入口的资源和多访问入口的资源 3.虚拟资源 （1）操作系统对资源区分二

3、种不同的概念 物理资源(实资源) 虚拟资源(逻辑资源) （ 2） 目的 方便用户使用 资源可动态分配，提高资源利用率,5.2 资源分配的机构和策略,5.2.1 资源分配机构 1. 资源描述器 (1) 什么是资源描述器 描述各类资源的最小分配单位的数据结构称为资源描述器 rd (resource descriptor)。 如：主存最小分配单位： 在分区分配中主存分区 磁盘最小分配单位： 磁盘面中的一个扇区,(2) 资源描述器的内容 资源名 资源类型 最小分配单位的大小 最小分配单位的地址 分配标志 描述器链接信息 存取权限 密级 最后一次存取时间 记账信息,2. 资源信息块 (1) 什么是资源信

4、息块 描述某类资源的请求者、可用资源和该类资源分配程序等必要信息的数据结构。 (2) 资源信息块的内容,资源信息块的内容,(3) 中央处理机资源信息块,5.2.2 资源分配策略 1. 常用的资源分配策略 (1) 先请求先服务(FIFO(First In First Out)策略) 排序原则：按请求的先后次序排序。 每一个新产生的请求均排在队尾，而当资源可用时，资源分配程序则从队列中选取第一个请求，并满足其需要。,(2) 优先调度 在优先调度策略下，对于每一个进程要指定一个优先级，优先级反映了进程要求处理的紧迫程度。 排序原则：按优先级的高低排序。 每一个新产生的请求，按其优先级的高低插到相应的

5、位置上。而当资源可用时，选取队列中第一个请求，并满足其需要。,2. 针对设备特性的调度（不讲解） 调度的目标：当有大量I/O请求时，降低完成这些I/O服务的总时间。,(1) 例 对磁盘访问有如下5个请求：,柱面号 盘面号 块号 5 2 1 5 3 8 5 3 5 40 6 3 2 7 7,(2) 移臂调度 总是选取与当前移动臂前进方向上最近的那个I/O请求，使移臂距离最短。,柱面号 盘面号 块号 2 7 7 5 2 1 5 3 8 5 3 5 40 6 3,对磁盘访问的5个请求应作如下调度：,(3) 旋转调度 总是选取与当前读写头最近的那个I/O请求，使旋转圈数最少。,柱面号 盘面号 块号 2

6、 7 7 5 2 1 5 3 5 5 3 8 40 6 3,对磁盘访问的5个请求应作如下调度：,5.3 死锁,5.3.1 什么是死锁 1. 死锁的例 (1) 设备共享 进程p1、p2 共享一台打印机和一台光标记阅读机 时刻t1，进程 p1占用打印机 进程 p2占用光标记阅读机。 时刻t2，进程 p1又请求光标记阅读机 进程 p2又请求打印机,(2) 用信号灯的P、V操作描述死锁 设进程A与进程B共享一台打印机(R1) 和一台光标记阅读机(R2) 。 用信号灯的P、V操作表示资源的申请和释放。 信号灯设置 s1：表示R1可用，初值为1。 s2：表示R2可用，初值为1。 讨论两种资源请求序列，哪种

7、情况可能产生互相死等的局面。,进程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(s2)； p(s1)； 占用R2 占用R1 v(s1)； v(s2)； v(s2)； v(s1)； v(s2)； v(s1)； ,2. 什么是死锁 在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，称这一组进程产生了死锁。 5.3.2 死锁的起因和条件 1. 引起死锁的原因 系统资源

8、不足而竞争资源（系统提供的资源个数少于并发进程所要求的该类资源数）； 进程推进顺序非法（如P(empty)与P(s)顺序交换时）。,2. 死锁图解,R1,R2,A,B,分配给,申请,申请,分配给,进程A与B，其中资源R1分配给A，R2分配给B。A再释放R1之前还需要R2，但B在释放R2之前需要R1，因此构成循环等待得到的资源，造成死锁。,3. 产生死锁的必要条件 (1) 互斥条件 涉及的资源是非共享的，即为临界资源。 (2) 不剥夺条件 进程所获得的资源在未使用完毕之前，不能被 其他进程强行夺走。 (3) 部分分配 进程每次申请它所需要的一部分资源。在等待 一新资源的同时，进程继续占用已分配到

9、的资源。 (4) 环路条件（循环等待条件） 存在一种进程的循环链，链中的每一个进程已 获得的资源同时被链中下一个进程所请求。,5.3.3 解决死锁问题的策略 解决死锁的策略： 采用静态资源分配方法预防死锁 采用有控资源分配方法避免死锁 死锁的检测与恢复,5.3.4 死锁的预防（静态策略） 破坏产生死锁四个必要条件中的一个或几个，可预防系统部产生死锁。 1. 破坏“互斥条件” 即不互斥使用临界资源（不可行） ； 2. 破坏“部分分配（占用并等待）条件” 系统对进程实行一次性分配的方案，即要么全部给它，要么一个也不给； 3. 破坏“不可剥夺条件” 即可剥夺资源（实现比较难）； 4. 有序资源分配法

10、（动态） 系统中所有资源都给定一个唯一的编号，所有分配请求必须以上升的次序进行。当遵守上升次序的规则时，若资源可用，则予以分配；否则，请求者等待。,5.3.5 死锁的避免（动态策略）,1.方法 对进程所发出的每一个申请资源的活动加以动态地检查，并根据检查结果决定是否进行资源分配。 2.避免死锁的实质：如何使系不统进入不安全状态。 3.安全状态 系统中所有进程能够按照某种次序分配资源并且依次运行完毕，这种进程序列P1，P2，P3Pn就是安全序列，如果存在安全序列，称系统处于安全状态，否则，处于不安全状态。,例：假设系统有三个进程P1、P2和P3，共有12台磁带机，进程P1共要求10台，p2、p3

11、分别要求5台和9台。设在T1时刻，P1、P2、P3分别已获得5台，2台和2台，试分析系统在T1时刻的安全状态。,存在一个安全序列P2，P1，P3，因此，系统在T1时刻是安全的。,4. 银行家算法 （1）历史：1965年Dijkstra提出用于银行顾客贷款，保证系统杜绝死锁的方法，1969年Haberman推广； （2）银行家算法的数据结构 银行家算法中数据结构如下： n ：系统中的进程个数； m ：系统中的资源类数。,1）Available（m）：现有资源向量。 Available（j）=k表示k个未分配的j类资源 2）Max（n，m）：资源最大申请量矩阵。 Max（i，j）=k表示第i个进程

12、在运行过程中对第j类资源的最大申请量为k。 3）Allocation（n，m）：资源分配矩阵。 Allocation(i,j)=k表示进程i已占有k个j类资源。 4）Need（n，m）：进程以后还需要的资源矩阵。 Need（i，j）=k表示进程i以后还需要k个第j类资源。 显然有Needi,j=Maxi,j-Allocationi,j。 5）Request（n，m）：进程申请资源矩阵。 Request（i，j）=k表示进程i申请k个第j类资源。,（3）银行家算法如下： 若进程i申请资源，申请资源向量为Request（i），则有如下资源分配过程： 1)如果Request（i）Need（i）或Re

13、quest（i）Max（i）， 则报错返回。 2)如果Request（i）Avaliable，则进程i进入等待资源状态， 返回。 3)假设进程进程i的申请已获批准，于是修改系统状态： Avaliable=Avaliable-Request（i） Allocation（i）=Allocation（i）+Request（i） Need（i）=Need（i）-Request（i）,4)调用安全状态检查算法: 设Work（m）为临时工作向量。初始时Work=Available。令 N=1，2，n。 a)寻求jN 使其满足：Need（j）=Work，若不存在这样的 j则转至c）。 b)Work=Work

14、+Allocation（j） N=N-j 转至a）。 c)如果N=空集 则返回（系统安全）。如果N空集 则返回 （系统不安全）。 5)若系统处于安全状态，则将进程i申请的资源分配给进程i,返回。 6)若系统处于不安全状态，则不将进程i申请的资源分配给进程i， 恢复原来的资源分配状态，让进程i等待。 Avaliable = Avaliable + Request（i） Allocation（i）=Allocation（i）-Request（i） Need（i）=Need（i）+ Request（i）,（4）例1：系统拥有某类资源10个。现有进程P、Q、R共享该类资源。它们申请该类资源的最大需求量

15、如下，当这些进程动态申请资源时，按银行家算法应如何分配，能保证不发生死锁。,进程 最大需求量 已占有资源 P 8 4 Q 4 2 R 9 2,可用资源 2,例2：设系统状态如下：,使用银行家算法回答下列问题： （1）Max的值分别是多少？ (2)此刻系统是否处于安全状态 （3）若进程3提出请求Request(2,2,2),系统可否将资源分配给它。,5.3.6 死锁的检测和恢复（解除）,1.死锁的检测（两个方法） （1）前银行家算法中的安全检测算法 1）将不需要，不占有资源的进程（即：Need=Allocation=0）记入表L中，并令Work=Available; 2)从进程集合中找一个未记入

16、L中的且Need=Work的进程，若不存在这样的进程，则转3）；否则将该进程记入表L中，Work=Work+Allocation,并重复执行2）； 3）若不能把所有进程都记入L表中，则表示这些进程将会发生死锁，否则不会产生死锁。,（2）简化资源分配图,算法： 1)在图中找出一个非孤立的进程顶点P,P的请求边均能立即满足； 2）若找到了这样的P，则将于P相连的边全部删除，转1），否则，简化过程结束。 如果化简后所有的顶点都成了孤立点，则称改图可完全化简，否则，称不可完全化简，系统中有死锁的充分必要条件是资源分配图不可完全化简。, r1, r2,P1,P2,P3,P4,化简过程如下：, r1, r2,P1,P2,P3,P4,第一步：p2,p4能立即满足, r1, r2,P1,P2,P3,P4,第二步：p1,p3也能立即满足, r2,r3,P1,P2,P3,练习：化简下面的资源分配图，判断此时系统是否会发生死锁。, r1,2.死锁的恢复（解除）,当发现进程死锁后，便立即把它从死锁状态中解脱出来，称