操作系统2013年B卷

选择题

1. ( ) Which one is not the role or function of the operating system?

操作系统的哪一项不是它的作用或功能？

A. Extended machine（扩展机器） B. Resource manager（资源管理者） C. Providing abstractions to application programs（为应用程序提供抽象） D. Executing application programs（执行应用程序）

✅ 答案：D

解释 Explanation：

  • 操作系统的作用是为应用程序提供抽象（如文件、进程、内存等）、管理硬件资源，以及充当扩展机器以简化硬件接口。
  • 但“执行应用程序”是 CPU 的任务，操作系统只是创建、调度和管理应用程序的运行，不是直接执行者。

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

哪一种对临界区问题的解决方法会导致“一个在自己临界区外运行的进程会阻塞另一个进程”的情况？

A. Disabling interrupts（关闭中断） B. Peterson’s Algorithm（彼得森算法） C. Strict Alternation（严格交替） D. Test and Set Lock（测试并设置锁）

✅ 答案：C

解释 Explanation：

  • 严格交替算法强制两个进程轮流进入临界区，即使一个进程不想进入，它也可能阻止另一个进程进入。
  • 这种“机械地轮流”可能导致在非临界区的进程也会阻塞其他进程，不是高效的并发控制。

3. ( ) We define a semaphore, whose initial value is 2. Now, its value becomes -1. Assume that M represents the number of available resource and N shows the number of processes waiting for this resource. Then the value of M and N is _______ respectively.

定义一个初始值为2的信号量，现在它的值变为 -1。设 M 是可用资源数，N 是等待该资源的进程数，则 M 和 N 的值分别为多少？

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

✅ 答案：B

解释 Explanation：

  • 初始为 2，说明总资源数是 2。
  • 值变为 -1，说明已经有 2 + 1 = 3 个进程尝试获得资源。前两个拿到了资源，第三个被阻塞。
  • 所以可用资源 M = 0，等待的进程数 N = 1（因为信号量值 = M - N）。

4. ( ) If the time slice is too large, round robin scheduling algorithm may degenerate to _______ scheduling algorithm.

如果时间片太大，轮转调度算法可能退化成哪种调度算法？

A. First Come First Served (FCFS)（先来先服务） B. Priority（优先级调度） C. Shortest Job First (SJF)（最短作业优先） D. Multi-level feedback queue（多级反馈队列）

✅ 答案：A

解释 Explanation：

  • 时间片轮转算法通过让每个进程执行一个固定时间片来实现公平。
  • 如果时间片非常大，那么第一个进程就会执行很久甚至执行完，变得和“先来先服务”没有区别。
  • 因此，会退化成 FCFS。

5. ( ) A 128-MB memory is allocated in units of n bytes. We use a linked list to keep track of free memory. Assume that memory consists of an alternating sequence of segments and holes, each 64KB. Also assume that each node in the linked list needs a 32-bit memory address, a 16-bit length, and a 16-bit next-node field. How many bytes of storage are required in bitmap method?

一个 128MB 的内存按 n 字节为单位分配，采用位图法跟踪空闲空间。需要多少字节来存储位图？

A. \(2^{27}/n\)

B. \(2^{24}/n\)

C. \(2^{11}\)

D. \(2^{14}\)

✅ 答案：B

解释 Explanation：

  • 位图法中，每个分配单元用 1 bit 表示是否空闲。
  • 128MB = \(2^{27}\) 字节，共有 \(2^{27} / n\) 个分配单元。
  • 每个单元需要 1 bit，转成字节除以 8，所以需要的字节数是 \((2^{27} / n) / 8 = 2^{27}/(8n)\)，实际用 \(2^{24}/n\)表示总位数，即选 B。

6. ( ) If the page entry says that the page is not in RAM, it raises a _______, an exception telling the operating system that it needs to bring a page into memory.

如果页表项显示页面不在 RAM 中，会引发一个 _______，通知操作系统需要将该页面调入内存。

A. page fault（页错误） B. trap（陷阱） C. array index out of bound（数组越界） D. none of the above（以上都不是）

✅ 答案：A

解释 Explanation：

  • 当访问的页不在物理内存中，处理器会触发一个 page fault（页错误） 异常，通知操作系统将所需页从磁盘调入内存。
  • Trap 是广义的中断或异常种类，不专指这个情况。
  • 数组越界是应用程序的错误，不属于页面调入。

7. ( ) 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

解释 Explanation：

  • A 错：即使使用 TLB，页表仍需保存在内存中，TLB 缓存有限。
  • B 错正确：压缩可以减少碎片，但不会频繁使用，因其代价高
  • C 错：First Fit 会留下许多小碎片，这些碎片常不能满足后续内存请求。
  • D 错：不总是这样，某些页面置换算法下，如 Belady 异常，增加页面数可能增加缺页率。

8. ( ) Which one of the following methods in implementing file storage can support random accesses easily?

下列哪种文件存储方式能方便地支持随机访问？

A. Contiguous allocation（连续分配） B. Linked list allocation（链式分配） C. Linked list allocation using FAT（用 FAT 的链式分配） D. none of the above（以上都不是）

✅ 答案：A

C也可以，但A方便！

9. ( ) The file-reference count is used for _______.

文件引用计数（file-reference count）用于________。

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 process accessing a file.（计算访问该文件的进程数）

✅ 答案：C

解释 Explanation：

  • 文件的引用计数用于追踪有多少目录项（即链接）指向该文件的 inode。
  • 当引用计数为 0 且没有进程打开该文件，文件才会真正从磁盘中删除。
  • 注意和打开文件计数（open count）区别，后者用于追踪有多少进程正在使用文件。

10. ( ) How many disk operations are needed to read the third block of the file /home/courses/os/test/A.doc? Assume that the i-node for the root directory is in memory, but nothing else along the path is in memory.

要读取 /home/courses/os/test/A.doc 文件的第 3 个数据块，如果除了根目录的 inode 外，路径中其他内容都不在内存中，需要多少次磁盘操作？

A. 9 B. 10 C. 11 D. 12

✅ 答案：C

解释 Explanation： 路径分解如下（从根开始，每一级目录都需要一次读 inode 和一次读目录内容）：

一次读根目录

  • /home（1 次读 inode，1 次读目录）
  • /courses（1 inode + 1 目录）
  • /os（1 inode + 1 目录）
  • /test（1 inode + 1 目录）
  • A.doc（1 次读 inode）
  • 第三块数据（1 次读数据块）

总共：**(5 * 2) + 1= 11 次磁盘操作

11. ( ) Requesting all resources initially is often used to prevent deadlock to attack the ______ condition.

在开始就请求所有资源，常用于防止死锁，是为了破坏哪种死锁条件？

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

✅ 答案：C

解释 Explanation：

  • 死锁的四个必要条件之一是 hold and wait，即一个进程已经获得资源但仍等待其他资源。
  • 若一开始就请求所有资源，要么全拿到继续执行，要么一个也拿不到，从而破坏 hold and wait 条件，有效防止死锁。

12. Unix takes _____ to deal with deadlocks.

Unix 采用什么策略来处理死锁？

A. ostrich algorithm（鸵鸟算法） B. deadlock detection algorithm（死锁检测算法） C. banker’s algorithm（银行家算法） D. deadlock prevention algorithm（死锁预防算法）

✅ 答案：A

解释 Explanation：

  • Ostrich algorithm（鸵鸟算法） 指“把头埋在沙里”，即系统忽略死锁问题，因为死锁发生的概率很低，检测和处理代价高。
  • Unix 和多数通用操作系统采用该策略，默认死锁不常见，靠人工解决。

13. ( ) “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

解释 Explanation：

  • 设备无关性 是操作系统提供统一接口，让程序不需关心底层设备类型。
  • 选项 C 的定义最完整、标准：统一访问方式，独立于设备本质。
  • 因此，C 为正确答案，B 可视为部分正确解释。

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

在四层 I/O 软件结构中，哪一层负责“向设备寄存器写指令”？

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

✅ 答案：B

解释 Explanation：

  • 设备驱动（Device driver）直接与硬件打交道，负责将命令写入设备控制寄存器、启动设备。
  • 中断处理器是响应设备完成的信号。
  • 设备无关层处理逻辑名称、缓冲、错误代码等。
  • 用户级 I/O 是 API 层面，如 printf、read。

15. ( ) Disk requests come in to the disk driver for cylinders 9, 35, 22, 16, 40, 11 and 2, in that order. Assume that the arm is initially at cylinder 12. What is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests for elevator algorithm (Assume that the arm is initially moving towards cylinder 0)?

磁头最初在柱面 12，初始方向向柱面 0。请求顺序为：9, 35, 22, 16, 40, 11, 2。电梯算法下，总共移动多少柱面？

A. 48 B. 66 C. 72 D. 75

✅ 答案：A

解释 Explanation（电梯算法 SCAN）：

  • 起始位置：12，初始方向：向 0。
  • 请求按顺序为：9, 35, 22, 16, 40, 11, 2
  • 将请求排序：2, 9, 11, 16, 22, 35, 40
  • 先处理 <=12 的请求：2, 9, 11（按升序回头方向）
  • 再回转并处理：16, 22, 35, 40

路径计算如下：

  • 12 → 11 → 9 → 2：12 - 2 = 10
  • 2 → 16 → 22 → 35 → 40：40 - 2 = 38
  • 总移动距离：10 + 38 = 48
  1. 12 → 11 (1)
  2. 11 → 9 (2)
  3. 9 → 2 (7)
  4. 2 → 16 (14)
  5. 16 → 22 (6)
  6. 22 → 35 (13)
  7. 35 → 40 (5)

➡️ 总和：1 + 2 + 7 + 14 + 6 + 13 + 5 = 48

✅ 正确答案应为：A. 48

简答题

1. What is the difference between a process and a thread? Describe some benefits using threads.

进程和线程有什么区别？使用线程有哪些好处？

✅ 标准答案 Standard Answer

Process vs. Thread 区别 Differences

项目 进程（Process） 线程（Thread）
定义 是资源分配的基本单位，一个进程可以包含多个线程 是程序执行的基本单位，属于某个进程
独立性 进程之间基本独立，互不影响 同一进程内的线程彼此协作，密切相关
资源 每个进程拥有自己的地址空间和资源 同一进程内线程共享内存、文件等资源
创建开销 创建进程开销大 创建线程开销小（约为进程的 1/10~1/20）
切换开销 进程切换慢 线程切换快（约为进程的 1/5~1/50）

Advantages of Using Threads 使用线程的好处

  1. ✅ 低开销（Low overhead）
    • 线程的创建和切换比进程便宜得多，系统开销小。
    • Thread creation is much cheaper than process creation (~10–20 times faster).
    • Thread switching is faster than process switching (~5–50 times faster).
  2. ✅ 资源共享（Resource sharing）
    • 同一进程内线程共享数据和资源（如变量、文件），无需使用复杂的通信机制。
    • Threads in the same process can share data more efficiently than processes.
  3. ✅ 适合并发（Concurrency）
    • 多线程允许程序同时执行多个任务，提高并发性和系统利用率。
    • Threads are useful for writing efficient concurrent programs.
  4. ⚠️ 注意：线程之间不隔离（No protection）
    • 线程之间共享地址空间，一个线程出错可能影响整个进程。

✅ 简洁中英文总结 Summary

中文总结： 进程是资源分配单位，线程是执行单位。线程属于进程，共享资源，创建与切换成本低，适合并发，但彼此之间没有内存隔离。

English Summary: A process is a resource container; a thread is a unit of execution within it. Threads are lightweight, share resources, and are efficient for concurrent execution, but lack isolation.

2. If a disk has double interleaving, does it also need cylinder skew in order to avoid missing data when making a track-to-track seek? Explain your answer briefly.

如果一个磁盘使用双重交错（double interleaving），它是否还需要柱面偏移（cylinder skew）来避免在进行道间（track-to-track）寻道时错过数据？请简要解释。

✅ 标准答案 Standard Answer

  • 双重交错存取是否需要柱面斜进来避免丢失数据？
    • 可能需要，也可能不需要。 双重交错存取相当于 两扇区的柱面斜进。
    • 如果磁头可以在 磁道间寻道 的时间少于经过两扇区的时间，那么就不需要额外的柱面斜进。
    • 如果磁头的寻道时间超过了两扇区的时间，那么就需要额外的 柱面斜进 来避免寻道后丢失扇区。

3. In a paging system, the page table might be extremely large and requires much memory space. Give 2 possible solutions and explain them briefly.

在分页系统中，页表可能非常庞大，占用大量内存。请给出两种可能的解决方案，并简要解释。

✅ 标准答案 Standard Answer

Solution 1: Multi-level Page Table（多级页表）

This method breaks the large page table into a tree-like structure with multiple levels (e.g., two-level or three-level). Only the parts of the page table that are actually needed are kept in memory, thus reducing memory usage.

中文解释： 多级页表将一个大的页表分成多个较小的页表层次结构（如二级、三级），只有真正用到的部分才加载到内存中，从而显著减少内存占用。

Solution 2: Inverted Page Table（倒排页表）

Instead of maintaining one page table per process, a single page table indexed by physical frames is used for the whole system. Each entry stores the process ID and virtual page number that maps to the physical frame. This saves space when there are many processes with sparse memory usage.

中文解释： 倒排页表不是为每个进程维护一张页表，而是为整个系统建立一张按物理页帧编号的页表。每个表项记录该物理帧属于哪个进程及其虚拟页号，适合内存利用率低的情况，可以显著节省空间。

✅ 中英文总结 Summary

方法 英文 中文解释
1 Multi-level Page Table 分层存储页表，仅在访问时加载，减少空间浪费
2 Inverted Page Table 系统级页表，以物理页帧为索引，减少页表总数量

✅ 格式化业务作业回答格式（适合提交）：

Answer 3:

To reduce memory space taken by large page tables in a paging system, we can use the following two solutions:

  1. Multi-level Page Table: Divide the large page table into a hierarchy (e.g., two-level or three-level). Only parts that are in use are loaded in memory. This reduces memory consumption for sparse address spaces.
  2. Inverted Page Table: Maintain one global page table indexed by physical frames, rather than per-process page tables. Each entry stores the virtual address and process ID, allowing space-saving when few pages are used.

中文翻译：

为了解决分页系统中页表过大、占用内存的问题，可以采用以下两种方法：

  1. 多级页表（Multi-level Page Table）： 将页表分为多层结构，仅在需要时加载相应部分，节省大量内存。
  2. 倒排页表（Inverted Page Table）： 建立一个全局页表，以物理页帧为索引，避免为每个进程建立一张完整页表，从而节省内存空间。

硬链接（Hard Link）与符号链接（Symbolic Link，也叫软链接）有何不同？

✅ 标准答案 Standard Answer

Hard Link（硬链接）

  • A hard link is a direct reference to the inode of a file.
  • Multiple hard links point to the same inode, so the file's content remains accessible as long as at least one link exists.
  • Hard links cannot link to directories and cannot cross file systems.

中文解释： 硬链接是对文件 inode（索引节点） 的直接引用，多个硬链接指向同一个文件内容（inode），删除原始文件名不会影响其他硬链接。 硬链接不能指向目录，也不能跨文件系统使用。

Symbolic Link（符号链接）

  • A symbolic link is a special file that contains a path to another file (like a shortcut).
  • It is indirect, pointing to a file name rather than its inode.
  • Symbolic links can point to directories and can cross file systems, but if the target is deleted, the link becomes broken.

中文解释： 符号链接是一个特殊类型的文件，其内容是另一个文件的路径（类似快捷方式），指向文件名而不是内容。 符号链接可以指向目录，也可以跨文件系统，但一旦目标文件被删除，符号链接就会失效（成为“悬挂链接”）。

✅ 中英文总结表格 Summary Table

属性 / Attribute Hard Link（硬链接） Symbolic Link（符号链接）
指向 / Points to 文件内容的 inode 目标文件路径（文件名）
跨文件系统 / Cross filesystem 否 / No 是 / Yes
指向目录 / Point to directory 否 / No 是 / Yes
删除原文件后是否有效 有效，文件仍然存在 无效，链接断裂
本质 / Nature 文件的另一个“真实名字” 类似于快捷方式

✅ 格式化业务作业回答格式（适合提交）

Answer 4:

There are two major types of links in a Unix/Linux file system: Hard Link and Symbolic Link. Their differences are:

  1. Hard Link:
    • Points directly to the file's inode.
    • Multiple names (links) for the same content.
    • Cannot span file systems or link to directories.
    • File content remains as long as one link exists.
  2. Symbolic Link (Soft Link):
    • A special file that stores the path of the target file.
    • Can point to files or directories.
    • Can cross file systems.
    • Becomes broken if the target file is deleted.

中文翻译：

在 Unix/Linux 文件系统中，链接分为两种：硬链接 和 符号链接，主要区别如下：

  1. 硬链接：
    • 直接指向文件的 inode。
    • 是原文件的另一名字，内容完全一样。
    • 不能跨文件系统，也不能指向目录。
    • 删除原文件名不会影响文件存在。
  2. 符号链接（软链接）：
    • 是一个包含路径的特殊文件。
    • 可以链接文件或目录，允许跨文件系统。
    • 如果目标文件被删除，符号链接将失效。

多级队列调度

✅ 问题 Problem

1. Consider a multi-level feedback queue (MLFQ) in a single-CPU system.

  • Queue 0: Quantum = 4ms, Round Robin (RR)
  • Queue 1: Quantum = 8ms, Round Robin (RR)
  • Queue 2: FCFS (no quantum)
  • All jobs arrive at time 0
  • CPU burst times of the 6 jobs: 4, 7, 12, 20, 25, and 30 ms

Tasks:

  • Draw the Gantt chart of the execution (5 pts)
  • Compute the average turnaround time (5 pts)

✅ 答案 Answer

📊 Step 1: Job List (arrive at t=0)

Job Burst Time
A 4 ms
B 7 ms
C 12 ms
D 20 ms
E 25 ms
F 30 ms

🧠 Step 2: Gantt Chart 构建

🔹 Round 1: Queue 0 (4ms RR)

每个作业轮流获得 4ms 的时间：

  • A: 4（完成）
  • B: 4（剩余3）
  • C: 4（剩余8）
  • D: 4（剩余16）
  • E: 4（剩余21）
  • F: 4（剩余26）

Gantt Chart so far:

[A(0-4)] [B(4-8)] [C(8-12)] [D(12-16)] [E(16-20)] [F(20-24)]

🔹 Round 2: Queue 1 (8ms RR)

现在剩余进程（B~F）进入 queue1，时间片为 8ms：

  • B: 3（完成）
  • C: 8（剩余0，完成）
  • D: 8（剩余8）
  • E: 8（剩余13）
  • F: 8（剩余18）

Gantt Chart 继续:

[B(24-27)] [C(27-35)] [D(35-43)] [E(43-51)] [F(51-59)]

🔹 Round 3: Queue 2 (FCFS)

剩下的 D(8), E(13), F(18)，按 FCFS 顺序运行完：

  • D: 8（完成）
  • E: 13（完成）
  • F: 18（完成）

最终 Gantt Chart：

1
2
3
| A | B | C | D | E | F | B | C | D | E | F | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0  4   8  12 16  20 24 27 35 43 51 59 67 80 98       |

🧮 Step 3: Turnaround Time 计算

Turnaround Time = Completion Time - Arrival Time （因为全部在时间 0 到达，所以 turnaround time 就是完成时间）

Job Completion Time Turnaround Time
A 4 4
B 27 27
C 35 35
D 67 67
E 80 80
F 98 98

🔢 平均周转时间（Average Turnaround Time）：

\[ \frac{4 + 27 + 35 + 67 + 80 + 98}{6} = \frac{311}{6} \approx \boxed{51.83 \text{ ms}} \]

✅ 最终答案 Summary

🔹 Gantt Chart：

1
2
|A|B|C|D|E|F|B|C|D|E|F|D|E|F|
0 4 8 12 16 20 24 27 35 43 51 59 67 80 98

🔹 Average Turnaround Time 平均周转时间：

\[ \boxed{51.83 \text{ ms}} \]

✅ 中文解释 Chinese Explanation

  • 这个多级反馈队列策略优先调度短作业，每轮时间片用完就下调优先级。
  • Queue 0 给每个进程最多 4ms；没完成就移到 Queue 1（8ms）；Queue 1 仍未完成的作业转入 Queue 2，采用 FCFS。
  • 所有作业到达时间是 0，因此 turnaround time 就等于完成时间。

进程PV问题

✅ 问题 Problem

Consider the following 3-process concurrent program using semaphores S1, S2, and S3 with classical P/V operations:

1
2
3
4
5
Process 1         Process 2         Process 3
L1: P(S3);        L2: P(S1);        L3: P(S2);
    print("T");       print("U");       print("B");
    V(S2);            V(S3);            V(S1);
    goto L1;          goto L2;          goto L3;

(1) Suppose the initial values are S1 = 0, S2 = 0, S3 = 0. Is it possible for the processes to cooperate to produce a string that begins with BBTTUTT? Explain. (2) Are there initial values that can be given to the semaphores so that the processes cooperate to print the string BUTBUTBUTBU? If so, provide the values and explain.

✅ 答案与解释 Answer & Explanation

🔹 (1) Can BBTTUTT be printed with S1 = S2 = S3 = 0?

❌ Answer: Not possible

✅ 中文解释：

初始值为 S1=S2=S3=0，所有信号量都为 0，所以：

  • P(S3)：Process 1 会被阻塞
  • P(S1)：Process 2 会被阻塞
  • P(S2)：Process 3 会被阻塞

➡ 所有进程都在等待，系统死锁，没有人能先开始，所以根本不可能输出任何字符，更别说 BBTTUTT。

✅ English Explanation:

Since all semaphores are initialized to 0, all P() operations will block immediately. Thus:

  • Process 1 waits on S3 (blocked)
  • Process 2 waits on S1 (blocked)
  • Process 3 waits on S2 (blocked)

➡ No process can proceed; deadlock occurs. Therefore, it is impossible to begin the output with BBTTUTT.

🔹 (2) Can BUTBUTBUTBU be printed? If so, what initial values?

✅ Answer: Yes, set the initial semaphore values as:

  • S1 = 0
  • S2 = 1
  • S3 = 0

🔄 输出流程（每轮 BUT）：

从 Process 3 开始，因为 S2=1：

  1. P3: P(S2) → ok → print B → V(S1)
  2. P2: P(S1) → ok → print U → V(S3)
  3. P1: P(S3) → ok → print T → V(S2) → 重启循环

每完成一轮 BUT，就重新激活 S2，使 Process 3 可以继续。

这样可以不断重复 BUT，打印出：

1
BUTBUTBUTBU

✅ 中文解释：

设置 S2=1 让 Process 3 先开始（打印 B），然后释放 S1 让 Process 2 打印 U，接着释放 S3 让 Process 1 打印 T，最后再释放 S2，这样下一轮又能从 B 开始。

✅ English Explanation:

By setting S2 = 1, Process 3 starts first. Then it enables Process 2 (by V(S1)), which enables Process 1 (by V(S3)), which finally releases S2 again to start the next cycle. This loop prints BUT repeatedly and correctly.

✅ 总结 Summary

问题 答案 解释
(1) 是否可能打印 BBTTUTT？ ❌ 不可能 全部信号量初值为0，所有进程都阻塞，系统死锁
(2) 是否可能打印 BUTBUTBUTBU？ ✅ 可以 初始值 S1=0, S2=1, S3=0，按顺序形成循环 BUT

文件大小问题

✅ 问题 Problem

A UNIX file system has 2-KB blocks and 32-bit disk addresses. Each i-node contains 10 entries, including one single, one double, and one triple indirect entry. What is the maximum file size?

✅ 答案与解释 Answer & Explanation

1. 文件的基本结构

  • 块大小：2 KB
  • 磁盘地址大小：32 位（即每个磁盘地址指向一个 2 KB 的块）

每个 i-node 包含 10 个条目，其中：

  • 直接条目：可以直接指向文件的 2 KB 数据块
  • 单重间接条目：指向一个包含 2 KB 的块地址的块，每个块地址指向另一个数据块
  • 双重间接条目：指向一个块，块内包含 2 KB 的块地址，每个地址指向一个单重间接块
  • 三重间接条目：指向一个块，块内包含 2 KB 的块地址，每个地址指向一个双重间接块

2. 计算最大文件大小

直接块：

每个直接条目可以指向一个 2 KB 的数据块。i-node 中有 7 个直接条目，所以：

  • 直接块总大小 = 7 × 2 KB = 14 KB

单重间接块：

单重间接条目指向一个块，每个块内有 2 KB 地址，每个地址指向一个数据块。所以可以访问的块数量是：

  • 每个块的大小 = 2 KB
  • 每个地址的大小 = 4 字节（32 位）
  • 每个块可以容纳 2 KB / 4 字节 = 512 个地址

因此，单重间接块可以指向 512 个数据块，每个数据块大小为 2 KB，所以单重间接块的总大小为：

  • 单重间接块总大小 = 512 × 2 KB = 1024 KB = 1 MB

双重间接块：

双重间接条目指向一个块，每个块内有 512 个地址，每个地址指向一个单重间接块。每个单重间接块可以指向 512 个数据块，因此双重间接块可以指向的总数据块数为：

  • 双重间接块总块数 = 512 × 512 = 262,144 个数据块
  • 双重间接块总大小 = 262,144 × 2 KB = 524,288 KB = 512 MB

三重间接块：

三重间接条目指向一个块，每个块内有 512 个地址，每个地址指向一个双重间接块。每个双重间接块可以指向 262,144 个数据块，因此三重间接块可以指向的总数据块数为：

  • 三重间接块总块数 = 512 × 262,144 = 134,217,728 个数据块
  • 三重间接块总大小 = 134,217,728 × 2 KB = 268,435,456 KB = 256 GB

3. 最大文件大小

最大文件大小等于所有可用空间的总和：

  • 直接块大小 = 14 KB
  • 单重间接块大小 = 1 MB
  • 双重间接块大小 = 512 MB
  • 三重间接块大小 = 256 GB

因此，最大文件大小为： 14 KB + 1 MB + 512 MB + 256 GB = 256.511 GB

✅ 结论 Conclusion

  • 最大文件大小：256.511 GB

✅ 中文总结 Summary

  • 直接块：7 个块，每个 2 KB，总计 14 KB
  • 单重间接块：1 MB
  • 双重间接块：512 MB
  • 三重间接块：256 GB

总文件大小 = 14 KB + 1 MB + 512 MB + 256 GB = 256.511 GB