操作系统计算题.doc

计算题:
一、 生产消费者问题
为解决生产者消费者问题,应该设两个同步信号量,一个说明空缓冲区得数目,用S1 表示,初值为有界缓冲区得大小Ｎ,另一个说明已用缓冲区得数目,用Ｓ２表示,初值 为0。
由于在此问题中有M个生产者与N个消费者,它们在执行生产活动与消费活动中要对有界缓冲区进行操作。由于有界缓冲区就是一个临界资源,必须互斥使用,所以，另外还需要设置一个互斥信号量mｕtex,其初值为1。
P:
i = 0;
while (1)
{
生产产品;
P(S1);
P(mutex);
往Buffer [i]放产品;
i = (i+1) % n;
V(mutex);
V(S2);
};

Q:
j = 0;
while (1)
{
P(S2);
P(mutex);
从Buffer[j]取产品;
j = (j+1) % n;
V(mutex);
V(S1);
消费产品;
};

二、 地址转换
例１:若在一分页存储管理系统中,某作业得页表如下所示。已知页面大小为10２4字节,试将逻辑地址１０11,２1４8，30０0，4000,5０12转化为相应得物理地址。

页号 　 　 　 　 　 　 块号
０ 　 　 　 　　　 　 　　 　 　 　 2
１ 　 　 　 　 　 　　　　 　 3
2 　 　 　 　 　 　 　 　１
３　 　 　 　 　 　 　 ６
解:本题中,为了描述方便,设页号为P,页内位移为W,逻辑地址为A,页面大小为Ｌ,则:
p=iｎｔ(A／L)
ｗ＝A　moｄ L
对于逻辑地址1０11
ｐ=int(１０11/1０2４)＝0
w=１011 mｏd 10２４=10１1
查页表第0页在第二块,所以物理地址为3059。
对于逻辑地址2148
p＝ｉｎt(2148/1024)=2
　 w=2148 mod　10２４=1０0
　查页表第2页在第1块，所以物理地址为112４。
对于逻辑地址３0０0
ｐ＝int(3000/１024)=2
　　w＝３0０0 mod　1024＝9２８
　查页表第2页在第1块, 所以物理地址为179６。
对于逻辑地址4000
p=ｉnt(4000/１024)＝３
ｗ=4000mod 1024=９2８
查页表第3页在第６块, 所以物理地址为７072。
对于逻辑地址5０12
　ｐ＝int(5012/1０24)＝４
　w＝５012moｄ102４=916
因页号超过页表长度，该逻辑地址非法。
例2:
在一分页存储管理系统中，逻辑地址长度为16位,页面大小为40９6字节,现有一逻辑地址为2F6AH,且第0,　1, 2页依次存放在物理块５， 10 ,11中,问相应得物理地址为多少?
解：由题目所给给条件可知，本页式系统得逻辑地址结构为:

逻辑地址2F６AH得二进制表示如下:

由此可知逻辑地址2F6AH得页号为2,该页存放在第11号物理块中,用十六进制表示志号为B，所以物理地址为BF6AH、
三、 求文件最大长度
例：设文件索引节点中有７个地址项,其中4个地
址项为直接地址索引,2个地址项就是一级间接地址索
引，1个地址项就是二级间接地址索引,每个地址项大
小为4字节，若磁盘索引块与盘块大小均为２56字
节，则可表示得单个文件得最大长度就是多少?
解答:本题得文件结构属混合索引分配方式。每个地址项大小为4字节,索引块与盘块大小为２５6字节,每个索引块中得项目数=2５6B/4B=64个。4个地址项为直接地址索引,对应得文件大小为４×２56B=1ＫB。2个地址项就是一级间接地址索引,对应得文件大小就是2×64×２56Ｂ=32ＫＢ,一个地址项就是二级间接地址索引,对应得文件大小为1×64×6４×256Ｂ=１０24KB。所以单个文件得最大长度=1KＢ+32KＢ＋１02４KＢ＝1057ＫB。
四、 磁盘调度算法:
1. 先来先服务ＦCFS　
2. 最短寻道时间优先SSＴF　
3. SCAN算法
4. 循环扫描(CＳCＡＮ)算法
例:假设一个活动头磁盘有２00道, 编号从0-1９9、 当前磁头正在１43道上服务, 并且刚刚完成了125道得请求、 现有如下访盘请求序列（磁道号）:
　 　 86, 1４7， 9１, 177, ９4, 150,　102, 175,　13０
试给出采用下列算法后磁头移动得顺序与移动总量(总磁道数)、
　 (１)、 先来先服务(FＣFS)磁盘调度算法、
（2)、 最短寻道时间优先(ＳＳTF)磁盘调度算法、
(3)、　扫描法（SCAＮ）磁盘调度算法、(假设沿磁头移动方向不再有访问请求时，　磁头沿相反方向移动、)
答案:三、(1)86,147,91，１77,94,1５0,102,175，130
　　(2)当前磁头在143道上:
　 147，150,１３0,１０2,94,９1,８6，175,177
　 (３）当前磁头在1４３道上,并且刚刚完成１25道得请求
　　 　１47，150,175,177,１3０，10２，94,91,86
五、 调度算法(求周转时间,加权周转时间)
1.先来先服务调度算法FCＦS:该算法按照进程进入就绪队列得先后顺序选择最先进入该队列得进程,把处理机分配给它,使之投入运行。
例
２.优先级调度算法:总就是选择具有最高优先级得进程首先使用处理机。在这种算法 中,首先考虑得问题就是如何确定进程得优先数。 分为：
ﻩ静态优先权:在创建进程得时候便确定得,且在进程得运行期间保持不变。(简单ﻩ易行,系统开销小,但不够精确,很可能出现优先权低得作业(进程）长期不被调 度得情况。所以,只在要求不太高得系统中,才使用静态优先数(权）)
ﻩ动态优先权:在创建进程时所赋予得优先权,可以随进程得推进而改变，以便获得 更好得调度性能　
例：

３、最短作业/进程优先法(SJＦ／SＰF）:SJＦ：从后备队列中选择估计运行时间最短得作业,先调入内存运行。
ＳＰF：从就绪队列中选择估计运行时间最短得进程，先将处理机分配给它，使它立即执行。
4、最高响应比作业优先算法(HRN）:就是对FCFS方式与SＪF方式得一种综合平衡响应比。Ｒ=(作业等待时间+需运行时间)/ 需运行时间
　 　=１+已等待时间　/ 需运行时间
＝1＋W/T
例：

六:页面置换算法
先进先出页面淘汰算法(FIFO)
选择在内存中驻留时间最长得页并淘汰之
理想淘汰算法—最佳页面算法(ＯＰT）
　　淘汰以后不再需要得或最远得将来才会用到得页面
最近最久未使用页面淘汰算法(ＬRＵ)
　选择最后一次访问时间距离当前时间最长得一页并淘汰之
即淘汰没有使用得时间最长得页
1． 已知页面走向为1、2、1、3、1、２、４、２、1、3、４,且开始执行时主存中没有页面。若只给该作业分配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少？假定现有一种淘汰算法,该算法淘汰页面得策略为当需要淘汰页面时,就把刚使用过得页面作为淘汰对象,试问就相同得页面走向,缺页率又为多少?
[分析及相关知识] 　 在进行内存访问时,若所访问得页已在主存,则称此次访问成功;若所访问得页不在主存,则称此次访问失败,并产生缺页中断。若程序P在运行过程中访问页面得总次数为Ｓ，其中产生缺页中断得访问次数为F,则其缺页率为：Ｆ／s、
解:根据所给页面走向，采用FIFO淘汰算法得页面置换情况如下:
页面走向 　 1 　　 　２　 　 　 1 　 3 　 1 　　2　 　 ４ 2　 　 1 ３ ４
物理块1 　 １　 　　 １ 　　 　 3 　 3 　 　 　2　 　 2 　 　 　 　 　　 １ １ 4
物理块2 　　 　２ 　 　　 2 　 １ 1 　 ４ 　 　　 　 4 　 　3　 　3
缺页　 　 　缺 缺　 缺　　　　 缺 　 缺 　缺 　 　缺 缺 缺
从上述页面置换图可以瞧出:页面引用次数为1１次,缺页次数为9次,所以缺页率为9／11。
若采用后一种页面淘汰策略,其页面置换情况如下：
页面走向 1 　2 　　 1 　　 　３　　 　 1　 　　 ２ 　　　 ４　　　　 2　 　 1 3 ４
物理块1 1 　1 　 　　　　3 1 　 　 　 　　1 1 　　3 ４
物理块2 　 　　 2 　 ２　 　　2　 　　 4　　 　 　2 　２ 2
缺页 　 缺 　 缺 　　 　 缺 　缺　 　　 　　 缺 缺　　 　 　缺　　 缺
在一个请求分页存储管理系统中,一个作业得页面走向为4，３,2，1，4,3,５,4，3，２,1，5,当分配给该作业得物理块数分别为３,4时,试计算采用下述页面淘汰算法时得缺页率（假设开始执行时主存中没有页面),并比较所得结果。
（1） 最佳置换淘汰算法
（2） 先进先出淘汰算法
（3） 最近最久未使用淘汰算法
解：(１)根据所给页面走向，使用最佳页面淘汰 算法时,页面置换情况如下:
走向 　4 3 2　 1 4 　３ 5 　4 3 2 　1 5

块1　 　4 4 　 4　 4　 4　 　　 2 2
块２ 　 ３ 3　 3　 　 3 　　　 3 　１
块３ 　 2 1　 　 5 　 5 5
缺页 　缺　 缺 缺 缺　 　 缺　 　 缺　　缺
缺页率为:7/12
走向 　　4 ３ ２ 　1　　４ 3　　５　　4 3 2 1 5

块1 ４ ４ 4 4 　　 4 　 　　 　1
块２　 　 ３ 　 3　 3 3　　 　 　3
块3 　 　 2　　2 　 ２　 　 　２
块4　 　　 　 1 　 　 5 　 　 　 5
缺页　 缺 缺 缺　缺　 　 　缺 　　 缺 缺
缺页率为：６/１2
由上述结果可以瞧出，增加分配 给作业　得内存块数可以降低缺页率
（2）根据所给页面走向,使用最佳页面淘汰　算法时,页面置换情况如下：
走向 ４ 　3 2 1 4 ３ 　5 4　 ３ ２　 1　 ５

块1 4 ４ ４　 1 　1 　1　 ５ 　 　 5 5
块２　　　　 ３　　 3 　3 4　 ４ 4 　 3 2
块3 　　 　 　　 2　 2 ２ 3 3 　　2 1
缺页 　 缺 缺 缺　缺　 　 缺 　 缺 缺
缺页率为:9/1２
走向 　 ４ 　３ 2 　1 　4 3 5 　4 3 　２ 1 5

块1 4 　4　 4 4 　 5　　5　　５ 5 1 1
块2 ３ 3 3 　 　 ３ ４　 ４ 　4 4 ５
块3 　 　 　 2 　２　 　 ２ 　２　 3 　3　 3 3
块4 　　 　　１ 　 　　 1 1 1 　2 　２ 2
缺页　 缺 　缺 缺 缺 　 　缺 　 　 缺 缺
缺页率为:10/1２
由上述结果可以瞧出,对先进先出算法而言,增加分配给作业得内存块数反而使缺页率上升，这种异常现象称为Beｌadｙ 现象 。
(３)　根据所给页面走向,使用最佳页面淘汰 算法时，页面置换情况如下:
走向 　 　４　 　3 　2 １ 4 　3 5 4 ３ 2 1 ５

块1　 　4　 4 4 1 1 1 5 　 ２　 2　　2
块2 　 　 　３　 ２ 4　 ４ ４　 　 4 １ 1
块3 　 　 　2 　3　 2 3 3　 　 　 　３ 3 5
缺页 　　缺 　缺 缺 缺　　 　　缺　 缺 　缺
缺页率为:１0/12
走向 4　　　3 ２　 　1 　 4 3 5 　　4 3 2 １ ５ 　
块1 　 4 4 　 4 4　 　 　 　 ４　　　 　 4 　4 5
块２　　 　 　3 3 3 　 3 　 　 3 　 ３ 3
块3　　　 　 2 　　2 　 5 　 　 5 　 1 1
块4 　 　　 　　 　1 　 　 １ 　 2 ２　　 2
缺页　 　 缺 缺 　缺 缺 缺 　　 　　 缺 缺 缺
缺页率为:8/12
　由上述结果可以瞧出,增加分配给作业得内存块数可以降低缺页率、