操作系统计算题.docx
《操作系统计算题.docx》由会员分享，可在线阅读，更多相关《操作系统计算题.docx（16页珍藏版）》请在冰点文库上搜索。
操作系统计算题
计算题:
生产消费者问题
为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用S1
表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用S2表示，初值为0。
由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。
由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还
1024字节,
需要设置一个互斥信号量mutex，其初值为1。
P:
Q:
i=0;
j=0;
while
（1）
while
（1）
{
{
生产产品；
P（S2）;
P（S”；
P（mutex）;
P（mutex）;
从Buffer[j]取产品；
往Buffer[i]放产
j=（j+1）%n;
品；
V（mutex）;
i=（i+1）%n;
V（S1）;
V（mutex）;
消费产品；
V（S2）;
};
};
二、地址转换
例1:
若在一分页存储管理系统中，某作业的页表如下所示。
已知页面大小为试将逻辑地址1011,2148,3000,4000,5012转化为相应的物理地址。
页号
块号
0
2
1
3
2
1
3
6
解：
本题中，为了描述方便，设页号为P,页内位移为W，逻辑地址为A，页面大小为L,
则：
p=int（A/L）
w=AmodL
对于逻辑地址1011
p=int（1011/1024）=0
w=1011mod1024=1011
查页表第0页在第二块，所以物理地址为3059。
对于逻辑地址2148
p=int（2148/1024）=2
w=2148mod1024=100
查页表第2页在第1块，所以物理地址为1124。
对于逻辑地址3000
p=int（3000/1024）=2
w=3000mod1024=928
查页表第2页在第1块，所以物理地址为1796。
对于逻辑地址4000
p=int（4000/1024）=3w=4000mod1024=928
查页表第3页在第6块，所以物理地址为7072。
对于逻辑地址5012
p=int（5012/1024）=4
w=5012mod1024=916
因页号超过页表长度，该逻辑地址非法。
例2:
在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为
2F6AH,且第0,1,2页依次存放在物理块5,10,11中，问相应的物理地址为多少？
解:
由题目所给给条件可知，本页式系统的逻辑地址结构为：
0010111101101010
由此可知逻辑地址2F6AH的页号为2,该页存放在第11号物理块中，用十六进制表示志号为B,所以物理地址为BF6AH.
三、求文件最大长度
例：
设文件索引节点中有7个地址项，其中4个地
址项为直接地址索引，2个地址项是一级间接地址索
弓I,1个地址项是二级间接地址索引，每个地址项大
小为4字节，若磁盘索引块和盘块大小均为256字
节，则可表示的单个文件的最大长度是多少？
解答：
本题的文件结构属混合索引分配方式。
每个地址项大小为4字节，索引块和盘
块大小为256字节，每个索引块中的项目数=256B/4B=64个。
4个地址项为直接地址索弓I,对应的文件大小为4X256B=1KB。
2个地址项是一级间接地址索引，对应的文件大小是2X64X256B=32KB，一个地址项是二级间接地址索引，对应的文件大小为1X64X
64>256B=1024KB。
所以单个文件的最大长度=1KB+32KB+1024KB=1057KB。
四、磁盘调度算法：
1.先来先服务FCFS
C丛1EJO号莊道开始）
蚊访冋的下一>磁道号
55
58
39
90
160
1&O
38
1B4
45
3
19
21
72
70
10
112
146
平均砰道烂底・35*3
2.最短寻道时间优先
〔从100号磁道开姑〕
被访问的T
一个確道号
移动JE离
（磁道数）
90
58
55
39
38
150
160
184
10
32
3
16
1
20
132
10
24
平均寻道怏度:
27*5
刚刚完成了125道的请求.现有如下访盘请求序列（磁道号）:
86,147,91,177,94,150,102,175,130
试给出采用下列算法后磁头移动的顺序和移动总量（总磁道数）.
（1）.先来先服务（FCFS）磁盘调度算法.
（2）.最短寻道时间优先（SSTF）磁盘调度算法.
（3）.扫描法（SCAN）磁盘调度算法.（假设沿磁头移动方向不再有访问请求时，磁头沿相
反方向移动.）
答案：
三、
（1）86,147,91，177,94,150，102，175，130
（2）当前磁头在143道上：
147，150，130，102，94，91，86，175，177
（3）当前磁头在143道上，并且刚刚完成125道的请求
147，150，175，177，130，102，94，91，86
五、调度算法（求周转时间，加权周转时间）
1.先来先服务调度算法FCFS:
该算法按照进程进入就绪队列的先后顺序选择最先
进入该队列的进程，把处理机分配给它，使之投入运行。
例
右二单道坏境卜.某批处鹿也燃令四道作业"Li知【他们的进入系统的I时爰旅估计诂算旳问如卜=
JI鮒时刻
1
A
0
1
0
1
1
B
1
100
1
11H
1
C
2
1
101
102
100
100
3
100
102
199
1.99
班作业G的世权则牯时何岛达1..
K竹-业u的帯权周传时问仅为1®*
2.优先级调度算法：
总是选择具有最高优先级的进程首先使用处理机。
在这种算法中，首先考虑的问题是如何确定进程的优先数。
分为：
静态优先权：
在创建讲程的时候便确定的，且在讲程的运行期间保持不变。
（简单
易行，系统开销小，但不够精确，很可能出现优先权低的作业（进程）长期不被调度的情况。
所以，只在要求不太高的系统中，才使用静态优先数（权））
动态优先权：
在创建进程时所赋予的优先权,可以随进程的推进而改变，以便获得
更好的调度性能
例：
彳列J2•有5个进程P1髦P2VP3.P4xP5,它们同时依次进入就绪臥列，它们的优先数和需要的处理机时间如下=
进丰呈
处理用L时间
优先数
P1
1（）
3
P2
1
1
P3
2
3
P4
1
4
P5
5
2
忽略进程调度所花的时间.要求：
（1）分別写出采用先来先服务调度算法和静态优先级调度算法中进稈的执行次序辛
（2）分别计算各进程在就绪队列屮的等待时间和平均等待时间°
解：
（1）采用先来先服势调度算法时各进程的执行次序为：
P1^P2—P3—P4—P5o
-采用静态优先级调度算法时各进社Ui勺执行次序为：
P4^P1—P3—P5^P2e
C2）FCFS中，平均等待日寸间=
（0+10+11+13+14）75=9.6；
静态优先级法中，平均等待时间=
<1+18+11+0+13）75=8-6
世小
处理村L时闫J
FCFS^r-VH'JI'd
静盡优先缓洼洋持时间
P1
1O
0
1
P2
1
10
18
F3
2
11
11
P4
1
13
O
P5
5
14
13
3•最短作业/进程优先法（SJF/SPF）:
SJF:
从后备队列中选择估计运行时间最短的作业，先调入内存运行。
SPF:
从就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执行。
4•最高响应比作业优先算法（HRN）：
是对FCFS方式和SJF方式的一种综合平衡响应比。
R=（作业等待时间+需运行时间"需运行时间
=1+已等待时间/需运行时间
=1+W/T
作业调度算法应用例子
估计运f亍
（5m）
可
的）
州可
JOB1:
8；00
120:
JOB2:
8：
S
50—
JOB3
9：
00
10
JQBI1
9i50
20:
刨平砂咖—
作曲師均瞒鄴洞W-||
先来先服务调度算法计算结果
件业
rw
TTWm]
弘涧
JCMJ1
»：
00
120
8；00
10：
00
120
1
TO!
tt
»：
50
Sfl
10：
CO
10：
50
120
P214
9；00
10
10：
50
11；UO
120
12
JCXU
9：
50
20
11：
on
11：
20
90
X
I-112-5
W=4^5
-150
19.9
最短作业优先作业算法计算结果
作业
atAMfHj
佔闵亍ffJR
结束rJW
周郞恤」
8:
001
I2fl
8:
00
10:
00
120
ri
J（JB2
8：
SO
5ft
10：
30
11:
20
150
3
J0B3
9；00
10
10：
（Ml
10=W
70
7
JOIkl十
9：
30
20
10：
W
10：
30
40
~2
糊恤1=95
W=3,25
3»）
13
最高响应比优先作业算法计算结果
渺肘间
（删
时间
JOB1
8：
00
120
8：
00
10：
（Ki
120
1
JOB2
8：
50
SO
10：
10
L1：
00
130
2.6
JOEJ
%00
10
10：
00
10；10
70
7
r
JOB4
9：
50
20
inoo
U：
20
90
45
砂鯛硼「血5
作蹄和蜩鄭搁W=1775
410
154
六：
页面置换算法
先进先出页面淘汰算法（FIFO）
选择在内存中驻留时间最长的页并淘汰之
理想淘汰算法一最佳页面算法（OPT）
淘汰以后不再需要的或最远的将来才会用到的页面
最近最久未使用页面淘汰算法（LRU）
选择最后一次访问时间距离当前时间最长的一页并淘汰之
即淘汰没有使用的时间最长的页
1.已知页面走向为1、2、1、3、1、2、4、2、1、3、4,且开始执行时主存中没有页面。
若只给该作业分配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少？
假定现有一种淘汰算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为
淘汰对象，试问就相同的页面走向，缺页率又为多少？
［分析及相关知识］在进行内存访问时，若所访问的页已在主存，则称此次访问成功；若
所访问的页不在主存，则称此次访问失败，并产生缺页中断。
若程序P在运行过程中访问
页面的总次数为S,其中产生缺页中断的访问次数为F,则其缺页率为：
F/s.
解：
根据所给页面走向，采用FIFO淘汰算法的页面置换情况如下：
页面走向
1
2
13
1
24
2
1
3
4
物理块1
1
1
3
3
22
1
1
4
物理块2
2
2
1
14
4
3
3
缺页
缺
缺
缺
缺
缺缺
缺
缺
缺
从上述页面置换图可以看出：
页面引用次数为
11次，缺页次数为
9次，所以缺页率为
9/11。
若采用后
种页面淘汰策略，
其页面置换情况如下：
贝面走向
1
2
13
1
24
2
1
3
4
物理块1
1
1
3
1
1
1
3
4
物理块2
2
2
2
4
2
2
2
缺页
缺
缺
缺
缺
缺
缺
缺
缺
在一个请求分页存储管理系统中，一个作业的页面走向为4,3,2,1,4,3,5,4,3,2,
1,5，当分配给该作业的物理块数分别为3,4时，试计算采用下述页面淘汰算法时的缺页
率（假设开始执行时主存中没有页面），并比较所得结果。
（1）最佳置换淘汰算法
（2）先进先出淘汰算法
（3）最近最久未使用淘汰算法
解：
（1）根据所给页面走向，使用最佳页面淘汰算法时，页面置换情况如下：
走向
4
3
2
14
3
54
3
2
15
块1
4
4
4
4
4
2
2
块2
3
33
3
3
1
块3
2
1
5
5
5
缺页
缺
缺
缺
缺
缺
缺
缺
缺页率为
:
7/12
走向
4
3
2
14
3
54
3
2
15
块1
4
4
4
4
4
1
块2
3
3
3
3
3
块3
2
2
2
2
块4
1
5
5
缺页
缺
缺
缺
缺
缺
缺
缺
缺页率为
:
6/12
由上述结果可以看出，:
增加分配
给作业
的内存块数可以降低缺页率
（2）根据所给页面走向，使用最佳页面淘汰
算法时，页面置换情况如下：
走向
4
3
2
14
3
54
3
2
15
块1
4
4
4
11
1
5
55
块2
3
3
34
4
4
32
块3
2
22
3
3
21
缺页
缺
缺
缺
缺
缺
缺缺
缺页率为
:
9/12
走向
4
3
2
14
3
54
3
2
15
块1
4
4
4
4
55
5
5
11
块2
3
3
3
34
4
4
45
块3
2
2
22
3
3
33
块4
1
11
1
2
22
缺页
缺
缺
缺
缺
缺
缺
缺
缺页率为
:
10/12
由上述结果可以看出，
对先进先出算法而言,
增加分配给作业的内存块数反而使缺页率上升，
这种异常现象称为
Belady
现象
。
（3）根据所给页面走向，使用最佳页面淘汰
算法时，页面置换情况如下：
走向432143543215
块1
444
1
1
1
5
2
2
2
块2
3
2
4
4
4
4
1
1
块3
2
3
2
3
3
3
3
5
缺页
缺缺缺
缺
缺
缺
缺
缺页率为：
10/12
走向
4
3
2
1
4354
32
1
5
块1
4
4
4
4
4
4
4
5
块2
3
3
3
3
3
3
3
块3
2
2
5
5
1
1
块4
1
1
2
2
2
缺页
缺
缺
缺
缺
缺
缺
缺
缺
缺页率为：
8/12
由上述结果可以看出，增加分配给作业的内存块数可以降低缺页率
升级会员 