D E 6 8 5 2
算法 进程名 创建时刻 结束时刻 先来先服务 P1 P2 P3 P4 P5 时间片轮转 P1 P2 P3 P4 P5 非剥夺式优先级 P1 P2 P3 P4 P5 剥夺式优先级 P1 P2 P3 P4 P5 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 3 9 13 18 20 4 18 17 20 15 3 9 13 18 20 3 20 8 13 15 3 7 9 12 12 4 16 13 14 7 3 7 9 12 12 3 18 4 7 7 (3+18+4+7+7)=7.80 (3+7+9+12+12)/5=8.60 (4+16+13+14+7)/5=10.80 (3+7+912+12)/5=8.60 周转时间 平均周转时间/ms
1、 假设一个可移动磁头的磁盘具有２００个磁道，其编号为０～１９９，当前它刚刚结
束了１２５道的存取，正在处理１４９道的服务请求，假设系统当前Ｉ／Ｏ请求序列为：８８，１４７，９５，１７７，９４，１５０，１０２，１７５，１３８。试问对以下的磁盘Ｉ／Ｏ调度算法而言，满足以上请求序列，磁头将如何移动？并计算总的磁道移动数。
（1） 先来先服务算法（ＦＣＦＳ） （2）扫描法（ＳＣＡＮ）
(1)FCFS算法： 5分 当前149 下一磁道 移动距离 88 61 147 59 95 52 177 82 94 83 150 56 102 48 175 73 138 37 总的磁道移动数为：61+59+52+82+83+56+48+73+37=551 (2)SCAN算法： 5分 当前149 下一磁道 移动距离 150 1 175 25 177 2 147 30 138 9 102 36 95 7 94 1 88 6 总的磁道移动数为：1+25+2+30+9+36+7+1+6=117
2、 设系统中有四种类型的资源（A，B，C，D）和五个进程（P1，P2，P3，P4，P5），A
资源的数量6，B资源的数量为3，C资源的数量为4，D资源的数量为2。在T0时刻系统状态如下表所示。系统采用银行家算法来避免死锁。请回答下列问题： （1）T0时刻是否为安全状态？若是，请给出安全序列。 （2）若进程P2请求资源（0，0，1，0），能否实现资源分配？为什么？ （3）在（2）的基础上，若进程P5请求资源（0，0，1，0），能否实现资源分配？为什么？
T0时刻系统状态 进程 P1 P2 P3 P4 P5 最大资源需求量 A 4 0 4 1 2 B 1 2 2 1 1 C 1 1 1 1 1 D 1 2 0 1 0 A 3 0 1 1 0 已分配资源量 B 0 1 1 1 0 C 1 0 1 0 0 D 1 0 0 1 0 系统剩余资源数量 A 1 B 0 C 2 D 0
（1）T0时刻为安全状态。其中的一个安全序列为（P4，P5，P1，P3，P2） （其他可能的安全序列有：（P4，P5，P1，P2，P3），（P4，P1，X，X，X）） （2）可以为P2分配资源，因为分配后的状态还是安全的，其分析如下表：
P4 P5 P1 P2 P3 WORK 1，0，2，0 1，0，1，0 2，1，1，1 2，1，1，1 5，1，2，2 5，2，3，2 NEED 0，0，1，0 2，1，1，0 1，1，0，0 0，1，0，2 3，1，0，0 ALLOCATION 1，1，0，1 0，0，0，0 3，0，1，1 0，1，1，0 1，1，1，0 新WORK 1，0，1，0 2，1，1，1 2，1，1，1 5，1，2，2 5，2，3，2 6，3，4，2 FINISH True True True True True 分配给P2：（0，0，1，0） （3）进程P5再请求资源（0，0，1，0），则不能为之分配资源。因为分配资源后，不存在
安全序列，其分析如下表：
P1 P2 P3 P4 P5 WORK 1，0，1，0 NEED 1，1，0，0 ALLOCATION 新WORK 1，0，0，0 FINISH False False False False False 分配给P5：（0，0，1，0） 0，1，0，2 此时，WORK不能满足任何一个3，1，0，0 进程的请求使之运行结束，即进入了不安全状态。 0，0，1，0 2，1，0，0 考虑下面的页访问串：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3。假定物理块数为3，若应用下面的页面替换算法，分别会出现多少次缺页？
（1）LRU替换法算法 （2）FIFO替换算法 （3）Optimal替换算法 答：LRU算法的情况如下表：（4分） 页面走向 物理页0 物理页1 物理页2 缺页否 1 1 Y 2 1 2 Y 3 1 2 3 Y 4 4 2 3 Y 2 1 4 2 1 Y 5 5 2 1 Y 6 5 6 1 Y 2 5 6 2 Y 1 1 6 2 Y 2 3 1 3 2 Y 7 7 3 2 Y 6 7 3 6 Y 3 缺页次数为12。（1分）
FIFO算法的情况如下表：（4分） 页面走向 物理页0 物理页1 物理页2 缺页否 1 1 Y 2 1 2 Y 3 1 2 3 Y 4 4 2 3 Y 2 1 4 1 3 Y 5 4 1 5 Y 6 6 1 5 Y 2 6 2 5 Y 1 6 2 1 Y 2 3 3 2 1 Y 7 3 7 1 Y 6 3 7 6 Y 3 缺页次数为12。（1分）
Optimal算法的情况如下表：（4分） 页面走向 物理页0 物理页1 物理页2 缺页否 1 1 Y 2 1 2 Y 3 1 2 3 Y 4 1 2 4 Y 2 1 5 1 2 5 Y 6 1 2 6 Y 2 1 2 3 3 2 6 Y 7 3 7 6 Y 6 3 缺页次数为8。（1分）