2020 年春《操作系统》期末真题

1. 32 位地址空间共有 $2^{32}$ 字节，即 4 GB。

2. 令 $B=\mathtt{0xMN000000}$。4 MB 页表覆盖全部 $2^{20}$ 个虚页，每项 4 B。源答案给出：

   • 第一级页表的逻辑地址为 $B+(B\mathbin{\gg}10)$；
   • 指向第一级页表自身的表项逻辑地址为 $B+(B\mathbin{\gg}10)+(B\mathbin{\gg}20)$。

   原因是第一级页表位于整片页表空间的第 $B\mathbin{\gg}22$ 个页面；先用 $B\mathbin{\gg}10$ 找到页目录，再用 $B\mathbin{\gg}20$ 找到其中的自映射表项。

3. 地址翻译结果如下：

   指令	一级索引 / 二级索引 / 偏移	关键页表项	结果
   Load [0x00001034]	000 / 001 / 034	0x00100007 → 0x00002067	0x12
   Store [0x00C07665]	003 / 007 / 665	0x00103007 → 0xEEFF0067	OK
   Store [0x00C005FF]	003 / 000 / 5FF	0x00103007 → 0x11220005，只读	Error
   Load [0x00C03012]	003 / 003 / 012	0x00103007 → 0x00000007	0x20
   Load [0xFF80078F]	3FE / 000 / 78F	0x001FE007 → 0x04150000，无效	Error
   Load [0xFFFFF00B]	3FF / 3FF / 00B	0x001FF007 → 0x00103067	0xCC

源答案把第一条指令的二级页表项地址写成了 0x00100001；按每项 4 B 计算应为 0x00100004，但其读取的页表项值及最终结果不受这个笔误影响。

三种算法的缺页次数为：

以“最近位置在左侧”记录页框，源答案的过程可压缩为：

引用:  5  4  3  2  4  5  4  1  5  2  5  4  5  2  1
OPT :  M  M  M  M  H  H  H  M  H  H  H  M  H  H  M
FIFO:  M  M  M  M  H  M  M  M  H  M  M  M  H  H  M
LRU :  M  M  M  M  H  M  H  M  H  M  H  M  H  H  M

设进程平均大小为 $S$，页表项大小为 $e$，页面大小为 $p$。页表大约占 $Se/p$ 字节，最后一页的平均内碎片约为 $p/2$ 字节，因此总额外开销为

令 $f'(p)=0$，得到

First Fit 最终结果：

关键过程是：X 先进入 [40,60)；C、D 释放后 [32,40) 和 [52,84) 成为空闲区；Y 进入从低地址开始遇到的 [52,84)；E 结束后相邻空闲区合并为 [82,110)；Z 最后进入 [10,20)。

Best Fit 最终结果：

这里 X 先进入与 12 KB 最接近的 [92,110)；C、D 释放后形成 [32,84)，Y 再从中取得 30 KB；E 结束后 [62,92) 合并为 30 KB 空闲区；Z 仍进入 10 KB 的 [10,20)。

1. 访问顺序为

   20 → 22 → 38 → 40 →（扫描到边界 50）→ 10 → 6 → 2

   磁头先从 20 移到 50，再从 50 返回 2，共移动 $(50-20)+(50-2)=78$ 个柱面，寻道时间为 $78\times4=312$ ms。

2. 源答案给出的过程为：

   相对时刻 / ms	磁头位置	处理后仍待访问的请求
   0	20	10、22、2、40、6、38
   8	22	10、2、40、6、38
   72	38	10、2、40、6、50、1
   80	40	10、2、6、50、1
   120	50	10、2、6、1、10
   280	10	2、6、1
   296	6	2、1
   312	2	1
   316	1	无

   因两个请求都访问 10 号柱面，磁头到达 10 时可一并处理。实际顺序为

   20 → 22 → 38 → 40 → 50 → 10 → 6 → 2 → 1

   总寻道时间为 316 ms。

源答案设置：

• empty = 50：仓库剩余空位；
• itemA = 0、itemB = 0：仓库内 A、B 产品数量；
• mutex = 1：互斥保护一次产品入库或出库操作。

ProducerA() {
    while (true) {
        P(empty);
        ProductA a = produceA();
        P(mutex);
        put(a);
        V(mutex);
        V(itemA);
    }
}

ProducerB() {
    while (true) {
        P(empty);
        ProductB b = produceB();
        P(mutex);
        put(b);
        V(mutex);
        V(itemB);
    }
}

ConsumerA() {
    while (true) {
        P(itemA);
        P(mutex);
        ProductA a = takeA();
        V(mutex);
        consume(a);
        V(empty);
    }
}

ConsumerB() {
    while (true) {
        P(itemB);
        P(mutex);
        ProductB b = takeB();
        V(mutex);
        consume(b);
        V(empty);
    }
}

源答案的 ConsumerB 原写作 P(itemA)，但 B 类客户必须等待 B 产品，且其余代码也使用 itemB 计数；上面已把这个明显笔误更正为 P(itemB)。

源答案列出四种写法，下面保留其中标为 Version 2 的完整方案：

int waiting = 0;
Semaphore mutex = 1;
Semaphore bus = 0;
Semaphore boarded = 0;

Bus() {
    P(mutex);
    int n = min(waiting, 50);
    for (int i = 0; i < n; i++) {
        V(bus);
        P(boarded);
    }
    waiting = max(waiting - 50, 0);
    V(mutex);
    depart();
}

Passenger() {
    P(mutex);
    waiting++;
    V(mutex);

    P(bus);
    boardBus();
    V(boarded);
}

mutex 不只保护计数，还让校车在确定本轮人数后一直持有互斥量，因而新乘客不能加入本轮；bus 逐个放行本轮乘客，boarded 让校车逐个确认上车完成。若 n=0，循环不执行，校车直接离开。

按源答案的推演：

1. 初始可用向量为 $(0,3,2,0)$。P1 可完成并释放资源，可用量变成 $(0,4,4,0)$；P4 随后可完成，变成 $(0,6,7,2)$；P5 再完成，变成 $(0,6,8,6)$。此时 P2 还需 $(0,8,5,0)$，P3 还需 $(1,0,0,2)$，二者都无法继续。因此状态不安全，最终 P2、P3 会陷入死锁。
2. 只增加一个 R1，最后的可用向量即可成为 $(1,6,8,6)$。此时 P3 先完成并释放已分配资源，可用量变为 $(2,9,13,10)$，P2 随后也能完成。因此最小代价是增加 1 个 R1。

这里应区分两个说法：初始时 P1、P4、P5 尚能推进，并非所有进程已经僵住；源答案所称“发生死锁”，指这三个进程依次完成后，P2、P3 最终进入的状态。

1. 一个间接索引块能存 $2\ \text{KB}/4\ \text{B}=512$ 个地址，因此最大文件大小为

   $$(10+512+512^2)\times 2\ \text{KB}=525332\ \text{KB}.$$

   间接索引块本身不计入文件大小。

2. 数据块为 2 KB 时，平均每个文件保存 1.75 KB 数据却占用 2 KB，利用率为 $1.75/2=87.5\%$。改成 1 KB 后，2 KB 文件占 2 个块，1.5 KB 文件也占 2 个块，平均仍是 1.75 KB 数据占 2 KB，利用率仍为 $87.5\%$。

3. 大文件更可能通过一级、二级间接索引访问，索引层级越多，需要的额外磁盘访问越多，随机读取性能因而下降。源答案建议利用局部性，把常访问部分尽量放在直接或一级索引可达区域，并使用块缓存、提前读取、磁盘碎片整理、合理分配与布局、磁盘调度或 RAID 等手段减少实际 I/O 开销。