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

资源分配与调度——主要内容 资源管理概述 资源分配的机构和策略 死锁 1

资源分配与调度——资源管理概述 资源管理概述

1. 资源管理功能 (1) 资源数据结构的描述 (2) 确定资源的分配原则 (调度原则) (3) 实施资源分配 (4) 存取控制和安全保护 资源分配与调度——资源管理概述 1. 资源管理功能 (1) 资源数据结构的描述 包含资源的物理名、逻辑名、类型、地址、分配状态等 信息。 (2) 确定资源的分配原则 (调度原则) 决定资源应分给谁，何时分配，分配多少等问题。 (3) 实施资源分配 执行资源分配；资源收回工作。 (4) 存取控制和安全保护 对资源的存取进行控制并对资源实施安全保护措施。 2

2. 资源的静态分配和动态分配 (1) 资源的静态分配 (2) 资源的动态分配 资源分配与调度——资源管理概述 系统对作业一级采用资源静态分配方法。 系统在调度作业时，根据作业所需资源进行分配；并在作 业运行完毕 时，收回所分配的全部资源。这种分配通常称 为资源的静态分配。 (2) 资源的动态分配 系统对进程一级采用资源动态分配方法。 系统在进程运行中，根据进程提出的资源需求，进行资源 的动态分配和回收。这种分配通常称为资源的动态分配。 3

3. 虚拟资源 (1) 操作系统对资源区分二种不同的概念 (2) 目的 资源分配与调度——资源管理概述 物理资源 (实资源) 3. 虚拟资源 (1) 操作系统对资源区分二种不同的概念 物理资源 (实资源) 虚拟资源 (逻辑资源) (2) 目的 方便用户使用 资源可动态分配，提高资源利用率 4

(3) 计算机系统中的物理资源与虚拟资源分析 资源分配与调度——资源管理概述 (3) 计算机系统中的物理资源与虚拟资源分析 资源类别 物理资源 虚拟(逻辑) 映射 处理机 CPU 存储器 主存 设备 外部设备 信息 文件物理结构 进程 进程调度 虚存 (程序地址空间) 地址映射 逻辑设备 虚拟设备 设备分配 动态映射 磁盘空间分配 文件目录查找 文件逻辑结构 5

资源分配与调度——资源分配机构和策略 资源分配结构和策略

1. 资源分配的机构 (1) 资源描述器 资源分配与调度——资源分配机构和策略 ① 资源描述器定义 描述描述各类资源的最小分配单位的数 1. 资源分配的机构 20KB 52KB 66KB 130KB 230KB 256KB1 主存 程序4 程序1 程序3 OS (1) 资源描述器 ① 资源描述器定义 描述描述各类资源的最小分配单位的数 据结构称为资源描述器 rd。 如：主存分区分配方法中，最小分配单 位为主存分区。 ② 资源描述器内容 资源名、资源类型、最小分配单位的大 小、地址、分配标志、描述器链接信息、 存取权限、密级、存取时间 内存分布状况图 6

描述某类资源的请求者、可用资源和该类资源分配程序等 必要信息的数据结构。 ② 资源信息块内容 资源分配与调度——资源分配机构和策略 (2) 资源信息块 ① 资源信息块定义 描述某类资源的请求者、可用资源和该类资源分配程序等 必要信息的数据结构。 ② 资源信息块内容 请求者队列 可利用资源队列 资源分配程序 等待队列头指针 可利用资源队列头指针 资源分配程序入口地址 资源信息块示意图 7

(3) 资源信息块例 资源分配与调度——资源分配机构和策略 中央处理机资源信息块内容  PCB1 PCB2 PCBk 进程调度程序 ready_q_start 可用处理机信息 scheduler_addr CPU 中央处理机资源信息块示意图 8

2. 资源分配策略 (1) 常用的资源分配策略 资源分配与调度——资源分配机构和策略 ① 先请求先服务 每一个新产生的请求均排在队尾； 2. 资源分配策略 (1) 常用的资源分配策略 ① 先请求先服务 每一个新产生的请求均排在队尾； 当资源可用时，取队首元素，并满足其需要。 排序原则：按请求的先后次序排序。  表头 按请求的先后次序 先 后 按自然顺序排列的资源请求队列 9

每一个新产生的请求，按其优先级的高低插到相应的 位置； 当资源可用时，取队首元素，并满足其需要。 排序原则：按优先级的高低排序。 资源分配与调度——资源分配机构和策略 ② 优先调度 对每一个进程指定一个优先级； 每一个新产生的请求，按其优先级的高低插到相应的 位置； 当资源可用时，取队首元素，并满足其需要。 排序原则：按优先级的高低排序。  表头 按按优先级的高低排序 高 低 按优先级高低排列的资源请求队列 10

当有大量I/O请求时，降低完成这些I/O服务的总时间。 资源分配与调度——资源分配机构和策略 ③ 针对设备特性的调度策略 ⅰ 调度的目标 当有大量I/O请求时，降低完成这些I/O服务的总时间。 ⅱ 例：讨论对磁盘访问的调度，有如下5个请求。 柱面号 盘面号 块号 5 2 1 5 3 8 5 3 5 40 6 3 2 7 7 11

总是选取与当前移动臂前进方向上最近的那个I/O请求， 使移臂距离最短。 资源分配与调度——资源分配机构和策略 ⅲ 移臂调度 总是选取与当前移动臂前进方向上最近的那个I/O请求， 使移臂距离最短。 对磁盘访问的5个请求，按移臂调度应作如下调整。 柱面号 盘面号 块号 2 7 7 5 2 1 5 3 8 5 3 5 40 6 3 12

总是选取与当前读写头最近的那个I/O请求，使旋转圈 数最少。 资源分配与调度——资源分配机构和策略 ⅳ 旋转调度 总是选取与当前读写头最近的那个I/O请求，使旋转圈 数最少。 对磁盘访问的5个请求，再按旋转调度应作如下调整。 柱面号 盘面号 块号 2 7 7 5 2 1 5 3 5 5 3 8 40 6 3 13

资源分配与调度——死锁 死锁

1. 什么是死锁 (1) 死锁的例子 资源分配与调度——死锁 设备共享 进程 p1、p2共享一台打印机和一台输入机 1. 什么是死锁 (1) 死锁的例子 设备共享 进程 p1、p2共享一台打印机和一台输入机 时刻 t1：进程 p1 —— 占用打印机， 进程 p2 —— 占用输入机； 时刻 t2：进程 p1 —— 又请求输入机， 进程 p2 —— 又请求打印机。 时刻t2后，系统出现僵持局面，即出现了死锁现象。 14

(2) 用信号灯的P、V操作描述死锁 资源分配与调度——死锁 设进程p1与进程p2共享一台打印机(r1) 和一台输入机(r2)， 信号灯设置—— s1：表示r1可用，初值为1 s2：表示r2可用，初值为1 讨论两种资源请求序列，哪种情况可能产生互相死等的 局面。 程序描述如下： 15

资源分配与调度——死锁 程序描述1 程序描述2     p(s1)； p(s2)； p(s1)； p(s2)； 程序描述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，有可能出现死锁。 16

2. 死锁的起因和条件 (3) 什么是死锁 在两个或多个并发进程中，如果每个进程持有某种资源而 (1) 引起死锁的原因 资源分配与调度——死锁 (3) 什么是死锁 在两个或多个并发进程中，如果每个进程持有某种资源而 又都等待着别的进程释放它或它们现在保持着的资源，否 则就不能向前推进。此时，称这一组进程产生了死锁。 2. 死锁的起因和条件 (1) 引起死锁的原因 ① 系统资源不足 ② 进程推进顺序非法 17

(2) 死锁图解 资源分配与调度——死锁 N A1 B1 C1 D1 A2 B2 C2 D2 P1进程 P2进程 • 死锁图解 A1 B1 C1 D1 A2 B2 C2 D2 P1进程 P2进程 • 死锁图解 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) 18

(3) 产生死锁的必要条件 资源分配与调度——死锁 ① 互斥条件 涉及的资源是非共享的，即为临界资源。 ② 不剥夺条件 进程所获得的资源在未使用完毕之前，不能被其他进程强 行夺走。 ③ 部分分配 进程每次申请它所需要的一部分资源。在等待一新资源的 同时，进程继续占用已分配到的资源。 ④ 环路条件 存在一种进程的循环链，链中的每一个进程已获得的资 源同时被链中下一个进程所请求。 19

3. 系统状态分析 (1) 初始状态描述 资源分配与调度——死锁 假定一个系统包括n个进程和m类资源，表示如下 3. 系统状态分析 (1) 初始状态描述 假定一个系统包括n个进程和m类资源，表示如下 ① 一组确定的进程集合，记作： p={p1，p2，…，pi，…，pn} ② 一组不同类型的资源集合，记作： r={r1，r2，…，rj，…，rm} ③ 矢量w说明各类可利用资源的总的数目 w={w1，w2，…，wj，…，wm} 21

(2) 资源请求矩阵 资源分配与调度——死锁 在时刻 t 资源请求矩阵，表示如下 dij 表示进程pi还需要j类资源的数目 d(t) = 22

(3) 资源分配矩阵 资源分配与调度——死锁 在时刻 t 资源分配矩阵，表示如下 aij 表示进程pi已占有j类资源的数目 a(t) = 23

关于安全状态 A safe state is one in which there is at least one sequence of resource allocations to processes that does not result in a deadlock (i.e., all of the processes can be run to completion). An unsafe state is, of course, a state that is not safe. 《Operating Systems - Internals and Design Principles 》(8th edition) -- William Stallings

4. 解决死锁问题的策略 资源分配与调度——死锁 破坏产生死锁的四个必要条件之一 解决死锁的策略 采用静态资源分配方法——预防死锁。 4. 解决死锁问题的策略 破坏产生死锁的四个必要条件之一 解决死锁的策略 采用静态资源分配方法——预防死锁。 采用有控资源分配方法——避免死锁 死锁的检测与忽略 24

5. 死锁的预防 (1) 静态预防死锁的方法 在作业调度时为选中的作业分配它所需要的所有资源，当 (2) 动态预防死锁的方法 资源分配与调度——死锁 5. 死锁的预防 (1) 静态预防死锁的方法 在作业调度时为选中的作业分配它所需要的所有资源，当 资源一旦分配给该作业后，在其整个运行期间这些资源为 它独占。 (2) 动态预防死锁的方法 ① 有序资源分配法 系统中所有资源都给定一个唯一的编号，所有分配请求必 须以上升的次序进行。当遵守上升次序的规则时，若资源 可用，则予以分配；否则，请求者等待。 25

申请者事先说明对各类资源的最大需求量。在进程活动 期间动态申请某类资源时，由系统审查现有该类资源的 资源分配与调度——死锁 ② 银行家算法 申请者事先说明对各类资源的最大需求量。在进程活动 期间动态申请某类资源时，由系统审查现有该类资源的 数目是否能满足当前进程的最大需求量，如能满足就予 以分配，否则拒绝。 26

系统拥有某类资源10个，现有进程P、Q、R共享该类资 源，它们申请该类资源的最大需求量如下。 资源分配与调度——死锁 ③ 银行家算法例 系统拥有某类资源10个，现有进程P、Q、R共享该类资 源，它们申请该类资源的最大需求量如下。 进程 最大需求量 已占有资源 P 8 4 Q 4 2 R 9 2 现申请资源个数 1 当这些进程动态申请资源时，按银行家算法应如何分 配，能保证不发生死锁。 27

资源分配与调度——小结 第5章 资源分配与调度 小结

资源分配与调度——小结 资源管理功能 资源分配策略 死锁 先请求先服务 优先调度 针对设备特性的调度 定义 举例 引起死锁的原因 先请求先服务 优先调度 针对设备特性的调度 死锁 定义 举例 引起死锁的原因 产生死锁的必要条件 死锁预防 死锁避免 有序资源分配方法 银行家算法 28