【总结】【OS】成组链接法
| 特性 | 说明 |
|---|---|
| 基本思想 | 将空闲磁盘块分成若干组，每组内采用栈结构管理，组间通过链表链接。内存中常驻超级块，记录当前组的空闲块信息，以实现高效分配与回收。 |
| 数据结构（内存） | 超级块（Super Block）包含： - 当前组空闲块数 free_count- 空闲块栈 free_stack[]，存储当前组可分配的空闲块号（栈顶块号可分配） |
| 数据结构（磁盘） | 每组的第一块（索引块）存储： - 下一组第一块的块号（链指针） - 本组其余空闲块号（不含自身） 该索引块本身不存储文件数据，仅用于组织空闲块。 |
| 分配过程 | 1. 若超级块中free_count > 1，则从栈顶取出块号分配，free_count--。2. 若 free_count = 1，则栈顶块号指向下一组索引块。先将该块内容读入超级块（加载下一组信息），然后将该块分配出去（作为数据块使用）。 |
| 回收过程 | 1. 若超级块栈未满，直接将回收块号压栈，free_count++。2. 若栈已满，则将当前超级块内容（ free_count和free_stack）写入回收块，然后将超级块重置：free_count = 1，栈中唯一元素为回收块号（该块成为新组索引块）。 |
| 优点 | - 分配和回收多数情况只需访问内存超级块，减少磁盘 I/O。 - 分组结构缩短搜索链长度，提升管理效率。 - 适用于大规模磁盘空间管理。 |
| 缺点 | - 超级块在内存，系统崩溃可能导致信息丢失（需持久化机制）。 - 实现较复杂，需处理组间切换的边界条件。 |
| 应用 | 经典应用于 UNIX 文件系统（如 UFS）的空闲块管理。 |
| 相关计算 | 设磁盘块大小为B字节，块号用N字节表示，则每组最多可容纳空闲块数为：(B / N) - 1（其中一项存下一组块号）。超级块栈大小通常为此值。 |
| 注意事项 | - 超级块需定期写回磁盘以保证一致性。 - 分配和回收操作需互斥，防止竞态条件。 - 初始化时从磁盘读取超级块信息（通常位于固定位置）。 |
| 类别 | 核心内容 | 详情说明 |
|---|---|---|
| 基本定义 | 大型文件系统的空闲磁盘块管理方法，结合空闲表法与空闲链表法优点，解决空闲表 / 链表过大问题，UNIX/Linux 系统采用 | 核心思想：分组管理 + 链栈结合，平衡内存开销与分配速度 |
| 核心数据结构 | 1. 空闲盘块号栈（内存）2. 组描述块（外存）3. 超级块（外存 + 内存） | 1. 栈记录当前组空闲块数 N 与块号，分配弹栈、回收压栈2. 每组首个块为组描述块，记录下一组块数与块号，最末组 S.free (0)=0（结束标志）3. 系统启动时读超级块入内存，同步内外存超级块数据 |
| 分配流程（k 块 / 组） | 1. 检查栈顶：栈非空则弹栈分配2. 栈空处理：读当前组描述块（原栈底块）的下一组信息入栈，释放原组描述块3. 重复 1-2 直到分配成功 | 例：k=100，当前组分配完时，加载下一组 100 个块号入栈，原组描述块转为普通空闲块 |
| 回收流程（k 块 / 组） | 1. 压栈回收：将释放块号压入空闲栈2. 栈满处理：新建组，当前栈中 k 个块作为新组，原栈底块作为组描述块，记录下一组信息，新组信息写入超级块3. 同步超级块到外存 | 例：k=100，栈满时，新组的组描述块记录旧组信息，新块号压入新栈 |
| 关键计算（k=100） | 1. 初始建树：每组最多 k 块，最末组 k-1 块2. 读写磁盘次数：仅组切换时读写外存，单次分配 / 回收通常仅内存操作 | 分配 / 回收 N 块时，磁盘 I/O 次数≈N/k（组切换次数） |
| 性能对比 | 与空闲表法、空闲链表法对比 | 1. 内存开销：小（仅存当前组栈 + 超级块）2. 分配速度：快（内存栈操作，组切换才读写磁盘）3. 适用场景：大型文件系统，解决空闲表 / 链表过大问题 |
| 408 高频易错点 | 1. 栈空 / 栈满时的组切换逻辑2. 最末组结束标志（S.free (0)=0）3. 超级块同步机制（防止数据丢失） | 1. 栈空是加载下一组，栈满是创建新组2. 结束标志常作为选择题考点3. 超级块需保证内存与外存数据一致 |
某个系统采用成组链接法来管理磁盘的空闲空间，目前磁盘的状态如图所示。
（1） 该磁盘中目前还有多少个空闲盘块？
（2） 请简述磁盘块的分配过程。
（3） 在为某个文件分配3个盘块后，系统要删除另一文件，并回收它所占的5个盘块，它们的盘块号依次为700、711、703、788、701，请画出回收后的盘块链接情况
接下来分配301号盘块
从更新后的内存栈中取栈顶盘块号（即 301 号），分配给进程；栈内空闲盘块数更新为N=100-1=99