第八章 磁盘管理
7.2 外存的分配
文件的物理结构（存储结构）
一、连续分配（顺序文件）
为每一个文件分配一组相邻接的盘块。
优点：顺序访问容易，顺序访问速度快。
缺点：要求为一个文件分配连续的存储空间；必须事先知道文件的长度；不便于增删改。
二、链接分配（链接文件）
优点：消除了磁盘的外部碎片，提高了外存的利用率；增删改方便；无需事先知道文件大小。
缺点：不便于查
链接方式分为隐式链接和显式链接。
- 隐式链接
破坏了块的完整性。
- 显式链接
把用于链接文件各物理块的指针显式的存放在内存的一张链接表中。
三、索引分配（索引文件）
- 单级索引
N*(A/b)*A
- 多级索引
N*(A/b)^n*A
- 多级混合索引（UNIX）
在UNIX System V的索引结点设有13个地址项。
（10+(A/b)+(A/b)^2+(A/b)^3）*A
7.3 空闲空间管理
一、空闲区表法
|
序号 |
第一空闲盘块号 |
空闲盘块数 |
|
1 |
2 |
4 |
|
2 |
9 |
3 |
|
3 |
15 |
5 |
|
4 |
—— |
—— |
二、空闲链表法
三、位示图法
- 盘块的分配
根据位示图进行盘块分配时，可分三步进行：
（1）顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。
（2）将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0” 的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按下式计算： b = n(i - l)+j
式中，n代表每行的位数。
（3）修改位示图，令map [i，j]=1
- 盘块的回收
盘块的回收分两步：
（1）将回收盘块的盘块号转换成位示图中的行号和列号。
转换公式为： i = (b - 1)DIV n+ 1 ；j = (b- l)MOD n + 1
（2）修改位示图。令map[i，j] = 0。
四、成组链接法
空闲盘块号栈存放当前可用的一组空闲盘块的盘块号和块数