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

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

满分：100 分　　考试时间：\underline{} 分钟

姓名：\underline{} 学号：\underline{} 班级：\underline{} 成绩：\underline{}

注意事项：请在答题纸或指定区域作答；计算题需写出必要计算过程；同步算法题需说明信号量及共享变量含义。

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

（6 分）操作系统在虚拟存储管理中引入工作集策略有何作用？工作集策略不适用于什么应用场景？可以举例说明。

（6 分）假定系统中有 N 个进程，竞争使用资源 R（R 属于临界资源）。已知资源 R 的个数为 8，每个进程最多需要资源 R 的个数为 3。当 N 取哪些值时，系统一定不会发生死锁？请解释理由。

（6 分）在多数操作系统环境下，应用程序在访问文件前需要首先打开（open）文件，为什么？请给出一种不需要应用程序在访问文件前首先打开文件的方案，并说明与“先打开再访问”的方案相比所具备的优点和存在的不足。

（6 分）在设计操作系统的 I/O 管理（包括磁盘 I/O）功能时，需要考虑多个设计目标，例如设备利用率高、I/O 设备之间的并行程度高等，而有些设计目标之间往往存在冲突，需要权衡。请举两个与 I/O 管理相关的设计目标存在冲突的例子，分别解释可能冲突的情况，并简要阐述在设计时采取什么策略对相互冲突的设计目标进行权衡。

二、虚拟页式存储管理与地址转换（18 分）

题目 2.1

已知某计算机系统采用虚拟页式存储管理，页的大小为 4KB。系统采用固定分配、请求调页和局部置换策略，页的置换采用 LRU（最近最久未使用）算法，为进程 P 分配的内存物理块（页框，page frame）数为 3。假定在时刻 t，进程 P 只有页号为 2、5、9 的页在内存中，对应的物理块号分别为 368H、120H、6AH。此时，进程 P 被调度执行，依次访问下列虚拟地址（假定这些虚拟地址均在进程 P 的虚拟地址空间内）：

（1）5296H　（2）2A68H　（3）610EH　（4）93A6H　（5）602H

要求：给出上述虚拟地址分别对应的物理地址，用十六进制表示，并说明计算过程；给出进程 P 依次访问上述 5 个虚拟地址后页表的内容；说明如何提高虚拟地址转换为物理地址的速度，给出 2 种方法并解释具体理由。

三、并发线程访问共享栈的正确性分析（12 分）

题目 3.1

设程序 P 包含下列代码片段。其中，stack 和 top 是全局变量，stack 存放栈元素，top 表示栈顶，栈元素为 int 类型，push 和 pop 分别为进栈和出栈函数。程序 P 对栈 stack 的所有操作均通过调用 push 和 pop 函数实现，且传递的参数以及对返回值的处理方法是正确的。

#define MAXSIZE 256
int stack[MAXSIZE];
int top = -1;
int push(int x) // 若栈满，则返回 -1；否则，将 x 进栈，返回 0
{
 if (top >= MAXSIZE - 1) return -1;
 top++;
 stack[top] = x;
 return 0;
}

int pop(int *x) // 若栈空，则返回 -1；否则，栈顶元素出栈并存入 x 所指的地址，返回 0
{
 if (top < 0) return -1;
 *x = stack[top];
 top--;
 return 0;
}

假定程序 P 执行时启动 2 个线程，这 2 个线程都对栈 stack 进行多次操作。在什么情况下会导致程序 P 对栈 stack 的 push 或 pop 操作结果不正确？请给出 3 种具体情况，并结合程序代码分别加以说明。

四、磁盘文件系统设计与计算（16 分）

某磁盘文件系统采用多级目录结构，目录当作文件，每个文件有唯一的 ID，磁盘逻辑块与物理块的大小均为 4096 个字节（磁盘物理块以下简称磁盘块）。目录文件存放符号目录项，每个符号目录项占 32 个字节，包括文件 ID 和文件名。基本目录项包括文件类型标志（目录文件或普通文件）和文件地址 addr 等。对于目录文件，addr 所指的 1 个磁盘块存放文件内容；对于普通文件，addr 所指的 1 个磁盘块按顺序存放文件内容所占用的若干磁盘块地址（每个地址占 8 个字节）。已知文件 ID 与其基本目录项所在磁盘块地址的对应关系以及根目录的 ID。

（1）每个普通文件的最大长度是多少个字节？每个目录下最多可包含多少个文件（包括子目录）？要求给出计算过程。

（2）设普通文件 f.dat 存在于目录 /user/data 下，为了获取 f.dat 的 ID，需要读几个磁盘块？若已知 f.dat 的 ID，读其第 42000 个字节（字节编号从 0 开始），需要读几个磁盘块？要求给出计算过程。

（3）在磁盘块大小不变的情况下，为了支持更大的文件，如何改进该文件系统？请给出 1 种改进方法，并说明改进后可支持的最大文件长度以及与改进前相比存在的不足。

五、进程管理与调度方案设计（12 分）

题目 5.1

假设要设计一个操作系统的进程管理与调度方案，所需的计算机硬件条件完全具备。要求如下：①支持多进程并发执行时的资源共享；②进程分为 8 个优先级，优先级高的进程先执行，但要避免饥饿；③必要时需将某些进程整体换出到外存。请阐述方案的设计思路。

要求：描述方案所采用的相关数据结构，并说明各数据结构及其所存储内容的含义和作用。

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

题目 6.1

已知并发执行的进程 P1、P2 和 P3 以及 A、B、C、D、E 和 F 这 6 个功能。A 必须在 B、C、D、E 和 F 开始之前完成；B 必须在 C 完成之后方能开始；F 必须在 B 和 D 完成之后方能开始。设 P1 执行 B，P2 依次执行 C、D 和 E，P3 执行 F，执行 A 的进程为 P1、P2 或 P3 的其中一个，且不可预先指定。请用信号量的 P、V 操作设计该问题的同步算法。

要求：给出所用共享变量（如果需要）和信号量及其初始值，并说明各自的含义；用伪代码写出进程 P1、P2 和 P3 的同步算法。

解析：

首先要保证 A 恰好由 P1、P2、P3 中最先进入相应临界区的一个进程执行，并且另外两个进程必须等到 A 完成以后才能继续。可使用共享变量

\[ aDone=false \]

以及互斥信号量

\[ mutex=1. \]

三个进程在开始自己原有功能前都执行同一个 doAOnce()。令第一个进入 mutex 的进程在持有 mutex 时执行 A 并设置 aDone=true；其他进程只有在 A 完成、mutex 被释放后才能通过，因此满足 A 在所有其他功能之前完成。

再设置：

\[ s_C=0,\quad s_B=0,\quad s_D=0. \]

$s_C$ 表示 C 已完成，供 P1 在执行 B 前等待；$s_B$ 表示 B 已完成，$s_D$ 表示 D 已完成，P3 必须同时等待这两个条件后才能执行 F。

伪代码如下：

boolean aDone = false;
semaphore mutex = 1;
semaphore sC = 0;
semaphore sB = 0;
semaphore sD = 0;

procedure doAOnce()
{
    P(mutex);
    if (!aDone) {
        A;
        aDone = true;
    }
    V(mutex);
}

process P1()
{
    doAOnce();
    P(sC);        // B must wait until C finishes
    B;
    V(sB);        // announce B finished
}

process P2()
{
    doAOnce();
    C;
    V(sC);        // allow B
    D;
    V(sD);        // announce D finished
    E;
}

process P3()
{
    doAOnce();
    P(sB);        // F waits for B
    P(sD);        // F also waits for D
    F;
}

这里 A 的执行者没有预先指定：谁最先成功执行 $P(mutex)$，谁就执行 A。并且因为 mutex 一直保持到 A 完成，另外两个进程不可能在 A 完成前离开 doAOnce()，所以 B、C、D、E、F 都不会提前开始。

页号	物理块号	状态
0	368H	在内存
2	--	不在内存
5	--	不在内存
6	6AH	在内存
9	120H	在内存