资源预览内容
第1页 / 共32页
第2页 / 共32页
第3页 / 共32页
第4页 / 共32页
第5页 / 共32页
第6页 / 共32页
第7页 / 共32页
第8页 / 共32页
第9页 / 共32页
第10页 / 共32页
亲,该文档总共32页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第5章 资源分配与调度,资源分配与调度,资源管理概述 资源分配的机构和策略 死锁,1,资源分配与调度主要内容,资源管理概述,资源分配与调度资源管理概述,2,1. 资源管理功能 (1) 资源数据结构的描述 包含资源的物理名、逻辑名、类型、地址、分配状态等 信息。 (2) 确定资源的分配原则 (调度原则) 决定资源应分给谁,何时分配,分配多少等问题。 (3) 实施资源分配 执行资源分配;资源收回工作。 (4) 存取控制和安全保护 对资源的存取进行控制并对资源实施安全保护措施。,资源分配与调度资源管理概述,3,2. 资源资源的静态分配和动态分配 (1) 资源的静态分配 系统对作业一级采用资源静态分配方法。 系统在调度作业时,根据作业所需资源进行分配;并在作 业运行完毕 时,收回所分配的全部资源。这种分配通常称 为资源的静态分配。 (2) 资源的动态分配 系统对进程一级采用资源动态分配方法。 系统在进程运行中,根据进程提出的资源需求,进行资源 的动态分配和回收。这种分配通常称为资源的动态分配。,资源分配与调度资源管理概述,4,3. 虚拟资源 (1) 操作系统对资源区分二种不同的概念 物理资源 (实资源) 虚拟资源 (逻辑资源) (2) 目的 方便用户使用 资源可动态分配,提高资源利用率,资源分配与调度资源管理概述,5,进程调度,地址映射,逻辑设备 虚拟设备,文件逻辑结构,资源分配与调度资源管理概述,进程,设备分配 动态映射,虚存 (程序地址空间),磁盘空间分配 文件目录查找,(3) 计算机系统中的物理资源与虚拟资源分析,资源分配结构和策略,资源分配与调度资源分配机构和策略,6,(1) 资源描述器 资源描述器定义 描述描述各类资源的最小分配单位的数 据结构称为资源描述器 rd。 如:主存分区分配方法中,最小分配单 位为主存分区。 资源描述器内容 资源名、资源类型、最小分配单位的大 小、地址、分配标志、描述器链接信息、 存取权限、密级、存取时间,资源分配与调度资源分配机构和策略,1. 资源分配的机构,内存分布状况图,7,(2) 资源信息块 资源信息块定义 描述某类资源的请求者、可用资源和该类资源分配程序等 必要信息的数据结构。 资源信息块内容,资源分配与调度资源分配机构和策略,资源信息块示意图,8,(3) 资源信息块例 中央处理机资源信息块内容,资源分配与调度资源分配机构和策略,中央处理机资源信息块示意图,9,2. 资源分配策略 (1) 常用的资源分配策略 先请求先服务 每一个新产生的请求均排在队尾; 当资源可用时,取队首元素,并满足其需要。 排序原则:按请求的先后次序排序。,资源分配与调度资源分配机构和策略,10, 优先调度 对每一个进程指定一个优先级; 每一个新产生的请求,按其优先级的高低插到相应的 位置; 当资源可用时,取队首元素,并满足其需要。 排序原则:按优先级的高低排序。,资源分配与调度资源分配机构和策略,11, 针对设备特性的调度策略 调度的目标 当有大量I/O请求时,降低完成这些I/O服务的总时间。,资源分配与调度资源分配机构和策略, 例:讨论对磁盘访问的调度,有如下5个请求。,柱面号 盘面号 块号 5 2 1 5 3 8 5 3 5 40 6 3 2 7 7,12, 移臂调度 总是选取与当前移动臂前进方向上最近的那个I/O请求, 使移臂距离最短。,资源分配与调度资源分配机构和策略,对磁盘访问的5个请求,按移臂调度应作如下调整。,柱面号 盘面号 块号 2 7 7 5 2 1 5 3 8 5 3 5 40 6 3,13, 旋转调度 总是选取与当前读写头最近的那个I/O请求,使旋转圈 数最少。,资源分配与调度资源分配机构和策略,对磁盘访问的5个请求,再按旋转调度应作如下调整。,柱面号 盘面号 块号 2 7 7 5 2 1 5 3 5 5 3 8 40 6 3,死锁,资源分配与调度死锁,14,(1) 死锁的例 设备共享 进程 p1、p2共享一台打印机和一台输入机 时刻 t1:进程 p1 占用打印机, 进程 p2 占用输入机; 时刻 t2:进程 p1 又请求输入机, 进程 p2 又请求打印机。 时刻t2后,系统出现僵持局面,即出现了死锁现象。,资源分配与调度死锁,1. 什么是死锁,15,(2) 用信号灯的P、V操作描述死锁 设进程p1与进程p2共享一台打印机(r1) 和一台输入机(r2), 用信号灯的p、v操作表示资源的申请和释放。 信号灯设置 s1:表示r1可用,初值为1 s2:表示r2可用,初值为1 讨论两种资源请求序列,哪种情况可能产生互相死等的 局面。 程序描述如下:,资源分配与调度死锁,16,程序描述1 程序描述2 进程p1 进程p2 进程p1 进程p2 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,有可能出现死锁。,资源分配与调度死锁,17,(3) 什么是死锁 在两个或多个并发进程中,如果每个进程持有某种资源而 又都等待着别的进程释放它或它们现在保持着的资源,否 则就不能向前推进。此时,称这一组进程产生了死锁。,资源分配与调度死锁,2. 死锁的起因和条件,(1) 引起死锁的原因 系统资源不足 进程推进顺序非法,18,资源分配与调度死锁,(2) 死锁图解,A1: p1 request (r1) B1: p1 request (r2) C1: p1 release (r1) D1: p1 release (r2) A2: p2 request (r2) B2: p2 request (r1) C2: p2 release (r2) D2: p2 release (r1),死锁图解,19,资源分配与调度死锁, 互斥条件 涉及的资源是非共享的,即为临界资源。 不剥夺条件 进程所获得的资源在未使用完毕之前,不能被其他进程强 行夺走。 部分分配 进程每次申请它所需要的一部分资源。在等待一新资源的 同时,进程继续占用已分配到的资源。 环路条件 存在一种进程的循环链,链中的每一个进程已获得的资 源同时被链中下一个进程所请求。,(3) 产生死锁的必要条件,21,资源分配与调度死锁,3. 系统状态分析 (1) 初始状态描述 假定一个系统包括n个进程和m类资源,表示如下 一组确定的进程集合,记作: p=p1,p2,pi,pn 一组不同类型的资源集合,记作: r=r1,r2,rj,rm 矢量w说明各类可利用资源的总的数目 w=w1,w2,wj,wm,22,资源分配与调度死锁,(2) 资源请求矩阵 在时刻 t 资源请求矩阵,表示如下,d(t) =,dij 表示进程pi还需要j类资源的数目,23,资源分配与调度死锁,(3) 资源分配矩阵 在时刻 t 资源分配矩阵,表示如下,a(t) =,aij 表示进程pi已占有j类资源的数目 什么情况下系统是安全的? 当进程请求某类资源时,进程对该类资源的需求量小于 当前时刻系统所拥有的该类资源的数目,那么满足进程 的这次请求,系统是安全的。,24,资源分配与调度死锁,4. 解决死锁问题的策略,破坏产生死锁的四个必要条件之一 解决死锁的策略 采用静态资源分配方法预防死锁。 采用有控资源分配方法避免死锁 死锁的检测与忽略,25,资源分配与调度死锁,5. 死锁的预防,(1) 静态预防死锁的方法 在作业调度时为选中的作业分配它所需要的所有资源,当 资源一旦分配给该作业后,在其整个运行期间这些资源为 它独占。,(2) 动态预防死锁的方法 有序资源分配法 系统中所有资源都给定一个唯一的编号,所有分配请求必 须以上升的次序进行。当遵守上升次序的规则时,若资源 可用,则予以分配;否则,请求者等待。,26,资源分配与调度死锁, 银行家算法 申请者事先说明对各类资源的最大需求量。在进程活动 期间动态申请某类资源时,由系统审查现有该类资源的 数目是否能满足当前进程的最大需求量,如能满足就予 以分配,否则拒绝。,27,资源分配与调度死锁, 银行家算法例 系统拥有某类资源10个,现有进程P、Q、R共享该类资 源,它们申请该类资源的最大需求量如下。,进程 最大需求量 已占有资源 P 8 4 Q 4 2 R 9 2,现申请资源个数 1 1 1,当这些进程动态申请资源时,按银行家算法应如何分 配,能保证不发生死锁。,第5章 资源分配与调度 小结,资源分配与调度小结,28,资源管理功能 资源分配策略 先请求先服务 优先调度 针对设备特性的调度 死锁 定义 举例 引起死锁的原因 产生死锁的必要条件 死锁预防 死锁避免 有序资源分配方法 银行家算法,资源分配与调度小结,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号