[操作系统]28. FAT 和 UNIX 文件系统

[supergem3000]

28. FAT 和 UNIX 文件系统 (jyywiki.cn)

磁盘上的数据结构

文件系统实现：文件=“虚拟”磁盘，目录=文件/目录的集合 磁盘不是Random Access Memory，是block device，按照块读写。 用block device模拟RAM（比如通过指针直接读写某个位置），会出现严重的读写放大。因此需要更适合磁盘的数据结构。

敌人：读写放大。被迫读写连续的一块内存。 朋友：局部性+缓存。适当地排布数据，使得临近的数据有 “一同访问” 的倾向；数据暂时停留在内存，延迟写回。

File Allocation Table (FAT)

从 5.25" 软盘开始：单面 180 KiB，360 个 512B 扇区 (sectors)。文件系统应该选用怎样的数据结构？ 文件：struct block * 的链表。任何复杂的高级数据结构都显得浪费。 目录：目录就是一个普通的文件。操作系统会对文件的内容作为目录的解读。

用链表存储数据：两种设计

• 在每个数据块后放置指针 优点：实现简单、无须单独开辟存储空间 缺点：数据的大小不是2^k；单纯的 lseek 需要读整块数据（需要把链表从头开始读一遍才能找到文件块所在位置）
• 将指针集中存放在文件系统的某个区域 优点：局部性好；lseek 更快 缺点：集中存放的数据损坏将导致数据丢失 哪种方式的缺陷是致命、难以解决的？第一种的读放大是无法解决的。第二张怕数据损坏，可以多存几份。

可以查阅Microsoft FAT Specification了解FAT具体定义和实现。

FAT性能：小文件比较合适。但大文件的随机访问不太行，比如4GB的文件跳到末尾有2^20次链表next操作。连续访问性能更佳。 FAT可靠性：维护若干个FAT副本防止元数据损坏。损坏的cluster也能在FAT中标记。

ext2/UNIX 文件系统

按对象方式集中存储文件/目录元数据（inode） 为大小文件区分 fast/slow path。小的时候用数组，大的时候用树。

ext2性能：inode 有 “集中存储” 的局部性，通过内存缓存减少读/写放大。大文件的随机读写性能提升明显。 ext2可靠性：依然是个很大的问题。存储 inode 的数据块损坏是很严重的。