江苏大学操作系统期末/考研复试大题复习

admin • 2023-04-14 18:40 • 程序人生

写在前面的话

基于：詹永照, 薛安荣. 操作系统设计原理[M]. 第二版. 科学出版社, 2021.
部分内容可能与王道考研等参考资料有所区别(如内存管理的clock算法与标志位、磁盘调度的scan算法)，请注意区分与取舍。

同步与互斥

假定一个阅览室最多可以容纳100人阅读，读者进入和离开阅览室时，都必须在阅览室门口的一个登记表上注册或注销。假定每次只允许一个人注册或注销，设阅览室内有100个座位。
（1）试问：应编制几个程序和设置几个进程？程序和进程的对应关系如何？
（2）试用PV操作编写读者进程同步算法

答案：
（1）应编制一个读者程序，有N个读者应设置N个读者进程。程序和进程对应关系1：N，读者程序为N个读者进程共享。
（2）

semaphore full,mutex;
PID seat[100];
int i;
full.value=100;
mutex.value=1;
for(int i=0;i<100;i++)
	seat[i]=-1;

process reader(PID procid){
	int i;
	P(&full);
	P(&mutex);
	i=0;
	while(seat[i]!=-1)
		i++;
	seat[i]=procid;
	V(&mutex);
	read at seat i;
	P(&mutex);
	seat[i]=-1;
	V(&mutex);
	V(&full);
}

死锁

银行家算法中，若出现以下资源分配情况，试问：
（1）系统是否安全?如果安全，请给出一个安全执行序列，如果不安全，说明理由。
（2）如果进程依次有如下资源请求，系统将怎样进行资源分配？说明理由

P

1

P_1

$P_{1}$ (1,0,2);

P

4

P_4

$P_{4}$ :(3,3,0);

P

0

P_0

$P_{0}$ :(0,2,0)

进程	最大资源需求量	已分配资源量	剩余资源量
	$R_1 R1 R 2 R_2 R2 R 3 R_3 R3$	$R_1 R1 R 2 R_2 R2 R 3 R_3 R3$	$R_1 R1 R 2 R_2 R2 R 3 R_3 R3$
$P_0 P0$	7 5 3	0 1 0	3 3 2
$P_1 P1$	3 2 2	2 0 0
$P_2 P2$	9 0 2	3 0 2
$P_3 P3$	2 2 2	2 1 1
$P_4 P4$	4 3 3	0 0 2

答案：
安全的。(1)先计算各个进程还需要的资源：

P_0

$P_{0}$ ：(7 4 3),

P_1

$P_{1}$ :(1 2 2),

P_2

$P_{2}$ : (6 0 0),

P_3

$P_{3}$ :(0 1 1),

P_4

$P_{4}$ : (4 3 1);
系统剩余资源量为(3 3 2)，满足

P_1

$P_{1}$ 或

P_3

$P_{3}$ 进程对资源的最大需求，可将资源分配给

P_1

$P_{1}$ 或

P_3

$P_{3}$ 进程，例如先分配给

P_1

$P_{1}$ ，

P_1

$P_{1}$ 和

P_3

$P_{3}$ 进程。执行完毕后归还所占资源，此时系统有可用资源数为(7 4 3)，此时系统可用资源数可满足任何一个进程的最大需求。故系统是安全的。
可执行的序列为

P_1P_3P_0P_2P_4

$P_{1} P_{3} P_{0} P_{2} P_{4}$ 或

P_3P_1P_0P_2P_4

$P_{3} P_{1} P_{0} P_{2} P_{4}$ 等。
(2) 系统按

P_1

$P_{1}$ ，

P_3

$P_{3}$ ，

P_0

$P_{0}$ ，

P_2

$P_{2}$ ，

P_4

$P_{4}$ 顺序执行，每个进程均能执行完。故

P_1

$P_{1}$ 的需求可以满足。

P_4

$P_{4}$ 请求（3，3，0）：剩余资源：（2，3，0）。系统剩余资源不能满足

P_4

$P_{4}$ 的要求，不能分配。

P_0

$P_{0}$ 请求（0，2，0）：剩余资源：（2，3，0），假设分配后，还剩余系统资源：（2，1，0）。

P_0

$P_{0}$ ~

P_4

$P_{4}$ 尚需的资源数均不能得到满足(或者说，虽然满足进程

P_0

$P_{0}$ 的当前请求但不满足进程对资源的最大需求)，故不能对

P_0

$P_{0}$ 分配。

内存管理

设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要8页数据存储空间，页的大小为4KB。操作系统采用固定分配局部置换策略为此进程分配4个页框，如下表在10:23时已经有4页进入内存，下表的装入时间和访问时间为一天内24小时时间。访问位的0表示未被访问，1表示已被访问。修改位的0表示未被修改，1表示已被修改。表中的访问时间均为对应的页最近一次被访问的时间。

页号	页框号	装入时刻	访问时刻	访问位	修改位
0	7	10:13	10:30	1	1
1	5	10:23	10:26	1	1
2	2	10:20	10:40	1	1
3	9	10:16	10:50	1	0

当进程执行到10:55时，要访问逻辑地址为6CDFH的数据，请回答下列问题：
（1）该逻辑地址对应的页号是多少？
（2）若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少？
（3）若采用最近最少用(LRU)置换算法，该逻辑地址对应的物理地址是多少？
（4）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框。示意图如下。

答案：
根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即

2^{12}

$2^{12}$ ，则得到页内位移占虚拟地址的低12位，页号占剩余高位。由于每位十六进制数占4bit，故十六进制数的低3位数为页内偏移量。
（1）页大小为4K，所以页内偏移地址为12位，于是前4位是页号，所以6CDFH的逻辑页号为：6
（2）FIFO，则被置换的页面所在页框为7，所以对应的物理地址为7CDFH
（3）LRU，则被置换的页面所在页框为5，所以对应的物理地址为5CDFH
（4）CLOCK,则被置换的页面所在页框为9，所以对应的物理地址为9CDFH

文件

一个*nix文件系统使用4KB磁盘块和4字节磁盘地址。如果每个i结点中有10个直接表项以及一个一次间接块、一个二次间接块和一个三次间接块，那么
（1）文件最大为多大？
（2）如果有且只有i结点已经在内存中，访问第12345字节需要读多少次磁盘？
（3）如果有且只有i结点已经在内存中，访问第1234567890字节需要读多少次磁盘？
答案：
（1）

4K/4=1K

$4 K / 4 = 1 K$

∗

10*4K+1K*4K+1K*1K*4K+1K*1K*1K*4K=4T4G4M40KB

$10 * 4 K + 1 K * 4 K + 1 K * 1 K * 4 K + 1 K * 1 K * 1 K * 4 K = 4 T 4 G 4 M 40 K B$
（2）因为12345<40K，故该地址落入直接索引中，由于i-node已在内存，因此只需要1次访问磁盘块，即一次访问含有该位置数据的磁盘块。
（3）因为

1234567890

4M40K<1234567890<4G4M40K

$4 M 40 K < 1234567890 < 4 G 4 M 40 K$ ，故该地址落入二级间接索引中，由于i-node已在内存，因此只需访问3次磁盘块。

磁盘

设某磁盘旋转速度为每分钟6000转。每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向服务，磁道号请求队列为50、200、80、110、180，对请求队列中的每个磁道需读取1个随机分布的扇区，则：
(1)在SSTF(最短寻道)调度情况下，读完这5个扇区总共需要多少时间，要求给出计算过程；
(2)在SCAN(扫描)调度情况下，读完这5个扇区总共需要多少时间，要求给出计算过程；
(3)就以上二种算法进行对比分析，并为用户选择提供建议说明。
答案：
由于转速为

6000

6000r/m

$6000 r / m$ ，则平均旋转延迟为

∗

1000

(

6000

∗

)

60*1000/(6000*2)=5ms

$60 * 1000 / (6000 * 2) = 5 m s$ ,总的旋转延迟时间为

∗

5*5ms=25ms

$5 * 5 m s = 25 m s$ 。由于旋转一周的时间为

10ms

$10 m s$ ，每个磁道有100个扇区，读取一个磁道上一个扇区的平均读取时间为

100

0.1

10ms/100=0.1ms

$10 m s / 100 = 0.1 m s$ ，总的读取扇区的时间=

0.1

∗

0.5

0.1ms*5=0.5ms

$0.1 m s * 5 = 0.5 m s$ 。
1）SSTF:执行顺序是100->110->80->50->180->200。则移到磁道长度为10+60+150=220。故读取上述磁道上所有扇区所花的总时间=220ms+25ms+0.5ms=245.5ms
2）采用SCAN调度算法访问磁道的顺序为100->110->180->200->80->50，则移到磁道长度为

100

150

250

100+150=250

$100 + 150 = 250$ 。故读取上述磁道上所有扇区所花的总时间=

250

0.5

275.5

250ms+25ms+0.5ms=275.5ms

$250 m s + 25 m s + 0.5 m s = 275.5 m s$ 。
两者算法都有寻道时间短、寻道优化的优势，而且两种寻道时间相差

30ms

$30 m s$ ，但相比较而言，SSTF可能会频繁切换服务方向，而SCAN不会。由于磁臂调度是机械运动，存在惯性，频繁切换服务方向会降低机械装置的使用寿命，故实际应用中SCAN优于SSTF。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

操作系统程序人生面试

二维码

)">

开发两年，作为过来人的建议

< <上一篇

【django】django-redis的使用方法

下一篇>>

搜索内容

江苏大学操作系统期末/考研复试大题复习

目录

写在前面的话

同步与互斥

死锁

内存管理

文件

磁盘

最新文章

分类

标签云

江苏大学 操作系统 期末/考研复试大题复习

目录

写在前面的话

同步与互斥

死锁

内存管理

文件

磁盘

最新文章

分类

标签云

江苏大学操作系统期末/考研复试大题复习