文件存储空间分配方法与内存分配有许多相同之处,即同样采用连续或离散分配方式。文件存储空间的分配单位是磁盘块而不是字节。
1 空闲表法
空闲表法属于连续分配方式,它与内存的动态分配方式雷同,它为每个文件分配一块连续的存储空间,即系统也为外存上所有空闲区建立一张空闲表,每个空闲区对应于一个空闲表项,其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块号等信息,再将所有空闲区按其起始盘块号递增排列。
空闲盘区的分配与内存的动态分配类似,同样采用首次适应算法,循环首次适应算法等。
系统在对用户所释放的存储空间进行回收时,也采取类似于内存回收的方法,即考虑回收区是否与空闲表中插入点的前区和后区相邻接,对相邻接者应该予以合并。
当文件较小时,采用连续分配方式,当文件较大时,可采用离散分配方式。
2 空闲链表法
空闲链表法是将所有空闲盘区拉成一条空闲链。把链表分成两种形式,空闲盘块链和空闲盘区链。
2.1 空闲盘块链
这是将磁盘上的所有空闲空间,以盘块为单位拉成一条链。
当用户因创建文件而请求分配存储空间时,系统从链首开始,依次摘下适当数目的空闲盘块分配给用户。
当删除文件而释放空间时,系统将回收的盘块依次插入空闲盘块链的末尾,其优点是用于分配和回收一个盘块的过程简单,但在为文件分配盘块时,可能要重复操作多次。
2.2 空闲盘区链
这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链,在每个盘区上除了含有只是下一个空闲盘区的指针外,还应有能指明本盘区大小(盘块数)的信息。
盘区分配与内存的动态分配类似,可采用首次适应算法,在回收盘区时,同样也要将回收区和相邻接的空闲盘区相合并,在采用首次适应算法时,可以采用显式链接法提高检索速度,在内存中为空闲盘区建立一张链表。
3 位示图法
利用二进制的一位表示磁盘中的一个盘块的使用情况,当其值为0时,表示对应的盘块空闲,为1时,表示已经分配,磁盘上的所有盘块都有一个二进制位与之对应。由所有盘块所对应的位构成一个集合,称为位示图,通常可用m×n个位数来构成位示图,并使m×n等于磁盘的总块数。
对于盘块的分配分为如下三步:
顺序扫描位示图,从中找出一个或一组值为0的二进制位。
将所找到的一个或一组二进制位转换成与之赌赢的盘块号。
修改位示图。
对于盘块的回收分为如下两步:
- 将回收盘块的盘块号转换成位示图中的行号和列号。
- 修改位示图。
优点
从位示图中很容易找到一个或一组相邻接的空闲盘块。
由于位示图很小,占用空间少,因而可将其保存在内存中,进而使在每次进行盘区分配时,无需首先把盘区分配表读入内存,节省磁盘启动时间。
3 成组链接法
空闲表法和空闲链表法都不适用于大型系统,因为这会使空闲表或空闲链表很长,在UNIX采用的成组链接法,结合上述两种方法。
- 空线盘块的组织,空闲盘块栈用来存放当前可用的一组空闲盘块的盘块号(最多含100个号),以及栈中尚有的空闲盘块号数N,顺便指出,N兼做栈顶指针使用,栈是临界资源,系统设置一把锁供进程互斥访问。其中,S.free(0)是栈底,栈满时栈顶为S.free(99)。
- 文件区中的所有空闲盘块被分成若干个组,如每100个盘块作为一组。
- 将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块S.free(0)~S.free(99)中,这样,由各组的第一个盘块可链接成一条链。
- 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中,作为当前可供分配的空闲盘块号。
- 最末一组只有99个盘块,其盘块号分别记入其前一组的S.free(1)~S.free(99)中,而在S.free(0)中则存放0,作为空闲盘块链的结束。
当系统要为用户分配文件所需的盘块时,须调用盘块分配过程来完成:
首先检查空闲盘块号栈是否上锁,如未上锁,便从栈顶取出一空闲盘块号,将与之对应的盘块分配给用户,然后将栈顶指针下移一格。
若该盘块号已是栈底,即S.free(0),这是当前栈中最后一个可分配的盘块号。将栈底盘块号所对应盘块的内容读入栈中,作为新的盘块号栈的内 容,并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。
然后,再分配一相应的缓冲区(作为该盘块的缓冲区)。最后,把栈中的空闲盘块数减1并返回。
在系统回收空闲盘块时,须调用盘块回收过程进行回收:
它是将回收盘块的盘块号记入空闲盘块号栈的顶部,并执行空闲盘块数加1操作。
当栈中空闲盘块号数目已达100时,表示栈已满,便将现有栈中的100个盘块号,记入新回收的盘块中,再将其盘块号作为新栈底