操作系统期末真题（一）解析

2026年9月22日 Crystal-Sky 23 min read 操作系统期末复习真题解析

一、（24分）简要回答下列问题。

1.（6分）磁盘空闲存储空间管理

题目 1.1

1.（6分）对于磁盘空闲存储空间管理，下列 2 种方法哪一种好？为什么？

（1）每个空闲块中指出下一个空闲块的块号。

（2）采用多个空闲块构成的链表存放空闲块号。

2.（6分）死锁判断

题目 1.2

2.（6分）下面关于死锁问题的叙述，是否正确？为什么？

（1）若 A、B、C、D 四个进程都处于阻塞状态，则 A、B、C、D 构成的进程集合出现死锁。

（2）若 A、B、C、D 四个进程构成的集合出现死锁，则 A、B、C、D 中的每个进程都一定占有资源。

（3）若系统处于不安全状态，则一定会导致死锁。

3.（6分）共享设备

题目 1.3

3.（6分）I/O 设备按共享属性分类可分为独占设备和共享设备。举一个共享设备的例子，针对你所举的例子，说明共享的含义，给出一种设备分配方法，并说明你的方法存在的不足。

4.（6分）内存管理设计目标的冲突

题目 1.4

4.（6分）在设计操作系统的内存管理功能时，需要考虑多个设计目标，例如内存利用率高、便于实现内存共享等，而有些设计目标之间往往存在冲突，需要权衡。举 2 个与内存管理相关的设计目标（不限于本题所列的设计目标）存在冲突的例子，分别解释可能冲突的情况，并简要阐述在设计时采取什么策略对相互冲突的设计目标进行权衡。

二、（18分）虚拟页式存储管理。

题目 2.1

某计算机系统采用虚拟页式存储管理，虚拟地址为 32 位，页的大小为 4096 个字节。采用请求调页、固定分配和局部置换策略，页的置换以及快表项的置换均采用 FIFO（First-In-First-Out）算法，页表在内存中。产生缺页中断时，系统将缺页调入内存，更新页表（不更新快表），返回到产生缺页中断的指令处重新执行。

1. 假定为进程 P 分配了 3 个物理块（或称页框、页帧，pageframe），快表长度为 2，进程 P 依次有页号为 10H、100H 和 60H 的页面调入内存中。此时，进程 P 被调度执行，快表为空，依次访问下列虚拟地址（假定这些虚拟地址均在进程 P 的虚拟地址空间内）：

（1）100860H　（2）20E60H　（3）100920H　（4）60100H　（5）100600H

得到这些虚拟地址对应的物理地址各需访问内存几次？说明每次访问内存的功能。

2. 指出该内存管理机制存在的一种不足。针对这种不足，给出一种改进方法，并解释理由。

解析：

页大小为 $4096=2^{12}=\mathrm{1000H}$ 字节，因此一个虚拟地址的低 12 位（即低 3 个十六进制位）是页内偏移，高位是页号。

所以五个地址对应的页号分别为：

\[ \mathrm{100H},\quad \mathrm{20H},\quad \mathrm{100H},\quad \mathrm{60H},\quad \mathrm{100H}. \]

初始状态：

\[ \text{内存中的页面（FIFO 先后次序）}:\quad 10H\rightarrow100H\rightarrow60H, \]

\[ \text{快表}:\quad \varnothing. \]

下面只统计“为了得到物理地址而访问内存”的次数，也就是访问内存中的页表的次数；访问快表本身不算访问主存。

次序	虚拟地址	页号	过程	为得到物理地址访问内存次数
1	100860H	100H	快表为空，快表未命中。访问内存中的页表，发现 100H 已在内存，取得页框号，并把 100H 的页表项装入快表。	1
2	20E60H	20H	快表未命中。第一次访问页表发现 20H 不在内存，发生缺页。按页面 FIFO 淘汰最早进入内存的 10H，调入 20H 并更新页表，但不更新快表。指令重新执行后快表仍未命中，因此第二次访问页表，取得 20H 的页框号，再把该项装入快表。	2
3	100920H	100H	100H 已在快表中，快表命中，直接得到页框号，不必访问内存中的页表。	0
4	60100H	60H	快表未命中，访问页表得到 60H 的页框号。把 60H 装入长度为 2 的快表；按 FIFO 淘汰最早进入快表的 100H。	1
5	100600H	100H	此时 100H 仍在内存，但已经被快表 FIFO 淘汰，因此快表未命中。访问页表取得其页框号。	1

因此，按题目“得到物理地址”的字面含义，五次访问分别需要：

\[ \boxed{1,\;2,\;0,\;1,\;1} \]

次主存访问。

如果课程讲义把“取得物理地址后真正访问目标数据/指令的那一次主存访问”也一起计算，则每项还要再加 1，得到：

\[ \boxed{2,\;3,\;1,\;2,\;2}. \]

这种口径统计的是“完成一次虚拟地址访问”的主存访问次数，而不是单纯“得到物理地址”的次数。

第 2 问：

题目中特别规定：发生缺页时“更新页表（不更新快表）”。这会带来一个重要问题：如果被淘汰的页面恰好还存在于快表中，那么它原来的快表项会变成失效的旧映射。之后再次访问该页时，若仍然命中这个旧快表项，就可能得到已经被其它页面占用的页框号，造成错误的地址转换。

改进方法是在页面被换出、页表项发生变化时，同时使对应快表项失效（invalidate）；也可以在缺页处理结束时将新页的有效映射装入快表。这样可以保证快表与页表的一致性，避免使用陈旧映射。

三、（12分）并发执行与共享变量。

题目 3.1

设有两个程序 P1 与 P2，其执行的代码分别如下。

程序 P1：

int x;
for (i = 0; i < 3; i++)
    x = x + 1;

程序 P2：

int x;
for (i = 0; i < 2; i++)
    x = x - 1;

其中，x 是共享变量，初值为 0。现启动 4 个进程（2 个进程对应程序 P1，2 个进程对应程序 P2）并发执行，请给出这 4 个进程均执行完成后所有可能的 x 值。

四、（16分）文件系统与多级目录。

题目 4.1

某文件系统采用多级目录结构，目录当作文件。目录项只包含文件名和 I 节点号，文件地址（磁盘物理块号）等其它文件属性放在 I 节点中。假定磁盘逻辑块与物理块的大小均为 1K 字节，磁盘物理块（以下简称磁盘块）号用 4 个字节表示，根据 I 节点号可计算出其 I 节点所在的磁盘块号，根据磁盘块号可确定磁盘物理地址。目录项中的文件地址由 10 个地址组成，其中 8 个地址是直接地址，1 个地址是一次间接地址，1 个地址项是二次间接地址，每个地址只包含磁盘块号。设文件 f.dat 存在于目录 /zhang/data 下。

1. 设每个目录文件所占空间不超过 2 个磁盘块，每个 I 节点所占空间不超过 1 个磁盘块，根目录文件的 I 节点号已知。为了获得文件 f.dat 的地址，最少需要读多少个磁盘块？最多需要读多少个磁盘块？要求给出计算过程。

2. 你认为如何提高根据文件名（文件路径名）获得文件地址的速度？请给出一种方法，并解释具体理由。

3. 在获得文件 f.dat 的地址后，若要读文件 f.dat 的第 269K 个字节（字节编号从 0 开始），需要读几个磁盘块？要求给出计算过程。

解析：

第 1 问：

路径为

\[ /\;\longrightarrow\;zhang\;\longrightarrow\;data\;\longrightarrow\;f.dat. \]

已知的是根目录文件的 I 节点号，但要知道根目录文件存放在哪些磁盘块，仍然要先根据 I 节点号读根目录的 I 节点。

沿路径逐级查找时，需要进行：

读根目录 I 节点；
读根目录文件，在其中找到 zhang 的 I 节点号；
读 zhang 的 I 节点；
读 zhang 目录文件，在其中找到 data 的 I 节点号；
读 data 的 I 节点；
读 data 目录文件，在其中找到 f.dat 的 I 节点号；
读 f.dat 的 I 节点，从而获得文件地址。

共有 4 个 I 节点需要读取：根目录、zhang、data、f.dat。每个 I 节点最多占 1 个磁盘块，因此 I 节点读取共需 4 个磁盘块。

需要搜索的目录文件有 3 个：根目录、zhang、data。

最理想时，每一级所需目录项都在读到的第 1 个目录块中，因此目录文件共读 3 个块：

\[ 4+3=\boxed{7}\text{ 个磁盘块}. \]

最坏时，每个目录文件都要读满 2 个块才能找到目标目录项，因此目录文件共读 $3\times2=6$ 个块：

\[ 4+6=\boxed{10}\text{ 个磁盘块}. \]

第 2 问：

可以建立目录项缓存（dentry cache）/路径名缓存，把最近访问过的“父目录 I 节点号 + 文件名 $\rightarrow$ 子文件 I 节点号”的映射保存在内存中，同时缓存常用 I 节点。

以后再次访问相同或相近路径时，很多路径分量可以直接在内存缓存中命中，不必每一级都重新读目录文件和 I 节点，因此能够显著减少磁盘 I/O，提高路径名解析速度。

第 3 问：

一个磁盘块大小为 $1K$，因此第 $269K$ 个字节的逻辑块号为

\[ \frac{269K}{1K}=269. \]

字节编号从 0 开始，所以直接地址覆盖逻辑块号

\[ 0\sim7, \]

共 8 块。

一个间接地址块大小为 $1K=1024$ 字节，每个磁盘块号占 4 字节，因此一次间接块可以保存

\[ \frac{1024}{4}=256 \]

个磁盘块号。

所以一次间接地址覆盖的逻辑块号为

\[ 8\sim(8+256-1)=8\sim263. \]

逻辑块 269 已经超过 263，因此需要使用二次间接地址。

在已经获得 f.dat 的 I 节点地址信息之后，为读到逻辑块 269，需要：

读二次间接的第一级间接块，取得第二级间接块号；
读第二级间接块，取得实际数据块号；
读实际数据块。

因此共需

\[ \boxed{3}\text{ 个磁盘块}. \]

五、（12分）调度方案分析。

题目 5.1

某应用场景分 2 类任务：交互式任务和后台任务，要求交互式任务绝对优先于后台任务执行，交互式任务之间、后台任务之间没有优先级的区别。小明为该应用场景的专用操作系统设计了一个调度方案：设置 6 个就绪队列 Q[6]，i（0$\leq$i<6）越小，Q[i] 的级别越高，调度程序总是选择执行级别高的队首任务，只有 Q[0]-Q[i-1] 为空，才会调度 Q[i] 的任务；就绪的后台任务进入 Q[5] 的队尾，就绪的交互式任务进入 Q[0] 的队尾，每个队列采用时间片轮转调度，执行的时间片到时被剥夺，所有队列的时间片大小相同；当高级队列有任务就绪时，正在执行的低级队列的任务被剥夺。交互式任务被剥夺时，降到下一级队列的队尾（Q[4] 的任务不降级）；后台任务被剥夺时，排在 Q[5] 的队尾。

1. 对于交互式任务，小明的设计方案存在饥饿的问题，请说明为什么？给出一种解决该问题的方法，并加以解释。

2. 对于交互式任务，在排除饥饿的情况下，小明的设计方案存在不够公平的问题，请说明为什么？给出一种解决该问题的方法，并加以解释。

3. 对于后台任务，给出一种与小明的设计相比调度开销更小的方法，解释理由，并说明你的方法可能带来的其它方面的不足。

解析：

第 1 问：饥饿。

交互式任务刚就绪时进入 Q[0]，以后每次因为时间片到或受到更高级队列任务影响而被剥夺，都可能逐级下降到 Q[1]、Q[2]、Q[3]、Q[4]。调度器永远先选择高优先级队列。

如果不断有新的交互式任务进入 Q[0]，或者高优先级队列长期保持非空，那么已经下降到 Q[3]、Q[4] 的旧任务就可能长期得不到 CPU，即发生饥饿。

一种典型解决方法是老化（aging）/周期性优先级提升：任务等待时间越长，逐步提高它的优先级；或者每隔一定时间把所有交互式任务统一提升回 Q[0]。这样任何等待足够久的交互式任务最终都会进入较高优先级，从而有机会执行。

第 2 问：公平性。

题目前提说明“交互式任务之间没有优先级的区别”，但该方案却因为任务到达时间和被剥夺次数不同，把交互式任务放在 Q[0]--Q[4] 的不同等级中。

例如，一个刚到达的交互式任务直接进入 Q[0]，而一个已经运行过、被剥夺过多次的交互式任务可能处于 Q[4]。即使已经通过老化等办法保证后者最终不会饿死，新任务仍然会在相当长的时间里优先于旧任务执行。这样，同属交互式任务的进程获得 CPU 的机会并不平等。

一种更直接的改进是：所有交互式任务只使用一个高优先级就绪队列，并在该队列内采用时间片轮转。所有交互式任务具有相同优先级，按照 RR 轮流执行；只要交互式队列非空，就不调度后台任务，因此仍然满足“交互式任务绝对优先于后台任务”的要求。

也可以保留多级队列，但规定只有真正用完整个时间片的任务才降级，而因更高级任务到达而提前被抢占的任务保持原级，并配合周期性优先级提升。不过从本题“交互式任务之间没有优先级区别”的要求看，统一 RR 队列更直接。

第 3 问：降低后台任务调度开销。

后台任务之间没有优先级差别，而且只在没有交互式任务时才执行。可以把后台任务放在一个FCFS 队列中：后台任务一旦获得 CPU，就一直运行到结束或阻塞；只有出现交互式任务时才立即抢占后台任务。

与固定小时间片的 RR 相比，后台任务之间不再因为时间片耗尽而频繁发生上下文切换，也减少了定时器中断和重新排队的开销，因此调度开销更小。

不足是：如果某个后台任务 CPU 执行时间很长，它可能长时间占用后台任务可获得的 CPU，使排在后面的后台任务等待较久，响应时间和公平性都会变差，容易出现“护航效应（convoy effect）”。

六、（18分）同步算法设计。

题目 6.1

某银行的业务分为现金和转账，这 2 项业务分别由 2 个和 1 个服务员负责办理。业务大厅最多能容纳 20 位等候办理业务的客户（不包括正在办理业务的客户）。客户到来时，若业务大厅已满，则离开；否则进入大厅根据办理的业务取号，然后等候服务员叫号，办理完业务后离开。试用信号量的 P、V 操作设计该问题的同步算法，给出所用共享变量（如果需要）和信号量及其初始值，并说明各自的含义。

解析：

这道题有三个关键约束：

大厅最多只能有 20 个正在等待的客户；已经开始办理业务的客户不计入这 20 人。
现金业务同时最多有 2 人正在办理，因为有 2 个现金服务员。
转账业务同时最多有 1 人正在办理，因为只有 1 个转账服务员。

可以使用一个共享变量记录大厅内当前等待人数，再用互斥信号量保护它。两个“服务员资源信号量”分别表示当前可用的现金服务员和转账服务员。

共享变量：

int waiting = 0;        // 当前在大厅等待、尚未开始办理业务的人数
int cashNo = 0;         // 现金业务取号计数（如需要显示号码）
int transferNo = 0;     // 转账业务取号计数（如需要显示号码）

信号量及初值：

\begin{align*} mutex &= 1 &&\text{保护 waiting 以及取号计数器等共享变量；}\\ cash &= 2 &&\text{表示 2 个现金服务员；}\\ transfer &= 1 &&\text{表示 1 个转账服务员。} \end{align*}

客户进程可以写成下面的形式。

Customer(type)
{
    P(mutex);
    if (waiting == 20)
    {
        V(mutex);
        leave();                // 大厅已满，直接离开
        return;
    }

    waiting++;                  // 进入大厅，成为等待客户

    if (type == CASH)
        myNo = ++cashNo;        // 现金业务取号
    else
        myNo = ++transferNo;    // 转账业务取号

    V(mutex);

    if (type == CASH)
        P(cash);                // 等待任意一个现金服务员叫号
    else
        P(transfer);            // 等待转账服务员叫号

    // P 成功，说明已经轮到该客户，开始办理业务。
    // 此时他不再属于“大厅中等待的人”。
    P(mutex);
    waiting--;
    V(mutex);

    do_service(type);           // 办理业务

    if (type == CASH)
        V(cash);                // 现金服务员空闲，可叫下一位
    else
        V(transfer);            // 转账服务员空闲，可叫下一位

    leave();
}

如果要求严格按照号码先后顺序叫号，可以规定现金业务和转账业务各自的信号量等待队列采用 FIFO，或者分别维护一个按取号顺序排列的 FIFO 等待队列。这样，被唤醒的客户顺序就与取号顺序一致。

这里最容易写错的是 $waiting$ 的减少时机：客户一旦通过 $P(cash)$ 或 $P(transfer)$ 获得服务员，说明已经开始办理业务，因此应当马上执行 $waiting--$。不能等办理完离开时才减，否则就把“正在办理业务的客户”错误地算进大厅 20 人的容量中。