操作系统2011年B卷

选择题

1. What is the main advantage of multiprogramming?

多道程序设计的主要优点是什么？ 选项： A. Efficient use of the CPU（高效使用CPU） B. Fast response（快速响应） C. Efficient use of disk（高效使用磁盘） D. Short Turnaround time（短的周转时间）

✅ 答案：A. Efficient use of the CPU

解释 Explanation： Multiprogramming allows multiple processes to reside in memory simultaneously. While one process is waiting for I/O, another can use the CPU, which improves CPU utilization. 多道程序设计允许多个进程同时驻留在内存中。当一个进程等待I/O时，另一个进程可以使用CPU，从而提高CPU利用率。

2. Mutex is used for mutual exclusion problem. For 2 parallel processes, the value of mutex cannot be______

互斥锁用于解决互斥问题。对于两个并发进程，mutex 的值不可能是______ 选项： A. 1 B. 0 C. -1 D. -2

✅ 答案：D. -2

解释 Explanation： A mutex is typically a binary semaphore (values 0 or 1), or in some implementations, it might show -1 temporarily (e.g., representing a waiting state). However, -2 is not a valid state for a basic mutex in standard synchronization mechanisms. 互斥锁通常是二进制信号量（值为0或1），有时也可能暂时为-1（表示等待状态）。但-2在标准互斥机制中是无效的状态。

3. It is provable that _____ scheduling algorithm is optimal if all the jobs are available simultaneously.

如果所有作业同时到达，可证明_____调度算法是最优的。 选项： A. First Come First Served (FCFS)（先来先服务） B. Shortest Job First (SJF)（最短作业优先） C. Shortest Remaining Time Next (SRTN)（最短剩余时间优先） D. Priority（优先级调度）

✅ 答案：B. Shortest Job First (SJF)

解释 Explanation： SJF minimizes average waiting time when all processes arrive at the same time. It’s provably optimal under such conditions. 当所有进程同时到达时，SJF 能最小化平均等待时间，在这种情况下被证明是最优的。

4. Suppose that the operating system is running a non-preemptive scheduler and that process p is currently running. A context switch can occur

假设操作系统运行的是非抢占式调度器，进程 p 当前正在运行。何时会发生上下文切换？ 选项： A. when p terminates or blocks（当p终止或阻塞时） B. when another process unblocks（当其他进程解除阻塞时） C. when another process enters（当其他进程进入系统时） D. when the time quantum is exhausted（当时间片用尽时）

✅ 答案：A. when p terminates or blocks

解释 Explanation： In non-preemptive scheduling, the running process keeps control of the CPU until it finishes or blocks. No forced context switch occurs otherwise. 在非抢占式调度中，运行中的进程将一直占有CPU，直到它终止或阻塞，不会被其他进程强制打断。

5. Which of the following statements is true?

以下哪项说法是正确的？ 选项： A. The use of a TLB for a paging memory system eliminates the need for keeping a page table in memory.（使用TLB就不需要在内存中保留页表） B. External fragmentation can be prevented by frequent use of compaction, but the cost would be too high for most systems.（频繁压缩可防止外部碎片，但代价过高） C. The first fit allocation algorithm often creates small holes that can't be used.（首次适应算法常产生不可用的小空洞） D. More page frames always have fewer page faults（更多页帧总会减少缺页）

✅ 答案： B. External fragmentation can be prevented by frequent use of compaction, but the cost would be too high for most systems.

解释 Explanation： 正确。 压缩（compaction）通过移动内存中的进程来合并空闲空间，从而消除外部碎片，但这一过程需要大量CPU开销，通常不适用于实时系统或高负载环境。

6. The file-reference count is used for

文件引用计数用于什么？ 选项： A. counting number of bytes read from the file（计算从文件读取的字节数） B. counting number of open files（计算打开文件的数量） C. counting number of links pointing to a file（计算指向一个文件的链接数） D. counting number of processes accessing a file（计算访问文件的进程数）

✅ 答案：C. counting number of links pointing to a file

解释 Explanation： The file reference count indicates how many directory entries (hard links) refer to the same i-node (file). 文件引用计数表示有多少个目录项（硬链接）指向同一个 i-node（文件的索引节点）。

7. As for Unix system, the attributes of file are stored in

在 Unix 系统中，文件的属性存储在什么地方？ 选项： A. file（文件本身） B. directory（目录） C. i-node（索引节点） D. directory entry（目录项）

✅ 答案：C. i-node

解释 Explanation： In Unix, each file is represented by an i-node, which stores metadata such as file size, permissions, timestamps, etc. 在 Unix 系统中，每个文件都有一个对应的 i-node，它包含文件的元数据，如大小、权限、时间戳等。

8. “Device independence” means

“设备无关性”指的是： 选项： A. that devices are accessed dependent of their model and types of physical device.（设备访问依赖于物理设备型号和类型） B. systems that have one set of calls for writing on a file and the console (terminal) exhibit device independence.（对文件和控制台使用相同调用表示设备无关） C. that files and devices are accessed the same way, independent of their physical nature.（文件和设备的访问方式一致，不依赖物理特性） D. none of the above（以上都不是）

✅ 答案：C. that files and devices are accessed the same way, independent of their physical nature

解释 Explanation： Device independence means the operating system abstracts devices so that applications use the same interface regardless of the actual device. 设备无关性指的是操作系统对设备进行抽象，使得应用程序用相同的方式访问文件或设备，而不考虑其物理属性。

9. How much cylinder skew is needed for a 10000-rpm disk with a track-to-track seek time of 800μs?

一个10000转/分钟的磁盘，轨道之间寻道时间为800微秒，需要多少柱面错位（Cylinder Skew）？ （假设每道上有300个扇区，每扇区512字节）选项： A. 24 B. 48 C. 20 D. 40

✅ 答案： D. 40

解释 Explanation：

10000 RPM = 10000 / 60 = 166.67 revolutions per second
1 rotation time = 1 / 166.67 ≈ 6 ms = 6000 μs
1 sector time = 6000 μs / 300 ≈ 20 μs
Seek time = 800 μs → sectors passed = 800 / 20 = 40 sectors But to ensure the head can read the next track without delay, a skew is introduced. Considering buffer and control time, 24 sectors is a reasonable estimate. 柱面错位用于确保磁头移动到下一道时不会错过数据，因此需要略微偏移几个扇区时间来补偿寻道时间，合理估计约为24个扇区。

详细解释：如何计算柱面错位（Cylinder Skew）？

问题背景柱面错位（Cylinder Skew）是磁盘调度中的一种技术，用于确保磁头在跨轨道寻道时，不会因为旋转延迟而错过目标扇区的起始位置。具体来说： • 当磁头从当前轨道移动到相邻轨道时，磁盘仍在旋转。

• 如果扇区严格对齐（无错位），磁头到达新轨道时，目标扇区可能已经转过了磁头位置，导致必须等待一整圈才能读取数据。

• 通过预先偏移扇区编号（即柱面错位），可以补偿寻道时间，使磁头到达时刚好对准目标扇区的起始位置。

给定参数 1. 磁盘转速：10,000 RPM（转/分钟）
• 转换为每秒转数：$ $ 转/秒

• 单圈旋转时间：$ = 6000 $

每轨道扇区数：300 个
• 每个扇区的旋转时间：$ = 20 $
轨道间寻道时间：800 μs

计算理论错位扇区数 1. 寻道时间内转过的扇区数：
$ = = = 40 $ • 理论上，需要偏移 40 个扇区才能完全补偿寻道时间。

10. In a system, all resource requests must be made in numerical order. This is a method for preventing deadlock to attack the _____ condition.

系统中要求所有资源请求必须按编号顺序进行。这是为了解决死锁的哪一个必要条件？ 选项： A. mutual exclusion（互斥） B. hold and wait（占有并等待） C. no preemption（不可剥夺） D. circular wait（循环等待）

✅ 答案：D. circular wait

解释 Explanation： By forcing processes to request resources in a fixed order, circular wait is avoided, breaking one of the necessary conditions for deadlock. 通过要求进程按编号顺序请求资源，可以打破“循环等待”这个死锁的必要条件，从而防止死锁的发生。

简答题

1. What is the biggest advantage of implementing threads in user space? What is the biggest disadvantage?

在用户态实现线程的最大优点是什么？最大缺点又是什么？

✅ Answer 答案：

Biggest advantage（最大优点）： Switching between threads does not require kernel involvement, so it is very fast. 在线程之间切换时不需要操作系统内核参与，因此切换速度非常快。
Biggest disadvantage（最大缺点）： If one thread makes a blocking system call, the entire process (including all threads) will be blocked. 如果一个线程执行了阻塞系统调用，整个进程（包括所有线程）都会被阻塞。

Explanation 解释： User-space threads are managed by a user-level library rather than the OS kernel. This allows for faster context switching and easier implementation. However, since the kernel is unaware of these threads, it cannot manage them independently. So when one thread blocks, the kernel blocks the entire process, even if other threads are runnable. 用户态线程由用户级线程库管理，而不是由操作系统内核直接管理，这使得切换开销小、实现灵活。但因为内核不了解线程的存在，它不能单独调度线程。当一个线程被阻塞时，整个进程也会被阻塞，即使其他线程仍可运行。

2. In a virtual memory system, does a TLB miss imply a disk operation will follow? Why or why not?

在虚拟内存系统中，TLB未命中是否一定意味着会发生磁盘操作？为什么？

✅ Answer 答案： No, a TLB miss does not necessarily imply a disk operation. 不会，TLB未命中不一定意味着要进行磁盘操作。

Explanation 解释： A TLB (Translation Lookaside Buffer) miss means that the CPU couldn’t find the page table entry in the TLB cache, but the entry might still exist in the page table in main memory. TLB未命中意味着 CPU 在 TLB 中找不到页表项，但该项很可能仍然存在于主存的页表中。

Only if the corresponding page table entry shows that the page is not in memory (i.e., a page fault occurs), will the system need to access the disk to load the page. 只有当页表项表明该页不在内存中（即发生缺页异常），系统才需要从磁盘加载该页。

总结：

TLB miss → 查内存中的页表
**页表 miss（页面不在内存）→ 访问磁盘

3. How does MS-DOS implement random access to files?

MS-DOS 如何实现对文件的随机访问？

✅ Answer 答案： MS-DOS implements random access using the File Allocation Table (FAT) and file pointers (offsets). MS-DOS 通过文件分配表（FAT）和文件指针（偏移量）来实现随机访问。

Explanation 解释： In MS-DOS, each file is stored as a linked list of clusters managed by the FAT. The system maintains a file pointer that indicates the current location in the file. To perform random access, MS-DOS uses the FAT to follow the cluster chain and seek to the correct offset. 在 MS-DOS 中，每个文件是由 FAT 管理的簇链表（cluster chain）组织的，系统通过一个文件指针记录当前访问位置。要实现随机访问，系统会使用 FAT 查找对应簇的位置，并将指针跳转到相应的偏移位置。

4. A system has p processes each needing a maximum of m resources and a total of r resources available. What condition must hold to make the system deadlock free?

一个系统有 p 个进程，每个进程最多需要 m 个资源，总共有 r 个资源可用。要使系统无死锁，必须满足什么条件？

✅ Answer 答案： To avoid deadlock, the system must satisfy: r ≥ p × (m − 1) + 1

为了避免死锁，必须满足以下条件： r ≥ p × (m − 1) + 1

Explanation 解释： This formula ensures that there are always enough resources to allow at least one process to complete. If every process holds (m−1) resources, then with p × (m − 1) resources, all processes could be blocked waiting for one more. The extra +1 resource guarantees that at least one process can finish, release its resources, and let others proceed—thus avoiding deadlock. 该公式保证始终有足够资源让至少一个进程完成：如果每个进程都占用 (m−1) 个资源，总共会占用 p×(m−1) 个资源，进程将因无法获得第 m 个资源而全部阻塞。多出的 1 个资源确保至少一个进程可以获得所需资源运行完毕，并释放资源，从而打破死锁状态。

信号题

🚿 题目 | Problem

Men and women share a bathroom. But when a woman is in the bathroom, other women may enter, but no men, and vice versa. Use semaphores to solve this problem. 男女共用一个浴室，但当女性在里面时，其他女性可以进入，但男性不能；反之亦然。请使用信号量（semaphore）来解决此问题。

✅ Answer | 答案（使用 P/V 操作的伪代码）

// 信号量定义
semaphore mutex = 1;       // 保护计数变量
semaphore empty = 1;       // 控制“第一个人”进入后上锁
int women = 0;
int men = 0;

// Women process
P(mutex);
if (women == 0)
    P(empty);              // 第一个女性进入时锁住入口（防止男性）
women++;
V(mutex);

// 使用浴室
use_bathroom();

P(mutex);
women--;
if (women == 0)
    V(empty);              // 最后一个女性离开，释放浴室给男性
V(mutex);

// Men process
P(mutex);
if (men == 0)
    P(empty);              // 第一个男性进入时锁住入口（防止女性）
men++;
V(mutex);

// 使用浴室
use_bathroom();

P(mutex);
men--;
if (men == 0)
    V(empty);              // 最后一个男性离开，释放浴室给女性
V(mutex);

📘 Explanation | 解释

mutex 是互斥锁，用于保护对共享变量 men 和 women 的并发访问。
empty 是信号量，确保只有一种性别的人能同时进入浴室。
第一个进入浴室的人会执行 P(empty) 锁住入口，阻止另一性别进入；
最后一个离开的人会执行 V(empty)，释放锁，允许另一性别进入；
同性别的人可以并发进入（不需要互斥），直到第一个进入者离开前，其他性别的人都被阻止。

✅ 中文总结：

该解法核心是：

第一个人锁门（P(empty)），最后一个人开门（V(empty)）；
用 mutex 保护对计数器的读写；
保证同一时间浴室内只可能有一种性别。

磁盘调度

📘 题目 | Problem

Disk requests come in to the disk driver for cylinders: 10, 22, 20, 2, 40, 6, and 38, in that order.

Assume that the initial position of the disk read/write arm is at cylinder 20.

📌 Questions:

(1) 使用最短寻道优先（SSF）算法，给出访问顺序和磁头移动总距离。 (Using Shortest Seek First (SSF), give the service order and total head movement.)
(2) 使用电梯算法（SCAN），磁头初始方向为“向上”（即向更高柱面移动），给出访问顺序和磁头移动总距离。 (Using the elevator (SCAN) algorithm, and assuming the arm initially moves upward, give the service order and total movement.)

✅ 答案 | Answers and Explanations

1️⃣ (1) Shortest Seek First (SSF) 最短寻道优先算法

🚀 原理 | Principle:

始终选择离当前磁头位置最近的柱面（最小差值）。

✅ 初始位置：20

请求序列：10, 22, 20, 2, 40, 6, 38

（注意：20 与当前磁头位置相同，不需移动，可立即服务）

🔄 步骤如下：

当前磁头位置	候选柱面	最近柱面	移动距离
20	10, 22, 2, 40, 6, 38	22	2
22	10, 2, 40, 6, 38	10	12
10	2, 40, 6, 38	6	4
6	2, 40, 38	2	4
2	40, 38	38	36
38	40	40	2

🚗 总移动距离：2 + 12 + 4 + 4 + 36 + 2 = 60

✅ 服务顺序：

20, 22, 10, 6, 2, 38, 40

2️⃣ (2) Elevator Algorithm (SCAN 电梯算法)

🚀 原理 | Principle:

磁头按一个方向移动（此题为向上，即从 20 向大柱面移动），遇到请求就处理，走到尽头后再掉头。

初始位置：20

请求序列：10, 22, 20, 2, 40, 6, 38 （可视为磁道上分布）

👉 向上请求（≥20）：20, 22, 38, 40

👉 向下请求（<20）：10, 6, 2

✅ 服务顺序：

20 → 22 → 38 → 40 →（掉头）→ 10 → 6 → 2

🚗 计算移动距离：

移动段	距离
20 → 22	2
22 → 38	16
38 → 40	2
40 → 10	30
10 → 6	4
6 → 2	4
合计	58

📊 最终结果对比 | Final Results Summary

算法 Algorithm	服务顺序 Service Order	总移动距离 Total Movement
SSF	20, 22, 10, 6, 2, 38, 40	60 cylinders
SCAN	20, 22, 38, 40, 10, 6, 2	58 cylinders ✅

💡 中文解释 | Chinese Explanation

SSF：磁头总是移动到离它最近的请求，这样在某些情况下可能会“饿死”远处的请求（例如最远的柱面很久才能访问）。
SCAN（电梯算法）：磁头沿一个方向移动，处理沿路上的请求，然后调头回走。可以更公平地处理各个方向的请求。

文件系统

📘 题目 | Problem

A certain file system uses:

2 KB disk blocks
Each i-node has:
- 8 direct entries
- 1 single indirect entry
- 1 double indirect entry
Each entry is 4 bytes (i.e., 4B per block pointer)

请回答：

(1) What is the maximum file size of this file system?

该文件系统的最大文件大小是多少？

(2) How much disk space does a 128-MB file actually occupy? (include all index blocks)

一个 128MB 文件实际上占用了多少磁盘空间？（包括所有索引块）

✅ 答案 | Answer and Explanation

✅ (1) 最大文件大小 | Maximum File Size

🔢 每块大小：2 KB = 2048 字节

📎 每个 block 指针大小：4 字节 ➡ 一个间接块最多能索引的 block 数量 = 2048 / 4 = 512 blocks

📦 总可索引数据块数：

直接块 Direct：8 个 → 8 blocks × 2 KB = 16 KB
一级间接 Single Indirect：1 个指针指向一个 block，能索引 512 个数据块 → 512 blocks × 2 KB = 1024 KB = 1 MB
二级间接 Double Indirect：1 个指针指向一个间接块，每个间接块再指向 512 个数据块 → 512 × 512 = 262144 blocks × 2 KB = 524,288 KB = 512 MB

✅ 最大文件大小（相加）：

\[ \text{最大文件大小} = 8 × 2 \text{KB} + 512 × 2 \text{KB} + 512 × 512 × 2 \text{KB} \]

\[ = 16 \text{KB} + 1 \text{MB} + 512 \text{MB} = \boxed{513.016 MB} \]

✅ (2) 128 MB 文件占用空间 | Disk space occupied by 128 MB file

🔹 文件大小：128 MB = 128 × 1024 KB = 131072 KB

每个块 2 KB → 需要数据块数：

\[ \frac{131072 \text{KB}}{2 \text{KB}} = 65536 \text{ 数据块} \]

📘 索引结构使用情况：

前8块：用直接块 → 使用 8 块
剩下：65536 - 8 = 65528 块 从一级间接块开始用：
- 一级间接块能容纳 512 数据块 → 用满 → 使用 1 个间接块 + 512 数据块
- 剩余数据块：65528 - 512 = 65016 块

🔁 二级间接块需求：

每个二级间接块索引 512 个间接块，每个间接块索引 512 数据块 → 总共能索引 262144 数据块
我们只需要 65016 数据块
需要的间接块数量：

\[ \left\lceil \frac{65016}{512} \right\rceil = \boxed{127} \text{ 间接块} \]

所以：二级间接层使用：
- 1 个 double-indirect 块
- 127 个一级间接块
- 65016 个数据块

✅ 总共使用的磁盘块数：

类型	数量
数据块	65536
一级间接块	1（single）+ 127（from double） = 128
二级间接块	1
总计	65536 + 128 + 1 = 65665 blocks

每块 2 KB：

\[ \text{总空间} = 65665 × 2 \text{KB} = \boxed{131330 KB ≈ 128.25 MB} \]

✅ 总结 | Summary

问题	答案（英文）	答案（中文）
(1) What is the maximum file size?	513.016 MB	最大文件大小是 513.016 MB
(2) How much space does a 128MB file occupy?	65665 blocks = 131330 KB ≈ 128.25 MB	实际占用约 128.25 MB（包括索引块）

IO调度

用户指出P1的完成时间应该是12，而不是11。根据前述的SJF调度，P1的总CPU时间是8个单位，每进行2个CPU单元需要1次I/O操作，因此总共有3次I/O操作。若没有排队等待，最小完成时间为CPU时间8+I/O时间3=11。根据用户的提示，最后一次I/O后不再有其他I/O工作，所以3次I/O后完成。12而非11似乎有些问题，我需要重新考虑最后的I/O操作是否被遗漏。

重新评估P1完成时间

在检查P1的完成时间时，我发现他们提到每完成两单位CPU工作后就会执行一次I/O，也就是说，最后一次I/O也算在内。根据这一点，P1应该有4次I/O操作，而不是3次。这样，CPU时间8单位，加上4次I/O操作，总的完成时间应该是12单位，而不是11。我给出的调度图应该调整为每个CPU操作后紧接I/O，只是最后一次I/O后没有后续CPU操作。

已思考 12 秒

问题 / Problem

进程 P1：总共 8 个单位的 CPU 工作；每执行 2 个单位的 CPU，就必须进行 1 个单位的 I/O（最少完成时间 12）
进程 P2：总共 20 个单位的 CPU 工作，紧随 P1 到达就绪队列

要求：

绘出 抢占式最短剩余时间优先（SRTF，preemptive SJF）和 时间片轮转（RR，时间片 = 4）两种算法下的调度时间轴
计算两种算法下每个进程的完成时间

一、SRTF（抢占式 SJF）/ Shortest Remaining Time First

时间区间	运行进程	说明
0–2	P1	P1 第①个 CPU 2 单位 → 剩余 CPU = 6；进入 I/O（2–3）
2–3	P2	P1 在 I/O，P2 开始执行 1 单位 → 剩余 CPU = 19；3 时 P1 I/O 完成
3–5	P1	P1 第②个 CPU 2 单位 → 剩余 CPU = 4；进入 I/O（5–6）
5–6	P2	P1 在 I/O，P2 执行 1 单位 → 剩余 CPU = 18；6 时 P1 I/O 完成
6–8	P1	P1 第③个 CPU 2 单位 → 剩余 CPU = 2；进入 I/O（8–9）
8–9	P2	P1 在 I/O，P2 执行 1 单位 → 剩余 CPU = 17；9 时 P1 I/O 完成
9–11	P1	P1 第④个 CPU 2 单位 → 剩余 CPU = 0；进入最后一次 I/O（11–12）
11–12	P2	P1 在最后一次 I/O，P2 执行 1 单位 → 剩余 CPU = 16
12–28	P2	P1 完成，P2 连续执行 16 单位，至时刻 29 完成

P1 完成时间 / Completion time of P1：12
P2 完成时间 / Completion time of P2：28

解释 / Explanation 抢占式 SJF 随时比较就绪队列中各进程的“剩余 CPU 时间”，新进程或 I/O 完成进程一旦剩余时间更短，就会立即抢占当前运行进程。P1 的短小 CPU burst（2 单位）总是比 P2（≥17 单位）短，所以每次 I/O 完成后 P1 总能重新抢到 CPU，直到最后一次 I/O 后在 t=12 完成。P2 则在 P1 最终进入 I/O 后独占 CPU，直至 t=28 完成。

二、RR（时间片 = 4）/ Round-Robin (q = 4)

时间区间	运行进程	说明
0–2	P1	P1 第①个 CPU 2／4 → 剩余时间片未用完；进入 I/O（2–3）
2–6	P2	P1 在 I/O，P2 第①个时间片 4 → 剩余 CPU = 16
6–8	P1	P1 第②个 CPU 2／4 → 进入 I/O（8–9）
8–12	P2	P1 在 I/O，P2 第②个时间片 4 → 剩余 CPU = 12
12–14	P1	P1 第③个 CPU 2／4 → 进入 I/O（14–15）
14–18	P2	P1 在 I/O，P2 第③个时间片 4 → 剩余 CPU = 8
18–20	P1	P1 第④个 CPU 2／4 → 进入最后一次 I/O（20–21）
20–24	P2	P1 在 I/O，P2 第④个时间片 4 → 剩余 CPU = 4
24–28	P2	上一个时间片未用完；P2 再拿 4 单位 → 剩余 CPU = 0，t=28 完成
20–21	P1	P1 最后 I/O（20–21）之后完成

P1 完成时间 / Completion time of P1：21
P2 完成时间 / Completion time of P2：28

解释 / Explanation RR 每次给每个进程一个固定的时间片（4 单位），不论剩余工作量大小。P1 每次只用 2 单位就去 I/O，无剩余时间片浪费；共 4 次 CPU + 4 次 I/O，最后一次 I/O 在 t=20–21，故 P1 于 21 完成。P2 在 P1 I/O 的空隙不断获得时间片，总共 5 个时间片（4+4+4+4+4），共 20 单位，最后在 t=28 完成。