操作系统2012

选择题

1. ( )

英文题目：Device controller informs CPU that it has finished its operation by causing a/an _____. 中文题目：设备控制器通知 CPU 它已完成操作，是通过引发一个 _____ 实现的。

选项：

A. DMA request（DMA 请求）
B. interrupt（中断）✅
C. trap（陷阱）
D. message（消息）

✅ 答案：B. interrupt 中断 📘 解释：设备完成 I/O 操作后，会向 CPU 发送一个 中断（interrupt），表示操作已完成，从而触发 CPU 的相应处理。

2. ( )

英文题目：When a process is created using the classical fork() system call, which of the following is not inherited by the child process? 中文题目：当一个进程使用传统的 fork() 系统调用创建时，以下哪个不会被子进程继承？

选项：

A. process address space（进程地址空间）
B. process ID（进程号）✅
C. user ID（用户 ID）
D. open files（打开的文件）

✅ 答案：B. process ID 📘 解释：fork() 会创建子进程，除了进程号不同外，其余资源（如地址空间、用户 ID、打开文件等）都是继承的。子进程拥有不同的进程 ID（PID），这是区分父子进程的关键。

3. ( )

英文题目：A 128-MB memory is allocated in units of n bytes. We use a linked list to keep track of free memory. Assume memory has alternating segments and holes, each 64KB. Each node in the linked list needs:

a 32-bit memory address,
a 16-bit length field,
a 16-bit next pointer. How many bytes of storage are required for the linked list method?

中文题目：128MB 的内存按 n 字节为单位分配，我们使用链表追踪空闲内存。假设内存是段和空洞交替，每段/空洞大小为 64KB。每个链表结点需要：

32 位地址，
16 位长度字段，
16 位下一个结点指针。问：链表管理共需要多少字节的存储？

选项：

A. 227/n
B. 224/n
C. 2¹¹
D. 2¹⁴ ✅

✅ 答案：D. 2¹⁴ = 16384 bytes（16KB） 📘 解释：

内存大小 = 128 MB = 128 × 2²⁰ 字节
每段 + 空洞 = 64KB ⇒ 每对占 128KB ⇒ 总共有 128MB / 128KB = 1024 对段+洞，共 1024 个空洞（每个都需要链表结点）
每个结点占：32 + 16 + 16 = 64 bits = 8 bytes
所以链表总开销 = 1024 × 16 = 16384 bytes = 2¹⁴ bytes

4. ( )

英文题目：Which of the following process scheduling algorithms has convoy effect? 中文题目：下列哪种进程调度算法存在 护航效应（convoy effect）？

选项：

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

✅ 答案：A. FCFS 📘 解释：FCFS 中如果一个慢进程在前面运行，后面的所有进程（即使很短）也要等待，导致所谓的“护航效应”——快进程被慢进程拖慢。

5. ( )

英文题目：If in a resource-allocation graph, each resource type has exactly one instance, which of the following indicates a deadlock situation? 中文题目：如果资源分配图中每种资源类型只有一个实例，以下哪种情况表示系统发生了死锁？

选项：

A. The graph has at least one cycle（图中至少存在一个环）✅
B. The graph has no cycle（图中没有环）
C. The graph is connected（图是连通的）
D. The graph is not connected（图不连通）

✅ 答案：A. The graph has at least one cycle 📘 解释：

如果每种资源只有一个实例（即不可重入），“存在环 = 死锁”。
在一般情况（资源有多个实例）时，环只是“可能”死锁。

6. ( )

英文题目：The spooling technique is often used to prevent deadlock to attack the ______ condition. 中文题目：SPOOLING 技术常用于防止死锁，它主要用于破坏哪个死锁条件？

选项： A. mutual exclusion（互斥） B. hold and wait（占有且等待）✅ C. no preemption（不可抢占） D. circular wait（循环等待）

✅ 答案：B. hold and wait 占有且等待 📘 解释：Spooling 是将 I/O 请求写入磁盘排队处理的技术。由于进程不会立即占用设备，而是等待资源可用，这打破了“占有并等待”这一死锁条件，从而防止死锁。

7. ( )

英文题目：Which of the following is not the advantage of segmentation with paging? 中文题目：以下哪项不是“分页结合段式管理”的优点？

选项： A. User can have a clear logical view of memory（用户拥有清晰的内存逻辑结构） B. Different access protections can be associated with different segment of memory（每段内存可有不同访问权限） C. No external fragmentation（无外部碎片） D. More efficient in time than pure fragmentation and pure paging（比纯分页或纯分段在时间上更高效）✅

✅ 答案：D. More efficient in time than pure fragmentation and pure paging 📘 解释：段页式系统优点包括逻辑结构清晰、支持访问控制、无外部碎片。但它的实现更复杂、性能开销更大，所以时间效率通常比单一机制差。 👉 选项 A 实际上是优点，正确选项是 D，不是 A。

8. ( )

英文题目：“Device independence” means ________. 中文题目：“设备无关性（Device Independence）”是指 ________。

选项： 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 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 📘 解释：“设备无关性”表示无论是文件还是设备，都能通过相同的系统调用进行访问。这增强了程序的可移植性和一致性。

9. ( )

英文题目：The purpose of current directory is ______. 中文题目：当前目录（current directory）的作用是？

选项： A. saving auxiliary storage space（节省辅存空间） B. saving main memory space（节省主存空间） C. speeding up the file retrieval speed（加快文件检索速度） D. speeding up the file access speed（加快文件访问速度）✅

✅ 答案：D. speeding up file access speed 加快文件访问速度 📘 解释：当前目录的设置使得用户或程序可以通过相对路径而非绝对路径访问文件，从而减少路径解析时间，提高访问效率。

10. ( )

英文题目：Assume the reference count of file F1 is 1 initially. Then:

Create symbolic link F2 → F1
Create hard link F3 → F1
Delete F1

Now, what are the reference counts of F2 and F3 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 📘 解释：

符号链接（symbolic link）不是实际的引用，只是路径映射，因此不影响引用计数
硬链接（hard link）会增加引用计数
删除 F1 时，F2 指向的目标丢失（悬挂符号链接），F3 仍然引用原始数据 👉 所以：F2 = 0（悬挂链接），F3 = 1（硬链接）

11. ( )

英文题目：A device driver is ______. 中文题目：设备驱动程序（device driver）是指什么？

选项： A. a type of system call（系统调用的一种） B. the part of a device that allows to physically function（使设备物理运作的部分） C. a feature of a hardware device that helps it interact with the OS（硬件设备的一种功能） D. a software routine that interfaces with a hardware device（与硬件设备交互的软件程序）✅

✅ 答案：D. a software routine that interfaces with a hardware device 📘 解释：设备驱动程序是一种软件模块，作用是让操作系统能与硬件设备通信，例如打印机、磁盘等。它翻译系统调用为设备操作。

12. ( )

英文题目：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. 中文题目：当页表项表示该页不在内存中时，会产生一种异常，用来通知操作系统将页面调入内存，这种异常是 ______。

选项： A. page fault（缺页异常）✅ B. trap（陷阱） C. array index out of bound（数组越界） D. none of the above（以上都不是）

✅ 答案：A. page fault 缺页异常 📘 解释：当访问的页面不在主存中，页表会触发page fault（缺页异常），操作系统响应该异常，执行调页操作将数据从磁盘读入内存。

13. ( )

英文题目：Batching of jobs improved early system performance by ______. 中文题目：早期操作系统中，批处理作业（batching）的引入改善了系统性能，其原因是 ______。

选项： A. reducing human setup time（减少人工设置时间）✅ B. background processing（后台处理） C. multiprogramming（多道程序） D. overlapping CPU and I/O operations（重叠 CPU 与 I/O 操作）

✅ 答案：A. reducing human setup time 📘 解释：在批处理系统中，多个作业连续自动运行，无需频繁人工干预（如卡片输入、启动），显著减少了人工设置时间，提高系统吞吐量。

14. ( )

英文题目：A counting semaphore was initialized to 4. Then 28 P (wait) operations and 18 V (signal) operations were completed. Assume the resulting value of the semaphore is 0. What is the number of waiting processes? 中文题目：一个计数型信号量初始值为 4，之后进行了 28 次 P 操作和 18 次 V 操作。已知当前信号量值为 0。问：有多少个进程处于等待状态？

选项： A. 2 B. 3 C. 6 ✅ D. 0

✅ 答案：C. 6 📘 解释：

初始值 = 4
实际 P 操作 = 28（使信号量减少）
实际 V 操作 = 18（使信号量增加）
设最终有 x 个进程在等待，即阻塞

根据信号量变化公式： 最终值 = 初始值 + V 次数 - P 次数 + 阻塞恢复次数 0 = 4 + 18 - 28 + x ⇒ x = 6 所以有 6 个进程正在等待。

15. ( )

英文题目：As for Unix system, the attributes of file are stored in ______. 中文题目：在 Unix 系统中，文件的属性存储在哪里？

选项： A. file（文件本身） B. directory（目录） C. i-node ✅ D. direct（直接块）

✅ 答案：C. i-node 📘 解释：在 Unix 文件系统中，文件的所有元信息（如权限、大小、创建时间、数据块位置）都存储在 i-node（索引节点）中，而不是文件本体或目录项中。目录项只包含文件名和对应的 i-node 号。

简答题

1. (5 分/pts)

英文题目：List the advantages and disadvantages of using a small page in a virtual memory system. 中文题目：请列举在虚拟内存系统中使用小页面（small page）的优点和缺点。

✅ 答案 / Answer：

(1) 优点 / Advantages：

✅ Less internal fragmentation ➤ 较少的内部碎片：因为每页更小，分配的空间更接近实际需要，减少浪费。
✅ Less unused program in memory ➤ 减少内存中未使用的程序部分：只需加载所需小部分程序到内存，节省空间。

(2) 缺点 / Disadvantages：

❌ Programs need many pages ➤ 程序需要更多页面：小页面意味着一个程序被分成更多片段。
❌ Larger page tables ➤ 页表更大：更多页面意味着页表项数量增加，占用更多内存并降低访问效率。

📘 总结 / Summary：

优点	缺点
内部碎片更少	页表更大
加载更精细、节省内存	程序被划分成更多页

2. (5 分/pts)

英文题目：What is a process? What is a thread? How are they similar and different? 中文题目：什么是进程（process）？什么是线程（thread）？它们有哪些相同点和不同点？

✅ 答案 / Answer：

Process（进程）： ➤ A program in execution ➤ 正在运行的程序，是操作系统资源分配和调度的基本单位。
Thread（线程）： ➤ A flow of control within a process ➤ 进程内部的执行控制流，共享进程的资源。

🟰 相同点 / Similarities：

都是操作系统中活动的实体（active entities）
都具有一组执行属性（如状态、指令计数器、寄存器等）
都消耗 CPU 和内存等系统资源

🔀 不同点 / Differences：

项目	Process（进程）	Thread（线程）
重量级	是，开销大（heavyweight）	否，开销小（lightweight）
资源	拥有独立的资源空间	共享进程资源（如内存）
调度	独立调度单元	由进程统一管理

📘 总结语 / Summary：

进程（process） 是资源分配的单位，每个进程有自己的地址空间。
线程（thread） 是CPU 调度的单位，多个线程共享一个进程的资源。
多线程比多进程更轻量，但也更容易出现资源共享冲突。

3. (5 分/pts)

英文题目：What are the advantages and disadvantages of using FAT (File Allocation Table) in implementing files? And how can we deal with these shortcomings?

中文题目：在实现文件系统时，使用 FAT（文件分配表） 有哪些优点和缺点？我们可以如何处理它的这些缺点？

✅ 答案 / Answer：

🔹 (1) 优点 / Advantages：

✅ The entire block is available for data ➤ 整块空间可用于数据，FAT 将所有指针集中到表中，数据块中没有元数据，空间利用率高。
✅ Random access is possible ➤ 支持随机访问，可以通过链式方式按序遍历文件块，找到任意位置。
✅ Directory entry needs only one number ➤ 目录项只需要一个数字（起始块号），简化目录结构管理。

🔻 (2) 缺点 / Disadvantages：

❌ Entire table must be in memory at once ➤ 整个 FAT 表必须一次性加载到内存中，在大磁盘或大量文件情况下占用内存严重，影响性能。

🛠️ 改进方法 / How to deal with it：

✅ 使用 Indexed Allocation（索引分配） 方法。
将所有指针集中到一个位置（索引块或i-node）。
只有在打开对应文件时，才将相关 i-node 加载进内存，从而节省内存并提高性能。

4. (5 分/pts)

英文题目：Disk requests come in to the disk driver for cylinders: 86, 147, 18, 95, 151, 12, 175, 30, in that order. The arm is initially at cylinder 143. What is the total distance (in cylinders) that the disk arm moves to satisfy all the requests, for:

(1) Shortest Seek First (SSF)
(2) Elevator (SCAN) Algorithm (Assume the arm is initially moving toward cylinder 0)

中文题目：磁盘调度时，磁头请求访问以下柱面： 86、147、18、95、151、12、175、30（按此顺序到达）。磁头初始位置在柱面 143。求磁头在以下调度算法下的总移动距离（柱面数）：

(1) 最短寻道优先（Shortest Seek First, SSF）
(2) 电梯算法（SCAN），假设磁头初始向 0 方向移动

✅ 答案与解释 / Solution & Explanation：

➤ (1) Shortest Seek First (SSF)

每次选择离当前位置最近的请求：

访问顺序（从 143 开始）：

1	143 → 147 → 151 → 175 → 95 → 86 → 30 → 18 → 12

计算移动距离：

1 2	\|143-147\| + \|147-151\| + \|151-175\| + \|175-95\| + \|95-86\| + \|86-30\| + \|30-18\| + \|18-12\| = 4 + 4 + 24 + 80 + 9 + 56 + 12 + 6 = ✅ 195 柱面

➤ (2) SCAN (Elevator) 算法

磁头从 143 开始向 0 移动，访问所有比它小的请求，然后掉头向大方向访问剩余请求：

访问顺序：

1	143 → 95 → 86 → 30 → 18 → 12 → 147 → 151 → 175

计算移动距离：

1 2	\|143-95\| + \|95-86\| + \|86-30\| + \|30-18\| + \|18-12\| + \|12-147\| + \|147-151\| + \|151-175\| = 48 + 9 + 56 + 12 + 6 + 135 + 4 + 24 = ✅ 294 柱面

📘 总结 / Summary：

算法	总移动距离（柱面数）
SSF（最短寻道优先）	✅ 195
SCAN（电梯算法）	✅ 294

隧道通行问题 / Tunnel Synchronization Problem

题目 / Problem：

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

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

(1)（4 分）

Passengers go through the tunnel one by one alternately from two directions.

从两个方向来的行人交替地一个一个通过隧道。

(2)（6 分）

The passengers at one direction must pass the tunnel continuously. Another direction’s passengers can start to go through the tunnel only when no passengers want to pass the tunnel from the opposite direction.

某一方向的行人连续地通过隧道，而另一方向的行人只能在对面没人时才可以通行。

✅ 答案 / Solution：

▶️ 设定说明 / Definitions：

将两个方向分别标记为 A 方向 和 B 方向
使用信号量和计数变量控制访问隧道的权限

(1) Alternating Access / 交替通行

✅ 设置信号量：

AB：表示 A 方向行人是否可以通行，初值为 1
BA：表示 B 方向行人是否可以通行，初值为 1
mutex：互斥访问隧道（确保同一时刻只有一个人），初值为 1

✅ A方向行人代码：

P(AB);          // 等待 A 方向的许可
P(mutex);       // 占用隧道资源
  通过隧道；
V(mutex);       // 释放隧道资源
V(BA);          // 允许 B 方向行人通行

✅ B方向行人代码：

P(BA);          // 等待 B 方向的许可
P(mutex);       // 占用隧道资源
  通过隧道；
V(mutex);       // 释放隧道资源
V(AB);          // 允许 A 方向行人通行

✅ 解释 / Explanation：

AB 和 BA 信号量交替控制两个方向的通行权。
每一名行人通行完后会唤醒对方方向的行人，实现交替通行。

(2) One-direction Priority / 一方优先通行

✅ 设置变量：

countA：表示当前隧道中 A 方向的行人数（初值 = 0）
countB：表示当前隧道中 B 方向的行人数（初值 = 0）

✅ 设置信号量：

SA：互斥访问 countA（初值 = 1）
SB：互斥访问 countB（初值 = 1）
mutex：控制隧道访问（初值 = 1）

✅ A方向行人代码：

P(SA);
  if (countA == 0) P(mutex);  // 首个 A 方向行人占用隧道
  countA++;
V(SA);

  通过隧道；

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

✅ B方向行人代码：

P(SB);
  if (countB == 0) P(mutex);  // 首个 B 方向行人占用隧道
  countB++;
V(SB);

  通过隧道；

P(SB);
  countB--;
  if (countB == 0) V(mutex);  // 最后一个 B 行人释放隧道
V(SB);

✅ 解释 / Explanation：

某一方向行人可以连续通行，直到该方向不再有人要通过时，才释放隧道使用权。
对方只能在隧道空闲（countA == 0 或 countB == 0）时重新占用。
避免了交替干扰，但仍实现互斥访问。

✅ 总结 / Summary：

模式	中文说明	技术实现
(1) 交替通行	两个方向轮流通过	使用两个互斥信号量 AB 和 BA 控制交替
(2) 一方优先	同一方向连续通过，另一方向等到无人	使用计数变量和互斥信号量，保护隧道访问

多级反馈队列调度（Multi-level Feedback Queue Scheduling）

✅ 题目 / Problem

Show your schedule with timeline and calculate the average turnaround time when using the multi-level feedback queue below. Take arrival time into account. Note that the priority of the top 2 queues is based on arrival times.

请使用多级反馈队列调度算法完成以下进程调度，并画出时间线，计算平均周转时间（Turnaround Time）。注意：要考虑进程的到达时间，并且前两个队列按到达顺序（Arrival Time）优先处理。

进程信息 / Process Info

Process ID	Arrival Time	Burst Time
A	0	7
B	2	9
C	5	4
D	7	8
E	8	2

✅ 解题思路 / Solution Idea

我们使用一个典型的三层多级反馈队列示例：

Queue Level	Time Quantum	Scheduling Policy
Q1 (highest)	3 units	FCFS (by arrival)
Q2	4 units	FCFS
Q3 (lowest)	unlimited	FCFS

调度规则如下：

进程初次进入 Q1，最多执行 4 单位时间。
若未完成，进入 Q2，再执行最多 6 单位时间。
若还未完成，则进入 Q3，一直执行直至结束。
每次选择优先级最高的队列中最早到达的进程执行。

死锁问题

系统中资源和进程如下：

资源情况：
- A：2 个实例
- B：3 个实例
- C：3 个实例
进程情况：
- P1：持有 1 个 B 和 1 个 C，等待 1 个 A。
- P2：持有 1 个 A，等待 1 个 B。
- P3：持有 1 个 A、2 个 B、1 个 C。

✅ (1) 资源分配图（Resource Allocation Graph）

英文解释：

Circles represent Processes (P1, P2, P3)
Squares represent Resources (A, B, C)
Dots inside the square represent instances
Arrows from process to resource mean requesting
Arrows from resource instance to process mean allocated

中英文说明图形结构：

✅ (2) 每个进程的状态（Process States）

Process	状态（State）	等待资源（Waiting For）
P1	Waiting 等待	Resource A（资源 A）
P2	Waiting 等待	Resource B（资源 B）
P3	Runnable 就绪	无需等待任何资源（Has all it needs）

解释：

P1 持有 B 和 C，但还在等 A。
P2 持有 A，但在等 B。
P3 拥有 A、B 和 C 的资源实例，已准备好运行。

✅ (3) 系统是否处于死锁状态？（Deadlock?）

答案 Answer：❌ No，系统没有处于死锁状态

英文解释：

Deadlock requires a cycle of processes waiting on each other.
Although P1 and P2 are both waiting, P3 is runnable and can complete, then release A, B, and C.
Once P3 releases resources, P1 can get A, and P2 can get B, so the system can proceed.

中文解释：

死锁的必要条件是形成循环等待，所有进程都相互等待，且没有一个能继续执行。
当前虽然 P1 等 A，P2 等 B，但 P3 不等待任何资源，它可以运行，释放资源。
一旦 P3 释放资源，P1 就能获得 A，P2 也能获得 B，系统可以继续运行。
✅ 所以：不是死锁状态。

✅ 总结（Summary）

问题	答案
(1) 资源分配图	见文字说明（也可要求画图）
(2) 状态	P1 和 P2 等待，P3 就绪
(3) 死锁？	❌ 没有死锁，P3 可运行并释放资源

虚拟内存页表大小与层次页表（Virtual Memory Page Table Size and Feasibility）

❓题目 (Problem)

考虑以下虚拟内存系统参数：

虚拟地址长度：44位（字节寻址）
页大小：4KB
物理地址长度：40位（字节寻址）
每个页表项（PTE）包含：物理页号 + 额外的4位（有效位、保护位、修改位、使用位）
所有虚拟页都在使用中（即页表中每个项都有效）

🔹(1) What is the total size of the page table?

🔹(1) 每个进程的页表总大小是多少？

✅ 解答 (Solution)

👉 Step 1: 页大小 = 4KB = 2¹² 字节

⇒ 页内偏移占 12 位

👉 Step 2: 虚拟地址空间为 44 位

所以虚拟页号部分占：44 - 12 = 32 位
即：虚拟页的总数为 2³² 个

👉 Step 3: 每个页表项（PTE）的大小

物理地址是 40 位，其中页内偏移为 12 位
所以物理页号大小为 40 - 12 = 28 位
加上额外的 4 位（有效、保护、脏、使用位）
所以：每个 PTE = 28 + 4 = 32 位 = 4 字节

👉 Step 4: 页表大小

总页数 = 2³²
每个页表项 4 字节
页表总大小 = 2³² × 4 字节 = 2³⁴ 字节 = 16 GB

✅ 答案 (Answer)

Page table size = 2³² × 4 Bytes = 2³⁴ Bytes = 16 GB per process

页表大小为每个进程 16GB

🔹(2) 为什么这样表示页表不可行？层次页表是否解决了这个问题？

🔹Why might it be infeasible to represent a page table as in (a)? Do hierarchical page tables resolve the issue?

✅ 解答 (Solution)

❗问题（Problem）：

每个进程的页表需要 16 GB 内存，这对于大多数系统而言是不现实的。
多个进程同时运行时，这种内存开销极高。

✅ 层次页表的解决方案（Hierarchical Page Tables Help）：

层次页表将页表分为多级结构，只有实际使用的页才会在页表中分配项。
不活跃或未使用的虚拟页段不需要映射项 ⇒ 节省空间。

✅ 示例（Example）：

一个两级页表可将 32 位虚拟页号分成 2 个 16 位段：
- 第一级：页目录（Page Directory）
- 第二级：页表（Page Table）
只有访问到某段虚拟地址时，才会实际分配那一段的页表项。

✅ 答案 (Answer)

It's infeasible because the page table per process is 16 GB, which is too large for practical systems. Hierarchical page tables reduce this by allocating space only for used virtual pages, so they can save a lot of memory.

中译：由于每个进程的页表需要 16GB 内存，这是非常大的开销，因此不可行。使用层次页表可以解决这个问题，因为它们只为被使用的虚拟页分配映射项，从而节省大量空间。

✅ 总结（Summary）

项目	答案
(1) 页表大小	2³² × 4 字节 = 16 GB
(2) 可行性	❌ 不可行，开销过大
(2) 层次页表	✅ 解决问题，仅存活页分配，节省空间

i-node 结构与磁盘块空间占用分析（i-node & Disk Block Calculation）

❓题目 (Problem)

一个文件系统使用以下设置：

每个磁盘块大小：2KB
每个 i-node 包含：
- 8 个直接索引（direct entries）
- 1 个一级间接索引（single indirect）
- 1 个二级间接索引（double indirect）
每个指针大小为 4 字节
问题：
1. 最大文件大小是多少？
2. 一个 128MB 的文件 实际占用了多少磁盘空间（包括所有索引块）？

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

🔹(1) 该文件系统允许的最大文件大小是多少？

✅ 解答 (Solution)

我们来分别计算：

✅ 1️⃣ 直接索引块：

每个 block 为 2KB，总共 8 个
总容量：8 × 2KB = 16KB

✅ 2️⃣ 一级间接块（single indirect）：

每个指针占 4 字节，2KB block 可容纳：2048 ÷ 4 = 512 个指针
指向的数据块容量：512 × 2KB = 1024KB = 1MB

✅ 3️⃣ 二级间接块（double indirect）：

一级索引块有 512 个指针 → 每个指向一个二级块
每个二级块也有 512 个指针
总数据块数：512 × 512 = 262,144 个数据块
数据容量：262,144 × 2KB = 524,288KB = 512MB

✅ 4️⃣ 总最大文件大小：

1 2	= 直接块容量 + 一级间接容量 + 二级间接容量 = 16KB + 1MB + 512MB ≈ 513MB + 16KB

✅ (1) 答案 (Answer)

Maximum file size ≈ 512MB + 1MB + 16KB ≈ 约 513MB

最大文件大小约为 513MB

🔹(2) How much disk space does a 128MB file actually occupy (including index blocks)?

🔹(2) 一个 128MB 文件 实际占用了多少磁盘空间？（包括所有直接和间接索引块）

✅ 解答 (Solution)

我们来逐步计算：

✅ 1️⃣ 文件大小：128MB = 128 × 1024 KB = 131072 KB

✅ 2️⃣ 数据块数：

每块 2KB ⇒ 131072 ÷ 2 = 65536 块数据

🔸我们还需要多少索引块？

✅ A. 直接块：8 块（最多可表示 16KB 数据）

数据还剩：131072 KB - 8×2KB = 131056 KB

✅ B. 一级间接块：512 块（表示 1MB 数据）

数据还剩：131056 KB - 1024 KB = 130032 KB
使用了 1 个间接索引块 + 512 个数据块

✅ C. 二级间接块：

需要的数据块数：130032 ÷ 2KB = 65016 块
一个二级块可表示 512 个数据块
需要二级块数：ceil(65016 ÷ 512) ≈ 128 个二级块
对应的一级指针块也需要 128 个（因为每个一级块指向一个二级块）

✅ 总额外索引块数（用于存储索引信息）：

类型	数量	大小
直接指针	8	已含在 i-node 中
一级间接指针块	1	2KB
一级块指向的数据块	512	已计入数据块
二级间接块	1	2KB
二级的一级指针块	128	128 × 2KB = 256KB
所有二级指针块指向的数据块	65016	已计入数据块