操作系统2011

选择题

1. (D) The ________ solution to the critical section problem will cause the situation that a process running outside its critical region may block another process.

(D) Strict Alternation

  • 中文翻译： 以下哪种临界区问题的解决方案会导致一个进程即使在临界区外运行，也可能阻塞另一个进程？

  • 选项： A. Peterson 算法 B. 银行家算法（Banker’s Algorithm） C. 测试并设置锁（Test and Set Lock） D. 严格交替法（Strict Alternation）

  • 答案：D. Strict Alternation（严格交替法）

  • 解释： Strict Alternation 是一种早期的同步方案，它强制两个进程交替进入临界区。即使某个进程不需要进入临界区，也会阻碍另一个进程进入。它违背了**空闲让进（progress）**原则，因此容易造成不必要的阻塞。

Peterson 算法、银行家算法、Test-and-Set Lock、严格交替法

✅ A. Peterson 算法

英文名：Peterson's Algorithm 用于：两个进程之间的互斥（Mutual Exclusion）

🧠 核心思想：

Peterson 算法是一个经典的软件实现方法，用于在两个进程之间实现互斥进入临界区，并满足互斥性、进程有空让进（progress）、有界等待等条件。

🛠 实现原理：

用两个共享变量：

  • flag[2]：标志位，表示进程是否想进入临界区
  • turn：表示轮到哪个进程先检查
1
2
3
4
5
6
7
// 假设进程 Pi 的编号为 i，另一个为 j = 1 - i
flag[i] = true;
turn = j;
while (flag[j] && turn == j);  // 等待
// 临界区
...
flag[i] = false;

✅ 特点：

  • 纯软件实现，不依赖硬件指令
  • 满足互斥、有界等待
  • 只能用于两个进程

✅ B. 银行家算法

英文名：Banker’s Algorithm 用于：*系统中资源的*安全分配，防止死锁

🧠 核心思想：

银行家算法由 Dijkstra 提出。它根据当前资源状态和进程最大需求，预测资源分配是否会导致系统进入不安全状态，以此判断是否批准资源请求。

像银行放贷一样：只有在确保即使贷款后仍能满足所有客户提款请求的前提下，才放贷。

🛠 关键数据结构：

  • Available[]: 当前可用资源数量
  • Max[][]: 每个进程最大资源需求
  • Allocation[][]: 每个进程当前已分配资源
  • Need[][]: 每个进程剩余资源需求 = Max - Allocation

✅ 特点：

  • 安全性检测 + 资源分配
  • 可以避免死锁
  • 实现复杂、开销较大
  • 适合银行式、多资源管理系统

✅ C. 测试并设置锁

英文名：Test-and-Set Lock，简称 TSL 或 T&S 用于：低级互斥原语（硬件支持的原子操作）

🧠 核心思想：

利用硬件原子指令 TestAndSet() 来构建互斥锁，不可中断，防止竞态条件。

🛠 示意代码：

1
2
3
4
5
6
7
8
9
10
bool TestAndSet(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

while (TestAndSet(&lock));  // busy waiting
// 临界区
...
lock = false;  // 释放锁

✅ 特点：

  • 利用原子性操作
  • 简单快速，适合多核并发
  • 缺点是 忙等待（busy waiting），浪费 CPU 时间

✅ D. 严格交替法

英文名：Strict Alternation 用于：两个进程互斥访问资源

🧠 核心思想：

通过一个共享变量 turn，强制两个进程交替进入临界区。

1
2
3
4
5
// 假设 P0 和 P1 共享变量 turn
while (turn != i);  // 轮到我才进入临界区
// 临界区
...
turn = j;  // 交给对方

✅ 特点：

  • 实现简单
  • 不能保证进程有空让进（progress）——即使另一个进程不想进临界区，也要等它"让位"
  • 容易造成效率低下或资源浪费

✅ 总结对比表格：

算法名称 类型 支持进程数 是否避免死锁 是否使用硬件 是否忙等待 特点概括
Peterson 算法 软件互斥 2 是 否 否 精巧安全，满足互斥与有界等待
银行家算法 死锁预防（资源调度） 任意 是 否 否 复杂但安全，预测型资源分配
Test and Set Lock 硬件互斥（原子操作） 多个 是 是 ✅是 快速高效但可能造成忙等待
严格交替法 软件互斥 2 否 否 否 太严格，导致效率低下，非实用

2. (A) If the time slice is too large, round robin scheduling algorithm may degenerate to ______ scheduling algorithm.

(A) First Come First Served (FCFS)

  • 中文翻译： 如果时间片过大，轮转调度算法可能退化为哪种调度算法？

  • 选项： A. 先来先服务（FCFS） B. 最短作业优先（SJF） C. 优先级调度 D. 多队列调度（Multiple Queues）

  • 答案：A. First Come First Served (FCFS)

  • 解释： 如果时间片非常大，当前运行的进程可能在时间片内就运行完毕，不会被抢占，从而变得和 FCFS（即谁先来谁先执行）一样，失去了轮转调度的抢占性特点。

3. (B) A semaphore has an initial value of 3. Now it becomes 1. If M is the number of available resources and N is the number of waiting processes, what are M and N?

(B) 1, 0

  • 中文翻译： 一个信号量初始值为3（表示有3个资源），现在变成1。若 M 表示可用资源数，N 表示等待该资源的进程数，则 M 和 N 分别是？

  • 选项： A. 0, 1 B. 1, 0 C. 1, 2 D. 2, 0

  • 答案：B. 1, 0

  • 解释： 信号量当前值为1，说明还有1个资源可用（M=1），而没有进程在等待资源（否则信号量值会为负），因此等待进程数为0（N=0）。

4. (B) The purpose of the page table is to map virtual pages into page frames. The ________ method is to avoid keeping all the page tables in memory all the time.

(B) Multi-level page table

  • 中文翻译： 页表用于将虚拟页映射到页框。以下哪种方法可以避免将所有页表同时保存在内存中？

  • 选项： A. TLB（Translation Lookaside Buffer） B. 多级页表（Multi-level page table） C. 倒排页表（Inverted page table） D. 哈希算法（Hash algorithm）

  • 答案：B. Multi-level page table

  • 解释： 多级页表通过分层管理页表，只在需要时加载某一部分页表到内存中，从而节省内存空间。与之不同，TLB 是缓存机制，倒排页表是为节省空间的另一种结构。

5. (C) With the LRU page replacement policy, and enough space for storing 3 page frames, the memory page reference string “ABCABDDCABCD” would produce how many page faults?

(C) 8 page faults

  • 中文翻译： 使用最近最少使用（LRU）页面替换策略，内存有3个页框，页面访问序列为 “ABCABDDCABCD”，会产生多少次缺页？

  • 选项： A. 6 次缺页 B. 7 次缺页 C. 8 次缺页 D. 9 次缺页

  • 答案：C. 8 page faults（8次缺页）

  • 解释： 跟踪页面访问过程：

    1
    2
    3
    4
    访问序列: A B C A B D D C A B C D
    页框容量: 3

    缺页时刻: A(1), B(2), C(3), D(4), C(5), A(6), B(7), D(8)

    总共 8 次缺页，按照 LRU 策略每次替换最久未使用的页面。

6. (A)

( ) Assume the reference count of file F1 is 1 initially. Firstly, we create a symbolic link file F2 linking to F1, and then create a hard link file F3 linking to F1. Afterwards, F1 is deleted. Now, the reference count of F2 and F3 is ______ respectively. 假设文件 F1 的引用计数最初是 1。首先创建一个符号链接 F2 指向 F1，然后创建一个硬链接 F3 指向 F1。之后删除 F1。那么 F2 和 F3 的引用计数分别是多少？

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

✅ 答案：A. 0, 1

解释：

  • 硬链接（Hard Link）共享的是文件本体的 inode，因此增加引用计数。
  • 符号链接（Symbolic Link）只是一个指向路径的普通文件，不增加原文件的引用计数。
  • 删除 F1 实际上是删除它的目录项，如果还有硬链接存在，文件内容不会被释放。
  • 最终情况：F3 是硬链接仍指向 F1 的 inode，所以计数为 1；F2 是符号链接，但其目标已被删除，引用计数为 0（因为它不增加原文件引用数）。

📚 一、相关知识点（含中英文对照）

1. i-node（索引节点）

  • 每个文件（无论是普通文件、目录或符号链接）在磁盘中都有一个对应的 i-node，记录文件元信息（如大小、权限、数据块指针等）。
  • 多个文件名可以指向同一个 i-node，这就是硬链接。

2. Hard Link（硬链接）

  • 是 多个路径指向同一个 i-node 的方式。
  • 多个硬链接共享相同的数据和元信息。
  • 每建立一个硬链接，i-node 的 reference count（引用计数）+1。
  • 当一个路径删除时，引用计数减 1，只有当引用计数为 0 时，文件才会真正被回收。

✅ 一个硬链接 = 真正的另一个“入口”点。

3. Symbolic Link（符号链接 / 软链接）

  • 是一个 特殊的文件，其内容是目标文件的路径字符串。
  • 它不会直接指向目标的 i-node，而是指向一个路径名。
  • 不影响目标文件的引用计数。
  • 如果目标被删除，符号链接会变成“悬挂链接”（dangling link），访问时报错。

🧠 类似 Windows 的快捷方式（.lnk 文件）。

4. Reference Count（引用计数）

  • 指的是有多少个目录项（即“路径”）指向该文件的 i-node。
  • 每新增一个硬链接，引用计数 +1；
  • 每删除一个硬链接（路径），引用计数 -1；
  • 当引用计数 = 0，且无进程打开该文件时，操作系统会回收磁盘空间。

5. 删除文件的本质

删除一个文件名（如 /F1）：

  • 并不是立即删除 i-node 和数据；
  • 操作系统只是把 路径名和 i-node 的映射关系删除；
  • 如果还有其他路径（如硬链接 F3）指向该 i-node，则数据依旧保留。

🧪 衍生例子（推荐记住）

操作 F1引用计数 符号链接状态 硬链接状态
创建 F1 1 无 无
创建符号链接 F2→F1 1 F2 可访问 F1 无变化
创建硬链接 F3→F1 2 F2 可访问 F1 F3 指向 F1
删除 F1 1 F2 变成断链 F3 仍可访问
删除 F3 0 F2 仍为断链 F1 数据彻底删除

✅ 总结要点（考试重点）

项目 硬链接（Hard Link） 符号链接（Symbolic Link）
是否共享 i-node 是 否（仅保存目标路径字符串）
是否增加引用计数 是 否
删除原文件影响 无影响（只要还有硬链接） 链接失效（dangling）
是否可跨文件系统 否 可以
是否可链接目录 否（限制） 可以

7. (C)

( ) How many disk operations are needed to fetch the i-node for the file /home/John/test.txt? Assume nothing along the path is in memory. Also assume that all directories fit in one disk block. 如果内存中没有缓存路径中的任何信息，访问 /home/John/test.txt 的 i-node 需要多少次磁盘操作？（假设每个目录占一个磁盘块）

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

✅ 答案：C. 7

解释： 每一级目录都需要两个操作：

  1. 读取目录所在的 i-node，
  2. 读取目录的数据块（查找下一级名字对应的 i-node 编号）

步骤如下：

  1. 读取根目录 / 的 i-node（1次）
  2. 读取根目录块（找到 "home" 的 i-node）（2次）
  3. 读取 "home" 的 i-node（3次）
  4. 读取 "home" 的目录块（找 "John" 的 i-node）（4次）
  5. 读取 "John" 的 i-node（5次）
  6. 读取 "John" 的目录块（找 "test.txt" 的 i-node）（6次）
  7. 读取 "test.txt" 的 i-node（7次）

共计 7 次磁盘操作。

8. (B)

( ) I/O software is typically organized in four layers. Computing the track, sector, and head for a disk read is done in the ________ layer. I/O 软件通常分为四层，磁盘读操作中计算磁道号、扇区号和磁头号的工作在哪一层完成？

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

✅ 答案：B. device drivers（设备驱动程序）

解释： 设备驱动程序是直接与硬件交互的层，它负责具体的操作，比如计算磁头、磁道和扇区的位置，然后发出相应的控制命令。

  • 中断处理程序：处理来自硬件的中断信号
  • 设备无关软件：处理抽象逻辑接口
  • 用户层软件：提供接口给应用程序

9. (A)

( ) Windows takes _____ approach to handle deadlock. Windows 系统采用哪种方法来处理死锁？

  • A. 鸵鸟策略（the Ostrich）
  • B. 检测与恢复（detection and recovery）
  • C. 避免（avoidance）
  • D. 预防（prevention）

✅ 答案：A. the Ostrich（鸵鸟策略）

解释： Windows 操作系统采用鸵鸟策略处理死锁问题，也就是说，假装问题不存在，因为在大多数实际场景中，死锁的概率较低，且处理开销大。

10. (B)

( ) Requesting all resources initially is often used to prevent deadlock to attack the ______ condition. 在进程一开始就请求所有资源的策略，主要是为了解决死锁的哪个条件？

  • A. 互斥（mutual exclusion）
  • B. 占有并等待（hold and wait）
  • C. 非抢占（no preemption）
  • D. 循环等待（circular wait）

✅ 答案：B. hold and wait（占有并等待）

解释： 死锁的四个必要条件中，“占有并等待”是指进程在占有一个资源的同时，还请求其他资源。如果让进程一开始就请求它所需的所有资源，则不会出现这种边占边等的情况，从而破坏这一死锁条件。

简答题

1. (5 pts)

Q: 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 implies that the full page table must be accessed (which is most likely stored in memory). We must have a miss of the page table (more specifically, a page fault) in order to require a disk operation.

不一定。 TLB（快表）缺失只是意味着在 TLB 中没有找到对应的页表项，此时需要去访问主存中的完整页表。 只有当访问页表后发现该页不在主存中（即发生缺页中断 page fault）时，才会触发磁盘操作来将页面调入内存。

📌 解释：

  • ✅ TLB miss → 访问内存中的页表 ✅
  • ❌ TLB miss ≠ 一定要访问磁盘 ❌
  • ✅ Page fault → 才可能导致磁盘 I/O ✅

2. (5 pts)

Q: Please describe the relationship between a process and a program. 请描述进程与程序之间的关系。

✅ Answer / 答案：

  1. Program is a static concept, a collection of instructions. 程序是静态的概念，是一组指令的集合。
  2. Process is a dynamic concept, it represents a program in execution. 进程是动态的概念，是程序的执行过程。
  3. A process consists of the program, its data, and the process control block (PCB). 一个进程由程序代码、相关数据和进程控制块组成。
  4. A program can be executed by multiple processes. 一个程序可以被多个进程执行（例如多次打开同一个应用）。
  5. A process can call multiple programs during execution. 一个进程在运行过程中也可以调用多个程序（例如打开子程序或库）。
  6. A process is temporary (exists during execution), while a program is permanent (stored on disk). 进程是临时的（只在运行时存在），程序是永久的（可长期保存在磁盘中）。

📌 总结：

  • 程序：静态、可执行代码、长期存在
  • 进程：动态、程序执行的实例、包含状态和控制信息
  • 一个程序 → 多个进程实例
  • 一个进程 → 可调用多个程序模块

3. (5 pts)

Q: What is the purpose of the open system call in UNIX? What would the consequences be of not having it? 在 UNIX 中，open 系统调用的作用是什么？如果没有它，会有什么后果？

✅ Answer / 答案：

(1) The purpose of the open system call is to allow the system to fetch the file's metadata (such as attributes and disk block addresses) into memory, making subsequent operations like read and write faster.

(1) open 的作用是让系统将文件的元数据（如属性、磁盘地址列表等）载入主存，从而使后续如 read 或 write 的操作更快更高效。

(2) Without open, every time a file is accessed (e.g., by read), the program would have to specify the file name, and the system would need to fetch the i-node every time, even if it was just used.

(2) 如果没有 open，每次访问文件时（例如使用 read），都必须重新指定文件名，系统也必须每次都重新读取该文件的 i-node（索引节点），即使刚刚才使用过。

📌 Consequences / 后果：

  • 会带来冗余的磁盘访问；
  • 难以维护文件状态（如读写指针、权限）；
  • 系统需要额外处理缓存管理和文件标识；
  • 整体变得繁琐、效率低下。

4. (5 pts)

Q: 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 / 答案： The system will be deadlock-free if:

r ≥ p × (m – 1) + 1

如果满足以下条件，系统就不会发生死锁：

r ≥ p × (m – 1) + 1

📌 Explanation / 解释：

  • 假设每个进程最多需要 m 个资源。
  • 若每个进程现在都已持有 m - 1 个资源，且还需要一个才能完成任务。
  • 如果系统中至少还剩下 1 个额外资源，那么至少有一个进程能获得资源并完成任务，释放其占用的资源。
  • 这样，其它进程就能依次获得资源完成任务，避免死锁。

📝 总结 / Summary：

参数 含义
p 进程数
m 每个进程所需最大资源数
r 系统总资源数
条件 r ≥ p(m – 1) + 1 可避免死锁

互斥题

💡题目 / Question (10pts)

In the Sim-City community Woobish, most people smoke, but the law requires that non-smokers be protected from passive smoke.

在 Sim-City 的 Woobish 社区，大多数人吸烟，但法律要求保护非吸烟者免受二手烟影响。

因此制定了一项规定：如果酒吧中有人是非吸烟者，其他人就不能点烟。

线程行为如下：

  • 吸烟者线程：

    1
    2
    3
    4
    enter_bar(true)  // 进入酒吧  
    want_smoke()     // 想要吸烟  
    done_smoking()   // 吸烟完毕  
    leave_bar(true)  // 离开酒吧

  • 非吸烟者线程：

    1
    2
    enter_bar(false) // 进入酒吧  
    leave_bar(false) // 离开酒吧

❓要求：

用 伪代码 写出使用 信号量 实现该规则的代码，确保非吸烟者在场时没人能吸烟。

✅答案 / Solution（伪代码）

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
semaphore mutex = 1      // 互斥锁
semaphore ok_to_smoke = 0

int smokers_in_bar = 0
int nonsmokers_in_bar = 0
int smoking_now = 0

procedure enter_bar(is_smoker):
    P(mutex)
    if is_smoker:
        smokers_in_bar += 1
    else:
        nonsmokers_in_bar += 1
    V(mutex)

procedure leave_bar(is_smoker):
    P(mutex)
    if is_smoker:
        smokers_in_bar -= 1
    else:
        nonsmokers_in_bar -= 1
        if nonsmokers_in_bar == 0:
            // 唤醒所有等待的吸烟者
            for i in range(smokers_in_bar):
                V(ok_to_smoke)
    V(mutex)

procedure want_smoke():
    P(mutex)
    if nonsmokers_in_bar > 0:
        V(mutex)
        P(ok_to_smoke)   // 等待非吸烟者离开
        P(mutex)
    smoking_now += 1
    V(mutex)

procedure done_smoking():
    P(mutex)
    smoking_now -= 1
    V(mutex)

🧠解释 / Explanation（中英文对照）

🔹结构变量解释：

变量 含义（中文） 含义（英文）
mutex 互斥锁，保护共享变量 mutual exclusion for shared variables
ok_to_smoke 吸烟许可信号量 semaphore used to allow smoking
smokers_in_bar 当前酒吧中的吸烟者人数 number of smokers in the bar
nonsmokers_in_bar 当前酒吧中的非吸烟者人数 number of non-smokers in the bar
smoking_now 正在吸烟的人数 number of people currently smoking

📌关键点总结 / Key Points Summary

  • 当有非吸烟者在酒吧时，吸烟者无法吸烟；
  • 非吸烟者离开后，释放 ok_to_smoke 信号，允许吸烟者开始吸烟；
  • 吸烟者之间可以并发吸烟，但前提是没有非吸烟者在场；
  • 所有状态通过 mutex 锁进行保护，防止并发修改出错。

💡银行家算法

Consider the following system snapshot using the data structures in the Banker’s Algorithm, with 4 resources (A, B, C, D) and 5 processes (P0 to P4).

考虑以下系统快照，使用银行家算法的相关数据结构，有 4 种资源（A, B, C, D）和 5 个进程（P0 到 P4）。

Process Max Allocation Available
A B C D A B C D A B C D
P0 6 0 1 2 4 0 0 1 3 2 1 1
P1 1 7 5 0 1 1 0 0
P2 2 3 5 6 1 2 5 4
P3 1 6 5 3 0 6 3 3
P4 1 6 5 6 0 2 1 2

✏️ Sub-questions:

  1. What are the contents of the Need matrix? → 需求矩阵（Need）是什么？
  2. Is the system in a safe state? Why? → 当前系统是否处于安全状态？为什么？
  3. If a request from P4 arrives for additional resources of (1,2,0,0), can the Banker’s algorithm grant it immediately? → 如果 P4 请求额外资源 (1,2,0,0)，银行家算法是否可以立刻批准请求？请说明理由。

✅答案 / Answer

🧮(1) Need Matrix 需求矩阵计算（Max - Allocation）

Need = Max - Allocation

Process Max Allocation Need = Max - Allocation
P0 6 0 1 2 4 0 0 1 2 0 1 1
P1 1 7 5 0 1 1 0 0 0 6 5 0
P2 2 3 5 6 1 2 5 4 1 1 0 2
P3 1 6 5 3 0 6 3 3 1 0 2 0
P4 1 6 5 6 0 2 1 2 1 4 4 4

🔹Answer (1): P0: 2 0 1 1 P1: 0 6 5 0 P2: 1 1 0 2 P3: 1 0 2 0 P4: 1 4 4 4

🔐(2) 安全状态判断 / Is the system in a safe state?

初始 Available 资源为：(3 2 1 1)

Step-by-step 安全序列判断：

  • P0: Need = (2 0 1 1) ≤ Available = (3 2 1 1) ✅ → P0 运行并释放资源：Available += (4 0 0 1) ⇒ (7 2 1 2)
  • P2: Need = (1 1 0 2) ≤ (7 2 1 2) ✅ → Available += (1 2 5 4) ⇒ (8 4 6 6)
  • P3: Need = (1 0 2 0) ≤ (8 4 6 6) ✅ → Available += (0 6 3 3) ⇒ (8 10 9 9)
  • P4: Need = (1 4 4 4) ≤ (8 10 9 9) ✅ → Available += (0 2 1 2) ⇒ (8 12 10 11)
  • P1: Need = (0 6 5 0) ≤ (8 12 10 11) ✅ → 完整运行，系统安全

🔹Answer (2): Yes, the system is in a safe state. → 是的，系统处于安全状态。

安全序列：P0 → P2 → P3 → P4 → P1

❌(3) 若 P4 请求额外 (1 2 0 0)，系统是否安全？

P4 当前 Allocation: (0 2 1 2) 请求后变成：Allocation = (1 4 1 2) Need = Max - Allocation = (0 2 4 4) Available = (3 2 1 1) - (1 2 0 0) = (2 0 1 1)

尝试找出一个满足 Need ≤ Available 的进程：

  • P0: (2 0 1 1) ≤ (2 0 1 1) ✅ → Available += (4 0 0 1) ⇒ (6 0 1 2)
  • 其他进程：
    • P2: (1 1 0 2) ❌ 不满足（1 > 0）
    • P1: (0 6 5 0) ❌
    • P3: (1 0 2 0) ❌
    • P4: (0 2 4 4) ❌

剩下的所有 Need 都比当前 Available 大，因此系统不再安全。

🔹Answer (3): No, request cannot be granted immediately. → 不可以立刻批准请求，系统将进入不安全状态。

📘总结 / Summary

问题编号 答案 中文解释
(1) Need 矩阵如上 Max - Allocation
(2) Yes 系统安全，存在安全序列
(3) No 批准请求后系统不安全，不可批准请求

反馈队列

英文原文： Consider a multi-level feedback queue in a single-CPU system. The first level (queue 0) is given a quantum of 8 ms, the second one a quantum of 16 ms, and the third is scheduled FCFS. Assume jobs arrive all at time zero with the following job times (in ms): → 4, 7, 12, 20, 25, and 30.

Show the Gantt chart for this system and compute the average waiting time and turnaround time.

中文翻译： 在一个单处理器系统中，考虑使用多级反馈队列（MLFQ）调度算法。

  • 第一队列（Queue 0）的时间片是 8ms，
  • 第二队列（Queue 1）的时间片是 16ms，
  • 第三队列（Queue 2）使用 FCFS（先来先服务）调度。

假设所有作业在时间 0 同时到达，作业执行时间分别为： 4ms, 7ms, 12ms, 20ms, 25ms, 30ms。

请画出甘特图（Gantt Chart），并计算出：

  • 平均等待时间（Average Waiting Time）
  • 平均周转时间（Average Turnaround Time）

✅答案 / Answer（含甘特图、中英文解释）

🌈 Step 1: 初始作业状态 / Initial Job List

Job Burst Time (ms)
J1 4
J2 7
J3 12
J4 20
J5 25
J6 30

注意： 所有作业在时间 t = 0 到达。

⏱️ Step 2: 多级反馈队列调度（MLFQ）

规则回顾：

  • 第一队列（Q0）：时间片 8ms，使用 RR。
  • 第二队列（Q1）：时间片 16ms，使用 RR。
  • 第三队列（Q2）：使用 FCFS。

执行过程：

时间 执行情况
0–4 J1（完成）
4–11 J2（完成）
11–19 J3（执行 8ms，剩余 4ms，进入 Q1）
19–27 J4（执行 8ms，剩余 12ms，进入 Q1）
27–35 J5（执行 8ms，剩余 17ms，进入 Q1）
35–43 J6（执行 8ms，剩余 22ms，进入 Q1）
43–47 J3（Q1，执行 4ms，完成）
47–59 J4（Q1，执行 12ms，完成）
59–75 J5（Q1，执行 16ms，剩余 1ms，进入 Q2）
75–91 J6（Q1，执行 16ms，剩余 6ms，进入 Q2）
91–92 J5（Q2，执行 1ms，完成）
92–98 J6（Q2，执行 6ms，完成）

📊 甘特图 / Gantt Chart

1
2
3
| J1 | J2 | J3 | J4 | J5 | J6 | J3 | J4 | J5 | J6 | J5 | J6 |
|----|----|----|----|----|----|----|----|----|----|----|----|
0    4    11   19   27   35   43   47   59   75   91   92   98

🧮 Step 3: 完成时间 / Completion Time

Job Burst Completion Time Turnaround Time = CT - AT Waiting Time = TAT - Burst
J1 4 4 4 0
J2 7 11 11 4
J3 12 47 47 35
J4 20 59 59 39
J5 25 92 92 67
J6 30 98 98 68

✅ 最终结果 / Final Answer

✔️ 平均周转时间（Average Turnaround Time）

\[ \frac{4 + 11 + 47 + 59 + 92 + 98}{6} = \frac{311}{6} = \boxed{51.83\text{ ms}} \]

✔️ 平均等待时间（Average Waiting Time）

\[ \text{总执行时间} = 4 + 7 + 12 + 20 + 25 + 30 = 98 \Rightarrow \text{平均执行时间} = \frac{98}{6} = 16.33 \Rightarrow \text{平均等待时间} = 51.83 - 16.33 = \boxed{35.5\text{ ms}} \]

img

📘总结 / Summary

指标项 数值 说明（中文）
平均周转时间 TAT 51.83 ms 从提交到完成所花时间平均
平均等待时间 WT 35.5 ms 等待在队列中未执行的平均时间
调度策略 MLFQ (8ms, 16ms, FCFS) 多级反馈队列

磁盘调度

英文原文： Consider the situation in which the disk read/write head is currently located at track 45 (of tracks 0–255) and moving in the positive direction. Assume that the following track requests have been made in this order: → 40, 67, 11, 240, 87

  1. What is the order in which the Elevator Algorithm (SCAN) would service these requests, and what is the total seek distance?
  2. What about the Shortest Seek First (SSF) algorithm?

中文翻译： 考虑如下情景：磁头当前在磁道 45 上，且正在向磁道号增大的方向移动（正方向），整个磁道范围是 0～255。磁盘请求序列按顺序为： → 40, 67, 11, 240, 87

请回答以下问题：

  1. 若使用 电梯算法（Elevator/SCAN），服务请求的顺序是什么？总寻道距离是多少？
  2. 若使用 最短寻道优先（Shortest Seek First, SSF） 算法，总寻道路径及距离是多少？

✅选项 / Choices（模拟选择题风格）

  • Elevator 调度顺序：45, 67, 87, 240, 40, 11
  • Elevator 寻道距离：424
  • SSF 顺序：45, 40, 67, 87, 11, 240
  • SSF 寻道距离：357
  • Elevator 顺序：45, 67, 87, 240
  • Elevator 寻道距离：195
  • SSF 顺序：45, 11, 40, 67, 87, 240
  • SSF 寻道距离：476
  • Elevator 顺序：45, 67, 240, 87, 40, 11
  • Elevator 寻道距离：513
  • SSF 顺序：45, 67, 87, 240, 40, 11
  • SSF 寻道距离：424
  • Elevator 顺序：45, 87, 240, 67, 40, 11
  • Elevator 寻道距离：408
  • SSF 顺序：45, 87, 67, 40, 11, 240
  • SSF 寻道距离：386

✔️标准答案 / Correct Answer：A

🧠详细解析 / Explanation（中英文）

🔁 Elevator Algorithm（SCAN）电梯算法

思路：

  • 当前磁头在 45，向“正方向”移动。
  • 先服务大于等于 45 的请求：67, 87, 240
  • 然后反转方向，服务剩余小于 45 的请求：40, 11

调度顺序：

1
45 → 67 → 87 → 240 → 40 → 11

寻道距离（每一跳）：

  • 67 - 45 = 22
  • 87 - 67 = 20
  • 240 - 87 = 153
  • 240 - 40 = 200
  • 40 - 11 = 29

总寻道距离=22+20+153+200+29=424总寻道距离 = 22 + 20 + 153 + 200 + 29 =

🚀 SSF Algorithm（Shortest Seek First）最短寻道优先

思路：

  • 当前在 45，每次选择距离当前磁道最近的请求处理。

调度过程：

  • 离 45 最近的是：40（|45-40|=5）
  • 接下来离 40 最近的是：67（|40-67|=27）
  • 接下来是：87（|67-87|=20）
  • 然后是：11（|87-11|=76）
  • 最后是：240（|11-240|=229）

调度顺序：

1
45 → 40 → 67 → 87 → 11 → 240

寻道距离：

  • 45 → 40 = 5
  • 40 → 67 = 27
  • 67 → 87 = 20
  • 87 → 11 = 76
  • 11 → 240 = 229

总寻道距离=5+27+20+76+229=357总寻道距离 = 5 + 27 + 20 + 76 + 229 =

📘总结 / Summary

算法 调度顺序 总寻道距离
Elevator 45 → 67 → 87 → 240 → 40 → 11 424
SSF 45 → 40 → 67 → 87 → 11 → 240 357

文件题

📘 题目 / Question (10 分/pts)

你有一个只使用 i 节点（i-nodes）和数据块（data blocks）组成的文件系统。每个 i-node 有 10 个入口（entries），每个入口为 4 字节。

(1)

假设一个 i-node 有 10 个入口，其中：

  • 7 个指向直接数据块（direct blocks）
  • 2 个指向一级间接块（single indirect blocks）
  • 1 个指向二级间接块（double indirect block）

假设：

  • 数据块大小 = 1024 字节（1KB）
  • 间接块大小 = 1024 字节
  • 每个指针大小 = 4 字节

问：该文件系统允许的最大文件大小是多少？

(2)

如果不使用 i-nodes，而是使用文件分配表（File Allocation Table，FAT），每个 FAT 表项是 4 字节。

给定一个大小为 100 MB 的磁盘，块大小为 1024 字节。

问：在这种情况下，能存储的最大文件大小是多少？

✅ 答案与解释 / Answer & Explanation

(1) 最大文件大小（i-node 模型）

✅ 中文解释：

  • 直接块：7 个 × 1KB = 7KB
  • 单级间接块：
    • 一个间接块有：1024 ÷ 4 = 256 个指针
    • 每个指向 1KB 数据 ⇒ 每个间接块可寻址 256KB
    • 两个单级间接块 ⇒ 2 × 256KB = 512KB
  • 二级间接块：
    • 一级间接块有 256 个指针，每个再指向一个含有 256 个指针的块
    • 总计可寻址：256 × 256 × 1KB = 65536KB = 64MB

✅ 最终计算：

最大文件大小 = 7KB（直接） + 512KB（单级间接） + 64MB（二级间接） 👉 最大 = 64MB + 512KB + 7KB ≈ 64.519MB

(2) 最大文件大小（FAT 模型）

✅ 中文解释：

  • 总磁盘空间：100MB = 102400KB
  • 每个数据块：1KB ⇒ 总共数据块数 = 102400 块
  • 每个 FAT 表项 4 字节 ⇒ FAT 表大小 = 102400 × 4B = 409600 字节 = 400KB
  • 数据区大小 = 100MB - 400KB = 约 99.6MB

👉 所以 最大文件大小为约 99.6MB

📊 总结表格 / Summary Table

问题 / Question 英文答案 中文解释
(1) i-node 模型 7KB + 512KB + 64MB = 64.519MB i-node 中通过直接块、一级间接块和二级间接块可寻址的数据总量
(2) FAT 模型 100MB - 400KB = 约 99.6MB FAT 表占据 400KB 空间，剩余部分可用于存储单个大文件

📘 分段分页内存系统

考虑如下一个分段分页内存系统（Segmented Paging Memory System）：

  • 某个进程有 4 个段（segments）
  • 系统中共有 5 个页表（page tables）
  • 每个页表有 8 个条目（entries）
  • 物理内存地址空间需要 12 位（bits）来表示
  • 系统中一共有 128 个物理页框（frames）

问题 / Questions

(1) 物理内存中总共有多少个字节？ (2) 虚拟地址的大小是多少位？ (3) 虚拟地址 0x312 映射到的物理地址是多少？ (4) 虚拟地址 0x1E9 映射到的物理地址是多少？

✅ 答案与解释 / Answer & Explanation

(1) How many bytes are contained within the physical memory?

物理内存中有多少字节？

  • 题目说物理地址用 12 位表示 ⇒ 可表示的地址数 = 2¹² = 4096 字节 = 4KB

📌 Answer: 4096 bytes (4KB) 📌 中文答案：4096 字节（4KB）

(2) How large is the virtual address?

虚拟地址需要多少位？

  • 每页框数 = 128 ⇒ 每页大小 = 4096 / 128 = 32B
  • 页内偏移（offset）需要 2⁵ = 32 ⇒ 5 位
  • 每个段有 8 个页 ⇒ 页号需要 3 位（2³ = 8）
  • 段号有 4 个 ⇒ 段号需要 2 位（2² = 4）

✅ 所以虚拟地址大小 = 段号（2 位）+ 页号（3 位）+ 页内偏移（5 位） = 10 位

📌 Answer: 10 bits 📌 中文答案：10 位

(3) Physical address for virtual address 0x312

img

虚拟地址 0x312 对应的物理地址是多少？

  • 0x312 = 二进制 11 0001 0010
    • 段号：11（2 bits）= 3
    • 页号：000（3 bits）= 0
    • 偏移：10010（5 bits）= 18
  • 假设段 3 页 0 映射到页框号 = 23（二进制为 010111）
  • 物理地址 = 页框号（7 bits）010111 + offset 10010 ⇒ 物理地址二进制：010111 ⇒ 十六进制 = 0x2F2

📌 Answer: 0x2F2 📌 中文答案：0x2F2

(4) Physical address for virtual address 0x1E9

虚拟地址 0x1E9 对应的物理地址是多少？

  • 0x1E9 = 二进制 01 1110 1001
    • 段号：01 = 1
    • 页号：111 = 7
    • 偏移：01001 = 9
  • 假设段 1 页 7 映射到页框号 = 108（十进制），即二进制 1101100
  • 物理地址 = 1101100 + offset 01001 ⇒ 二进制地址为 110110001001 ⇒ 十六进制 = 0xD89

📌 Answer: 0xD89 📌 中文答案：0xD89

✅ 总结表格 / Summary Table

问题编号 英文答案 中文解释
(1) 4096 bytes (4KB) 物理地址 12 位 ⇒ 2¹² = 4096 字节
(2) 10 bits 段号 2 位 + 页号 3 位 + 偏移 5 位
(3) 0x2F2 段 3 页 0 偏移 18 映射为物理地址
(4) 0xD89 段 1 页 7 偏移 9 映射为物理地址