操作系统2010

选择题

---

1. When the printing event which a process requested is finished, transition _______ will occur.

当一个进程请求的打印事件完成时，会发生哪种状态转换？

A. Running → Ready B. Running → Blocked C. Blocked → Running D. Blocked → Ready ✅

---

2. Shared variables are those that ______

共享变量是指哪些变量？

A. 只能被系统进程访问 B. 只能被多个进程互斥地访问 C. 只能被用户进程访问 D. 可以被多个进程访问 ✅

✔️ 正确答案：D. can be accessed by a lot of process

🔍 解释 Explanation: 共享变量是指可以被多个进程同时访问的变量。 为了防止竞态条件（race condition），访问共享变量通常需要使用同步机制（如互斥锁、信号量等），但它本质上就是多个进程共享的数据区域。

---

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

如果所有作业同时可用，可以证明哪种调度算法是最优的？

A. FCFS（先来先服务） B. SJF（最短作业优先） ✅ C. Round-robin（时间片轮转） D. Priority（优先级调度）

✔️ 正确答案：B. SJF

🔍 解释 Explanation: SJF（Shortest Job First）在所有作业同时到达的前提下，能够提供最短平均等待时间，因此是理论上的最优算法。 它在实践中难以实施的原因是：事先很难准确知道每个作业的运行时间。

---

4. In a system, we require all processes to request all their resources before starting execution. This is a method for preventing deadlock to attack the ________ condition.

如果系统要求所有进程在开始执行前就请求所有资源，这是为了破坏死锁中的哪个必要条件？

A. Mutual Exclusion（互斥） B. Hold and Wait（占有且等待） ✅ C. No Preemption（不可抢占） D. Circular Wait（循环等待）

✔️ 正确答案：B. Hold and Wait

🔍 解释 Explanation: Hold and Wait 是死锁的四个必要条件之一，指的是进程在保持已有资源的同时，还请求其他资源。 如果强制进程在执行前一次性请求所有资源，那么进程要么全部满足、要么一个也得不到，从而避免资源保持与等待的情况，就能破坏该条件，防止死锁。

---

5. Which of the following algorithm can result in external fragmentation problem?

下列哪种算法会导致外部碎片（external fragmentation）问题？

A. first fit（首次适应） B. next fit（下一次适应） C. best fit（最佳适应）✅ D. worst fit（最差适应）

✔️ 正确答案：** C. best fit（最佳适应）**

因为它每次都分配最小刚好满足需求的空闲块， 这样就会留下大量非常小、用不了的“边角料”， 结果就是：外部碎片越来越多，新的大请求越来越难满足。

---

6. Which of the following page replacement algorithm need to clear R bit periodically?

下列哪种页面置换算法需要定期清除 R 位（引用位）？

A. FIFO（先进先出） B. Second Chance（第二次机会） C. Aging（老化算法） ✅ D. Working Set（工作集）

✅ 正确答案：C. Aging

📘 解释 Explanation： Aging 算法会定期检查每个页面的 R 位，并将其加入一个 8 位或更多位的“老化计数器”。如果一个页面最近被访问过，它的 R 位为 1；如果没有，它为 0。每次周期性地将 R 位加进计数器后清除 R 位，使得“老化”的页面逐渐变得不活跃，从而更可能被置换。

---

7. Writing commands to the device registers is done in which layers?

向设备寄存器写命令是在哪一层完成的？

A. Interrupt handlers（中断处理程序） B. Device drivers（设备驱动程序） ✅ C. Device-independent OS software（设备无关操作系统） D. User-level I/O software（用户层 I/O 软件）

✅ 正确答案：B. Device drivers

📘 解释 Explanation： 设备驱动是操作系统中与硬件直接交互的一层，负责向设备的寄存器写入控制命令（如启动、停止、读取等），也包括处理中断、读取设备状态等。

---

8. “Device independence” means

“设备无关性”是指：

A. 访问设备依赖于它们的型号和物理类型 B. 系统为写文件和终端提供一组相同的调用 C. 文件和设备以相同方式访问，与其物理特性无关 ✅ D. 以上都不是

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

📘 解释 Explanation： “设备无关性”指的是操作系统提供一种统一的方式来访问不同类型的设备，用户不需要知道设备是磁盘、终端还是打印机，都通过相同的 I/O 接口或 API 进行访问。

---

9. The purpose of the open file call is to ______.

open() 文件调用的目的是：

A. 在主存中查找指定文件 B. 将指定文件复制到主存 C. 在存储介质中查找该文件的目录 D. 将文件的目录项加载到主存中 ✅

✅ 正确答案：D. fetch the directory of the file into main memory

📘 解释 Explanation： 调用 open() 时，操作系统会：

• 在文件系统中查找文件对应的目录项（directory entry）
• 并将其信息加载到主存（如打开文件表）

这让后续对文件的访问更快（例如读写时可以直接查表）。

---

10. As for MS-DOS/Windows system, the attributes of file are stored in______.

在 MS-DOS 或 Windows 系统中，文件的属性存储在什么地方？

A. file（文件内容） B. directory（目录） C. directory entry（目录项） ✅ D. i-node（索引节点）← Linux/Unix 使用

✅ 正确答案：C. directory entry

📘 解释 Explanation： 在 MS-DOS / Windows 中，每个文件的属性（如只读、隐藏、创建时间等）都存储在目录项（directory entry）中，而不像 Linux 使用 i-node。

---

填空题

---

1. Operating systems can be viewed from two viewpoints: Extended Machine (扩展机器) and Resource Manager (资源管理者).

✅ 答案：Extended Machine, Resource Manager

📘 解释 Explanation： 操作系统既是对硬件的抽象（扩展机器），也是对资源的统一管理者。

• 扩展机器（Extended Machine）：屏蔽底层复杂硬件，提供统一接口。
• 资源管理者（Resource Manager）：管理 CPU、内存、I/O 等资源。

---

2. If we implement thread in kernel space, ______ is a basic unit of CPU utilization.

✅ 答案：Thread（线程）

📘 解释 Explanation： 如果线程在线程由内核实现（Kernel-level Thread），那么线程就是调度的基本单位（即 CPU 利用的基本单位）。 反之，如果是用户级线程，CPU 调度的单位还是进程。

---

3. The initial value of the semaphore S is 2. If the current value is -1, then there are ______ processes waiting.

✅ 答案：1

📘 解释 Explanation：

• 信号量初始值为 2，表示最多允许 2 个进程进入。
• 当前值为 -1，说明有3 个进程请求了资源：2 个成功（使值变为 0 和 -1），剩下的 1 个被阻塞在等待队列中。 所以，阻塞队列中有 1 个进程。

---

4. ______ scheduling algorithm can deal with the urgent process in time.

✅ 答案：Priority（优先级）

📘 解释 Explanation： 优先级调度算法允许紧急（高优先级）的任务优先执行，因此能够及时处理紧急任务。

---

5. A computer with a 32-bit address uses a two-level page table. Virtual addresses are split into a 9-bit top-level page table field, an 11-bit second-level page table field, and an offset. Each page is 4096 bytes. And there are ______ pages in the address space.

✅ 答案：2²⁰（即 1048576）

📘 解释 Explanation：

• 虚拟地址总长：32 位
• 偏移（offset）位数 = log₂(4096) = 12 位（因为页面大小是 2¹²）
• 剩下的地址用于页号：32 - 12 = 20 位 所以，一共有 2²⁰ 个页面。

---

6. Disk requests come in to the disk driver for cylinders 10, 22, 20, 2, 40, 6, and 38, in that order. The arm is initially at cylinder 20. A seek takes 6 msec per cylinder moved.

✅ Elevator (SCAN) 算法，初始向上：348 ms ✅ Closest Cylinder Next（SSTF）算法：360 ms

📘 解释 Explanation：

• Elevator/SCAN 算法：磁臂上下扫描，遇到请求就处理。
• SSTF 算法：总是选择当前最接近的请求。虽然短期效率高，但可能导致“饥饿”。
• 总移动的 cylinder 数 × 每 cylinder 的开销 = 总寻道时间。

---

🔶 已知条件（Given）：

• 请求队列（Disk request queue）：10, 22, 20, 2, 40, 6, 38
• 磁头初始位置（Initial head position）：20
• 每移动一个柱面（cylinder）的寻道时间：6 ms

---

🧭 1. Elevator (SCAN) 算法（初始向上）

SCAN 又称“电梯算法”，磁头向一个方向移动（此处为向上），依次处理沿途的请求，到头后反转方向。

✅ 排序并分类：

升序排列：2, 6, 10, 20, 22, 38, 40 当前磁头在 20，初始向上 → 处理顺序为： 22 → 38 → 40 → 然后掉头 → 10 → 6 → 2

⚠️ 注意：20 本身也在请求中，也会处理。

✅ 处理顺序：

起点: 20
→ 22 （+2）
→ 38 （+16）
→ 40 （+2）
→ 掉头 → 10（+30）
→ 6 （+4）
→ 2 （+4）

✅ 计算寻道距离：

2 + 16 + 2 + 30 + 4 + 4 = 58 cylinders
寻道时间 = 58 × 6ms = ✅ 348ms

---

🧭 2. SSTF（Shortest Seek Time First）

每次选择与当前磁头最近的请求，优先服务最近的磁道。

✅ 初始位置：20

剩余请求队列：10, 22, 20, 2, 40, 6, 38

✅ 处理过程如下：

步骤	当前位置	剩余请求队列	最近请求	移动距离
1	20	10, 22, 2, 40, 6, 38	22	2
2	22	10, 2, 40, 6, 38	10	12
3	10	2, 40, 6, 38	6	4
4	6	2, 40, 38	2	4
5	2	40, 38	38	36
6	38	40	40	2

✅ 总移动距离：

2 + 12 + 4 + 4 + 36 + 2 = 60 cylinders
寻道时间 = 60 × 6ms = ✅ 360ms

---

✅ 总结对比表：

算法	顺序处理的磁道	总移动柱面数	总寻道时间
SCAN（向上）	20 → 22 → 38 → 40 → 10 → 6 → 2	58	✅ 348 ms
SSTF（最短优先）	20 → 22 → 10 → 6 → 2 → 38 → 40	60	✅ 360 ms

---

7. With symbolic links, only the true owner of the file has a pointer to the i-node.

✅ 答案：True / 正确

📘 解释 Explanation： 符号链接（symbolic link）*实际上是一个指向目标文件路径的“软链接”，只有*原始文件的拥有者持有指向 i-node 的真实链接；符号链接自身是一个文件，内容是目标路径。

---

简答题

---

1. Describe the difference between a process and a program.

答： 进程是具有独立功能的程序在某个数据集合上的一次运行活动，是操作系统资源分配和调度的基本单位。程序是指令的有序集合。

区别：

• 进程是动态的，表示程序执行的状态；程序是静态的，只是存储在磁盘上的代码。
• 进程是一个活动的实体，是正在执行的程序；程序是静态的，不会改变，直到被加载到内存中。
• 进程与程序之间不一定一一对应：一个程序可以同时有多个进程在执行，一个进程也可以对应一个程序或程序的一部分。
• 进程可以创建子进程，从而形成进程树，而程序只是一个静态的代码。

English Answer: A process is an instance of a program being executed on a particular data set, and it is the basic unit for resource allocation and scheduling in an operating system. A program is an ordered set of instructions. Differences:

• A process is dynamic, representing the state of a program during execution; a program is static, just the stored code on the disk.
• A process is an active entity, while a program remains unchanged until loaded into memory.
• A process and a program are not necessarily one-to-one: one program can have multiple processes executing simultaneously, and one process can correspond to a part of a program or the whole program.
• A process can create child processes, forming a process tree, while a program is static code.

---

2. Describe the concept of the critical resource and critical region, and give an example for each.

答：

• 临界资源：在同一时刻，只允许一个进程访问的资源。例如：硬件资源如打印机、输入机，或者软件资源如共享的变量、文件、表格、队列等。
• 临界区：指访问临界资源的程序段。在临界区内，只允许一个进程访问临界资源，其他进程必须等待，直到该进程执行完毕。 举例：
  • 临界资源：打印机。
  • 临界区：假设 a 是共享变量，则访问 a 的那段代码就是临界区，例如：a := a + 1; print(a);。

English Answer:

• Critical resource: A resource that only one process can access at any given time. For example, hardware resources like printers or input devices, or software resources like shared variables, files, tables, queues, etc.
• Critical region: The portion of the program that accesses a critical resource. Inside the critical region, only one process is allowed to access the critical resource, and other processes must wait until the current process is finished. Example:
  • Critical resource: A printer.
  • Critical region: If a is a shared variable, the program segment that accesses a is the critical region, e.g., a := a + 1; print(a);.

---

3. Will a Resource Allocation Graph with a cycle lead to deadlock? Why?

答： 不一定。

• 如果每个资源只有一个资源实例，那么有环的资源分配图肯定会导致死锁。
• 如果每个资源有多个资源实例，那么有环的资源分配图可能导致死锁，但不一定会。因为在多实例的情况下，某些进程可能仍然能够获得所需的资源，从而避免死锁。

English Answer: Not necessarily.

• If each resource has only one instance, a cycle in the resource allocation graph will definitely lead to deadlock.
• If each resource has multiple instances, a cycle in the resource allocation graph may lead to deadlock, but it is not guaranteed. This is because, in the case of multiple instances, some processes may still be able to acquire the resources they need and avoid deadlock.

---

4. How many disk operations are needed to fetch the i-node for the file /usr/ast/workspace/mp1.tar? Why?

假设根目录的i-node已经在内存中，但路径上的其他内容都不在内存中，且假设每个目录都适合存储在一个磁盘块中，如何计算获取文件 /usr/ast/workspace/mp1.tar 的 i-node 所需的磁盘操作次数？

先访问i-node，接着访问目录！

Answer:

为了访问文件 /usr/ast/workspace/mp1.tar 的 i-node，需要执行一系列的磁盘操作。具体步骤如下：

① directory for /

② i-node for /usr

③ directory for /usr

④ i-node for /usr/ast

⑤ directory for /usr/ast

⑥ i-node for /usr/ast/workspace

⑦ directory for /usr/ast/workspace

⑧ i-node for /usr/ast/workspace/mp1.tar

因此，总共需要 8 次磁盘操作来读取所有所需的 i-node 和目录项。

---

🧮 页表题（含中文翻译）

There are 32 pages in the user space of virtual storage. Each page is 1K bytes in size. The computer has 16K bytes of main memory.

用户空间有 32 页，每页大小为 1KB。主存有 16KB。

---

(1) How many bits are needed to describe the logical address space?

逻辑地址空间需要多少位来描述？

✅ 解答：

英文： Each page = 1 KB = 2¹⁰ bytes There are 32 pages → virtual address space = 32 KB = 2¹⁵ bytes So, 15 bits are needed to address the entire logical space.

中文： 每页 1KB = 2¹⁰ 字节，共有 32 页，所以逻辑地址空间为 32KB = 2¹⁵ 字节， 因此需要 15 位 来表示逻辑地址。

✅ 答案：15 bits

---

(2) How many bits are needed to describe the physical address space?

物理地址空间需要多少位来描述？

✅ 解答：

英文： Physical memory = 16 KB = 2¹⁴ bytes So, 14 bits are needed to address the entire physical space.

中文： 物理内存为 16KB = 2¹⁴ 字节， 所以需要 14 位 来描述物理地址空间。

✅ 答案：14 bits

---

(3) Given that page 0, 1, 2, 3 are loaded into frames 5, 10, 4, 7 respectively, what is the physical address of logical address 2,652 and 1,340 (both in decimal)?

假设虚页 0,1,2,3 分别装入了物理块 5,10,4,7，求逻辑地址 2652 和 1340（十进制） 对应的物理地址。

---

🧩 思路 / Thought Process：

• 每页大小为 1K = 2¹⁰ 字节，因此：
  • 页内偏移(offset) = 逻辑地址的低 10 位
  • 虚页号(VPN) = 逻辑地址的高位（15 - 10 = 5 位）

✅ 分析地址 2652：

Step 1: Convert 2652 to binary

2652 (decimal) = 0000101001011100₂  
→ 虚页号 = 00010₂ = 2  
→ 页内偏移 = 101001011100₂ = 0x25C = 604

Step 2: 页号 2 对应物理块号 4（题目给定）

Step 3: 构建物理地址

• 物理块号 4 = 0100₂（因为每块为 1KB = 2¹⁰ 字节）
• 将块号与页内偏移拼接得到物理地址二进制：

物理地址 = 0100 101001011100₂ = 0100101001011100₂  
         = 0x125C = 4700₁₀

✅ Answer: 4700 (decimal) = 0x125C (hex)

---

✅ 分析地址 1340：

Step 1: Convert 1340 to binary

1340 = 0000010100111100₂  
→ 虚页号 = 00001₂ = 1  
→ 页内偏移 = 0100111100₂ = 0x13C = 316

Step 2: 页号 1 对应物理块号 10 = 1010₂

Step 3: 构建物理地址

物理地址 = 1010 0100111100₂ = 10100100111100₂  
         = 0x293C = 10556₁₀

✅ Answer: 10556 (decimal) = 0x293C (hex)

---

✅ 最终答案汇总：

问题（Question）	英文回答	中文解释	最终答案
(1) Logical address bits	15 bits	逻辑地址空间为 32KB → 2¹⁵ → 15 位	✅ 15 bits
(2) Physical address bits	14 bits	物理内存为 16KB → 2¹⁴ → 14 位	✅ 14 bits
(3.1) Address of 2652	4700 (decimal) = 0x125C	页号2 → 块号4，拼接偏移	✅ 4700
(3.2) Address of 1340	10556 (decimal) = 0x293C	页号1 → 块号10，拼接偏移	✅ 10556

---

✅ 互斥题

英文题目：

One tunnel, which is very narrow, allows only one passenger to pass at once. Please use semaphores to realize the following situation:

• The passengers from one direction must pass continuously.
• The other direction's visitors can start to go only when no passengers want to pass the tunnel from the opposite direction.

中文翻译：

有一条非常窄的隧道，每次只允许一个方向的行人连续通过。 使用信号量完成如下同步机制：

• 某个方向的行人一旦开始通行，必须连续通过；
• 只有当对向无行人要通过时，反方向的人才能开始进入隧道。

---

✅ 解法简述（基于题目代码）

信号量说明（Semaphores）

我们使用以下几个信号量和变量：

名称	类型	含义
mutex	信号量（初始为 1）	控制隧道资源的互斥访问
SA	信号量（初始为 1）	控制方向 A 的人数更新互斥
SB	信号量（初始为 1）	控制方向 B 的人数更新互斥
countA	整数	正在通行或等待通行的 A 方向行人数
countB	整数	正在通行或等待通行的 B 方向行人数

---

✅ A方向行人代码流程

Down(SA);               // 上锁，准备修改 countA
countA = countA + 1;
if (countA == 1)
    Down(mutex);        // 第一个 A 方向的行人锁住隧道
Up(SA);                 // 释放 SA，允许其他 A 行人更新 countA

// === 通行隧道 ===

Down(SA);
countA = countA - 1;
if (countA == 0)
    Up(mutex);          // 最后一个 A 行人走完后释放隧道资源
Up(SA);

🚶‍♂️解释（中英文）

• 英文：The first A-direction person locks the tunnel (by Down(mutex)). Only when the last A person leaves (countA == 0), the tunnel is unlocked (Up(mutex)).
• 中文：第一个 A 行人上锁隧道（Down(mutex)），最后一个 A 行人离开时才释放锁（Up(mutex)），从而实现 连续通行。

---

✅ B方向行人代码流程

Down(SB);              
countB = countB + 1;
if (countB == 1)
    Down(mutex);        // 第一个 B 方向的行人锁住隧道
Up(SB);

// === 通行隧道 ===

Down(SB);
countB = countB - 1;
if (countB == 0)
    Up(mutex);          // 最后一个 B 行人走完后释放隧道资源
Up(SB);

🚶‍♀️解释（中英文）

• 英文：Just like A-direction, B-direction people will use mutex to ensure mutual exclusion.
• 中文：与 A 方向逻辑相同，B 方向的人也会使用 mutex 信号量来保证 独占访问隧道。

---

✅ 实现目的（英文 + 中文总结）

English：

• This semaphore solution ensures that:
  1. Only one direction's passengers pass at a time.
  2. Once started, passengers of one direction pass continuously.
  3. Only when that direction finishes, the opposite can enter.

中文：

• 此方案保证：
  1. 同一时刻隧道只允许一个方向通行；
  2. 某方向一旦开始通行，会 连续通过；
  3. 当该方向的行人全部走完后，另一方向才可能通行。

---

✅ 调度题

English version:

In a batch system, the arrival and burst time of four jobs are listed below (unit: hours in decimal). Please calculate their:

1. Start time and Finish time under FCFS and SJF scheduling.
2. Average Turnaround Time (TAT) under each algorithm.

中文版本：

在一个批处理系统中，有 4 个作业，它们的提交时间（Arrival Time）和运行时间（Burst Time）如下表（单位：小时，带小数）。 请计算：

1. 使用 FCFS（先来先服务）和 SJF（最短作业优先）调度算法时，每个作业的开始时间、完成时间和周转时间。
2. 计算两种算法下的平均周转时间（Average Turnaround Time）。

---

✅ 【原始数据】

作业编号	Arrival Time（提交时间）	Burst Time（执行时间）
Job 1	10.00	2.00
Job 2	10.20	1.00
Job 3	10.40	0.50
Job 4	10.50	0.30

---

✅ 【调度算法分析】

一、FCFS（First Come First Serve） 先来先服务

按 到达时间排序：

Job1（10.00） → Job2（10.20）→ Job3（10.40）→ Job4（10.50）

计算步骤如下：

Job	Arrival	Burst	Start Time	Finish Time	Turnaround Time (完成时间 - 提交时间)
1	10.00	2.00	10.00	12.00	2.00
2	10.20	1.00	12.00	13.00	2.80 (13.00 - 10.20)
3	10.40	0.50	13.00	13.50	3.10 (13.50 - 10.40)
4	10.50	0.30	13.50	13.80	3.30 (13.80 - 10.50)

平均周转时间：

(2.00+2.80+3.10+3.30)/4=2.80 hours(2.00 + 2.80 + 3.10 + 3.30) / 4 =

---

二、SJF（Shortest Job First）最短作业优先（非抢占）

思路：

• 每次选择 当前已到达的作业中执行时间（Burst）最短的。
• 初始时间为 10.00，从 Job1 开始，后续选择最短作业。

调度顺序如下：

Job1（10.00，2.00） → Job4（10.50，0.30） → Job3（0.50） → Job2（1.00）

（Job1执行完后，时间已到12.00，所有作业都已到达，此时按 burst 排序：Job4→Job3→Job2）

Job	Arrival	Burst	Start Time	Finish Time	Turnaround Time
1	10.00	2.00	10.00	12.00	2.00
4	10.50	0.30	12.00	12.30	1.80
3	10.40	0.50	12.30	12.80	2.40
2	10.20	1.00	12.80	13.80	3.60

平均周转时间：

(2.00+1.80+2.40+3.60)/4=2.45 hours(2.00 + 1.80 + 2.40 + 3.60) / 4 =

---

✅ 【术语解释 | Terminology Explanation】

英文术语	中文术语	含义
Arrival Time	到达时间	作业提交到系统的时间
Burst Time	执行时间	作业运行所需时间
Start Time	开始时间	作业开始执行的时刻
Finish Time	完成时间	作业执行完毕的时刻
Turnaround Time (TAT)	周转时间	完成时间 - 到达时间
FCFS	先来先服务	按到达顺序
SJF	最短作业优先	选择执行时间最短的作业（非抢占）

---

✅ 【结论 | Conclusion】

• FCFS平均周转时间：2.80 小时
• SJF平均周转时间：2.45 小时（更优）

👉 SJF 能提高系统效率，但可能导致“长作业饥饿”。

---