文件分配与空闲空间

复习

文件与文件描述符：把设备和持久数据变成可读写的字节流
目录与路径：用树形名字组织大量文件
文件怎样落到磁盘：数据块、元数据和索引节点的基本关系

TL;DR

文件的数据块怎么摆放，有几种分配方式：连续、链式、索引
连续分配快但难扩展，链式灵活但随机访问慢，索引方式折中
磁盘上的空闲块，需要专门的空闲空间管理
常见做法：位图、空闲链表

正文

　　上一章说，文件的数据被拆成若干块，inode 记着这些块的位置。可这些块到底怎么摆放？哪些块是空的、可以拿来用？这一章回答这两个问题。

数据块怎么摆

　　把文件的数据块放到磁盘上，常见有三种思路。

连续分配：一个文件的数据块，占据磁盘上一段连续区域。

优点：读写快，找第 n 块只要“起始位置 + n”
缺点：文件长大后，后面可能没空位了，只好挪地方，代价大

链式分配：每一块里留一小段，指向下一块，像链条一样串起来。

优点：灵活，随便哪块空的都能接上，文件扩展方便
缺点：想找第 n 块，得从头上顺着链一个个找，随机访问很慢

索引分配：单独拿出一个“索引块”，里面存着这个文件所有数据块的编号。

优点：既能灵活分配，又能直接跳到任意一块
缺点：索引块本身要占空间；文件很大时，一个索引块可能不够，还得“索引套索引”
这正是 inode 里记录数据块位置的常见做法

方式	随机访问	扩展	代价
连续	快	难	需连续空间
链式	慢	易	要顺链查找
索引	快	易	需索引块

空闲空间怎么管

　　有了文件的摆放方式，还得知道“磁盘上哪些块还空着”。常见的管理方法有：

位图（bitmap）：用一位代表一个块，0 表示空闲、1 表示占用。简单直观，查找连续的若干空闲块也方便。
空闲链表：把所有空闲块用链串起来，分配时从链上取。
分组、计数等变体：为了减少管理开销、加快查找。

　　位图很受欢迎——它直观、便于快速扫描，也能轻松找出一段连续的空闲块。

分配与回收的循环

　　于是，文件系统的日常就是这样一个循环：

创建文件 → 从空闲空间里找块 → 更新 inode 指向这些块
删除文件 → 把它的块标记回空闲 → 释放 inode

　　把“数据怎么放”和“空闲块怎么管”这两件事打理清楚，磁盘上的文件才能既找得到、又用得省。可磁盘很慢，每次读写都要等，怎么缓解？下一章，我们看缓冲与页面缓存。

思考题

　　索引分配比链式分配更适合“随机读写”，为什么？如果文件特别大，一个索引块装不下所有数据块编号，可以怎么办？

小结

知识点

三种数据块分配方式：连续、链式、索引
连续快但难扩展，链式灵活但随机访问慢
索引方式折中，inode 常采用
空闲空间管理：位图、空闲链表

参考资料

Wikipedia(zh)：文件系统：文件分配
Wikipedia(zh)：空闲空间管理：空闲空间

　　因为索引分配把“所有数据块的位置”集中记录在一个索引块里，想访问第 n 块，直接查索引就能一步定位；链式分配则必须从第一块开始，顺着链一路找过去，访问靠后的块很慢。所以随机读写场景下索引占优。若文件太大、一个索引块装不下所有编号，可以用多级索引：索引块里存的不是数据块号，而是“下级索引块”的编号，逐级展开；也可以让 inode 同时保留直接、间接、双重间接等入口。这正是“加一层”应对规模问题的又一例。