写在前面的话

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

答案：

内存管理

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

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

答案：

根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即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）

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

磁盘

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

答案：