成组链接法介绍
计算机上的⽂件是记录在磁盘上的，⽽磁盘空间的分配是以盘块为单位的，那么如何管理磁盘中已经被使⽤的块和未被使⽤的块是操作系统必须要考虑的问题。下⾯将介绍⽐较实⽤⼜有点复杂的成组链接法，看它是如何把磁盘中所有的空闲盘块都记录起来，⼜不耗费太多的内存空间。
请看下图：
下⾯的⽂字来⾃汤⽒的操作系统教材：
1、空闲盘块的组织
（1）空闲盘块号栈：⽤来存放当前可⽤的⼀组空闲盘块的盘块号(最多含100 个号)，以及栈中尚有的空闲盘块号数N。顺便指出，N 还兼作栈顶指针⽤。例如，当N=100 时，它指向S.free(99)。由于栈是临界资源，每次只允许⼀个进程去访问，故系统为栈设置了⼀把锁。（只有这个是放在内存中的，其它是在磁盘上。）
(2) ⽂件区中的所有空闲盘块被分成若⼲个组，⽐如，将每100 个盘块作为⼀组。假定盘上共有10 000
个盘块，每块⼤⼩为1 KB，其中第201～7999 号盘块⽤于存放⽂件，即作为⽂件区，这样，该区的最末⼀组盘块号应为7901～7999；次末组为7801～7900……；第⼆组的盘块号为301～400；第⼀组为201～300，如上图右部所⽰。
(3) 将每⼀组含有的盘块总数N 和该组所有的盘块号记⼊其前⼀组的第⼀个盘块的
S.free(0)～S.free(99)中。这样，由各组的第⼀个盘块可链成⼀条链。
(4) 将第⼀组的盘块总数和所有的盘块号记⼊空闲盘块号栈中，作为当前可供分配的空闲盘块号。
(5) 最末⼀组只有99 个盘块，其盘块号分别记⼊其前⼀组的S.free(1) ～S.free(99)中，⽽在S.free(0)中则存放“0”，作为空闲盘块链的结束标志。(注：最后⼀组的盘块数应为99，不应是100，因为这是指可供使⽤的空闲盘块，其编号应为(1～99)，0号中放空闲盘块链的结尾标志。)
2、空闲盘块的分配与回收
当系统要为⽤户分配⽂件所需的盘块时，须调⽤盘块分配过程来完成。该过程⾸先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出⼀空闲盘块号，将与之对应的盘块分配给⽤户，然后将栈顶指针下移⼀格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后⼀个可分配的盘块号。由于在该盘块号所对应的盘块中记有下⼀组可⽤的盘块号，因此，须调⽤磁盘读过程，将栈底盘块号所对应盘块
的内容读⼊栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有⽤数据已读⼊栈中)。然后，再分配⼀相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1 并返回。
在系统回收空闲盘块时，须调⽤盘块回收过程进⾏回收。它是将回收盘块的盘块号记⼊空闲盘块号栈的顶部，并执⾏空闲盘块数加1 操作。当栈中空闲盘块号数⽬已达100 时，表⽰栈已满，便将现有栈中的100个盘块号记⼊新回收的盘块中，再将其盘块号作为新栈底。
实例讲解成组链接法
如果对上⾯的讲解感到迷惑的话，请看下⾯的例⼦，这是⼀个很经典的练习题：
例题.某个系统采⽤成组链接法来管理磁盘的空闲空间，⽬前磁盘的状态如图1所⽰。
（1） 该磁盘中⽬前还有多少个空闲盘块？
（2） 请简述磁盘块的分配过程。
（3） 在为某个⽂件分配3个盘块后，系统要删除另⼀⽂件，并回收它所占的5个盘块，它们的盘块号依次为700、711、703、788、701，请画出回收后的盘块链接情况。
图1：当前磁盘状态
1
解答：
（1）：301；⾸先看空闲盘块号栈，此时N=2，表⽰有两个空闲盘块299、300，⽽盘块300号上⾯⼜写着有100个空闲盘块：301-400，它还有下⼀个链接的盘块400；在盘块400中，记录有100个空闲盘块401-500；然后⼜链接到500号盘块，在500号盘块中，虽然N=100，但是第⼀个是0，它表⽰空闲盘块链的结尾。因此，总共的空闲盘块有：299、300、301-400、401-500、501-599；即301个空闲盘块。
（2）：参考介绍部分。
（3）：这个是最重要的部分，也是理解整个成组链接法的关键部分，我看很多博客都没有详细写明分配和回收的过程，因此这也正是我写这篇博客的原因。
步骤1、分配三个空闲盘块：
分配的过程是这样的，⾸先看空闲盘块号栈，发现N=2，那么到达栈顶即S.free[2-1]=299，即把299号盘块分配出去了，这时磁盘状态
如下：
然后分配第⼆个盘块，这时N=1，如果再分配就会变成空栈了，因为S.free[N-1]=S.free[0]!=0，所以需要将300号盘块的内容拷贝到空闲盘块号栈，并分配300号盘块（如果S.free[0]=0，则表⽰没有空闲盘块，将会阻塞进程）：
接下来分配301号盘块你也会做啦：
回收700、711、703、788、701号盘块：
回收的过程也是从栈顶开始的，⾸先看N=99，然后回收700，会将700放在S.free[N]的位置，然后将N加1变成100：
然后回收711号盘块，因为此时空闲栈的N=100，已经满了，如果再回收，需要将空闲盘块栈的内容移动到711号盘块上，然后将空闲盘块栈的S.free[0]设置为711，N设置为1：
最后回收703/788/701也是同理：
发布评论