admin 管理员组文章数量: 887021
操作系统期末考试复习经典计算题
-
-
- 1.银行家算法
- 2.计算周转时间
-
- 2.1 先来先服务（FCFS）
- 2.2 短作业优先调度算法（SJF）
- 2.3 优先级调度算法和高响应比优先调度算法
- 3.页面置换算法（虚拟存储器）
- 4.磁盘调度算法
- 5.存储器管理：基于顺序搜索的动态分区分配算法
- 6.存储器管理-分页存储方式：计算物理地址和有效访问时间（EAT）
- 7.存储器管理和进程调度，作业调度相结合
- 8.哲学家进餐
-
1.银行家算法
在银行家算法的例子中，如果出现下述资源分配情况，试问：
Process Allcation Need Available
P0 0 0 3 2 0 0 1 2 1 6 2 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 3 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
（1）该状态是否安全？
（2）进程P2提出请求Request(1,2,2,2)后，系统是否能将资源分配给它？
解：（1）利用安全性算法，对上述资源进行分配后找到可分配序列，<P0,P3,P1,P2,P4>，所以是安全的
Process Work Allcation Need work(Work+Allocation) Finish
P0 1 6 2 2 0 0 3 2 0 0 1 2 1 6 5 4 true
P1 1 9 8 6 1 0 0 0 1 7 5 0 2 9 8 6 true
P2 2 9 8 6 1 3 5 4 2 3 5 6 3 12 13 10 true
P3 1 6 5 4 0 3 3 2 0 6 5 2 1 9 8 6 true
P4 3 12 13 10 0 0 1 4 0 6 5 6 3 12 14 14 true
(2)首先Request2(1,2,2,2)<=Need2;Request2(1,2,2,2)<=Available，于是假定系统对其进行资源分配
并修改Available、Allcation2、Need2向量，修改结果为Available(0,4,0,0),Allcation2(2,5,7,6),Need2(1,1,3,4)
Process Work Allcation Need work(Work+Allocation) Finish
P0 0 0 3 2 0 0 1 2
P1 1 0 0 0 1 7 5 0
P2 2 5 7 6 1 1 3 4
P3 0 3 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
资源分配后对程序进行安全性检查，发现对于任意Needi<=Available(0,4,0,0)不成立。即Available不能满足任何进程的请求，系统进入不安全状态。所以不能分配!
2.计算周转时间
2.1 先来先服务（FCFS）
- 周转时间=完成时间-到达时间
带权周转时间=周转时间/服务时间
举例：在一个单道批处理系统中，有一组作业的提交时刻和运行时间如下
作业名 A B C D
提交时间 8.0 8.5 9.0 9.1
运行时间 1.0 0.5 0.2 0.1
采用先来先服务算法，请计算该组作业的平均周转时间和平均带权周转时间。
解：
作业名 A B C D 平均
提交时间 8.0 8.5 9.0 9.1
开始时间 8.0 9.0 9.5 9.7
完成时间 9.0 9.5 9.7 9.8
周转时间 1.0 1.0 0.7 0.7 0.85
带权周转时间 1.0 2.0 3.5 7.0 3.375
所以，平均周转时间T=(1.0+1.0+0.7+0.7)/4=0.85
平均带权周转时间W=(1.0+2.0+3.5+7.0)/4=3.375
2.2 短作业优先调度算法（SJF）
- 注意与SPF短进程调度算法的差别
举例：在一个单道批处理系统中，有一组作业的提交时刻和运行时间如下表所示
作业名 A B C D
提交时间 8.0 8.5 9.0 9.1
运行时间 1.0 0.5 0.2 0.1
采用短作业优先的调度算法，请计算该组作业的平均周转时间和平均带权周转时间。
解：
作业名 A B C D 平均
提交时间 8.0 8.5 9.0 9.1
开始时间 8.0 9.3 9.0 9.2
完成时间 9.0 9.8 9.2 9.3
周转时间 1.0 1.3 0.2 0.2 0.675
带权周转时间 1.0 2.6 1.0 2.0 1.65
所以，平均周转时间 T=(1.0+1.3+0.2+0.2)/4=0.675
平均带权周转时间 W=(1.0+2.6+1.0+2.0)/4=1.65
2.3 优先级调度算法和高响应比优先调度算法
优先权=（等待时间+要求服务时间）/要求服务的时间==相应时间/要求服务时间
举例：在一个单道批处理系统中，有一组作业的提交时刻和运行时间如下表所示
作业名 A B C D
提交时间 8.0 8.5 9.0 9.1
运行时间 1.0 0.5 0.2 0.1
采用采用作业响应比高优先的调度算法，请计算该组作业的平均周转时间和平均带权周转时间。
解：
9.0时，计算响应比：
B的响应比=1+0.5/0.5=2
C的响应比=1+0/0.2=1
D没有到达(先执行B)
9.5时，计算响应比
C的响应比 =1+0.5/0.2=3.5
D的响应比=1+0.4/0.1=5(先执行D)
作业名 A B C D 平均
提交时间 8.0 8.5 9.0 9.1
开始时间 8.0 9.0 9.5 9.6
完成时间 9.0 9.5 9.6 9.8
周转时间 1.0 1.0 0.5 0.8 0.825
带权周转时间 1.0 2.0 5.0 4.0 3
所以，平均周转时间T=(1.0+1.0+0.5+0.8)/4=0.825
平均带权周转时间W=(1.0+2.0+5.0+4.0)/4=3
3.页面置换算法（虚拟存储器）
假定系统为某进程分配了三块物理页，并有以下页面：
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
Y表示缺页，N表示不缺页。（初始的三次千万记得要加！！）
OPT最佳置换算法：每次选择未来长时间不被访问的或者以后永不使用的页面进行淘汰。(虽好，但不可能实现)
页面走向 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
物理块0 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
物理块1 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
物理块2 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
缺页 Y Y Y Y N Y N Y N N Y N N Y N N N Y N N
缺页次数 9
页面置换次数 6
缺页率 9/20
FIFO先进先出页面置换算法：把内存中最先进入的页面予以淘汰。
页面走向 7 0版权声明：本文标题：大学操作系统期末考试复习经典计算题快速回顾 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727377129h1110995.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论