操作系统原理：成组链接法，提高空闲块管理效率

对空闲块链表的改进是将空闲盘块分成若干组，每一组空闲盘块的地址存放在上一个空闲盘块组的第一个空闲块中，该组中其余n-1个空闲盘块是实际空闲的，如图7-7所示。假设每100个空闲块为一组。通常第一组可能不足100块，第一组空闲盘块的地址（块号）通常放在一个专用块中，专用块的第1个单元给出下一组空闲盘块的个数，第2个单元以后存放下一组空闲盘块的地址（块号）；第二组有100个空闲盘块，其地址（块号）放在第一组中的第一个空闲盘块中，该块的第1个单元给出第二组空闲盘块的个数，第2个单元以后存放第二组空闲盘块的地址（块号）；以此类推，组与组之间形成链接关系。最后一组有99个空闲盘块，其地址（块号）放在前一组中的第一个空闲盘块中，而该块的第二个单元填“0”，表示该块中存放的是最后一组的块号，空闲链接到此结束。这种方式成为成组链接。

图7-7　空闲块成组链接表

系统在初始化时首先把专用块内容读取到内存中，当需要分配空闲块时，就直接在内存中找到哪些块是空闲的，每分配一块后把空闲块数减1。但在把一组中的第一个空闲块分配出去之前，应把登记在该块中的下一组的块号及块数保存到专用块中（此时原专用块中的信息已经无用，因为它指出的一组空闲块都已被分配了）。当一组空闲块被分配完后，则再把专用块的内容读到内存中，指出下一组可供分配的空闲块。

假设初始化时系统已把专用块读入内存储器三单元开始的区域中，分配和回收算法如下。

（1）分配——空闲块

查L单元内容（空闲块数）：

当空闲块数＞1，i=L+空闲块数；

从i单元得到——空闲块号；

把该块分配给申请者；

空闲块数减1。

当空闲块数=1，取出L+1单元内容（一组的第一块块号或0）；(www.xing528.com)

取值等于0，无空闲块，申请者等待；取值不等于0，把该块内容复制到专用块；该块分配给申请者；

把专用块内容读取到内存L开始的区域。

（2）归还——块

查找L单元的空闲块数；

当空闲块数＜100，空闲块数加1；

j：=L+空闲块数；

归还块数填入j单元；

当空闲块数=100，把内存中登记的信息写入归还块中；把归还块号填入L+l单元；

将L单元置换成1。

采用成组链接后，分配、回收空闲块时均在内存中查找和修改，只有在一组空闲块分配完或空闲的磁盘块构成一组时才需要启动磁盘读写。因此，成组链接的管理方式比普通的链接方式效率高。

这种方案的优点是能够迅速找到大量空闲盘块地址。有些UNIX版本便采用这种方案。