操作系统中的可用空间管理指南 _内存管理

系统会跟踪空闲磁盘块, 以便在创建文件时为文件分配空间。同样, 要重新使用删除文件后释放的空间, 可用空间管理也至关重要。系统维护一个可用空间列表, 该列表跟踪未分配给某些文件或目录的磁盘块。可用空间列表主要可以实现为：
位图或位向量–
位图或位向量是位的序列或集合，每个位对应一个磁盘块。bit有两种取值:0和1:0表示已分配块，1表示空闲块。
图1中磁盘上给定的磁盘块实例(其中分配了绿色的块)可以用16位的位图表示:0000111000000110。

文章图片
优点 -

简单易懂。
找到第一个空闲块是有效??的。它需要扫描位图中的单词(一组8位)以查找非零单词。 (一个值为0的字的所有位均为0)。然后, 通过扫描非零字中的第一个1位来找到第一个空闲块。

块号可以计算为：
(每个字的位数)*(0值字的个数)+非零字的第1位的偏移量。
对于图-1，我们按顺序扫描位图，寻找第一个非零单词。
第一组8位(00001110)构成一个非零字, 因为所有位都不为0。找到非0字后, 我们寻找第一个1位。这是非零字的第5位。因此, 偏移量= 5。
因此, 第一个空闲块号= 8 * 0 + 5 = 5。
链表–
在这种方法中, 空闲磁盘块被链接在一起, 即, 空闲块包含指向下一个空闲块的指针。第一个磁盘块的块号存储在磁盘上的单独位置, 也缓存在内存中。

文章图片
在图2中, 可用空间列表头指向块5, 块5指向块6, 下一个空闲块, 依此类推。最后一个空闲块将包含一个空指针, 指示空闲列表的结尾。
此方法的缺点是遍历可用空间列表所需的I / O。
分组–
这种方法将空闲块的地址存储在第一个空闲块中。第一个空闲块存储一些(例如n个)空闲块的地址。在这n个块中, 前n-1个块实际上是空闲的, 最后一个块包含下一个空闲n块的地址。
这种方法的一个优点是可以很容易地找到一组空闲磁盘块的地址。
计数 -
这种方法存储了第一个空闲磁盘块的地址和第一个空闲磁盘块之后的n个空闲连续磁盘块。
列表中的每个条目都将包含：