PPT《第5章 资源分配与调度》

每一个新产生的请求,按其优先级的高低插到相应的 位置;

当资源可用时,取队首元素,并满足其需要.排序原则:按优先级的高低排序. 资源分配与调度――资源分配机构和策略 ? 表头 按按优先级的高低排序 高低按优先级高低排列的资源请求队列

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) 死锁的例 设备共享 进程 p

1、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) 死锁图解 N

0 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) 死锁图解

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

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