写在前面的话

基于：詹永照, 薛安荣. 操作系统设计原理[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 P1​(1,0,2); P 4 P_4 P4​:(3,3,0); P 0 P_0 P0​:(0,2,0)

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

答案：
安全的。(1)先计算各个进程还需要的资源：
P 0 P_0 P0​：(7 4 3), P 1 P_1 P1​:(1 2 2), P 2 P_2 P2​: (6 0 0), P 3 P_3 P3​:(0 1 1), P 4 P_4 P4​: (4 3 1);
系统剩余资源量为(3 3 2)，满足 P 1 P_1 P1​或 P 3 P_3 P3​ 进程对资源的最大需求，可将资源分配给 P 1 P_1 P1​或 P 3 P_3 P3​进程，例如先分配给 P 1 P_1 P1​， P 1 P_1 P1​和 P 3 P_3 P3​进程。执行完毕后归还所占资源，此时系统有可用资源数为(7 4 3)，此时系统可用资源数可满足任何一个进程的最大需求。故系统是安全的。
可执行的序列为 P 1 P 3 P 0 P 2 P 4 P_1P_3P_0P_2P_4 P1​P3​P0​P2​P4​或 P 3 P 1 P 0 P 2 P 4 P_3P_1P_0P_2P_4 P3​P1​P0​P2​P4​等。
(2) 系统按 P 1 P_1 P1​， P 3 P_3 P3​， P 0 P_0 P0​， P 2 P_2 P2​， P 4 P_4 P4​顺序执行，每个进程均能执行完。故 P 1 P_1 P1​的需求可以满足。
P 4 P_4 P4​请求（3，3，0）：剩余资源：（2，3，0）。系统剩余资源不能满足 P 4 P_4 P4​的要求，不能分配。
P 0 P_0 P0​请求（0，2，0）：剩余资源：（2，3，0），假设分配后，还剩余系统资源：（2，1，0）。 P 0 P_0 P0​~ P 4 P_4 P4​尚需的资源数均不能得到满足(或者说，虽然满足进程 P 0 P_0 P0​的当前请求但不满足进程对资源的最大需求)，故不能对 P 0 P_0 P0​分配。

内存管理

设某计算机的逻辑地址空间和物理地址空间均为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} 212，则得到页内位移占虚拟地址的低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$
$10\ast 4K+1K\ast 4K+1K\ast 1K\ast 4K+1K\ast 1K\ast 1K\ast 4K=4T4G4M40KB$
（2）因为12345<40K，故该地址落入直接索引中，由于i-node已在内存，因此只需要1次访问磁盘块，即一次访问含有该位置数据的磁盘块。
（3）因为$4M40K<1234567890<4G4M40K$，故该地址落入二级间接索引中，由于i-node已在内存，因此只需访问3次磁盘块。

磁盘

设某磁盘旋转速度为每分钟6000转。每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向服务，磁道号请求队列为50、200、80、110、180，对请求队列中的每个磁道需读取1个随机分布的扇区，则：
(1)在SSTF(最短寻道)调度情况下，读完这5个扇区总共需要多少时间，要求给出计算过程；
(2)在SCAN(扫描)调度情况下，读完这5个扇区总共需要多少时间，要求给出计算过程；
(3)就以上二种算法进行对比分析，并为用户选择提供建议说明。
答案：
由于转速为$6000r/m$，则平均旋转延迟为$60\ast 1000/(6000\ast 2)=5ms$,总的旋转延迟时间为$5\ast 5ms=25ms$。由于旋转一周的时间为$10ms$，每个磁道有100个扇区，读取一个磁道上一个扇区的平均读取时间为$10ms/100=0.1ms$，总的读取扇区的时间=$0.1ms\ast 5=0.5ms$。
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$。故读取上述磁道上所有扇区所花的总时间=$250ms+25ms+0.5ms=275.5ms$。
两者算法都有寻道时间短、寻道优化的优势，而且两种寻道时间相差$30ms$，但相比较而言，SSTF可能会频繁切换服务方向，而SCAN不会。由于磁臂调度是机械运动，存在惯性，频繁切换服务方向会降低机械装置的使用寿命，故实际应用中SCAN优于SSTF。