操作系统期末考试样卷

选择题

1. ( D ) The operating system is not responsible for the following activities in connection with process management?

选项 Options:

  • A. Suspending and resuming processes（挂起和恢复进程）
  • B. Providing mechanism for process synchronization（提供进程同步机制）
  • C. Handling deadlock（处理死锁）
  • D. Keeping track of free memory（跟踪空闲内存）

✔️ 正确答案：D

解释 Explanation:

  • The task of keeping track of free memory is part of memory management, not process management.
  • 操作系统中，“跟踪空闲内存”是内存管理（memory management）*的职责，而不是*进程管理（process management）。

📘 操作系统中的进程管理 (Process Management) vs 内存管理 (Memory Management)

✅ 一、进程管理（Process Management）负责的主要任务：

  1. 创建与终止进程（Process Creation and Termination）
    • 系统负责创建新进程，并在任务完成后终止它。
  2. 进程调度（Process Scheduling）
    • 决定哪个进程可以使用 CPU，比如用调度算法（FCFS, RR, SJF 等）。
  3. 进程状态维护（State Maintenance）
    • 跟踪进程的状态：就绪（ready）、运行（running）、等待（waiting）等。
  4. 进程同步（Process Synchronization）
    • 进程之间协调访问共享资源，避免冲突（如使用信号量、互斥锁）。
  5. 进程通信（Process Communication）
    • 提供进程间通信机制，如管道、消息队列、共享内存等。
  6. 死锁处理（Deadlock Handling）
    • 检测、预防、避免或解除死锁。
  7. 进程挂起与恢复（Suspend/Resume）
    • 系统可以根据资源状态或策略暂停并恢复进程。

✅ 二、内存管理（Memory Management）负责的主要任务：

  1. 内存分配与回收（Allocation and Deallocation）
    • 给进程分配内存并在进程终止后释放。
  2. 跟踪空闲内存（Tracking Free Memory）
    • 操作系统需要记录哪些内存空闲，哪些已分配。
  3. 地址转换（Address Translation）
    • 将虚拟地址转换为物理地址（如使用页表、段表）。
  4. 内存保护与共享（Protection and Sharing）
    • 防止一个进程访问另一个进程的内存，并支持合法共享。
  5. 内存置换（Page Replacement）
    • 当内存不足时选择替换哪一页（使用 LRU、FIFO、NRU 等算法）。

🚫 为什么 D 选项是正确答案？

D. Keeping track of free memory（跟踪空闲内存）

  • ✅ 这是内存管理（Memory Management）的一项核心功能。
  • ❌ 而题目问的是“与进程管理相关中操作系统不负责的内容”，因此 D 正确。

📌 小结口诀（帮记忆）：

“进程调度和死锁，挂起恢复别忘掉；内存管理看分配，跟踪地址最重要。”

2. ( C ) Which of the following process schedule algorithm can lead to starvation?

选项 Options:

  • A. FCFS（先来先服务）
  • B. Round Robin（时间片轮转）
  • C. SJF（最短作业优先）
  • D. Guaranteed Scheduling（保证调度）

✔️ 正确答案：C

解释 Explanation:

  • SJF (Shortest Job First) may cause starvation for longer processes because shorter ones can keep arriving and being scheduled first.
  • 最短作业优先可能导致长作业长期等待，如果持续有短作业到来，长作业可能永远得不到执行机会——这就是饥饿（starvation）。

📘 进程调度算法与饥饿问题（Scheduling & Starvation）

✅ 一、什么是进程调度？What is Process Scheduling?

进程调度是操作系统决定哪个进程先使用 CPU 的策略，它的目标是高效、公平、响应快等。

⚠️ 什么是饥饿（Starvation）？

  • 定义（Definition）：当一个进程长时间无法获得 CPU 资源执行时，我们称该进程发生了饥饿（也叫饿死）。
  • 原因（Cause）：调度算法长期优先安排其他进程，导致低优先级或长作业被反复延后。

✅ 二、常见调度算法对比

算法 中文名 是否可能饥饿 特点
FCFS 先来先服务 ❌ 不会 按照进程到达顺序调度，简单公平，但可能导致长作业堵塞
Round Robin 时间片轮转 ❌ 不会 每个进程轮流获得时间片，适合分时系统，响应好，避免饥饿
SJF 最短作业优先 ✅ 可能饥饿 优先执行执行时间短的进程，长作业可能一直得不到执行
Guaranteed Scheduling 保证调度 ❌ 不会 尽量让每个进程获得公平的 CPU 时间比例

✔️ 正确答案：C. SJF（最短作业优先）

解释 Explanation:

  • 在 SJF 中，长作业总是被较短的新作业插队，可能永远得不到执行，导致饥饿。
  • 英文：SJF favors short jobs, and if short jobs keep arriving, long jobs may never run.

🧠 小结口诀：

“最短作业快，长作业悲哀；时间片轮转，人人有份。”

3. ( B ) _______ register contains the size of a process.

选项 Options:

  • A. Base（基址寄存器）
  • B. Limit（限长寄存器）
  • C. Index（索引寄存器）
  • D. Stack pointer（栈指针）

✔️ 正确答案：B

解释 Explanation:

  • The limit register holds the size (or boundary) of the process’s memory.
  • 限长寄存器（Limit register）*用于存储进程可用的*最大内存大小，确保进程不会访问越界内存。

📘 寄存器与进程地址空间（Registers & Process Address Space）

✅ 一、操作系统如何保护进程内存空间？

操作系统使用基址寄存器（Base Register）和限长寄存器（Limit Register）来确保进程只能访问属于自己的内存区域，防止越界访问。

✅ 二、各个选项说明

寄存器 中文名称 功能 是否与“进程大小”有关
A. Base 基址寄存器 指向进程内存空间的起始地址 ❌ 与大小无关，只表示起点
B. Limit 限长寄存器 表示进程能访问的最大范围（即大小） ✅ 表示进程的大小
C. Index 索引寄存器 用于数组、循环等场景进行偏移运算 ❌ 与进程大小无关
D. Stack Pointer 栈指针 指向栈的顶部，用于函数调用、局部变量 ❌ 与进程整体大小无关

✔️ 正确答案：B. Limit（限长寄存器）

解释 Explanation:

  • Limit Register 保存了一个进程可以访问的最大字节数，表示它的内存大小。
  • 操作系统在执行内存访问时会检查： 逻辑地址 < limit 是否成立，以防止越界访问。
  • 英文：The limit register holds the size of the process and is used for memory protection.

🔒 示例：内存保护机制

假设某进程：

  • Base = 1000（开始地址）
  • Limit = 400（进程最多使用 400 字节）

那么该进程最多可以访问地址范围：1000 ~ 1399。

如果访问逻辑地址 450（实际地址 1450）：

  • 系统检测 450 > 400 → 拒绝访问（越界）

🧠 小结口诀：

“基址起点定方向，限长定义有多长。”

4. ( B ) Deadlock can arise if four conditions hold simultaneously. Which of the following is not one of these four conditions?

选项 Options:

  • A. mutual exclusion（互斥）
  • B. busy waiting（忙等）
  • C. hold and wait（保持并等待）
  • D. no preemption（不可抢占）
  • E. circular wait（循环等待）

✔️ 正确答案：B

解释 Explanation:

  • Busy waiting is not one of the four necessary conditions for deadlock.
  • 死锁的四个必要条件是：互斥、保持并等待、不可抢占、循环等待，而忙等（busy waiting）只是一种等待实现方式，不是死锁发生的根本条件。

📘 死锁的四个必要条件（Deadlock: The Four Necessary Conditions）

死锁发生的必要前提是：互斥（Mutual Exclusion）、保持并等待（Hold and Wait）、不可抢占（No Preemption）、循环等待（Circular Wait）。这四个条件缺一不可，是从原理上定义死锁的核心。

✅ 1. 互斥（Mutual Exclusion）

  • 定义：至少存在一个资源，它在某一时刻只能由一个进程占有。
  • 本质原理：资源无法共享，会造成其他进程只能等待。
  • ✅ 举例：打印机一次只能由一个进程使用。

✅ 2. 保持并等待（Hold and Wait）

  • 定义：进程已经持有至少一个资源，同时还在等待其他资源。
  • 本质原理：系统中存在“边占边等”的状态，容易形成“链式阻塞”。
  • ✅ 举例：进程 A 拿着打印机，等待扫描仪；进程 B 拿着扫描仪，等待打印机。

✅ 3. 不可抢占（No Preemption）

  • 定义：资源不能被强行剥夺，只能被进程主动释放。
  • 本质原理：系统无法打破僵局，不能强制把资源还给系统。
  • ✅ 举例：不能强行让一个进程释放它当前正在写入的文件。

✅ 4. 循环等待（Circular Wait）

  • 定义：存在一组进程 {P1, P2, ..., Pn}，其中 P1 等待 P2 占有的资源，P2 等待 P3，以此类推，Pn 又等待 P1 的资源，形成一个闭环。
  • 本质原理：资源之间形成闭环依赖结构，无法解开。
  • ✅ 举例：A 等 B，B 等 C，C 等 A，陷入循环。

❌ Busy Waiting ≠ 死锁必要条件

  • 忙等（Busy Waiting）：指进程在等待资源时不断占用 CPU 轮询，而不是进入阻塞状态。
  • 重点：
    • 它是一种等待的实现方式，并非导致死锁的逻辑必要条件。
    • 忙等可能浪费 CPU，但不一定造成死锁。
  • ✅ 可以用忙等实现互斥（如自旋锁），但不是死锁的本质条件。

🧠 总结记忆口诀：

“互斥占资源，持有等别家，不能强行拿，绕圈没得爬。”

5. ( D ) Let graph represent “resource allocation graph”. Which statement is wrong?

选项 Options:

  • A. If graph contains cycle, and there is only one instance per resource type, then there is deadlock.（若图中有环，且每种资源只有一个实例，则必有死锁）
  • B. If graph contains cycle, and there can be several instances per resource type, then there may or may not have deadlock（若图中有环，资源类型有多个实例，可能有死锁也可能没有）
  • C. If graph contains no cycle, then no deadlock（若图中无环，则无死锁）
  • D. If no deadlock, then graph contains no cycle（若无死锁，则图中无环）

✔️ 正确答案：D

解释 Explanation:

  • This is not always true. If the resource allocation graph allows multiple instances per resource type, a cycle may exist without a deadlock.
  • 若每种资源有多个实例，即使存在环，系统也可能没有死锁。所以，“无死锁就一定无环”是错误的。

📘 死锁与资源分配图（RAG）原理笔记

🔶 什么是资源分配图（RAG）？

  • 资源分配图是一种有向图，用于描述进程与资源之间的分配和请求关系。
  • 图中包含两类节点：
    • 进程节点：表示系统中的进程（用圆圈表示）
    • 资源节点：表示系统中的资源（用方框表示）
  • 有两类边：
    • 请求边：从进程指向资源（表示进程请求该资源）
    • 分配边：从资源指向进程（表示该资源分配给了该进程）

🔷 四种情况与图中“环”的关系

✅ A. 如果图中有环，且每种资源只有一个实例 → 一定死锁

  • ✔️ 正确
  • 原理：当每种资源只有一个实例时，形成环意味着每个进程都在等待其他进程释放资源，且系统无法打破这个等待链。
  • 图示：一个闭环意味着没有“断口”可以推进。

✅ B. 如果图中有环，且每种资源可以有多个实例 → 可能死锁，也可能没有

  • ✔️ 正确
  • 原理：多个实例意味着可能还有“备用资源”可供调度，环并不一定导致完全卡死。

✅ C. 图中没有环 → 一定无死锁

  • ✔️ 正确
  • 原理：无环结构说明不存在进程之间的循环等待链，因此不可能形成死锁。

❌ D. 如果无死锁，则图中一定无环

  • ❌ 错误（⚠️ 关键考点）
  • 反例原理：在多个资源实例的情况下，系统可以出现“有环但无死锁”的情形。
    • 比如环中某些资源还有可用实例，使得某个进程最终可获得资源，释放后打破环。
  • 所以，有环 ≠ 死锁（当资源可有多个实例时）

🧠 关键总结：死锁与环的逻辑关系

情况 是否一定有死锁 是否一定有环
图中无环 ❌ 无死锁 ✔️ 无环
图中有环 + 每资源1实例 ✔️ 一定死锁 ✔️ 有环
图中有环 + 多个实例 ❓ 可能死锁/可能无死锁 ✔️ 有环
系统无死锁 ❌ 不代表一定无环 ❓ 可能有环/无环

6. ( B ) The ability of a computer system to switch execution among several jobs that are in memory at the same time is called ______.

选项 Options:

  • A. time slicing（时间片轮转）
  • B. multiprogramming（多道程序设计）
  • C. multiprocessing（多处理器）
  • D. multitasking（多任务处理）

✔️ 正确答案：B

解释 Explanation:

  • Multiprogramming means several programs are kept in memory at the same time, and the CPU switches between them to keep itself busy.
  • 多道程序设计（Multiprogramming）指多个程序同时驻留在内存中，操作系统根据空闲 CPU 时间进行切换，提高资源利用率。

7. ( A ) In the readers-writers problem, processes p and q are allowed to simultaneously access the shared resource if and only if _____.

选项 Options:

  • A. p and q are both reading（p 和 q 都在读）
  • B. p and q are both writing（p 和 q 都在写）
  • C. Either p or q or both is reading（p 或 q 或两者都在读）
  • D. Either p or q or both is writing（p 或 q 或两者都在写）

✔️ 正确答案：A

解释 Explanation:

  • In the readers-writers problem, multiple readers can access the shared data at the same time, but writers need exclusive access.
  • 在读者-写者问题中，多个“读者”可以同时读取共享资源，但写者写入时必须是独占访问，所以只有当 p 和 q 都是“读者”时才能并发访问。

8. ( D ) Suppose that a machine has 48-bit virtual address and 32-bit physical address. If pages are 4KB, how many entries are in the page table if it has only a single level?

选项 Options:

  • A. 2²⁷
  • B. 2¹⁶
  • C. 2²⁴
  • D. 2³⁶

✔️ 正确答案：D

解释 Explanation:

  • Page size = 4KB = 2¹² bytes → offset = 12 bits
  • Virtual address = 48 bits → virtual page number = 48 - 12 = 36 bits
  • So page table has 2³⁶ entries.
  • 页大小为 4KB（2¹²），虚拟地址为 48 位 → 页号为 48 - 12 = 36 位，所以单级页表需要 2³⁶ 个表项。

📘 知识点笔记：页表大小与虚拟地址结构

🧠 背景知识：分页机制（Paging）

  • 分页（Paging）是虚拟内存管理的一种技术，虚拟地址空间被划分为固定大小的页（Page），而物理内存被划分为帧（Frame）。
  • 进程运行时，虚拟页被映射到物理帧，这个映射关系记录在页表（Page Table）中。

🧮 关键计算逻辑（以本题为例）

📌 已知信息：

  • 虚拟地址空间：48 位
  • 物理地址空间：32 位（用于计算帧号，不影响页表大小）
  • 页大小（Page Size）：4KB = 2¹² 字节
  • 页表结构：单级页表（single-level）

📌 步骤一：拆解虚拟地址结构

虚拟地址共 48 位，由两部分组成：

部分 位数 说明
页号 (Page Number) 48 - 12 = 36 位 用于索引页表
页内偏移 (Page Offset) 12 位 表示页内具体地址

📌 步骤二：确定页表大小（表项数量）

  • 页表的每一项对应一个虚拟页

  • 所以页表中一共需要多少个表项 = 虚拟页的数量 =

    236=2³⁶ 个表项2^{36} =

✔️ 正确答案：D. 2³⁶

🎓 拓展：页表项数量的通用公式

若：

  • 虚拟地址长度 = V 位
  • 页大小 = 2^P 字节

则：

页表项数=2V−P = 2^{V - P}

📌 额外知识：多级页表（多用于大地址空间）

  • 当虚拟地址空间太大时（如 64 位），页表项会非常多，占用内存大。
  • 为了节省空间，操作系统会采用多级页表（multi-level page table），把一个大的页表拆成多级索引结构。
  • 本题特指 单级页表，所以直接按页号位数计算。

✅ 总结记忆法则：

页表大小 = 2^(虚拟地址位数 - 页内偏移位数)

9. ( B ) “Computing the track, sector, and head for a disk read” is done in which layers?

选项 Options:

  • A. Interrupt handlers（中断处理器）
  • B. Device drivers（设备驱动）
  • C. Device-independent OS software（设备无关的软件层）
  • D. User-level I/O software（用户级 I/O 软件）

✔️ 正确答案：B

解释 Explanation:

  • Device drivers handle hardware-specific operations like computing track, sector, and head for disk operations.
  • 设备驱动程序（Device drivers）*负责与特定硬件通信，包括对磁盘的*柱面、磁头、扇区定位等底层操作。

10. ( A ) If there are no name collisions in a file system, the easiest method is to use______.

选项 Options:

  • A. single-level directory system（单级目录系统）
  • B. two-level directory system（双级目录系统）
  • C. single-level or two-level directory system（单级或双级目录系统）
  • D. hierarchical directory system（分层目录系统）

✔️ 正确答案：A

解释 Explanation:

  • If no filename conflicts, then a single-level directory is simplest and sufficient.
  • 如果文件名不会冲突，使用单级目录结构最简单，不需要划分用户或层次结构。

11. ( C ) Which page will NRU, LRU and Second Chance replace respectively?

给出页面信息如下：

Page Loaded Last Ref R M
0 126 280 1 0
1 230 265 0 1
2 140 270 0 0
3 110 285 1 1

选项 Options:

  • A. 2, 2, 1
  • B. 2, 3, 1
  • C. 2, 1, 2
  • D. 3, 1, 2

✔️ 正确答案：C

解释 Explanation:

  • NRU (Not Recently Used)：优先选择 R=0 且 M=0 的页面 → 只有 Page 2 属于类别 0（最低优先级），所以选择 Page 2。
  • LRU (Least Recently Used)：选择“最近最久未被访问”的页面 → Page 1 的 Last Ref 是 265，是最旧的。
  • Second Chance：按队列顺序检查 R 位，R=1 的给予第二次机会（清零 R 并跳过），最终会选择 Page 2。

加载顺序是根据 Loaded 时间：

  • Page 3（110） ➝ Page 0（126） ➝ Page 2（140） ➝ Page 1（230）
  • 所以 FIFO 队列顺序是：3 → 0 → 2 → 1

12. ( D ) A computer has six tape drives, with n processes competing for them. Each process may need two drives. For which values of n is the system deadlock free?

选项 Options:

  • A. 8
  • B. 7
  • C. 6
  • D. 5

✔️ 正确答案：D

解释 Explanation:

🎯 原理解析（简洁 + 中文解释 + 英文关键词）

我们来分析这类题目的 核心原理 —— 死锁避免：最大需求 - 1 原则。

🧠 问题背景（Problem Setup）

  • 系统中有 6 个磁带机（tape drives）
  • 有 n 个进程（processes），每个最多需要 2 个设备
  • 问：当 n 是多少时，不会死锁？

🚨 死锁的四个必要条件（Deadlock conditions）

死锁的发生需要以下四个条件同时成立：

  1. 互斥（Mutual exclusion）
  2. 请求与保持（Hold and wait）
  3. 不剥夺（No preemption）
  4. 环路等待（Circular wait）

我们要防止死锁，可以从这些条件中破坏其中之一。

在这个问题中，我们使用的是 死锁避免策略之一：确保系统永远不会进入不安全状态。这通常用 **银行家算法（Banker's Algorithm）**或简化策略来做估计。

✨ 关键思想：最大需求 - 1 原则

如果每个进程最多需要 K 个资源，系统中有 R 个资源，那么只要：

n × (K - 1) < R 系统就一定不会死锁。

这个规则是来自银行家算法的简化形式。

✅ 应用于本题：

  • K = 2（每个进程最多要 2 个磁带机）
  • R = 6（总共 6 个磁带机）
  • 所以系统死锁安全的最大进程数 n 应满足：

\[ n \times (2 - 1) < 6 \\ n < 6 \\ \Rightarrow n \leq 5 \]

💡 为什么这个原理成立？

因为每个进程最多要 2 个，如果每个进程最多先拿到 1 个磁带机就停住，那最多同时有 n 个磁带机被占用。

如果我们保证总共还有至少 1 个磁带机剩下，就一定能让某个进程拿到它所需的第二个磁带机，完成工作后释放资源，其他进程也就可以继续下去，不会死锁。

所以只要：

总资源数 > 进程数 × (最大需求 - 1)，系统就一定不会进入死锁。

🧾 各选项分析

选项 n 是否满足 n × (2 - 1) < 6 是否死锁？
A 8 8 × 1 = 8 ≥ 6 ❌ 可能死锁
B 7 7 × 1 = 7 ≥ 6 ❌ 可能死锁
C 6 6 × 1 = 6 ≥ 6 ❌ 可能死锁
D 5 5 × 1 = 5 < 6 ✅ 安全，无死锁

✅ 总结口诀

“每进程少要一个，总数要大于。”

只要你记住这个公式：

\[ n \times (K - 1) < R \]

就能快速判断有没有死锁风险！

13. ( B ) Show the bitmap after writing file B using five blocks.

初始 bitmap（格式化后）：

1
1000 0000 0000 （第0块被根目录使用）

写入文件 A 用了 6 块，从第1到第6块，bitmap 更新为：

1
1111 1110 0000 0000

写入文件 B 用 5 块，从第7块开始：第7~11 → bitmap 更新为：

1
1111 1111 1111 0000

✔️ 正确答案：B

解释 Explanation:

  • 系统总是从编号最小的空闲块开始分配，所以文件 B 使用了块 7～11。

14. ( B ) In which of the four I/O software layers is “Writing commands to the device registers” done?

选项 Options:

  • A. Interrupt handlers（中断处理程序）
  • B. Device drivers（设备驱动）
  • C. Device-independent OS software（设备无关软件）
  • D. User（用户层）

✔️ 正确答案：B

解释 Explanation:

  • 设备驱动（Device drivers）直接与硬件通信，它负责把命令写入设备寄存器（register）。
  • 英文解释：Device drivers interact directly with hardware and are responsible for writing commands to device registers.

15. ( B ) How much cylinder skew is needed for a 7200-rpm disk with 1ms track-to-track seek time?

已知：

  • 转速：7200 RPM = 120 转/秒 → 每转 = 8.33ms
  • 1ms seek time → 要跳过的扇区数 = 200/8.33 ≈ 24

✔️ 正确答案：B

解释 Explanation:

  • Cylinder skew 是为了补偿相邻柱面间切换的时间而跳过的扇区数，计算结果约为 24。
  • 英文解释：To allow for 1ms seek time without missing the next sector, about 24 sectors must be skipped.

🧾 Question（问题）

1. (5 pts) List at least three key differences between user-level threads and kernel-level threads. 列出用户级线程（User-Level Threads）和内核级线程（Kernel-Level Threads）之间至少三个主要区别。

✅ Answer（答案）

Feature（特征） User-Level Thread（用户级线程） Kernel-Level Thread（内核级线程）
1. 管理者 (Management) Managed by application（由应用程序管理） Managed by kernel（由操作系统内核管理）
2. 系统感知 (Kernel Awareness) Kernel not aware of thread（内核无感知） Kernel aware（内核知道并调度线程）
3. 上下文切换 (Context Switch) Very fast（切换开销小） Slower（切换开销大）
4. 数量限制 (Thread Limit) Can create many（数量几乎不受限） Limited by kernel（受内核资源限制）
5. 易用性 (Ease of use) Must be used carefully（需小心管理，如阻塞） Easier to program（使用简单，阻塞处理自动）

💡 Explanation（解释）

✅ 1. 管理者 / Management

  • 用户级线程是由程序本身的线程库（如 pthread）管理的，操作系统内核并不知道它们的存在。
  • 内核级线程由操作系统内核直接管理和调度。

✅ 2. 内核是否感知 / Kernel Awareness

  • 用户线程对内核是“不可见”的，内核调度的是整个进程，而不是线程。
  • 内核线程被操作系统完全掌控，可以独立调度。

✅ 3. 上下文切换 / Context Switching

  • 用户线程之间的切换不涉及内核，因此非常快。
  • 内核线程切换需要进入内核态，上下文切换代价高。

✅ 4. 数量限制 / Thread Limit

  • 用户线程几乎可以无限制地创建，因为只是用户空间的数据结构。
  • 内核线程会占用内核资源（如 PCB、栈），数量受限。

✅ 5. 使用便利性 / Simplicity

  • 用户线程必须自己管理阻塞问题（如一个线程 I/O 阻塞会阻塞整个进程）。
  • 内核线程可以自动处理阻塞，更加健壮，使用更方便。

📌 小结总结

用户级线程：快但不安全，轻但复杂。 内核级线程：稳但重，慢但省心。

🧾 Question（问题）

2. (5 pts) In a virtual memory system, does a TLB miss imply a disk operation will follow? Why or why not? 在虚拟内存系统中，TLB 未命中（TLB miss）是否意味着一定会进行磁盘操作？为什么？

✅ Answer（答案）

No. A TLB miss only means the translation for the virtual address is not found in the TLB, so the page table must be accessed (usually from main memory). A disk operation is only required if the page is also not in memory, i.e., a page fault occurs.

不一定。 TLB 未命中仅表示虚拟地址的映射不在 TLB（快表）中，需要从内存中访问页表获取对应物理地址。只有当页表也找不到该页（即发生缺页异常 page fault）时，才需要从磁盘加载页面，触发磁盘操作。

💡 Explanation（解释）

✅ 什么是 TLB（Translation Lookaside Buffer）？

TLB 是一个快速缓存，存储最近使用的虚拟地址到物理地址的映射，用于加速地址转换。

  • 如果 TLB 命中（hit）：地址直接转换，非常快。
  • 如果 TLB 未命中（miss）：必须去主内存中查找页表（page table）获取映射关系。

✅ TLB miss ≠ Page Fault

情况 是否需要磁盘操作？
TLB miss 但页在内存 ❌ 不需要磁盘，只查页表
TLB miss 且页不在内存 ✅ 需要磁盘加载该页

所以，TLB miss 通常只意味着稍慢的内存查找，不等同于 page fault。

✅ Page fault 才会触发磁盘操作

当访问的页在主内存中也找不到（页表项无效），才说明该页尚未载入内存，需要操作系统从磁盘加载它——这才是磁盘操作的触发点。

📝 总结 Summary

TLB miss 只是“查不到缓存”，要查内存页表；只有 Page fault 才是真的“内存也没有”，才去磁盘找。

  • ❌ TLB miss ≠ Disk access
  • ✅ Page fault → Disk access

🧾 Question（问题）

3. (5 pts) How many disk operations are needed to open the file /usr/student/lab/test.doc? Why? 打开文件 /usr/student/lab/test.doc 需要多少次磁盘操作？为什么？ （假设路径中所有内容最初都不在内存中；每个目录占用一个磁盘块）

✅ Answer（答案）

需要 9 次磁盘读操作。

步骤 操作描述 中文解释
1 Read i-node for / 读取根目录 / 的 i-node
2 Read directory block for / 读取 / 目录本身的数据块
3 Read i-node for /usr 读取 /usr 的 i-node
4 Read directory block for /usr 读取 /usr 的目录数据块
5 Read i-node for /usr/student 读取 /usr/student 的 i-node
6 Read directory block for /usr/student 读取 /usr/student 的目录数据块
7 Read i-node for /usr/student/lab 读取 /usr/student/lab 的 i-node
8 Read directory block for /usr/student/lab 读取该目录的数据块
9 Read i-node for /usr/student/lab/test.doc 读取最终文件 test.doc 的 i-node

💡 Explanation（解释）

✅ 背景：UNIX 文件系统结构

在 UNIX/Linux 文件系统中：

  • i-node（索引节点） 保存文件/目录的元数据（如大小、权限、数据块位置）。
  • 目录文件 是一个特殊的文件，它的内容是映射：文件名 → i-node 编号。
  • 打开一个文件要先解析它的路径，从根目录 / 开始逐层查找。

✅ 为什么是 9 次磁盘访问？

假设文件路径 /usr/student/lab/test.doc，每一层的处理都需要：

  1. 读该目录的 i-node
  2. 根据 i-node 找到该目录文件的数据块，再去读 目录内容

但最后的 test.doc 是文件，只需要读取它的 i-node，不需要读取它的数据内容（因为只是打开文件，还没读内容）。

所以总共：

  • 每个中间目录（3 层）都要：2 次访问（i-node + 目录块）
  • 加上根目录 /：2 次
  • 加上 test.doc：1 次（i-node）

\[ 2（/） + 2（/usr） + 2（/student） + 2（/lab） + 1（test.doc） = 9 次磁盘访问 \]

📝 总结 Summary

路径上每个目录要访问 i-node 和目录块，最终文件只需要 i-node，总共 9 次磁盘读操作。

  • ❗ 文件系统分层解析路径时，每层都可能引发磁盘操作
  • ✅ 这个题考的是对 UNIX 文件系统结构的理解（i-node + 目录）

🧾 Question（问题）

1. (10 pts) A tunnel, which is very narrow, allows only one passenger to pass once. Please use semaphores to implement the following situations:

一个非常狭窄的隧道，每次只能允许一个行人通过。请使用信号量（semaphores）来实现以下两种情况：

(1) (4 pts)

Passengers go through the tunnel one by one alternately from two directions. 来自两个方向的行人需要交替地通过隧道。

(2) (6 pts)

The passengers at one direction must pass the tunnel continuously. Another direction’s visitors can start to go through the tunnel only when no passengers want to pass from the opposite direction. 一个方向的行人必须连续通过，只有当这个方向没有人再想通过时，另一个方向的行人才能开始进入。

✅ Answer（答案）

✅ (1) 两方向交替通行 / Alternating Passage

设定：

  • 用两个信号量 AB 和 BA 控制通行顺序。
  • 初始值都为 1，互相唤醒对方，实现交替。
1
2
3
4
5
6
7
8
9
10
11
12
13
// A方向的行人：
P(AB);         // 等待 A 方向的通行许可
P(mutex);      // 进入隧道（互斥）
通过隧道；
V(mutex);      // 离开隧道
V(BA);         // 允许 B 方向的行人进入

// B方向的行人：
P(BA);         // 等待 B 方向的通行许可
P(mutex);      // 进入隧道
通过隧道；
V(mutex);      // 离开隧道
V(AB);         // 允许 A 方向的行人进入

💬 中文解释：

  • 每次一个方向的人通过隧道后，就唤醒另一个方向的行人。
  • mutex 保证每次只有一个人进入隧道。
  • AB 和 BA 控制“谁先来”，实现“你来我往”的交替效果。

✅ (2) 一方向连续通行 / One Side Continuous Passage

设定：

  • 用 countA 和 countB 记录当前在隧道中各方向行人的数量；
  • SA 和 SB 是对应方向的互斥信号量，保护各自计数器；
  • mutex 控制两个方向在隧道的互斥访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// A方向的行人
P(SA);
    if (countA == 0) P(mutex); // 如果是第一个来的人，就锁住隧道
    countA++;
V(SA);

通过隧道；

P(SA);
    countA--;
    if (countA == 0) V(mutex); // 最后一个人离开，释放隧道
V(SA);

// B方向的行人
P(SB);
    if (countB == 0) P(mutex);
    countB++;
V(SB);

通过隧道；

P(SB);
    countB--;
    if (countB == 0) V(mutex);
V(SB);

💬 中文解释：

  • 连续通行的关键：只要一个方向还有人继续进入，另一个方向就必须等。
  • 第一次进入该方向的人会申请 mutex，锁住隧道；
  • 最后一个离开的时候才释放 mutex，另一个方向的人才能进入。
  • 这就实现了“一方向连续通行，另一方向等待”的效果。

📝 总结 Summary

场景 核心同步逻辑 信号量含义
交替通行 通行后唤醒对方 AB/BA 控制轮流
一方连续 第一人上锁，最后一人解锁 count 控制人数，mutex 控制隧道访问

🧾 Question（问题）

1. (8 pts) Five batch jobs A through E arrive at a computer center at almost the same time. They have estimated running times and priorities as follows:

五个批处理作业 A~E 几乎同时到达计算机中心，它们的运行时间和优先级如下（5 为最高优先级）：

Job Arrival Time Execution Time Priority
A 0 10 3
B 0 6 5 (最高)
C 0 2 2
D 0 4 1
E 0 8 4

请对下面几种调度算法，计算 平均周转时间（Mean Turnaround Time）。

Turnaround Time（周转时间） = 完成时间 - 到达时间（此题到达时间都是 0）

✅ Answer（答案）

(1) Round Robin (RR)（轮转调度法）

思想： 每个作业轮流执行，时间片分配平均；假设时间片为 1，忽略切换开销。

过程模拟（简化描述）：

  • 前 10 分钟：5 个作业都运行了 2 分钟（A,B,E,D,C 各执行 2 次）
  • C 需要 2 分钟，10 分钟时完成
  • 然后每轮执行 4 个剩下作业（A,B,E,D），再花 8 分钟，D 18 分钟完成
  • 剩下 3 个作业轮转到 B 24 分钟完成，E 28 分钟完成，A 30 分钟完成
Job Finish Time Turnaround Time
C 10 10
D 18 18
B 24 24
E 28 28
A 30 30
平均 — 22 分钟

Mean Turnaround Time: 22 min

(2) Priority Scheduling（优先级调度）

思想： 根据优先级从高到低运行（数值大的优先级高）。

运行顺序：B（5） → E（4） → A（3） → C（2） → D（1）

Job Start Finish Turnaround
B 0 6 6
E 6 14 14
A 14 24 24
C 24 26 26
D 26 30 30
平均 — — 20 分钟

Mean Turnaround Time: 20 min

(3) First-Come, First-Served (FCFS)（先来先服务）

运行顺序：A (10) → B (6) → C (2) → D (4) → E (8)

Job Start Finish Turnaround
A 0 10 10
B 10 16 16
C 16 18 18
D 18 22 22
E 22 30 30
平均 — — 19.2 分钟

Mean Turnaround Time: 19.2 min

(4) Shortest Job First (SJF)（短作业优先）

运行顺序：C (2) → D (4) → B (6) → E (8) → A (10)

Job Start Finish Turnaround
C 0 2 2
D 2 6 6
B 6 12 12
E 12 20 20
A 20 30 30
平均 — — 14 分钟

Mean Turnaround Time: 14 min

📊 总结（Summary）

调度算法 平均周转时间 (min) 中文说明
Round Robin 22 各进程轮流执行
Priority Scheduling 20 高优先级先执行
FCFS 19.2 到达顺序执行（本题中是A→B→C→D→E）
SJF 14 短作业优先执行，效率最高

🧾 Question（问题）

1. (10pts) A system has five processes (P1 ~ P5) and four allocatable resources (A, B, C, D). The current Allocation (已分配资源)、Need（尚需资源）和系统当前 Available（可用资源）如下表所示：

系统有 5 个进程和 4 类可分配资源，下表显示了它们的当前资源分配情况、还需要的资源数量和系统当前可用资源数量。

Process Allocation A B C D Need A B C D Available A B C D
P1 0 0 1 2 0 0 1 2
P2 1 0 0 0 1 7 5 0
P3 1 3 5 4 2 3 5 6
P4 0 6 3 2 0 6 5 2
P5 0 0 1 4 4 3 1 4 Available: 1 6 2 2

请回答以下两个问题：

(1) Is this state safe? Why?

当前系统是否处于安全状态？请说明理由。

(2) Can P3's request (1,2,2,2) be granted? Why?

如果进程 P3 请求额外的资源 (1,2,2,2)，系统是否能满足？请说明理由。

  1. 该状态是安全的。

s (1,6,2,2)>(0,0,1,2)，先满足P1的请求，执行完毕后回收P1资源(0,0,3,2)，则可用资源变为(1,6,5,4)；

s (1,6,5,4)>(0,6,5,2)，可满足P4的请求，执行完毕后回收P4资源(0,3,3,2)，则可用资源变为(1,9,8,6)；

s (1,9,8,6)>(0,6,5,6)，可满足P5的请求，执行完毕后回收P5资源(0,0,1,4)，则可用资源变为(1,9,9,10)；

s (1,9,9,10)>(1,7,5,0)，可满足P2的请求，执行完毕后回收其资源(1,0,0,0)，则可用资源变为(2,9,9,10)；

s (2,9,9,10)>(2,3,5,6)，可满足P3的请求，执行完毕后回收其资源(1,3,5,4)，则可用资源变为(3,12,14,14)，即为资源总量。

存在一安全序列：{P1,P4,P5,P2,P3}，故该状态是安全的。

（2）

Process Allocation A B C D Need A B C D Available A B C D
P1 0 0 1 2 0 0 1 2
P2 1 0 0 0 1 7 5 0
P3 2 5 7 6 1 1 3 4
P4 0 6 3 2 0 6 5 2
P5 0 0 1 4 4 3 1 4 Available: 0 4 2 2

因为P3会预知一部分的资源，会导致可用资源(0,4,0,0)不能满足任何一个进程的Need请求，故此状态为不安全状态，故不能将P3请求的资源分配给它！

🧾 题目（Question）：

2. (8 pts) A UNIX file system has 1-KB blocks and 32-bit disk addresses. What is the maximum file size if i-nodes contain 10 direct entries, and one single, double, and triple indirect entry each?

中文翻译： 一个 UNIX 文件系统使用 1KB 的磁盘块（block） 和 32 位的磁盘地址（disk address）。 如果每个 i-node 包含 10 个直接指针（direct entries），以及 一个单重间接指针（single indirect）、双重间接指针（double indirect）、三重间接指针（triple indirect），请问这个文件系统中一个文件的最大文件大小是多少？

✅ 答案（Answer）：

Maximum file size = 16,843,018 blocks = 16.06 GB

中文翻译： 最大文件大小为 16,843,018 个块，即大约 16.06 GB

🔍 详细解释（Explanation with 中英文对照）：

1. 每个磁盘块大小为 1 KB

Each disk block size = 1 KB

2. 指针大小 = 32 bits = 4 Bytes

所以每个间接块中可以存储的指针数量为：

\[ \frac{1024 \text{ Bytes}}{4 \text{ Bytes/pointer}} = 256 \text{ pointers} \]

Each block (1KB) can hold

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

3. 指针数量计算（Pointer Count）

  • 直接指针（Direct pointers） = 10 → 可以指向 10 个数据块

  • 单重间接（Single indirect） = 256 个数据块 → 一块间接块中有 256 个指向数据块的指针

  • 双重间接（Double indirect） = 256 × 256 = 65,536 → 一块间接块，指向 256 个间接块，每个间接块指向 256 个数据块

  • 三重间接（Triple indirect） = 256 × 256 × 256 = 16,777,216 → 三重间接指针可以间接访问 1600 多万个数据块

4. 总共能访问的数据块数（Total number of addressable data blocks）：

\[ 10 + 256 + 256^2 + 256^3 = 10 + 256 + 65,536 + 16,777,216 = \boxed{16,843,018 \text{ blocks}} \]

每个块是 1KB，总文件大小为：

\[ 16,843,018 \text{ KB} ≈ 16.06 \text{ GB} \]

✅ 结论（Conclusion）：

英文： The maximum file size supported by this UNIX file system is 16,843,018 KB, or approximately 16.06 GB.

中文： 该 UNIX 文件系统支持的最大文件大小为 16,843,018 KB，大约是 16.06 GB。

🧾 题目（Question）：

2. (9pts) Suppose that a disk drive has 300 cylinders, numbered 0 to 299. The drive is currently serving a request at cylinder 143. The queue of pending requests, in FIFO order, is: 86, 147, 291, 18, 95, 151, 12, 175, 30 Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms?

(1) First-Come First-Served (FCFS) (2) Shortest Seek First (SSF) (3) Elevator (SCAN) Algorithm, assume initial direction is toward cylinder 0

中文翻译： 一台磁盘驱动器有 300 个柱面（cylinders），编号为 0 到 299。磁头当前在 143 号柱面上。等待队列中的请求柱面按 FIFO 顺序 为： 86, 147, 291, 18, 95, 151, 12, 175, 30 请问在以下三种调度算法下，磁头需要移动的总距离（单位：柱面数）是多少？

（1）先来先服务 FCFSda （2）最短寻道优先 SSF （3）电梯算法 SCAN（初始方向为朝向 0）

✅ 答案与解释（Answers and Explanations）：

🌐 (1) First-Come First-Served (FCFS) 先来先服务

  • 访问顺序：143 → 86 → 147 → 291 → 18 → 95 → 151 → 12 → 175 → 30
  • 计算每次移动距离（取相邻两个值差的绝对值）：
1
2
3
4
5
6
7
8
9
10
|143 - 86| = 57  
|86 - 147| = 61  
|147 - 291| = 144  
|291 - 18| = 273  
|18 - 95| = 77  
|95 - 151| = 56  
|151 - 12| = 139  
|12 - 175| = 163  
|175 - 30| = 145  
总移动距离 = 57 + 61 + 144 + 273 + 77 + 56 + 139 + 163 + 145 = 🔷1114

✅ 总移动：1114 柱面

🌐 (2) Shortest Seek First (SSF) 最短寻道优先

每次都选择离当前位置最近的请求。初始在 143，接下来总是选最近的柱面：

  • 排序与路径（每一步都找最近）：
1
2
3
4
5
6
7
8
9
10
143 → 147 (4)  
147 → 151 (4)  
151 → 175 (24)  
175 → 95 (80)  
95 → 86 (9)  
86 → 30 (56)  
30 → 18 (12)  
18 → 12 (6)  
12 → 291 (279)  
总移动距离 = 4 + 4 + 24 + 80 + 9 + 56 + 12 + 6 + 279 = 🔷474

✅ 总移动：474 柱面

🌐 (3) Elevator / SCAN Algorithm 电梯算法

初始方向是向下（朝 0），先访问比 143 小的请求，然后再反转方向往上。

  • 所有请求按大小分两部分：
    • 向下访问的请求（≤143）：95, 86, 30, 18, 12
    • 向上访问的请求（>143）：147, 151, 175, 291
  • 向下访问顺序（按降序）：143 → 95 → 86 → 30 → 18 → 12
  • 向上再访问：→ 147 → 151 → 175 → 291
  • 每次移动距离：
1
2
3
4
5
6
7
8
9
10
143 → 95 = 48  
95 → 86 = 9  
86 → 30 = 56  
30 → 18 = 12  
18 → 12 = 6  
12 → 147 = 135  
147 → 151 = 4  
151 → 175 = 24  
175 → 291 = 116  
总移动距离 = 48 + 9 + 56 + 12 + 6 + 135 + 4 + 24 + 116 = 🔷410

✅ 总移动：410 柱面

📌 最终结果汇总（Summary Table）：

调度算法（Algorithm） 总移动柱面数（Total Movement）
FCFS 1114
Shortest Seek First (SSF) 474
Elevator (SCAN) 410

Question / 题目

(1)

A 36-bit processor has 4 active processes running concurrently. The virtual address table is shown below (V=valid bit, PID=process ID, VPN=virtual page number). All addresses are in hexadecimal.

一个 36位处理器 有 4 个进程并发运行。下表显示了部分虚拟地址（V=有效位，PID=进程ID，VPN=虚拟页号），所有地址为十六进制。

V PID VPN
1 9 0x0DF0
1 A 0x3630
1 C 0x1B70
1 C 0x37C1
0 F 0x1F04
1 A 0x3640
1 9 0x1FFF
1 A 0x23A4
1 9 0x3004
1 A 0x0D7C
1 C 0x0DF0
0 B 0x1F04
1 A 0x0DF0
1 9 0x020D
1 A 0x31A2
1 C 0x07C1

(1) IPT Question

Assume an Inverted Page Table (IPT) is used. The system uses a 4MB page size. The physical address 0x363055B is given. What virtual address and which process does this map to?

假设操作系统使用 倒排页表（IPT），每页大小为 4MB（即 2²² 字节）。 现在给出一个物理地址 0x363055B，请问它是哪个 进程的哪个虚拟地址？

(2) Page Table Memory

If the OS switches to using an index-based linear page table, how much memory (in KB) is required for just process A? Assume each Page Table Entry (PTE) includes a valid bit and dirty bit.

如果操作系统改用 基于索引的线性页表，那么单独进程 A 的页表需要多少 KB 的内存？ 每个页表项（PTE）包含 有效位（valid bit） 和 修改位（dirty bit）。

✅ Solution / 解答与解释

img

计算高位->查表->左移->或运算！

img