Chapter 4: File Systems（文件系统）

大纲

1. Files（文件）

文件是计算机存储数据的基本单位。文件可以包含文本、程序、图像、视频等各种类型的数据。

文件属性（Attributes）：文件名、类型、大小、创建时间、权限等。
文件操作（Operations）：创建、删除、读取、写入、移动、重命名等。
文件类型（File Types）：普通文件、目录文件、特殊文件（设备文件、管道等）。

2. Directories（目录）

目录用于组织和管理文件，是文件系统中的重要结构。

目录结构（Directory Structure）：层次结构（树形）、单级目录、多级目录、图结构等。
目录操作（Directory Operations）：创建、删除、打开、关闭、列出目录内容等。
目录实现（Directory Implementation）：线性列表、哈希表等。

3. File System Implementation（文件系统实现）

文件系统的实现涉及存储管理和数据结构的设计。

磁盘管理（Disk Management）：如何存储、分配和管理文件数据。
文件分配方法（File Allocation Methods）：连续分配（Contiguous）、链接分配（Linked）、索引分配（Indexed）。
文件访问控制（File Access Control）：用户权限管理，如读取、写入、执行权限。

4. Example File Systems（文件系统示例）

不同操作系统使用不同的文件系统，以下是一些常见的例子：

FAT（File Allocation Table）：早期的Windows文件系统，简单但不支持大文件。
NTFS（New Technology File System）：Windows现代文件系统，支持权限管理和日志功能。
ext4（Fourth Extended File System）：Linux广泛使用的文件系统，支持大文件和日志功能。
APFS（Apple File System）：苹果设备的文件系统，优化了SSD性能。

Overview（概述）

文件系统的长期存储需求（Requirements for Long-Term Information Storage）

为了有效管理和存储数据，文件系统需要满足以下要求：

必须能够存储大量数据（Must store large amounts of data）
- 计算机中的数据量通常较大，因此文件系统需要高效地管理存储空间。
存储的信息必须在使用它的进程终止后仍然存在（Information stored must survive the termination of the process using it）
- 文件必须是持久化的，不会因进程结束而丢失。
多个进程必须能够并发访问信息（Multiple processes must be able to access the information concurrently）
- 文件系统需要支持并发访问，并提供相应的同步机制以防止数据冲突。

解决方案（Solution）

在磁盘或其他外部存储介质上存储信息，存储单位称为“文件”（Store information on disk or other external media in units called files）。
文件系统是操作系统的一部分，负责管理文件（The file system is a part of the operating system that manages files）。

Basic Functions of File System（文件系统的基本功能）

提供文件和目录的逻辑视图（Present logical (abstract) view of files and directories）
- 使用户不必关注底层硬件的复杂性，而是通过文件和目录的形式直观地管理数据。
提高存储设备的使用效率（Facilitate efficient use of storage devices）
- 例如优化磁盘访问，减少磁盘碎片，提高数据存取速度。
支持文件共享（Support sharing）
- 多个用户和进程可以访问同一文件，并且文件系统提供访问控制机制来保护数据安全。

File System（文件系统）

文件系统既要考虑用户的需求，也要关注底层实现。

用户视角（User’s View on File Systems）

用户通常关心：

文件如何命名？（How are files named?）
允许对文件进行哪些操作？（What operations are allowed on them?）
目录树是什么样的？（What does the directory tree look like?）

实现者视角（Implementer’s View on File Systems）

文件系统的开发者需要考虑：

文件和目录如何存储？（How are files and directories stored?）
如何管理磁盘空间？（How is disk space managed?）
如何保证系统的高效性和可靠性？（How to make everything work efficiently and reliably?）

Files（文件）

文件是存储数据的基本单位，涉及多个重要概念：

文件内容（Contents）

文件命名（File Naming）
- 文件名通常由用户定义，并遵循不同操作系统的命名规则（如 Windows 使用 example.txt，Linux 可区分大小写 Example.txt 和 example.txt）。
文件结构（File Structure）
- 结构化文件（如数据库）、无结构文件（如二进制数据流）、层次化结构（如 HTML 文件）。
文件类型（File Types）
- 普通文件（文本、图片、视频）、目录文件、设备文件等。
文件访问（File Access）
- 顺序访问（Sequential Access）和随机访问（Random Access）。
文件属性（File Attributes）
- 文件大小、创建时间、权限等。
文件操作（File Operations）
- 创建、删除、打开、关闭、读取、写入、重命名等。
使用文件系统调用的示例程序（An Example Program Using File System Calls）
- 例如，在 C 语言中可以使用 open()、read()、write()、close() 进行文件操作。

File Naming（文件命名）

1. 文件命名规则（File Naming Rules）

文件名（FileName）+ 扩展名（FileExtension）
- 例如：document.txt，其中 document 是文件名，.txt 是扩展名。
有效文件名（Valid Name）
- 字符数限制（Number of Characters）：通常最大支持 255 个字符（视文件系统而定）。
- 允许的字符（Allowed Characters）：文件名可以由字母（A-Z, a-z）、数字（0-9）、特殊字符（如 _、-、. 等）组成。
- 大小写区分（Lower vs. Upper Case）：Windows 通常不区分大小写，而 Linux/Unix 区分大小写，例如 file.txt 和 File.txt 被视为两个不同的文件。

2. 文件扩展名（File Extensions）

文件扩展名通常用于表示文件的类型，并由应用程序识别，例如：

扩展名	示例文件	含义
`.bak`	`file.bak`	备份文件（Backup file）
`.c`	`file.c`	C 语言源代码（C source program）
`.gif`	`file.gif`	GIF 图片（CompuServe Graphical Interchange Format image）
`.hlp`	`file.hlp`	帮助文件（Help file）
`.html`	`file.html`	HTML 网页文件（World Wide Web HyperText Markup Language document）
`.jpg`	`file.jpg`	JPEG 静态图片（Still picture encoded with the JPEG standard）
`.mp3`	`file.mp3`	MP3 音乐文件（Music encoded in MPEG layer 3 audio format）
`.mpg`	`file.mpg`	MPEG 视频文件（Movie encoded with the MPEG standard）
`.o`	`file.o`	目标文件（编译器输出，但未链接）（Object file）
`.pdf`	`file.pdf`	PDF 文档（Portable Document Format file）
`.ps`	`file.ps`	PostScript 文件（PostScript file）
`.tex`	`file.tex`	TeX 格式化输入文件（Input for the TEX formatting program）
`.txt`	`file.txt`	纯文本文件（General text file）
`.zip`	`file.zip`	压缩归档文件（Compressed archive）

File Structure（文件结构）

1. 文件的组织方式（File Organization Methods）

无结构文件（None Sequence of Words/Bytes）
- 例如 Unix 和 Windows 系统中的文件就是一系列连续的字节，没有固定的结构。
简单记录结构（Simple Record Structure）
- 行（Lines）：文件按行组织，例如 .txt 文本文件。
- 固定长度（Fixed Length）：文件中的每条记录具有相同长度，例如数据库的固定格式记录。
复杂结构（Complex Structures）
- 记录树（Record Tree）：用于存储层次化的数据，如 XML 文件。
- 可变长度记录（Records Not Necessarily the Same Length）：例如 JSON 文件，每条记录的字段可能不同。
- 记录包含键（Records Contain Keys）：例如数据库索引文件。
- 基于键的树形排序（Tree Sorted on Key）：例如 B+ 树索引文件。

2. 三种文件结构（Three Kinds of File Structures）

字节序列（Byte Sequence）：如普通文本文件（.txt）。
记录序列（Record Sequence）：如数据库文件，数据按记录存储。
树结构（Tree）：如文件系统索引或数据库索引文件。

File Types（文件类型）

1. 文件类型分类（File Types）

（1）普通文件（Regular Files）

普通文件用于存储用户数据，可以分为：

ASCII 文件（ASCII File）：可以直接显示、打印和编辑的文本文件，如 .txt、.c。
二进制文件（Binary File）

：具有内部结构的文件，如：
- 可执行文件（Executable File）：如 .exe、.bin。
- 归档文件（Archive File）：如 .zip、.tar、.rar。

（2）目录文件（Directories）

目录文件用于维护文件系统结构，存储文件和目录的元数据。

（3）特殊文件（Special Files）

字符特殊文件（Character Special Files）

：
- 用于建模串行 I/O 设备，如终端（/dev/tty）、打印机（/dev/lp0）、网络接口等。
块特殊文件（Block Special Files）

：
- 用于建模块存储设备，如磁盘（/dev/sda、/dev/nvme0n1）。

File Types（文件类型示例）

文件类型	示例
（a）可执行文件（Executable File）	`.exe`、`.bin`
（b）归档文件（Archive File）	`.zip`、`.tar`

文件访问（File Access）

1. 顺序访问（Sequential Access）

从文件开头开始读取所有字节/记录（Read all bytes/records from the beginning）。
不能跳跃访问（Cannot jump around），但可以倒回或向后移动（Could rewind or back up）。
适用于磁带存储介质（Convenient when medium was magnetic tape）。

2. 随机访问（Random Access）

可以按任意顺序读取字节/记录（Bytes/records read in any order）。
对于数据库系统至关重要（Essential for database systems）。
两种指定读取位置的方法（Two methods for specifying where to start reading）

：
1. 读取后移动文件标记（Read and then move file marker）。
2. 先移动文件标记（seek），再读取（Move file marker, then read，如 UNIX 方式）。

文件属性（File Attributes）

操作系统会为每个文件关联额外的信息（Operating systems associate extra information with each file）。
这些信息被称为文件属性（metadata）

，例如：
- 文件大小（Size）
- 创建时间（Creation time）
- 修改时间（Modification time）
- 访问权限（Access permissions）
- 所有者（Owner）

文件操作（File Operations）

文件系统支持多种基本操作，包括：

创建（Create）：创建新文件。
删除（Delete）：删除文件。
打开（Open）：打开文件，以便读/写。
关闭（Close）：关闭文件，释放资源。
读取（Read）：从文件中读取数据。
写入（Write）：向文件中写入数据。
追加（Append）：在文件末尾追加数据。
定位（Seek）：移动文件指针以进行随机访问。
获取属性（Get Attributes）：查询文件的元数据。
设置属性（Set Attributes）：修改文件属性（如权限）。
重命名（Rename）：修改文件名称。

示例：Unix 文件拷贝程序（An Example Program Using File System Calls）

功能：拷贝文件 [copyfile sourcefile destfile]

/* 文件拷贝程序（File Copy Program） */
#include <sys/types.h>
#include <fcntl.h>
#include <stdlib.h>
#include <unistd.h>

#define BUF_SIZE 4096
#define OUTPUT_MODE 0700  /* 目标文件权限 */

int main(int argc, char *argv[]) {
    int in_fd, out_fd, rd_count, wt_count;
    char buffer[BUF_SIZE];

    if (argc != 3) exit(1); /* 语法错误 */

    /* 打开源文件 */
    in_fd = open(argv[1], O_RDONLY);
    if (in_fd < 0) exit(2); /* 无法打开，退出 */

    /* 创建目标文件 */
    out_fd = creat(argv[2], OUTPUT_MODE);
    if (out_fd < 0) exit(3); /* 无法创建，退出 */

    /* 复制循环 */
    while (1) {
        rd_count = read(in_fd, buffer, BUF_SIZE); /* 读取数据 */
        if (rd_count <= 0) break; /* 读取结束或错误 */
        
        wt_count = write(out_fd, buffer, rd_count); /* 写入数据 */
        if (wt_count <= 0) exit(4); /* 写入失败 */
    }

    /* 关闭文件 */
    close(in_fd);
    close(out_fd);

    if (rd_count == 0) exit(0); /* 成功 */
    else exit(5); /* 读取错误 */
}

目录（Directory）

目录内容（Contents）

目录是用于管理文件的结构，主要有以下几种类型：

单级目录系统（Single-Level Directory System）
两级目录系统（Two-Level Directory System）
层次化目录系统（Hierarchical Directory System）
路径名（Path Names）
目录操作（Directory Operations）

目录（Directory）

文件系统使用目录（或文件夹）来跟踪文件（File systems have directories or folders to keep track of files）。
目录是一个文件，它包含文件名和文件位置的对应关系（Directory is a file containing correspondence between filenames and file locations）。
目录条目（Directory Entries）包含有关文件的信息，如：
- 文件属性（Attributes）
- 文件大小（Size）
- 创建时间（Creation time）
- 文件位置（File location）
当创建文件时，会创建相应的目录条目；当文件被删除时，相应的目录条目也会被移除（Directory entries are created when the files they describe are created and removed when files are deleted）。

目录的组织方式（Organize the Directory to Obtain）

目录组织的目标

提高查找效率（Efficiency）：快速定位文件。
便捷的命名（Naming）

：
- 允许不同用户使用相同文件名（Two users can have the same name for different files）。
- 同一文件可以有多个不同的名字（The same file can have several different names）。
分组管理（Grouping）

：
- 按属性组织文件（Logical grouping of files by properties，如 Java 代码、游戏等）。

目录结构（Directory Structure）

1. 单级目录结构（Single-Level Directory）

所有文件存储在一个根目录下（A single level directory has one root directory containing all files）。
缺点：不同用户不能有相同的文件名，容易导致文件管理混乱。

2. 两级目录结构（Two-Level Directory）

有一个根目录（root directory）和多个用户目录（user directories）（A two-level directory has a root directory and user directories）。
不同用户可以使用相同的文件名，但仍然不能创建子目录。

3. 层次化目录结构（Hierarchical Directory）

包含一个根目录（root directory），并且可以有任意数量的子目录（A hierarchical directory has a root directory and arbitrary number of subdirectories）。
优点

：
- 支持文件分类存储（更易管理）。
- 路径更加灵活，支持相对路径和绝对路径。
- 便于权限管理，不同用户可有不同目录。

单级目录系统（A Single-Level Directory System）

特点（Characteristics）

所有用户共享一个目录（A single directory for all users）。
示例

（Example）：
- 目录包含 4 个文件（Contains 4 files）。
- 这些文件属于 3 个不同的用户（Owned by 3 different people, A, B, and C）。

单级目录系统的优缺点（A Single-Level Directory System）

优点（Advantages）

✅ 简单易懂，支持方便（Easy to support and understand）。

缺点（Disadvantages）

❌ 命名问题（Naming Problem）：所有文件必须有唯一的名字（All files must have unique names）。 ❌ 名称冲突问题（Name Collision Problem）：多个用户可能想用相同的文件名，但系统不允许。 ❌ 分组问题（Grouping Problem）：文件数量多时，难以管理和记忆文件名（Difficult to remember file names in a large file system）。

两级目录系统（Two-Level Directory Systems）

特点（Characteristics）

为每个用户提供单独的目录（Separate directory for each user）。
路径名由“用户名 + 文件名”确定（A user name and a file name define a path name）。

示例（Example）：

Root Directory
 ├── User A
 │   ├── file1
 │   ├── file2
 ├── User B
 │   ├── file3
 ├── User C
 │   ├── file4

两级目录系统的优缺点（Two-Level Directory Systems）

优点（Advantages）

✅ 解决名称冲突问题（Resolves name collision problem）：不同用户可以有相同的文件名（Can have the same file name for different users）。 ✅ 搜索效率高（Efficient searching）：每个用户都有自己的文件夹，减少查找范围。 ✅ 支持文件共享和访问控制（File sharing and protection）。

缺点（Disadvantages）

❌ 仍然无法进行更细致的文件分类（Grouping problem not resolved）。

层次化目录系统（Hierarchical Directory Systems）

特点（Characteristics）

是两级目录系统的推广（Generalization of two-level directory with arbitrary height）。
叶子节点（Leaf nodes）是文件，内部节点（Interior nodes）是目录。
每个用户都有一个“当前目录”（Current Directory / Working Directory），可以通过 cd 命令或系统调用更改目录（Can change current directory via cd command or system call）。
路径名可以是绝对路径或相对路径（Path names can be absolute or relative）。

层次化目录系统示例（Hierarchical Directory Systems Example）

/ (Root)
├── home
│   ├── userA
│   │   ├── Documents
│   │   │   ├── report.pdf
│   │   ├── Pictures
│   │   │   ├── photo.jpg
│   ├── userB
│   │   ├── Downloads
│   │   │   ├── file.zip
├── var
│   ├── log
│   │   ├── system.log
├── etc
│   ├── config
│   │   ├── settings.conf

层次化目录系统的优缺点（Advantages and Disadvantages of Hierarchical Directory Systems）

优点（Advantages）

✅ 解决名称冲突问题（Resolves name collision problem）：不同用户可以有相同的文件名（Can have the same file name for different users）。 ✅ 搜索效率高（Efficient searching）：目录结构清晰，易于管理。 ✅ 支持文件共享和访问控制（File sharing and protection）。 ✅ 支持文件分类管理（Grouping capability）：可以根据文件类型、项目等进行分组。

路径名（Path Name）

两种指定文件路径的方法（Two Different Methods for Specifying File Names in a Directory Tree）

绝对路径名（Absolute Path Name）
- 从根目录 / 开始，一直到目标文件的完整路径。
- 适用于所有目录，不受当前目录的影响。
相对路径名（Relative Path Name）
- 从当前工作目录（Working Directory）到目标文件的路径。
- 依赖于当前目录，适用于更短的路径表示。

路径表示方式（Path Representation in Different Systems）

操作系统	路径示例
Windows	`C:\Users\ast\mailbox`
UNIX/Linux	`/usr/ast/mailbox`
MULTICS	`>usr>ast>mailbox`

特殊目录符号（Special Entries in the File System）

. （Dot）→ 当前目录（Current Directory）
.. （Dot Dot）→ 父目录（Parent Directory）

UNIX 目录树（A UNIX Directory Tree）

示例（Example）

假设当前工作目录是 /usr/ast，以下是两个不同的路径示例：

1 2	cp /usr/lib/dictionary . # 复制文件到当前目录 cp ../../lib/dictionary . # 使用相对路径复制文件

/usr/lib/dictionary → 绝对路径（Absolute Path）
../../lib/dictionary → 相对路径（Relative Path）

31. 目录操作（Directory Operations）

常见目录操作（Common Directory Operations）

操作	说明（Description）
创建目录（Create a new directory）	`mkdir(path, mode)`
删除空目录（Remove an empty directory）	`rmdir(path)`
打开目录（Open a directory for reading）	`opendir(path)`
关闭目录（Close a directory to release space）	`closedir(dir)`
读取目录（Read next entry in the directory）	`readdir(dir)`
重命名目录（Rename a directory）	`rename(oldpath, newpath)`
创建链接（Create a link to an existing file）	`link(oldpath, newpath)`
删除链接（Remove a hard link）	`unlink(path)`
更改工作目录（Change the working directory）	`chdir(path)`
重置目录读取位置（Rewind a directory so it can be reread）	`rewinddir(dir)`

Linux 目录结构（Linux Directory Structure）

Linux 文件系统的特点（Characteristics of Linux File System）

✅ 基于树形结构（Tree Hierarchy） → 目录和文件按层次组织。 ✅ 从 UNIX 目录结构演化而来（Evolved from Unix File System）。 ✅ 常见目录名称有固定功能（Common Directory Names for Common Functions）。

Linux 目录结构（Common Linux Directories）

目录（Directory）	作用（Purpose）
`/`	根目录（Root Directory），所有文件和目录的起点
`/bin`	存放基本命令的二进制文件（Essential binaries, like `ls`, `cp`）
`/boot`	存放系统引导所需的文件（Boot loader files）
`/dev`	设备文件目录（Device files, e.g., `/dev/sda`）
`/etc`	系统配置文件（System configuration files）
`/home`	用户主目录（User home directories, e.g., `/home/user`）
`/lib`	共享库（Shared libraries）
`/mnt`	挂载点（Mount point for temporary file systems）
`/opt`	可选软件包（Optional software packages）
`/proc`	内核及进程信息（Kernel and process information）
`/root`	`root` 用户的主目录（Home directory for the root user）
`/sbin`	管理员二进制文件（System binaries, like `shutdown`, `fdisk`）
`/tmp`	临时文件（Temporary files, cleared on reboot）
`/usr`	用户级应用程序（User binaries, libraries, documentation）
`/var`	变化的数据文件（Variable data, logs, caches, spool files）

文件系统实现（File System Implementation）

内容（Contents）

📌 文件系统布局（File System Layout） 📌 文件的实现（Implementing Files） 📌 目录的实现（Implementing Directory） 📌 共享文件（Shared Files） 📌 磁盘空间管理（Disk Space Management） 📌 文件系统可靠性（File System Reliability） 📌 文件系统性能（File System Performance）

文件系统布局（File System Layout）

主引导记录（MBR, Master Boot Record）

位于磁盘的 第 0 扇区（Sector 0），用于引导计算机启动。
分区表（Partition Table） 记录了磁盘的不同分区的起始和结束地址。
其中一个分区会被标记为 活动分区（Active Partition），即系统从这里引导。

每个分区的结构

每个分区都包含自己的 文件系统（如 UNIX 文件系统、Windows 文件系统等）。
引导块（Boot Block） 是每个分区的起始部分，存储了一个小型的 引导程序，用于加载该分区上的操作系统。

操作系统启动（OS Startup）

1️⃣ BIOS 读取 MBR，找到 活动分区。 2️⃣ 读取该分区的 引导块 并执行其中的代码。 3️⃣ 加载 操作系统内核，启动系统。

文件系统布局（File System Layout）

文件系统的布局通常包含以下信息：

分区总大小（Total Size of the Partition）
块大小（Block Size）（通常是 2ⁿ × 扇区大小）
指向空闲块列表的指针（Pointer to Free Blocks）
根目录的 inode 号（Inode Number of the Root Directory）
魔数（Magic Number） → 用于标识文件系统的类型。

文件字节 vs 磁盘扇区（File Bytes vs Disk Sectors）

📌 文件（Files）

由 字节序列（Sequence of Bytes） 组成。
文件 I/O 以 字节（Bytes） 为单位进行读写。

📌 磁盘（Disks）

由 扇区（Sectors） 组成，每个扇区通常是 512 字节。
磁盘 I/O 以 扇区（Sectors） 为单位进行读写。

📌 文件系统如何组织数据？

定义块大小（Block Size）：一般为 2ⁿ × 扇区大小，例如 4KB = 8 × 512B。
将多个连续扇区分配给一个块（Contiguous Sectors Form a Block）。
文件系统将磁盘视为一系列块（Disk as an Array of Blocks），必须进行 块分配和空闲管理（Block Allocation & Free Space Management）。

文件存储的实现（Implementing Files）

如何存储文件数据？

文件系统需要 跟踪磁盘块（Disk Blocks） 与 文件（Files） 之间的对应关系。常见的三种方法如下：

1️⃣ 连续分配（Contiguous Allocation）

📌 特点

文件占用 连续的磁盘块，所有数据按顺序存储。

📌 优点 ✅ 读写速度快（顺序访问，无需查找）。 ✅ 简单易实现。

📌 缺点 ❌ 容易产生外部碎片（External Fragmentation），新文件可能找不到足够大的连续空间。 ❌ 文件扩展困难，如果需要增加大小，可能需要重新分配到新的空间。

2️⃣ 链接分配（Linked List Allocation）

📌 特点

每个文件存储在 多个非连续的磁盘块 中，块之间通过 指针（Pointers） 连接。

📌 优点 ✅ 避免了外部碎片问题（不需要连续存储）。 ✅ 文件可以动态增长，不需要预留固定大小。

📌 缺点 ❌ 随机访问速度慢，因为要逐块查找。 ❌ 存储指针需要额外的磁盘空间。

3️⃣ 索引分配（Indexed Allocation）

📌 特点

为每个文件分配一个 索引块（Index Block），索引块中存储了该文件所有数据块的地址。

📌 优点 ✅ 支持随机访问（直接查找索引块，不需要逐块遍历）。 ✅ 文件可以动态增长，不受连续空间的限制。

📌 缺点 ❌ 索引块需要额外的存储空间。 ❌ 索引块大小有限，可能需要 多级索引（Multi-Level Indexing） 来支持大文件。

💡 总结

分配方式	优点	缺点
连续分配（Contiguous Allocation）	读写快、实现简单	可能产生外部碎片，扩展困难
链接分配（Linked List Allocation）	动态存储，避免碎片	随机访问慢，占用额外空间
索引分配（Indexed Allocation）	支持随机访问，扩展灵活	需要额外存储索引块

连续分配（Contiguous Allocation）

📌 方式

每个文件 作为 连续的一块磁盘空间 存储（即文件的所有数据都在相邻的磁盘块中）。
需要 记录起始扇区（Starting Sector） 和 文件长度（Length of File）。

📌 优缺点

✅ 优点

简单实现：只需存储 起始扇区 + 长度。
读取速度快：适用于 顺序访问 和 直接访问，因为磁盘读写头无需频繁移动。

❌ 缺点

外部碎片问题（External Fragmentation）：删除文件后，会留下很多零散的空闲块。
文件大小必须预先知道，否则扩展时可能无法分配连续空间。
适用于 CD-ROMs/DVDs 等 一次性写入的存储介质（文件大小已知，且不会删除）。

链接分配（Linked List Allocation）

📌 方式

将文件存储为链表（Linked List），磁盘块 可以分散在磁盘的各个位置。
每个块的第一部分存储指向下一个块的指针，数据存储在剩余空间。

链接分配（Linked List Allocation）的优缺点

✅ 优点

不会有外部碎片（External Fragmentation）。
目录项（Directory Entry）简单，只需存储 起始地址。
文件可以动态增长，只要磁盘有空闲块，就可以继续分配。
适用于顺序访问（Sequential Access），按链表顺序读取数据。

❌ 缺点

随机访问慢（需要按链表顺序遍历）。
数据块的大小受指针大小影响（块的一部分被用于存储指针）。

使用 FAT 进行链接分配（Linked List Allocation Using FAT）

📌 方式

文件分配表（FAT, File Allocation Table） 存储 所有磁盘块的指针信息，避免存储指针在数据块中。
FAT 位于磁盘分区的前面

，包含：
- 每个 磁盘块 一个条目。
- 每个条目存储 下一个块的地址。
- 特殊标记 -1 表示文件结尾（EOF）。
- 特殊值 0 表示块是空闲的（Free）。
由于 FAT 被加载到内存，访问更快。

使用 FAT 进行链接分配的优缺点

✅ 优点

整个数据块可用于存储数据，不浪费空间存储指针。
随机访问比普通链表快，因为 FAT 在内存中可以快速查找数据块。
目录项（Directory Entry）简单，只需存储 起始块号。

❌ 缺点

FAT 需要占用大量内存，因为必须一次性加载整个 FAT。
例如：
- 磁盘大小：200 GB
- 块大小：1 KB
- FAT 条目大小：4 字节
- 需要存储 200 GB ÷ 1 KB = 200M 个块的 FAT 条目
- 需要 200M × 4B = 800 MB 的内存来存储 FAT！

💡 总结

分配方式	优点	缺点
连续分配（Contiguous Allocation）	读取快，适用于 CD/DVD	需要预知文件大小，容易碎片化
链接分配（Linked List Allocation）	没有外部碎片，文件可动态增长	随机访问慢，占用部分块空间存指针
FAT（File Allocation Table）	提供随机访问，数据块全可用	FAT 需要占用大量内存

📌 FAT 主要用于 DOS 和 Windows 早期系统（如 MS-DOS、Windows 98），现代操作系统通常使用 更先进的文件系统（如 NTFS、EXT4、APFS）。

索引分配（Indexed Allocation）—— iNode 方式

📌 方式

所有指针集中存储在一个位置，即 索引块（Index Block） 或 索引节点（iNode）。
每个文件都有一个 iNode，存储文件的 属性信息（如权限、大小、时间戳等）以及 磁盘块地址。

索引分配（Indexed Allocation）的机制

📌 目录项（Directory Entry）

目录项（Directory Entry）不直接存储磁盘块地址，而是存储 iNode 号（iNumber）。
只有 在文件被打开时，iNode 才会被加载到内存，节省空间。

索引分配的扩展问题

📌 问题：如果 iNode 只能存储固定数量的磁盘块地址，当文件增长超出这个限制怎么办？

🔹 解决方案：使用多级索引（Multi-Level Indexing）

直接索引（Direct Blocks）：iNode 直接存储数据块地址（适用于小文件）。
一级间接索引（Single Indirect Block）：iNode 存储一个指向 索引块（Index Block） 的地址，索引块存储数据块地址。
二级间接索引（Double Indirect Block）：iNode 存储一个指向 一级索引块 的地址，一级索引块存储 二级索引块，二级索引块存储数据块地址。
三级间接索引（Triple Indirect Block）：更进一步嵌套索引块，可以支持超大文件。

📌 例如：Linux ext2 文件系统

iNode 结构支持直接块、一级间接块、二级间接块和三级间接块，文件越大，索引层级越多。

多级索引分配（Multi-Level Indexed Allocation）

📌 索引分配的 4 种存储方式

索引方式	存储内容	适用场景
直接索引（Direct Blocks）	iNode 直接存储数据块地址	小文件（例如文本文件、配置文件）
一级间接索引（Single Indirect Block）	指向数据块地址的索引块	中等大小的文件
二级间接索引（Double Indirect Block）	指向一级索引块的索引块	大文件
三级间接索引（Triple Indirect Block）	指向二级索引块的索引块	超大文件（例如高清视频、大型数据库）

54. 索引分配（iNode）的优缺点

✅ 优点

查找速度快，支持随机访问（不像链表分配那样需要顺序遍历）。
不会有外部碎片，因为磁盘块可以自由分配（不像连续分配需要连续空间）。
iNode 只有在文件被打开时才需要加载到内存，节省内存空间。

❌ 缺点

索引结构需要额外存储空间（特别是多级索引会消耗较多磁盘块）。

💡 总结：不同文件分配方式对比

分配方式	优点	缺点	适用场景
连续分配（Contiguous Allocation）	读取速度快，适用于顺序访问	外部碎片，文件大小需固定	CD/DVD 等只读存储
链接分配（Linked List Allocation）	适用于动态增长的文件	随机访问慢，占用一部分存储空间存指针	适用于顺序存储
FAT（File Allocation Table）	提供快速随机访问	FAT 需要占用大量内存	适用于 DOS/早期 Windows
索引分配（iNode）	支持快速查找和随机访问	需要额外的索引存储	适用于现代文件系统（如 ext4, NTFS）

📌 现代操作系统（如 Linux、macOS、Windows）大多采用 iNode 结构（或类似方法）来管理文件。 你对 iNode 结构有进一步的疑问吗？😊

目录的实现（Implementation of Directories）

📌 目录的存储方式

目录像普通文件一样存储。
目录条目存储在 数据块 中。
目录文件 是 目录条目 的列表。

📌 目录条目

当一个文件被打开时，文件系统通过 路径名 查找相应的 目录条目。
目录条目提供了文件相关的必要信息，用于定位磁盘块：
- 文件的磁盘地址（连续块）。
- 文件的第一个块号（对于链接列表分配）。
- 文件的 iNode 号（对于索引分配）。

目录实现（2）—— 文件属性的位置

📌 文件属性存储位置

在目录条目中
- 固定大小的条目。
- 目录条目存储磁盘地址和文件属性。
- 适用于 MS-DOS 和 Windows 文件系统。
在单独的数据结构（例如 iNode）中
- 目录条目仅包含文件名和 iNode 号。
- iNode 存储文件的所有属性。
- 适用于 Unix 和类 Unix 系统。

目录实现（3）

📌 目录结构：

目录实现（4）—— 长文件名处理

📌 解决方案 1：固定长度文件名

文件名通常为 255 字符。
最简单的方式，但会导致空间浪费。

目录实现（5）—— 长文件名处理

📌 解决方案 2：目录条目包含固定部分和可变部分

固定部分：包含条目的大小、属性等。
可变部分：包含文件名。
节省空间：通过可变部分灵活存储文件名。
问题：当文件删除时，会留下一个可变大小的空隙，可能需要在读取文件名时触发 页面错误（Page Fault），特别是在一个目录条目跨越多个页面时。

目录实现（6）—— 长文件名处理

📌 解决方案 3：固定长度目录条目，指向堆上的文件名

目录条目固定长度，但通过指针指向堆上的文件名。
优点

：
- 便于删除文件，避免压缩。
- 不需要填充字符来填充文件名后的空间。
问题

：
- 需要管理堆空间，可能引发 页面错误（Page Fault）。

目录实现（7）—— 搜索文件的方式

📌 文件搜索方式

线性搜索：逐个遍历目录中的条目。
哈希表：通过哈希函数加速查找过程。
缓存搜索结果：缓存最近的搜索结果，提高后续访问效率。

📌 总结目录实现的关键在于如何管理文件名、文件属性以及如何高效地进行文件查找。在现代文件系统中，通常结合多个策略来优化空间利用和性能，例如使用 哈希表 加速查找，或者通过堆管理长文件名。

共享文件（Shared Files）

📌 共享文件概念

共享文件 允许文件出现在多个目录中。
目录和共享文件之间的连接称为链接，文件系统实际上是一个 有向无环图（DAG），而不是传统的树形结构。

实现方式与问题

目录存储磁盘地址的问题

若目录直接保存文件的磁盘地址，需要在每个链接目录中复制地址（如目录B和C都链接文件A时，需存储两份地址）。
后果：若通过目录B或C修改文件（如追加内容），新分配的磁盘块仅对当前目录可见，导致数据不一致。

共享文件（2）

📌 文件系统包含共享文件

共享文件的实现通过链接来连接多个目录和文件。

共享文件（3）

📌 解决方案

不在目录中列出磁盘块地址，而是使用一个小的数据结构 iNode 来存储文件信息，称为 硬链接（Hard Link）。
硬链接：多个目录指向同一个 iNode，文件共享同一数据块。
符号链接（Symbolic Link）

：创建一个新的类型为 LINK的文件，包含目标文件的路径名，指向目标文件。
- 一个目录指向文件的 iNode。
另一个目录包含指向该文件的“路径”。

共享文件（4）— 硬链接

硬链接 是一个文件在多个目录中共享的数据块。
这使得文件内容可以在不同位置显示，并且每个位置的删除不会影响其他位置的数据。

共享文件（5）— 示例：硬链接

📌 例子

工作目录：/users/pat/bin/

原始文件列表：

1
2
3

total 4
-rwxr-xr-x 1 pat DP3832 1358 Jan 15 11:01 lcat
-rwxr-xr-x 1 pat DP3832 504 Apr 21 18:30 xtr

创建硬链接：
1
$ ln /users/steve/wb .

新的文件列表：

total 5
-rwxr-xr-x 1 pat DP3832 1358 Jan 15 11:01 lcat
-rwxr-xr-x 2 steve DP3725 89 Jun 25 13:30 wb
-rwxr-xr-x 1 pat DP3832 504 Apr 21 18:30 xtr

共享文件（6）— 符号链接

符号链接（Symbolic Link） 是一种特殊的链接，包含指向原始文件的路径。
创建符号链接：
1
$ ln -s /users/steve/wb ./symwb

新的文件列表：

total 5
-rwxr-xr-x 1 pat DP3832 1358 Jan 15 11:01 lcat
-rwxr-xr-x 1 pat DP3725 15 Jul 20 15:22 symwb --> /users/steve/wb
-rwxr-xr-x 1 pat DP3832 504 Apr 21 18:30 xtr

共享文件（7）— 删除文件

📌 删除符号链接的情况

删除原始文件时，符号链接变为“断开的链接（dangling link）”，即指向的目标文件不存在。
删除符号链接不会影响原始文件。

共享文件（8）— 删除文件

📌 删除文件时的操作

目录条目从目录中删除。
文件中的所有块返回到空闲块列表。
共享问题：如果文件有多个链接，只有当所有链接都删除时，文件才真正被清除。

共享文件（9）— 硬链接删除

硬链接通过在 iNode 中放置 引用计数 来管理文件的多个链接。
引用计数：计算指向该文件的目录数量。
文件删除：当引用计数为 0 时，释放文件的数据块。

71. 共享文件（10）— 符号链接的删除

符号链接

：
- 仅当原始文件被删除时，符号链接才变成“断开的链接”。
- 删除符号链接不会影响文件本身。

共享文件（11）— 符号链接的局限性

📌 符号链接的缺点

额外的磁盘空间和 iNode：需要额外的存储来保存链接文件。
路径遍历的额外开销：需要额外的开销来处理路径遍历。
悬挂链接（Dangling Link）：当原始文件移动或删除时，符号链接会失效。
多重副本问题：当文件被复制到其他介质时（例如磁带备份），符号链接可能会导致额外的副本问题。

共享文件（11）— 硬链接（Hard Link）的局限性

📌 硬链接的缺点

跨文件系统限制
- 硬链接要求所有链接与目标文件位于同一文件系统（因inode编号仅局部唯一）
- 移动文件到其他文件系统时
  
  ：
  - 系统自动复制文件内容（非链接）
  - 原链接与新文件引用计数独立更新
目录链接特权
- 仅超级用户（root）可创建目录的硬链接
- 防止风险：避免文件系统形成循环引用（破坏DAG结构）

总结

硬链接和符号链接都允许文件在多个位置出现，但它们在实现和功能上有显著区别：
- 硬链接 对文件的多个目录条目指向相同的 iNode。
符号链接 存储原文件的路径，如果原文件被删除，符号链接将变得无效。

磁盘空间管理

文件存储的策略有几种常见方式，主要分为：

连续分配（Contiguous Allocation）：
- 为一个 n 字节的文件分配 n 个连续的磁盘字节。
- 如果文件增长，必须重新分配空间并将文件移到磁盘上的新位置，这会导致外部碎片，且是一个代价较高的操作。
块分配（Block Allocation）：
- 将文件分成多个固定大小的块（例如，大小为 k 字节的块），然后将这些块分配给文件。
- 这种方式通常用于解决连续分配的问题，因为它允许文件分散在磁盘上的不同位置，而不必在物理上连续分布。

问题：连续分配

外部碎片：当文件增长时，可能没有足够的连续空间存储新内容，导致文件必须被移动到新的位置，这会增加开销并导致外部碎片。

几乎所有的文件系统都会将文件分成固定大小的块，这些块不需要是相邻的，从而避免了连续分配所带来的问题。

块大小（Block Size）

回顾

文件系统定义了块大小。
块大小 = 2^n * 扇区大小，也就是一个块由多个连续的扇区组成。
文件系统将磁盘视为一个由块组成的数组，文件需要分配相应的块，且必须管理磁盘上的空闲空间。

大块大小的优缺点

优点

：
- 较少的块数量，减少管理和寻址的开销。
- 提高了文件访问的速度。
缺点

：
- 内存碎片（Internal Fragmentation）：每个块的末尾可能会浪费一部分空间，尤其是当文件比块小的时候，浪费的空间较多。

小块大小的优缺点

优点

：
- 更高的磁盘空间利用率，因为每个块的空闲空间会更少。
缺点

：
- 增加了磁盘寻址的次数，导致文件访问速度较慢。

常见的块大小为 1KB、2KB 或 4KB。

块大小（2）

性能和空间利用率的冲突：

较大的块大小可以提供更高的磁盘数据传输速度，但会导致更低的空间利用率。
较小的块大小虽然提供更高的空间利用率，但会导致文件访问速度变慢。

块大小（3）

数据传输速率与空间利用率之间的关系

：
- 较大的块大小提供更高的磁盘数据传输速率，低空间利用率。
- 较小的块大小提供更高的空间利用率，但磁盘寻址更多，降低性能。

跟踪空闲块（1）

如何管理磁盘上的空闲块呢？有几种方法：

使用链表：每个块存储尽可能多的空闲磁盘块号码，形成链表。例如，使用 1KB 块和 32 位磁盘块号时，每个块可以存储 256 个空闲块的地址。

78. 跟踪空闲块（2）

使用位图（Bitmap）

：
- 磁盘上有 n 个块时，位图的长度为 n 位，每一位表示一个磁盘块的状态。
- 如果某个块为空闲状态，该位设置为 1；如果该块已分配，设置为 0。

位图方法通常更好，尤其是当位图能够完全存储在内存中的时候。

79. 跟踪空闲块（3）

位图与链表的对比：

位图：假设一个 16GB 的磁盘，块大小为 1KB，那么需要 2^24 位的位图，占用 2048 块。
链表：同样的磁盘，使用链表会需要 65793 个块来存储空闲块的地址。

位图占用的空间较小，除非磁盘几乎满了（即空闲块很少），链表才可能占用比位图更多的空间。

问题重述

我们有以下信息：

磁盘大小：16GB，块大小为1KB。 • 因此，总块数 = 16GB / 1KB = 2^24 块（因为 16GB = 2^34 bytes，1KB = 2^10 bytes，所以 2^34 / 2^10 = 2^24 块）。

两种管理空闲块的方法： • 位图（Bit map）：

◦ 每个块用1位表示是否空闲。

◦ 需要的总位数 = 2^24 位。

◦ 将这些位存储在磁盘块中：每个块是1KB = 8 * 1024 = 8192 位。

◦ 因此，需要的块数 = ceil(2^24 / 8192) = 2^24 / 2^13 = 2^11 = 2048 块。

• 链表（Linked list）：

◦ 每个空闲块存储下一个空闲块的地址。

◦ 假设地址用固定长度表示（如32位或4字节）。

◦ 每个空闲块可以存储：1KB / 4 bytes = 256 个地址（但这里提到的是255，可能是考虑到某些元信息）。

◦ 因此，需要的块数 = ceil(空闲块数 / 255)。

◦ 对于完全空的磁盘（所有块都空闲），空闲块数 = 2^24。

◦ 因此，需要的块数 = ceil(2^24 / 255) ≈ 65793 块。

比较： • 位图需要2048块，链表需要65793块（在磁盘几乎全空时）。

• 因此，位图通常更节省空间。

• 只有在磁盘几乎满（即空闲块很少）时，链表需要的块数可能少于位图的2048块。

80. 跟踪空闲块（4）

计数法（Counting）

：
- 不直接存储每个空闲块的地址，而是存储第一个空闲块的地址和后面连续空闲块的数量。
- 这种方法可以有效减少存储空间，尤其是在多个连续空闲块的情况下。

每个条目将包含一个磁盘地址和一个计数值，这种方法的空间利用效率更高，尽管每个条目需要更多的空间。

总结：

磁盘空间管理中，通过合理的块大小和空闲块跟踪方式，可以在性能和空间利用率之间找到平衡。位图和链表是两种常见的管理空闲空间的方法，而计数法则通过合并多个空闲块的管理来进一步优化空间利用。

文件系统可靠性（1）

文件系统的丢失可能是灾难性的，因此进行备份是应对各种情况（如灾难恢复或误操作）的重要手段。

备份目的：

灾难恢复：如果文件系统丢失或损坏，备份可以帮助恢复数据。
错误恢复：例如，通过回收站等方式恢复因用户错误而删除的文件。

备份存储介质：

三级存储（Tertiary Storage）

：通常指的是较为低成本的存储设备。
- 磁带（Tape）：可以存储数十GB甚至上百GB的数据，价格低廉（每GB成本非常低）。
- 访问方式：磁带是顺序访问设备，随机访问的速度较慢。
- 备份操作需要时间并且占用空间。

文件系统可靠性（2）

备份问题：

是否备份整个文件系统？
- 二进制文件、特殊I/O文件通常不需要备份。
是否备份未修改的文件？
- 通常不备份自上次备份以来未修改的文件。
增量备份：
- 例如：每月进行完全备份，每日进行修改文件的增量备份。
备份压缩：
- 在将数据写入磁带之前进行数据压缩，以节省存储空间。
如何备份活动中的文件系统？
- 不希望在备份时将系统关闭，这样会影响系统的可用性。
备份介质的安全性：
- 备份数据的安全性也需要保证，避免介质丢失或泄露。

文件系统可靠性（3）

磁盘到磁带的备份策略：

物理备份（Physical Dump）：
- 从磁盘的第一个块开始，一直到最后一个块，按顺序写入每个块。
- 优点：简单且快速。
- 缺点
  
  ：
  - 不能选择性地跳过某些目录。
  - 无法进行增量备份。
  - 无法按需恢复个别文件。
逻辑备份（Logical Dump）：
- 从指定目录开始，递归备份所有文件和目录，并且备份自某个基准日期以来发生更改的文件。
- 基准日期可以是上次的增量备份、上次的完整备份等。
- 也会备份所有修改文件所在路径上的所有目录。

文件系统一致性（1）

大多数系统提供一个工具程序来检查文件系统的一致性，常见的有：

Windows：scandisk
UNIX：fsck

一致性检查内容：

块（Blocks）
文件（目录）

fsck：检查块

基本事实：每个磁盘块必须属于某个文件（或目录），或在空闲列表中。
```
fsck
```
会构建两个表，分别记录每个块的计数信息。
- 读取所有i节点并标记已用的块。
- 检查空闲列表或位图，标记空闲块。

文件系统一致性（2）

不一致的状态：

丢失的块：
- 某些块既不在文件中，也不在空闲列表中，这些“丢失的块”应当添加到空闲列表中。
空闲列表中的重复块：
- 如果使用位图管理空闲块，空闲块不可能重复。如果发生这种情况，应该修复空闲列表，确保每个块只出现一次。
某块同时属于多个文件：
- 这种情况应该分配一个新的块，复制原块的内容，然后将其添加到文件中，并提醒用户该文件可能包含来自另一个文件的数据。
某块在文件中且也在空闲列表中：
- 这种情况下，应该从空闲列表中移除该块。

文件系统一致性（3）

fsck：检查目录

使用每个文件的计数器（而不是每个块的计数器）来检查目录。
从根目录开始递归遍历所有目录，增加每个文件的计数器，包含硬链接的文件也要计算在内。
比较这些计数器与i节点中存储的链接计数。

问题：

引用计数过大或过小

：
- 解决方法：纠正引用计数，强制i节点中的链接计数与实际目录条目的数量一致。

文件系统可靠性（4）

一致性检查：通过工具（如 fsck）检查文件系统中的不一致性，修复缺失的块、重复块以及错误的目录引用等问题，从而确保文件系统的健康状态。

缓存管理（Caching）

缓存是一种优化文件系统性能的技术，旨在减少磁盘I/O操作的开销。

避免磁盘I/O开销：缓存可以将频繁访问的数据存储在内存中，避免每次访问都去磁盘读取，减少磁盘I/O的负担。
块预读（Block Read Ahead）：当文件系统预测将要访问的块时，提前将这些块加载到缓存中，以提高缓存命中率。
减少磁盘臂运动：通过优化磁盘的寻道顺序，减少磁头的移动，避免磁盘寻道开销，从而提高性能。

示例文件系统（Example File Systems）

不同的操作系统有不同的文件系统，其中一些经典的例子包括：

MS-DOS 文件系统：早期的文件系统，主要用于MS-DOS操作系统。
Windows 98 文件系统：继承和扩展了MS-DOS的文件系统，增加了对更大硬盘和文件的支持。
Unix V7 文件系统：早期的Unix操作系统使用的文件系统，具有独特的设计和特点。

MS-DOS 文件系统（1）

MS-DOS文件系统中的目录项结构定义了文件的存储信息。这些目录项包含有关文件的信息，例如文件名、文件大小、文件的磁盘位置等。

MS-DOS 文件系统（2）

不同块大小的最大分区：不同的块大小对最大支持的分区大小有影响，MS-DOS文件系统的不同配置可能有不同的限制。

FAT32

FAT32 是在Windows 95第二版中引入的文件系统，它支持更大的磁盘分区和文件。
28位磁盘地址：FAT32使用28位磁盘地址，可以理论上支持最大8TB的分区（2⁸ × 2¹⁵字节），但通常限制为2TB。

FAT32相比FAT16的优势：

支持更大的磁盘：FAT32能够处理比FAT16更大的磁盘。
较大的分区支持：使用FAT32时，8GB的磁盘可以作为一个单独的分区，而使用FAT16时需要将其分成四个分区。
更小的块大小：在相同大小的磁盘分区中，FAT32能够使用更小的块大小，从而提高存储空间的利用率。

FAT32（续）

FAT32的缺点

：
- 文件系统管理较为简单，缺乏较强的权限控制和安全性。
- 不支持超过2TB的分区（虽然理论上可以支持）。

97. Windows 98 文件系统（1）

在Windows 98中，扩展了MS-DOS的文件系统，采用了新的目录项结构来支持更长的文件名和额外的文件属性。

扩展MS-DOS目录项：Windows 98引入了更长的文件名（长文件名，LFN），并采用特殊的目录项格式来存储这些长文件名。

Windows 98 文件系统（2）

长文件名条目：Windows 98文件系统使用多条目录项来存储一个长文件名。每个条目存储文件名的一部分以及一些附加的元数据（如校验和）。

Windows 98 文件系统（3）

长文件名存储示例

：
- 文件名可能非常长，如“the quick brown fox jumps over the lazy dog”。这种长文件名会被拆分成多个条目存储，以便在文件系统中管理。

UNIX V7 文件系统（1）

UNIX V7 文件系统是早期Unix系统中使用的文件系统，具有树状目录结构，从根目录开始组织文件。

文件名限制：文件名最大支持14个字符，并且可以包含任何ASCII字符（除了/和NUL字符）。
目录项结构：每个目录项有两个字段：文件名和文件的i节点号（占2字节）。
文件系统限制：文件系统最多支持64K个文件。

UNIX V7 文件系统（2）

i节点（inode）：每个文件和目录都有一个i节点，它包含了文件的元数据，如文件的权限、大小、创建时间、最后访问时间等。

练习题 2：Unix 文件系统最大文件大小计算

问题描述 假设一个 Unix 文件系统使用如下参数：

块大小（Block Size）：1KB
磁盘地址大小：4 字节（即每个指针占 4 字节）
每个 i 节点（inode）结构包含：
- 10 个 直接块指针（Direct Block Pointers）
- 1 个 单级间接块指针（Single Indirect Pointer）
- 1 个 双级间接块指针（Double Indirect Pointer）
- 1 个 三重间接块指针（Triple Indirect Pointer）

分析与计算过程：

1. 直接块（Direct Blocks）

每个直接块指针指向一个 1KB 的数据块
共 10 个直接块指针 👉 可以访问：10 × 1KB = 10KB

2. 单级间接块（Single Indirect Block）

一个块大小为 1KB，可以容纳的指针数为：

\[ \frac{1024 \text{ bytes}}{4 \text{ bytes/pointer}} = 256 \text{ 个指针} \]
所以单级间接块可以访问：256 × 1KB = 256KB

3. 双级间接块（Double Indirect Block）

第一层：一个块中有 256 个指针，指向单级间接块
每个单级间接块再指向 256 个数据块

\[ 256 × 256 = 65,536 \text{ 块} \Rightarrow 65,536KB = 64MB \]

4. 三重间接块（Triple Indirect Block）

三层结构：每层 256 个指针

\[ 256 × 256 × 256 = 16,777,216 \text{ 块} \Rightarrow 16,777,216KB ≈ 16GB \]

总文件大小计算：

类型	块数	大小（KB）
直接块	10	10KB
单级间接块	256	256KB
双级间接块	65,536	65,536KB ≈ 64MB
三重间接块	16,777,216	16,777,216KB ≈ 16GB
总计	16,843,018 块	16,843,018KB ≈ 16.06GB

结论：

该 Unix 文件系统在使用 1KB 块、4 字节地址，并配备 10 个直接块指针、单/双/三重间接指针的情况下，最大文件大小约为 16.06GB。

这种文件系统的设计采用了直接指针和间接指针的组合，通过不同级别的间接块使得文件可以扩展到更大的容量。

UNIX V7文件系统（3）

在Unix文件系统中，查找文件路径涉及多个步骤。假设我们需要查找文件 /usr/ast/mbox，那么路径查找的步骤通常包括：

读取根目录（/）的i节点：首先需要读取根目录的i节点，它包含了文件系统的结构信息。
读取根目录的内容：接下来读取根目录，获取其中的文件和子目录信息。
读取/usr目录的i节点：然后读取 /usr 目录的i节点，获取 /usr 目录的文件结构。
读取/usr目录的内容：读取 /usr 目录本身，获取其子目录（例如 ast）的信息。
读取/ast目录的i节点：读取 ast 子目录的i节点。
读取/ast目录的内容：读取 /usr/ast 目录的内容，获取 mbox 文件的i节点。
读取mbox文件的i节点：最终读取 mbox 文件的i节点，得到文件的数据块信息。

小测验（Quiz）

问题：

需要多少次磁盘操作来读取文件 /usr/student/lab/mp1.tar 的第二个数据块？为什么？

文件和数据块需要另当别论，会多一次读取！

假设条件：

分析步骤：

读取根目录的i节点：首先，系统需要读取根目录 / 的i节点。
读取根目录的内容：然后需要读取根目录，查找其中 /usr 目录的条目。
读取/usr目录的i节点：接着，读取 /usr 目录的i节点。
读取/usr目录的内容：读取 /usr 目录，查找其中 /usr/student 目录的条目。
读取/usr/student目录的i节点：接下来，读取 /usr/student 目录的i节点。
读取/usr/student目录的内容：读取 /usr/student 目录，查找其中 /usr/student/lab 目录的条目。
读取/usr/student/lab目录的i节点：读取 /usr/student/lab 目录的i节点。
读取/usr/student/lab目录的内容：读取 /usr/student/lab 目录，查找其中 mp1.tar 文件的条目。
读取mp1.tar文件的i节点：然后，读取 mp1.tar 文件的i节点，得到文件的块信息。
读取mp1.tar文件的第二个数据块：最后，读取 mp1.tar 文件的第二个数据块。

总共需要进行的磁盘操作次数：

10次磁盘操作，包括9次目录和文件i节点的读取，以及1次数据块的读取。

结论：

需要 10次磁盘操作 来读取文件 /usr/student/lab/mp1.tar 的第二个数据块。

这个过程展示了传统Unix文件系统中路径查找和文件数据读取的基本操作。每一步都需要对路径上的每一个目录执行磁盘操作。

Chapter 4: File Systems（文件系统）

大纲

1. Files（文件）

2. Directories（目录）

3. File System Implementation（文件系统实现）

4. Example File Systems（文件系统示例）

Overview（概述）

文件系统的长期存储需求（Requirements for Long-Term Information Storage）

解决方案（Solution）

** Basic Functions of File System（文件系统的基本功能）**

File System（文件系统）

用户视角（User’s View on File Systems）

实现者视角（Implementer’s View on File Systems）

Files（文件）

文件内容（Contents）

File Naming（文件命名）

1. 文件命名规则（File Naming Rules）

2. 文件扩展名（File Extensions）

File Structure（文件结构）

1. 文件的组织方式（File Organization Methods）

2. 三种文件结构（Three Kinds of File Structures）

File Types（文件类型）

1. 文件类型分类（File Types）

（1）普通文件（Regular Files）

（2）目录文件（Directories）

（3）特殊文件（Special Files）

File Types（文件类型示例）

文件访问（File Access）

1. 顺序访问（Sequential Access）

2. 随机访问（Random Access）

文件属性（File Attributes）

文件操作（File Operations）

示例：Unix 文件拷贝程序（An Example Program Using File System Calls）

目录（Directory）

目录内容（Contents）

** 目录（Directory）**

目录的组织方式（Organize the Directory to Obtain）

目录组织的目标

目录结构（Directory Structure）

1. 单级目录结构（Single-Level Directory）

2. 两级目录结构（Two-Level Directory）

3. 层次化目录结构（Hierarchical Directory）

** 单级目录系统（A Single-Level Directory System）**

特点（Characteristics）

单级目录系统的优缺点（A Single-Level Directory System）

优点（Advantages）

缺点（Disadvantages）

两级目录系统（Two-Level Directory Systems）

特点（Characteristics）

示例（Example）：

两级目录系统的优缺点（Two-Level Directory Systems）

优点（Advantages）

缺点（Disadvantages）

** 层次化目录系统（Hierarchical Directory Systems）**

特点（Characteristics）

层次化目录系统示例（Hierarchical Directory Systems Example）

** 层次化目录系统的优缺点（Advantages and Disadvantages of Hierarchical Directory Systems）**

优点（Advantages）

路径名（Path Name）

两种指定文件路径的方法（Two Different Methods for Specifying File Names in a Directory Tree）

路径表示方式（Path Representation in Different Systems）

特殊目录符号（Special Entries in the File System）

** UNIX 目录树（A UNIX Directory Tree）**

示例（Example）

31. 目录操作（Directory Operations）

常见目录操作（Common Directory Operations）

Linux 目录结构（Linux Directory Structure）

Linux 文件系统的特点（Characteristics of Linux File System）

Linux 目录结构（Common Linux Directories）

文件系统实现（File System Implementation）

内容（Contents）

文件系统布局（File System Layout）

主引导记录（MBR, Master Boot Record）

每个分区的结构

操作系统启动（OS Startup）

文件系统布局（File System Layout）

文件字节 vs 磁盘扇区（File Bytes vs Disk Sectors）

文件存储的实现（Implementing Files）

如何存储文件数据？

1️⃣ 连续分配（Contiguous Allocation）

Basic Functions of File System（文件系统的基本功能）

目录（Directory）

单级目录系统（A Single-Level Directory System）

层次化目录系统（Hierarchical Directory Systems）

层次化目录系统的优缺点（Advantages and Disadvantages of Hierarchical Directory Systems）

UNIX 目录树（A UNIX Directory Tree）

连续分配（Contiguous Allocation）

使用 FAT 进行链接分配（Linked List Allocation Using FAT）

索引分配（Indexed Allocation）的机制

目录实现（4）—— 长文件名处理

目录实现（5）—— 长文件名处理

目录实现（7）—— 搜索文件的方式

共享文件（Shared Files）

共享文件（2）

共享文件（4）— 硬链接

块大小（2）