2009 年《操作系统》A 卷（打印版）

这份材料只有题目，没有配套答案。它与另一份封面明确写有“2009 年北航《操作系统》期末试卷”的材料题干完全不同，因此不是同卷的格式副本，单独保留。源 DOC 中的两幅资源图由我按相同连线重画，公共汽车流程图则改写成文字流程。

一、名词解释（每题 5 分，共 25 分）

1. 缓冲区
2. 进程
3. 文件控制块（FCB）
4. 特权指令
5. 临界资源

二、判断题（每题 1 分，共 5 分）

1. 并发进程的执行结果只取决于进程本身，不受外界影响。（　）
2. 任何一个进程在申请新资源前总是先归还已得到的资源，则系统不会死锁。（　）
3. P、V 操作不仅可用来实现进程的同步与互斥，而且可以防止系统死锁。（　）
4. 银行家算法是在保证至少有一个进程能得到所需的全部资源的前提下进行资源分配的。（　）
5. 如果不能控制并发进程执行的相对速度，则它们在共享资源时一定会出现与时间有关的错误。（　）

三、简答题（每题 5 分，共 20 分）

1. 操作系统在进程管理方面的五项主要活动是什么？
2. 操作系统在存储管理方面有哪三项主要活动？
3. 操作系统在外存管理方面有哪三项主要活动？
4. 操作系统在文件管理方面有哪五项主要活动？

四、死锁问题（共 15 分）

1. 资源分配图（5 分）

下面的资源图（a）和（b）是否会出现死锁？圆表示进程，方框表示资源，小圆点表示资源实例；箭头方向与原卷一致。

2. 无死锁条件证明（10 分）

假设在一个系统中，有 $m$ 个同类资源，由 $n$ 个进程共享。进程每次只可以申请与释放一个资源。若如下两个条件成立，证明该系统不存在死锁：

1. 每个进程的最大资源需求量 $Max_i$ 在 1 与 $m$ 之间。
2. 所有进程的最大需求量之和少于 $m+n$。

建议使用以下符号：

• $Max_i$：每个进程的最大资源需求量；
• $Need_i$：每个进程仍待满足的资源需求量；
• $Allocation_i$：每个进程已经被满足的资源需求量。

五、进程同步（共 15 分）

1. P、V 操作（5 分）

描述进程间通信原语 P 操作与 V 操作的定义。

2. 公共汽车上的同步（10 分）

司机与售票员的工作流程为：

• 司机：启动车辆 → 行车 → 到站停车；
• 售票员：关车门 → 售票 → 开车门。

初始状态为车辆停在起点站、车门开启，等待第一批乘客；发车时间到后，售票员关好车门，司机才可以启动车辆。请回答：

1. 司机与售票员之间是同步关系还是互斥关系？
2. 用 P、V 操作管理时应定义几个信号量？初值为多少？
3. 在上述两个流程中填入适当的 P、V 操作，使二者安全、协调地工作。

六、存储管理（10 分）

一个 32 位虚拟存储系统采用两级页表：逻辑地址的第 22～31 位索引第一级页表，第 12～21 位索引第二级页表，第 0～11 位是页内偏移。进程地址空间为 4 GB。

如果从 0xC0300000 开始映射第一级页表所占的 4 KB 空间，4 MB 大小的页表空间起始位置应映射在哪里？说明理由。一个 32 位地址占 4 字节。

七、进程调度（10 分）

系统有 1 个 CPU，所有进程只使用 CPU；时间从 0 开始，最高优先级为 0。

进程	到达时间	优先级	所需运行时间
A	0	2	3
B	2	3	8
C	4	4	6
D	6	1	5
E	8	0	4

绘图说明以下调度过程，并在以时间为横轴的图中标明每个进程的“等待”和“运行”状态：

1. 先来先服务（FCFS）；
2. 轮转调度（Round-Robin），时间片为 2；
3. 优先级轮转法（Priority Round-Robin），时间片为 2；
4. 最短进程优先算法（Shortest Process Next）。