CSCI3150 Assignment 2 · 详细解析

课程：Introduction to Operating Systems 原题：assignment2.pdf（本地课件），PDF p.1–3；截止时间为 2026-10-28 23:59（香港时间） 用途：完整解释文件块寻址、目录项填写与绝对路径查找。 覆盖：Q1(a)、Q1(b)(i)–(iv)、Q2(a) 的五个数据块、Q2(b)。 约定：块大小严格取原题 4096 bytes；文件内字节偏移和逻辑块编号均从 0 开始。四次读取独立作答，按题目给出的读取长度处理。

题号导航：Q1(a) · Q1(b) · Q2(a) · Q2(b)

Question 1：公共题干与映射

题面（assignment2.pdf · Q1 · p.1）

p.1 Figure 1 shows the inode of a file in the Simple File System (SFS) and the contents of its indirect block. Both have already been read into memory. Each data block is 4 KB (4096 bytes). Each cell of the indirect block is 4 bytes.

图（p.1）：Inode and indirect block of an SFS file. 元素：inode 的 direct_blk[0] 为 6，direct_blk[1] 为 11，indirect_blk 为 30；数据块 30 中的 Cell 0–12 存放下表所列的数据块号，后面还有未画出的单元。 看什么：两个直接指针指向文件的前两个块；间接指针指向存放块号的索引块，再由该索引块找到后续文件内容。图中的省略号不能理解为未展示的双重或三重间接指针。

表（题面，p.1）：inode 中展示的块指针

表（题面，p.1）：间接数据块 30 的内容

需要区分两个编号：逻辑块号是这个块在文件内的顺序，磁盘数据块号是它在磁盘上的位置。例如文件内逻辑块 2 不是磁盘块 2；它经过 Cell 0 映射到磁盘块 34。

Question 1(a)：最大文件大小

题面（assignment2.pdf · Q1(a) · p.1）

p.1 (a) (10 marks) What is the maximum size of a single file in this SFS?

先计算一个间接块能放多少个指针，再加上两个直接指针所能表示的文件内容。

间接块共 4096 字节，一个 Cell 占 4 字节，所以指针数为：

每个指针都能指向一个 4096 字节的文件数据块，因此最多有：

最大文件大小：

答案：4,202,496 bytes，即 4104 KiB，也就是 4 MiB + 8 KiB。 题目用 KB 指 1024 字节；这里写 KiB 以消除单位歧义。

验算：间接部分为 1024 × 4096 = 4,194,304 字节，直接部分为 2 × 4096 = 8192 字节，两者相加为 4,202,496 字节。数据块 30 自己的空间存的是指针，不是用户文件内容，所以不额外加 4096 字节。

这与课件 L05 的单级间接索引方法一致，但课件 p.13 的例子使用 12 个直接指针，本题只有 2 个，不能照抄课件的数字。

Question 1(b)：每次读取哪些文件数据块

题面（assignment2.pdf · Q1(b) · p.1）

p.1 (b) (40 marks) A user program calls read_t(inum, offset, buf, count), which reads count bytes of the file starting at byte offset. Here inum is the inode number of the file in Figure 1, and buf points to a user-defined buffer. offset and count are in bytes.

For each call below, list the numbers of the data blocks that are read from disk, in the order they are read. List only the data blocks that contain file data.

表（题面，p.1）：原题给出的调用与示例

通用方法：先求文件内范围，再映射磁盘块

设起始偏移为 $o$，读取长度为 $c$，块大小为 $B=4096$。由于起始字节本身就算第一个字节，读取的最后一个字节为 $o+c-1$。首尾逻辑块分别为：

取从首块到尾块的全部逻辑块，再换成磁盘块号。逻辑块 0、1 使用直接指针；逻辑块 $k\ge2$ 使用间接块中的 Cell $k-2$。

下面的表由原题数据推导，不是新增题设：

补充：为什么末端用减一而不是直接除。 正长度读取覆盖从起点 s 开始的 n 个字节，其下标依次是 s、s+1，直到 s+n−1；因此末块由最后这个字节的位置决定。若误用 s+n，恰好在块边界结束的读取会多算下一块。也可以使用半开区间 [s,s+n)，明确右端只是停止位置，并不被读取。

这里的块号先是文件内部的逻辑编号，再通过题面映射表变成磁盘数据块号。题目列的数据块号不连续，所以不能从第一个磁盘块号出发连续加一。每次独立读取都重新按给定偏移计算，不能偷偷沿用上一小问的结束偏移。若读取长度为零则区间为空，不能使用带 n−1 的正长度公式；本题各问长度为正，所以主解法无须增加这个分支。

(i) 从偏移 130 读取 10000 字节

题面（assignment2.pdf · Q1(b)(i) · p.1）

p.1 (i) read_t(inum, 130, buf, 10000);

末字节是 130 + 10000 − 1 = 10129，故读取范围为 130–10129。

读取逻辑块 0、1、2；按映射表，对应磁盘块 6, 11, 34。

验算每块实际贡献：块 6 提供 4096 − 130 = 3966 字节，块 11 提供完整的 4096 字节，块 34 提供 10129 − 8192 + 1 = 1938 字节。总计 3966 + 4096 + 1938 = 10000 字节。

(ii) 从偏移 6000 读取 26000 字节

题面（assignment2.pdf · Q1(b)(ii) · p.1）

p.1 (ii) read_t(inum, 6000, buf, 26000);

末字节是 6000 + 26000 − 1 = 31999，故读取范围为 6000–31999。

依次读取逻辑块 1、2、3、4、5、6、7。逻辑块 1 使用第二个直接指针，之后使用 Cell 0–5。

答案：11, 34, 36, 40, 45, 46, 49。

验算：首块提供 8192 − 6000 = 2192 字节，中间逻辑块 2–6 共五个完整块，尾块提供 32000 − 28672 = 3328 字节。总计 2192 + 5 × 4096 + 3328 = 26000 字节。块 6 对应文件开头的逻辑块 0，这次读取不经过它。

(iii) 从偏移 4096 读取 8192 字节

题面（assignment2.pdf · Q1(b)(iii) · p.1）

p.1 (iii) read_t(inum, 4096, buf, 8192);

末字节是 4096 + 8192 − 1 = 12287。

这是完整读取逻辑块 1 和 2，各 4096 字节，总计 8192 字节。

答案：11, 34。

易错点：12288 是读取区间之后的第一个字节，不是本次要读的字节。如果把尾块算成 floor((offset + count) / 4096)，会错误地再列出磁盘块 36。

(iv) 从偏移 16384 读取 40960 字节

题面（assignment2.pdf · Q1(b)(iv) · p.1）

p.1 (iv) read_t(inum, 16384, buf, 40960);

末字节是 16384 + 40960 − 1 = 57343。

读取逻辑块 4–13，共 13 − 4 + 1 = 10 块；在间接块中对应 Cell 2–11。

答案：40, 45, 46, 49, 51, 52, 54, 60, 71, 90。

验算：起点 16384 = 4 × 4096，读取长度 40960 = 10 × 4096，因此恰好读取十个完整块，最后一块为逻辑块 13。Cell 12 中的 93 属于下一块，不读取。

Q1(b) 最终填写表

四行都不列 30：原题明确 inode 和间接块已在内存，而且只要求含文件内容的数据块。这里也不把四行当作同一程序连续读取并累积缓存；原题未要求这样的缓存模拟。

Question 2：公共题干与目录树

题面（assignment2.pdf · Q2 · p.2）

p.2 Use the SFS directory hierarchy in Figure 2 for both parts of this question:

/ is the root directory. dir1 through dir13 are directories; file1 through file5 are regular files.

The inode number of / is 0. The inode numbers of dir1 through dir13 are 1 through 13, respectively. The inode numbers of file1, file2, file3, file4, and file5 are 14, 15, 16, 17, and 18, respectively.

Each directory occupies one data block of 4 KB (4096 bytes). Directory / uses data block 0, and dir1 through dir13 use data blocks 1 through 13, respectively.

图（p.2）：Directory hierarchy. Shaded nodes are regular files. 元素：根目录有 dir1、dir2、dir3 和 file1 四个直接孩子；灰色的 file1–file5 是普通文件，其余节点是目录。所有父子连线已在原 PDF 渲染图上逐条核对。 看什么：. 取本节点编号，.. 取上一层父节点编号，普通目录项只记录直接孩子。图上的同一行不代表同一父目录。

示意图（p.2，我画的，非讲义原图）：完整重画原题父子关系；括号内为 inode 号。

/ (0)
├── dir1 (1)
│   └── dir4 (4)
├── dir2 (2)
│   └── dir5 (5)
│       ├── dir7 (7)
│       │   └── file2 (15)
│       └── dir8 (8)
│           ├── dir11 (11)
│           │   └── file3 (16)
│           └── dir12 (12)
├── dir3 (3)
│   └── dir6 (6)
│       ├── dir9 (9)
│       └── dir10 (10)
│           └── dir13 (13)
│               ├── file4 (17)
│               └── file5 (18)
└── file1 (14)

本题中每个目录的数据块号恰好与 inode 号相同，但它们仍是不同对象：inode 记录元数据和块指针，目录数据块存放名称与 inode 号的映射。普通文件的数据块号没有给出，不能拿普通文件的 inode 号冒充其数据块号。

Question 2(a)：填写五个目录块

题面（assignment2.pdf · Q2(a) · p.3）

p.3 (a) (30 marks) Each directory entry is defined by the following C structure:

typedef struct dir_mapping {
    char f_name[20]; /* The file name */
    int i_number;   /* The inode number */
} DIR_NODE;

p.3 Each directory contains at least the two entries . and .., which refer to the directory itself and its parent directory, respectively. The parent of the root directory is itself.

For example, data block 6, belonging to dir6, contains:

表（题面，p.3）：原题给出的数据块 6 示例

p.3 Give the contents of data blocks 0, 1, 5, 8, and 10 in the same format. You may omit the column headers f_name and i_number.

每张表按三步填写：先写 . 指向自己，再写 .. 指向父目录，最后列出直接孩子。题目要求列有效目录项，不需要把 4096 字节中未使用的部分填成虚构条目。

数据块 0：根目录

根目录 inode 是 0；根目录的父目录是自己，所以 . 和 .. 都是 0。其直接孩子为 dir1、dir2、dir3 和 file1；file1 的 inode 是题设指定的 14。

数据块 1：dir1

dir1 的 inode 是 1，父目录为根目录 0，唯一直接孩子是 dir4。

数据块 5：dir5

dir5 的 inode 是 5，父目录为 dir2，因此 .. 是 2。直接孩子是 dir7 和 dir8。file2 虽然在这棵子树里，却属于 dir7，不能直接列在 dir5 下。

数据块 8：dir8

dir8 的 inode 是 8，父目录为 dir5，因此 .. 是 5。直接孩子为 dir11 和 dir12；file3 是 dir11 的孩子，不直接放入本表。

数据块 10：dir10

dir10 的 inode 是 10，父目录为 dir6，因此 .. 是 6。直接孩子只有 dir13；file4、file5 应出现在 dir13 的目录块中。

验算：五张表分别有 6、3、4、4、3 个有效条目，等于各自直接孩子数再加 . 与 .. 两项。每个 .. 均与原图的父边一致。

Question 2(b)：逐层取得 file3 的 inode

题面（assignment2.pdf · Q2(b) · p.3）

p.3 (b) (20 marks) For the absolute path

/dir2/dir5/dir8/dir11/file3

show the sequence of inodes and directory data blocks visited, starting from the root directory /, to obtain the inode number of file3. Give the number of each inode and data block in the sequence.

For example, to obtain the inode number of file1, the sequence is:

inode 0 → data block 0 → inode 14.

题目要的是名称查找过程。每一层先通过当前目录 inode 找到它的目录数据块，再在该块中查下一个名字，取得下一个 inode 号。

答案：

inode 0 → data block 0 → inode 2 → data block 2
→ inode 5 → data block 5 → inode 8 → data block 8
→ inode 11 → data block 11 → inode 16

因此 file3 的 inode 号是 16。路径中不含 . 或 ..，所以虽然这些条目存在，也不额外走它们；同层其他目录不是目标路径的一部分，不展开访问。

验算：路径有五个名称分量，恰好查五个目录数据块，产生五次名称到 inode 的映射。序列按原题示例保留末尾 inode 16。实际上，在数据块 11 中找到 file3 → 16 时就已知道 inode 号；按题目格式列到目标 inode，并不需要继续读取 file3 的文件内容。本题没有给出 file3 的数据块号，也无需猜测。

按小问完成检查

四组读取已用 Python 对每一个请求字节枚举所属块，与首尾公式的结果交叉比对；目录树录入后也运行了路径查找核验。证据保存在 核验记录（本地资料）。

来源与证据

• 原题：assignment2.pdf（本地课件），p.1–3；已提取全文并视觉核对全部三页，尤其是 Figure 1 的 Cell 编号与 Figure 2 的全部父子连线。
• 方法参照：L05-文件系统实现-2022未核.pdf（本地课件），已抽取文本，使用 p.13（单级间接索引）、p.18（目录项）、p.21–22（路径查找与读取）的文字。该文件是历史讲义转换副本；本题的指针数、根 inode 号和数据块号均以当前作业为准。
• 考试证据：读了 assignment2.pdf；未识别用途的 PDF：无