成组链接法是一种结合了空闲表法和空闲链表法优点的磁盘空闲空间管理方法，主要用于大型文件系统（如 UNIX、Linux），有效解决了空闲表/链表过大的问题。

 

1. 核心思想

分组管理：将空闲盘块分组（如100块/组），每组首个盘块（组描述块）记录下一组的盘块数量和盘块号。

链栈结合：

• 内存维护空闲盘块号栈（存当前组盘块号）。
• 组间通过组描述块链接（类似链表）。

---

2. 数据结构示例

假设磁盘空闲盘块为 ( 201 ~ 7999 )，分组如下：

• 组1：( 201 ~ 300 )（300号为组描述块，记录组2信息）。
• 组2：( 301 ~ 400 )（400号记录组3信息）。
• ...
• 组末：( 7901 ~ 7999 )（无下组，7900号描述块存结束标志“0”）。

内存栈初始存组1盘块号 ( 201 \sim 300 )（栈顶指针指向300）。

---

3. 盘块分配流程

普通分配（栈非空）：

• 指针 取栈顶块（如分配299号，指针指向298，栈内空闲数 ( -1 )）。

栈底分配（需加载下组）：

若分配栈底块（如300号）：

1. 读300号块内容（组2盘块号 ( 301 ~ 400 )）入栈。
2. 分配300号块（原组描述块数据已备份到栈）。

 

---

4. 盘块回收流程

栈不满（<100 块）：

• 回收块号压栈（如回收200号，栈指针 ( )，空闲数 ( +1 )）。

栈满（ =100 块）：

新建组描述块：

1. 原栈中100块号（如 ( 201 ~ 300 )）写入新回收块（如200号）。
2. 新回收块（200号）成为新组描述块，栈重置为 ()（空闲数 ( =1 )）。

---

 

5. 超级块（Super Block）

• 存储位置：磁盘卷头，记录分组信息（如每组块数、组链接关系）。
• 内存同步：系统启动时读入内存，操作后需保持内存与磁盘超级块一致（一致性至关重要，否则文件系统崩溃）。

 

---

6. 与其他方法对比

方法	管理单位	内存开销	分配速度	适用场景
空闲表法	连续盘区	大（表随磁盘增大）	快（连续分配）	小磁盘/简单系统
空闲链表	盘块/盘区	中（链表指针）	块链慢/盘区快	老系统/嵌入式
位示图法	单盘块	小（位示图）	极快（位运算）	现代OS（如Linux）
成组链接	分组盘块	小（栈+超级块）	快（栈操作+组加载）	大型UNIX/Linux文件系统

 

---

核心考点

1、分配/回收示例：

• 分配：栈空时读组描述块（I/O一次），否则内存操作。
• 回收：栈满时写新组描述块（I/O一次）。

2、超级块作用：

• 分组元信息存储，内存与磁盘同步（ crash 恢复依赖此）。

3、优势总结：

• 内存开销小（仅栈+超级块）。
• 分配高效（栈操作 O(1)，组切换 I/O 极少）。
• 无外部碎片（离散分配，分组优化大块分配）。

---

总结

        成组链接法是大型文件系统的“高效管家”，通过分组+链栈设计，平衡了分配速度与内存开销。理解其栈操作（分配弹栈，回收压栈）和组描述块切换机制，能深入掌握 UNIX/Linux 文件系统的存储管理精髓。

✨ 一句话记忆：成组链接分组管，栈存当前组块号，分配弹栈栈底换组，回收压栈满组开新！ ✨