OS算法作业

一、银行家算法 P137-139 第三章

1．假设有PA、PB、PC、PD、PE 共5个进程，共享A、B、C 3种资源，且系统资源总数分别为A=7、B=5、C=10。在T0时刻有以下分配情况： 资源 进程 PA PB PC PD PE 试求

（1） T0时刻系统可利用资源向量Available的值。 答：Available 的值是(2,0,3)

（2）以下2个小题没有因果关系，每小题都是以T0时刻分配情况为前提条件判断能否分配及理由。若能分配，请将分配过程填入表格，并写出存在的安全序列。

①PB进程申请资源A、B、C分别为 0、1、0，能否分配？为什么？ 答：不能分配，对于B的分配，资源不够。

②PC进程申请资源A、B、C分别为 0、0、2，能否分配？为什么？ 答： 可以分配。（2,0,3）的值足够分给（0,0,2）

安全序列：(PA,PC,PB,PE,PD) 资源 进程 PA PB PC PD PE

已分配（Allocation） A B C 0 1 2 0 3 0 2 1 2 2 0 3 1 0 2 需求（Need） A B C 2 0 1 3 1 7 1 0 2 0 5 6 1 2 0 Work+Allocation A B C 2 1 3 5 5 7 4 2 5 7 5 10 5 2 7 最大需求（MAX） A B C 2 1 3 3 4 7 3 1 4 2 5 9 2 2 2 已分配（Allocation） A B C 0 1 2 0 3 0 2 1 0 2 0 3 1 0 2 2.假定由5个进程{PA、PB、PC、PD、PE}和三种资源A、B、C且系统总共拥有的资源数量分别为A=7、B=5、C=10。在某时刻若有以下分配情况：（注意以下的4个小题没有因果关系，每小题都是以此分配情况为前提条件） 。

最大需求（MAX） 已分配 (Allocation) A、 B、 C A、 B、C PA 2 1 3 0 1 2 PB 3 4 7 0 3 0 PC 3 1 4 2 1 0 PD 2 5 9 2 0 3 PE 2 2 2 1 0 2

（1） PB进程申请资源A、B、C分别为 0、1、0，能否分配？为什么？ （2） PE进程申请资源A、B、C分别为 0、0、1，能否分配？为什么？ （3） PC进程申请资源A、B、C分别为 0、0、2，能否分配？为什么？ （4） PD进程申请资源A、B、C分别为 0、0、2，能否分配？为什么？

答：可利用资源A=2，B=0，C=3 题号 （1） （2） （3） （4） 不能分配 能分配 能分配 不能分配 （2,0,3）分配（0,1,0），资源不够分配 （2,0,3）分配（0,0,1），资源足够分配 （2,0,3）分配（0,0,2），资源足够分配 （2,0,3）分配（0,0,2），但在后面PA进程满足之后不能用于满足其他进程。 (3) (2分)

因为（3）已经分配了0 0 2，所以可利用资源是2 0 1 进程 PA PB PC PD PE allocation need Work+allocation finish T(1) T(4) T(2) T(5) T(3) 0 0 2 2 1 1 3 1 0 0 2 0 2 3 2 2 3 1 0 1 0 1 0 5 2 1 7 2 6 0 2 5 4 7 5 1 5 2 5 2 3 7 5 10 7 (4) （2分）

因为（4）已经分配了0 0 2 所以可利用资源是2 0 1 进程 PA PB PC PD PE allocation need work finish 0 0 2 2 1 1 3 1 0 0 2 0 0 5 2 2 3 1 0 1 0 1 0 5 2 1 7 4 4 0 2 1 3 T F F F F

二、磁盘调度算法 P311 第七章

1．磁头当前位置100#磁道，并正在向磁道号增加方向移动，现有以下访问请求序列： 65、59、38、88、96、106、73、12、125等待中。假设每移动一个磁道需要2ms，请按下列磁盘调度算法分别计算为完成上述各次访问的总寻道时间和平均寻道。寻道过程填入下表： 1、最短寻道时间优先 磁道号 96 88 73 65 59 38 12 106 125 移动磁道数 4 8 15 8 6 21 26 94 19 2、电梯调度SCAN 磁道号 106 125 96 88 73 65 59 38 12 移动磁道数 6 19 29 8 15 8 6 21 26 3、循环电梯调度SCAN 磁道号 106 125 12 38 59 65 73 88 96 移动磁道数 6 19 113 26 21 6 8 15 8 总寻道时间=402ms 平均寻道时间=44.67ms 总寻道时间=276ms 平均寻道时间=30.6ms 总寻道时间=444ms 平均寻道时间=49.3ms 最短寻道时间优先----离哪个磁道最近就先访问哪个 电梯调度SCAN-----先向上走（高），再向下走（低） 循环电梯调度SCAN----向向上走（高），然后回到最低再向上走（高）

三、作业调度算法

1.在单道批处理系统中，有下列四个作业，当第4个作业进入系统后（10:30）开始调度，采用响应比高优先的调度算法，忽略调度及I/O所需的时间。提示：响应比=1+作业等待时间/作业计算时间。

作业 A B C D 到达时间 10:00 10:06 10:12 10:30 需计算时间 24分钟 1小时 36分钟 12分钟 响应比 2.25 2.6 2.5 3 完成时间 周转时间（分钟） 带权周转时间 10:54 12:42 11:42 11:06 54 156 90 36 2.25 2.6 2.5 3 这四个作业按响应比高优先调度算法依次执行的次序是： A D C B 这四个作业按响应比高优先调度算法的平均周转时间是： 84 这四个作业按响应比高优先调度算法的平均带权周转时间是： 2.59

2．短作业/进程优先。假设：最后一个作业进入开始调度，忽略系统调度开销。（10:10开始） 作业 到达时间 需计算时间 （服务时间） 完成时间 周转时间（分钟） 带权周转时间 完成-到达 10:55 12:05 10:25 10:15 75 185 35 5 周转/服务 2.5 2.64 3.5 1 1 2 3 4 计算：

9:40 9:00 9:50 10:10 30分钟 70分钟 10分钟 5分钟 平均周转时间： (2.5+2.64+3.5+1)/4=2.41 平均带权周转时间： (75+185+35+5)/4=75 执行顺序： 4、3、1、2

四、页面置换算法 P188 第四章

先进先出（FIFO）置换算法 页面走向 缺页标志 4 √ 3 √ 4 3 2 √ 4 3 2 1 √ 1 3 2 4 4 √ 1 4 2 3 3 √ 1 4 3 2 5 √ 5 4 3 1 4 × 5 4 3 3 × 5 4 3 2 √ 5 2 3 4 1 √ 5 2 1 3 5 × 5 2 1 物理块1# 4 物理块2# 物理块3# 换出页号 缺页中断率= 9/12=75% 缺页次数=9

最近最久未使用（LRU）置换算法

3 2 1 页面走向 4 缺页标志 √ 物理块1# 4 物理块2# 物理块3# 物理块4# 换出页号 √ 4 3 √ 4 3 2 √ 4 3 2 1 4 × 4 3 2 1 3 × 4 3 2 1 5 √ 4 3 5 1 2 4 × 4 3 5 1 3 × 4 3 5 1 2 √ 4 3 5 2 1 1 √ 4 3 1 2 5 5 √ 5 3 1 2 4 缺页次数=8

缺页中断率=8/12=66.7%

本文来源：https://www.bwwdw.com/article/pbih.html