CSCI3150 L05 File System Implementation

课程：CSCI3150 Introduction to Operating Systems · 2022未核 本讲：L05 File System Implementation · 原件 L05-文件系统实现-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.1–28 定位：从磁盘分区布局计算inode地址与多级索引容量，并逐次追踪路径查找和文件读写引起的I/O。 承接：#L04-01 目录映射；#L04-02 描述符与打开状态

p.1 标题页。

从接口进入磁盘上的结构

两个互相配合的问题（p.2–3）【新】

p.3 There are two different aspects to implement file system

Data structures

What types of on-disk structures are utilized by the file system to organize its data and metadata?

Access methods

How does it map the calls made by a process as open(), read(), write(), etc.

Which structures are read during the execution of a particular system call?

p.2 把本讲移动到Persistence中的File System。p.3要求同时回答：数据和元数据放成什么结构，以及一次open/read/write会访问其中哪些结构。前者是静态布局，后者是动态路径。只画出inode却不能说明怎样从文件名找到它，还没有解释完整文件系统。

分块、数据区与inode区（p.4–6）

p.4 Let’s develop the overall organization of the file system data structure.

Divide the disk into blocks.

Block size is 4 KB.

The blocks are addressed from 0 to N -1.

p.5 Reserve data region to store user data

File system has to track which data block comprise a file, the size of the file, its owner, etc.

p.6 Reserve some space for inode table

This holds an array of on-disk inodes.

Ex) inode tables : 3 ~ 7, inode size : 256 bytes

4-KB block can hold 16 inodes.

The filesystem contains 80 inodes. (maximum number of files)

p.4将示例磁盘分成0–63号块。这里的4KB按图中地址计算采用4096字节，因此全盘64×4096=262144字节。p.5把8–63号的56块保留为数据区，共56×4096=229376字节；还必须留下记录这些数据属于谁的元数据。

p.6把3–7号块分给inode表，共5块，每个inode为256字节。算一遍：每块4096÷256=16个inode，5块共80个。80限制可记录的对象数量，并不表示有80个数据块；目录也需要inode，空文件也可能占用inode但没有文件数据块。

图（p.4–6）：磁盘块布局逐步成形 元素：64个格子，块8–63标D，块3–7标I，块1/2预留位图。 看什么：区分存对象属性的inode区和实际承载内容的数据区。

两张位图与超级块（p.7–8）

p.7 This is to track whether inodes or data blocks are free or allocated.

Use bitmap, each bit indicates free(0) or in-use(1)

data bitmap: for data region for data region

inode bitmap: for inode table

p.8 Super block contains this information for particular file system

Ex) The number of inodes, begin location of inode table. etc

Thus, when mounting a file system, OS will read the superblock first, to initialize various information.

p.7用inode bitmap记录哪些inode已用，用data bitmap记录哪些数据块已用。分配inode与分配数据块是两种独立资源，不能只查其中一张表。算一遍：80个inode至少需80位即10字节；56个数据块至少需56位即7字节。本教学布局仍给每张位图整整一个4KB块，简单布局的预留空间不等于最小信息量。

p.8在块0放superblock，记录inode数量、inode表起点等全局参数。挂载先读它，才能知道其他结构在哪，而不是把某张图上的固定偏移当所有文件系统的通用常量。

从inode号算到扇区（p.9–10）【新】

p.9 Each inode is referred to by inode number.

by inode number, File system calculate where the inode is on the disk.

Ex) inode number: 32

Calculate the offset into the inode region (32 x sizeof(inode) (256 bytes) = 8192

Add start address of the inode table(12 KB) + inode region(8 KB) = 20 KB

p.10 Disks are not byte addressable, but sector addressable.

Disk consist of a large number of addressable sectors, (512 bytes)

Ex) Fetch the block of inode (inode number: 32)

Sector address iaddr of the inode block:

blk : (inumber * sizeof(inode)) / blocksize

sector : ((blk * blocksize) + inodeStartAddr ) /sectorsize

p.9给定inode号32，inode表起点12KB，每项256字节。先把对象编号转换成表内字节偏移，再加表起点；p.10再把磁盘字节位置转换为512字节扇区号。公式按讲义重排：

o是inode表内偏移，a是该inode的磁盘字节地址，b是相对inode表的块序号，s是该块起始扇区号。本例32恰好落在块首，所以对象地址与块首地址相同；一般inode还需要块内偏移，不能把两者始终等同。完整定位顺序见附录 A1。

A1 inode32的完整地址换算（p.9–10）

inode表从3号4KB块开始，所以起点为3×4096=12288。inode32的表内位置为32×256=8192，所在表内块序号为8192÷4096=2，块内偏移0。全盘块号是3+2=5，块首字节地址5×4096=20480，以512字节扇区计为20480÷512=40。若读取整个4KB块，覆盖扇区40–47；inode32自身位于块最初256字节。

回到正文：从inode号算到扇区

inode怎样找到文件内容

inode字段的含义（p.11–12）

p.11 inode have all of the information about a file

File type (regular file, directory, etc.),

Size, the number of blocks allocated to it.

Protection information(who ones the file, who can access, etc).

Time information.

Etc.

p.12 Size Name What is this inode field for?

2 mode can this file be read/written/executed?

2 uid who owns this file?

4 size how many bytes are in this file?

4 time what time was this file last accessed?

4 ctime what time was this file created?

4 mtime what time was this file last modified?

4 dtime what time was this inode deleted?

4 gid which group does this file belong to?

2 links_count how many hard links are there to this file?

2 blocks how many blocks have been allocated to this file?

4 flags how should ext2 use this inode?

4 osd1 an OS-dependent field

60 block a set of disk pointers (15 total)

4 generation file version (used by NFS)

4 file_acl a new permissions model beyond mode bits

4 dir_acl called access control lists

4 faddr an unsupported field

12 i_osd2 another OS-dependent field

p.11列出类型、大小、分配块数、权限与时间。p.12给EXT2结构示例；下面保留表中的字段和尺寸，尺寸均按原表字节数抄录。

表（p.12）：EXT2 inode示例

读这张表要把inode理解为元数据记录，文件名来自目录项。已视觉核对ctime行：讲义写created；补充：通常Unix/EXT2的ctime表示状态变更时间，不能按这张教学表解释成通用创建时间。表的字段尺寸也不应充当任意版本磁盘格式的实现规范。

这张表补足“inode 含有元数据”背后的具体内容：查权限用 mode/uid/gid，追踪名字用 links_count，计算文件长度看 size，寻找内容块看 block。不能拿 block 区的 60 字节当成文件数据区，也不能把 size 与已占用磁盘空间直接划等号。

直接、一级与多级间接索引（p.13–15）【新】

p.13 To support bigger files, we use multi-level index.

Indirect pointer points to a block that contains more pointers.

inode have fixed number of direct pointers (12) and a single indirect pointer.

If a file grows large enough, an indirect block is allocated, inode’s slot for an indirect pointer is set to point to it.

(12 + 1024) x 4 K or 4144 KB

p.15 Most files are small Roughly 2K is the most common size

Average file size is growing Almost 200K is the average

Most bytes are stored in large files A few big files use most of the space

File systems contains lots of files Almost 100K on average

File systems are roughly half full Even as disks grow, file system remain -50% full

Directories are typically small Many have few entries; most have 20 or fewer

p.13的直接指针直接给出数据块号，间接指针先指向一个“装块号的块”。4KB索引块、每个块号4字节，可装4096÷4=1024个块号。12个直接指针加一个一级间接指针可覆盖(12+1024)×4=4144KiB文件内容；索引块本身不算文件内容。

p.14二级间接需要先读一个装“一级索引块号”的块，再读选中的一级索引块，才得数据块号；覆盖1024×1024个数据块。三级再多一层。12直接+一级+二级覆盖(12+1024+1048576)×4096=4299210752字节，略大于4GiB。这里算可寻址内容容量，不是整个文件连元数据的总物理占用。

图（p.14）：多级索引关系 元素：文字明确区分single、double、triple indirect，二级指向间接块，三级指向二级块。 看什么：每多一级，多一次索引选择，也多一层可覆盖的块集合。

p.15的测量表解释混合设计：多数文件小，而多数总字节由少量大文件占据。小文件用直接指针节省间接访问，大文件需要时再分配索引块。原表还报告典型小文件约2K、平均接近200K、文件系统平均约100K个文件、约半满、很多目录20项以下；这些是讲义引用的历史测量，不能当作今天所有工作负载的统计规律。

p.15 给出一组文件系统测量概述，而不是本课程所有机器都必须满足的常数：最常见文件大小约 2K，平均大小近 200K 且在增长；少量大文件占据大部分字节；一个文件系统平均约 100K 个文件；容量大致使用一半；目录通常较小，多数不超过 20 个条目。它说明为何直接指针对小文件很合适、又为何必须用间接索引容纳少数大文件。这里的“常见大小”与“平均大小”不同，是因为大文件会拉高平均值；不要用 200K 推断大多数文件都在 200K 左右。

补充：索引容量与实际占用要分两张账。 一个间接块存的是数据块地址，因此“它能指向多少块”应先用块大小除以每个地址占用的字节数。这个间接块自己也占磁盘空间，但它的内容不是文件正文，不能一边把它作为索引开销，一边又计入用户可存的数据容量。最大文件大小回答的是映射结构最多能表示多少正文；实际占用还要看当前文件用了哪些数据块，以及为了找到这些数据块分配了哪些索引块。

跨过直接索引末端时，新增的一个正文块可能同时要求分配一个间接块；因此逻辑文件只增长少量字节，磁盘占用却可能增加不止一个块。跨越两级索引边界时同理，要逐层问“这条路径上的表是否已经存在”，不能默认每次读取都新建整棵索引，也不能默认所有表一开始全部分配。读题时把“求最大容量”“列实际数据块”“数冷缓存 I/O”分开，三种问题的计数对象不同。

SFS的两直接加一级间接例题（p.16–17）

题面（L05-文件系统实现-2022未核.pdf · Example (a)(b) · p.16，图片视觉读取）

p.16 Answer the following questions:

(a) What is the biggest size we can have for a file with SFS?

(b) Provide data block numbers in sequence that will be read from the disk (only data blocks that contain file data) when read_t (inum, offset, buf1, count) is called in a user program, where inum is the corresponding inode number for the above inode, and buf1 is a pointer that points to a user-defined buffer.

Here, each cell represents a 4-byte memory space and the decimal number inside is the unsigned integer stored correspondingly.

表（题面，p.16）：inode与135号间接块

表（题面，p.16）：read_t请求

p.17给出的解法先除4096。起始逻辑块a是offset除4096向下取整；最后一个字节是offset+count−1，因此最后逻辑块也要向下取整。逻辑块0/1查直接指针，逻辑块a≥2查Cell[a−2]。物理块号不要求连续，不能把第一个物理块号一路加一。

算一遍：(i)开始7000÷4096取整为1，结束字节15999所在逻辑块为3，所以读逻辑块1、2、3，映射为96、146、198；135是索引块，题目明确只列数据块，因此不写进答案序列。(a)容量为(2+1024)×4096=4202496字节。所有六个请求的逐步计算和实际覆盖字节见附录 A2。

考试角度：（C 级 通识）常见考法是同时求最大文件容量、逻辑块区间和物理块序列；索引块I/O次数与题目要列的数据块序列必须分开。

补充：把“寻址容量”与“真正读了哪些块”分开。 inode 的直接指针直接给出文件数据块号；一级间接指针先给出一个保存块号的索引块，再从里面取数据块号。索引块本身不属于文件的用户数据，所以容量只计算可寻址的数据块，不能把索引块的 4096 字节加进文件内容容量。

沿 p.16–17 的两直接块例子，逻辑块 0、1 从 inode 直接取；逻辑块 2 对应间接表 Cell0，逻辑块 3 对应 Cell1。因此表下标是“逻辑块号减 2”，不是照抄逻辑块号。读跨块区间时先在文件逻辑字节空间切分，再把每个逻辑块映射到物理块；物理块可能不连续，不能从第一个物理块号开始简单加一。

题目若改问磁盘 I/O 次数，还需加入未缓存的 inode、索引块等读取。若同一间接表已经在内存里，后面多读一个数据块未必再读一次索引块。先确定题目要的是数据块序列、总寻址容量还是冷缓存 I/O，三个问题的数字可以不同而都正确。

A2 SFS最大容量与六次跨块读取（p.16–17）

页内每个块号4字节，因此一个4096字节间接块存1024个指针；两直接块加这1024块，容量为1026×4096=4202496字节。这里只受寻址结构限制；实际文件还受磁盘空闲量等条件约束。

对非空读取先计算最后一个字节e=offset+count−1，随后计算首末逻辑块与页内偏移。结果逐项如下。

Example1：668−268=400字节，全在块78。Example2：首块4096−268=3828字节，第二块2172字节，合计6000。

(i)：7000=1×4096+2904，15999=3×4096+3711；首块1192字节、中间块4096字节、末块3712字节，共9000。逻辑1直接取96；逻辑2/3查Cell0/1，得到146/198。

(ii)：15000=3×4096+2712，39999=9×4096+3135；首块1384，中间逻辑4–8共5块20480，末块3136，合计25000。逻辑3–9查Cell1–7，不包括Cell0。

(iii)：20000=4×4096+3616，55999=13×4096+2751；首块480，中间逻辑5–12共8块32768，末块2752，合计36000。对应Cell2–11，逐项为235、236、237、315、369、444、455、569、678、679。

(iv)：1000在逻辑0，21999=5×4096+1519；首块3096，中间逻辑1–4共4块16384，末块1520，合计21000。先取两个直接指针78/96，再查Cell0–3得到146/198/235/236。

每项都按包含端点的字节区间核回count。135只用来取得间接表，题面排除了这类索引块，因此不能插入所求数据块序列。

回到正文：SFS的两直接加一级间接例题

名字查找与空闲空间

目录记录不是固定文件名数组的同义词（p.18）

p.18 Directory contains a list of (entry name, inode number) pairs.

Each directory has two extra files .”dot” for current directory and ..”dot-dot” for parent directory

For example, dir has three files (foo, bar, foobar_is_a_pretty_longname)

p.18 inum | reclen | strlen | name

5 12 2 .

2 12 3 ..

12 12 4 foo

13 12 4 bar

24 36 28 foobar_is_a_pretty_longname

表（p.18）：目录记录

inum连接对象；reclen让读取者跳到下一记录；字符串字段记录名字。课件表中strlen的数值照录，不拿它直接代替C库strlen返回值。长名字记录占36字节，而短名字记录占12，表明这种目录表示允许不同记录长度。.与..也是名字映射，分别指当前与父目录。

补充：按 reclen 真正走一遍 p.18 的目录。 若这五条记录从本段偏移 0 连续排列，起点分别是 0、12、24、36、48；最后一条占 36 字节，因此下一条若存在，应从 84 开始。每次是“当前记录起点 + 当前 reclen”，不是“加文件名长度”，也不是“所有项固定加 12”。这几个偏移是根据原表逐项累加得到，不是另一份磁盘格式规定。

还要把原表数值与字符串函数分开：. 的可见字符数为 1，.. 为 2，foo 和 bar 为 3；表中分别写 2、3、4、4。长名字 foobar_is_a_pretty_longname 可分成 foobar（6）、_is（3）、_a（2）、_pretty（7）、_longname（9），合计 27 个可见字符，含终止字节为 28。这五行都按“字符数再加一个终止字节”理解得通，但 C 库 strlen 本身不计终止字节；因此表的列名不能直接当成 C 函数返回值。记录总长度 reclen 还包含其他字段及可能的填充，不能只凭这张表推断任意文件系统的完整二进制布局。

根目录数据块与路径遍历（p.19）

p.19 Question: What is the content of Block 0?

Answer:

题面（L05-文件系统实现-2022未核.pdf · 两个Question · p.19，图片视觉读取）

p.19 Question: What is the content of Block 0?

Assume the inode numbers of “/”, “dir1”, “dir2”, “file1” are 0, 1, 2 and 3, respectively. Moreover, each directory file only occupies one data block (4 KB for one data block), and the data block numbers allocated to “/”, “dir1” and “dir2” are 0, 1 and 2, respectively.

Suppose a user provides the following absolute path: /dir1/file1

In order to obtain the inode number of file1, the sequence of the inode numbers and the data block numbers we need to pass (starting from the root directory)

图（p.19）：/下有dir1与dir2，dir1下有file1 元素：根inode0，dir1 inode1，dir2 inode2，file1 inode3；三目录的数据块分别0、1、2。 看什么：inode给出目录数据块位置，数据块内名字映射给出下一inode号，两种编号交替出现。

算一遍：Block0是根的目录内容，记录.→0、..→0、dir1→1、dir2→2。根的父仍是根，故前两个值都为0。查/dir1/file1：inode0→数据块0，找dir1得到inode1→数据块1，找file1得到inode3。取得inode号到此结束；若题目要求读取文件内容，才继续读inode3及其数据块。

分配位图与路径读取（p.20–22）

p.20 File system track which inode and data block are free or not.

In order to manage free space, we have two simple bitmaps.

When file is newly created, it allocated inode by searching the inode bitmap and update on-disk bitmap.

Pre-allocation policy is commonly used for allocate contiguous blocks.

p.21 Issue an open(“/foo/bar”, O_RDONLY),

Traverse the pathname and thus locate the desired indoe.

Begin at the root of the file system (/)

In most Unix file systems, the root inode number is 2

Filesystem reads in the block that contains inode number 2.

Look inside of it to find pointer to data blocks (contents of the root).

By reading in one or more directory data blocks, it will find “foo” directory.

Traverse recursively the path name until the desired inode (“bar”)

Check finale permissions, allocate a file descriptor for this process and returns file descriptor to user.

p.22 Access Paths: Reading a File From Disk (Cont.)

p.22 Issue read() to read from the file.

Read in the first block of the file, consulting the inode to find the location of such a block.

Update the inode with a new last accessed time.

Update in-memory open file table for file descriptor, the file offset.

When file is closed:

File descriptor should be deallocated, but for now, that is all the file system really needs to do. No disk I/Os take place.

p.20创建对象时先搜索inode位图，找到空位并标已用；分配数据又查数据位图。预分配连续块可让后续增长更容易获得连续空间，但分配仍要维护正确的已用状态。

p.21的open(/foo/bar)从根inode开始，读根数据查foo，再读foo inode与目录数据查bar，最后读bar inode并检查权限、建立描述符。不要从路径字符串中的字符位置直接推磁盘位置。p.22 read依据inode找到数据块、更新内存中的打开偏移；讲义模型还更新访问时间。close释放描述符，本简化模型无需新增磁盘I/O。补充：缓存、时间戳策略和延迟写会改变实际系统的物理I/O数量，必须先说明采用哪个模型。

读时序图怎样计数（p.23）

p.23 File Read Timeline (Time Increasing Downward)

图（p.23）：File Read Timeline，时间向下 元素：root/foo/bar的inode列、目录数据列和bar的三个数据块列；open有5次读，每次read有inode读、数据读、inode写。 看什么：按纵向时间数请求，不按路径长度直接乘一个不明常数。

算一遍：open为根inode、根目录数据、foo inode、foo目录数据、bar inode，共5次读。随后三个read各为2读1写，合计6读3写；整图11读3写，共14次I/O。这里按图的无缓存、每次写访问时间模型计算；若缓存inode并延迟时间更新，答案会改变。

表（p.23）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

写与创建为何涉及更多元数据（p.24–25）

p.24 Issue write() to update the file with new contents.

File may allocate a block (unless the block is being overwritten).

Need to update data block, data bitmap.

It generates five I/Os:

one to read the data bitmap

one to write the bitmap (to reflect its new state to disk)

two more to read and then write the inode

one to write the actual block itself.

To create file, it also allocate space for directory, causing high I/O traffic.

p.25 File Creation Timeline (Time Increasing Downward)

p.24新增一个文件数据块时，读写数据位图各1次，读写inode各1次，写数据块1次，合计5。若只覆盖已分配块，未必需要新的分配位图操作；创建新名字还要修改目录。

图（p.25）：创建/foo/bar再写三个数据块 元素：创建阶段读root inode/data、foo inode/data，读写inode bitmap，写foo data，读写bar inode，写foo inode；每个write阶段包含数据位图读写、bar inode读写与数据写。 看什么：目录保存名字，inode保存对象状态，位图保存分配状态，三者要一起更新。

算一遍：依图创建阶段6读4写=10次；随后每个write为2读3写，三个共15次；合计25次。这个数字是该教学时间线的模型计数，不是任意create系统调用的硬性成本。

补充：创建为什么不能只写新文件内容。 想让路径 /foo/bar 表示一个新文件，至少要维护四种事实：哪个 inode 归它；哪个目录项把 bar 映射到该 inode；哪些数据块归它；inode 中的大小和指针如何描述这些块。位图只回答“是否已被占用”，不会自动生成目录项；目录项只回答“名字找到哪个对象”，也不会自动初始化数据块。

把 p.25 的写入流程当作一次多对象状态改变，就能看出崩溃一致性问题。若先让目录项指向尚未初始化的 inode，掉电后名字可能连到无效状态；若先分配了空间却没来得及把它接入可达结构，可能遗留无法正常找到的占用。这是本讲访问路径继续通向日志/恢复机制的原因。这里解释风险，不把本页简化顺序宣称为完整的崩溃安全协议。

表（p.25）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

缓存与延迟写解决不同瓶颈（p.26–28）

课件程序与接口（p.26，原页片段）

Reading and writing files are expensive, incurring many I/Os.
For example, long pathname(/1/2/3/…./100/file.txt)
One to read the inode of the directory and at least one read its data.
Literally perform hundreds of reads just to open the file.

In order to reduce I/O traffic, file systems aggressively use system memory(DRAM) to cache.
Early file system use fixed-size cache to hold popular blocks.
Static partitioning of memory can be wasteful;
Modem systems use dynamic partitioning approach, unified page cache.
Read I/O can be avoided by large cache.

p.27 Write traffic has to go to disk for persistent. Thus, cache does not reduce write I/Os.

File system use write buffering for write performance benefits.

delaying writes (file system batch some updates into a smaller set of I/Os).

By buffering a number of writes in memory, the file system can then schedule the subsequent I/Os.

By avoiding writes

Some application force flush data to disk by calling fsync() or direct I/O.

p.26指出长路径的每级都可能读inode与目录数据，缓存能免去重复读。统一页缓存动态分享内存，比固定分区更能适应当前需求。p.27则指出最终需要持久化的数据仍要写到盘，但写缓冲可以合并多次修改、重排I/O，甚至取消最终不再需要的中间写。

算一遍（补充；数字是我为演示取的，讲义没给）：同一块在刷盘前被更新10次，若每次同步写是10次写；若只需最后状态且允许缓冲，可能合为1次。减少的是中间版本的物理写，并不免除最终持久化义务。p.28收束为数据结构、访问路径与缓存三条线。

本讲核心考点

• 分配位图区分inode与数据块两种资源（p.4–8，C 级通识考法）。
• inode32位于字节20480、块起始扇区40（p.9–10，C 级通识考法）。
• 间接索引容量取决于块尺寸与块号尺寸（p.13–17，C 级通识考法）。
• 路径查找交替经过inode与目录数据（p.18–23，C 级通识考法）。
• 读写I/O数量必须先固定缓存与时间戳模型（p.23–27，C 级通识考法）。

附录

必要演算已移至对应页正文，保留原锚点供旧链接使用。

来源与证据

• 原件：L05-文件系统实现-2022未核.pptx（本地课件）；PDF副本（本地课件） p.1–28。本文页码均为 PDF 页号。

• 考试证据：读了 课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无

• 2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。