第八章 磁盘存储器的管理
一、外存的组织方式
1.1 连续组织方式
优点
- 顺序访问容易
- 顺序访问速度快
缺点
- 要为一个文件分配连续的存储空间，产生许多外部碎片，降低了外存空间利用率
- 必须事先知道文件长度
- 不能灵活增删记录
- 对于哪些动态增长的文件很难事先知道文件最终大小。及时事先知道，采用预分配存储空间的方法时，也会使大量存储空间长期空闲
1.2 链接组织方式
链接组织方式为文件分配多个不连续的盘块，在通过每个盘块上的连接指针将同属于一个文件的多个离散盘块连接成一个链表
- 消除了磁盘的外部碎片，提高外存利用率
- 增删改记录容易
- 能适应文件的动态增长
1. 隐式链接
文件目录的每个目录项中都含有指向链接文件第一盘块和最后一盘块的指针
只适合于顺序访问，对随机访问十分低效
可靠性差
2. 显式链接
将物理块指针显式存放在内存里的一张链接表中
分配给文件的所有盘块号都在该表中，又称为文件分配表 FAT
1.3 FAT 技术
略
1.4 NTFS 文件组织方式
以簇作文文件基本单位
1.5 索引组织方式
1. 单级索引组织方式
链接组织方式的问题
- 不能支持高效的直接存取
- FAT 占用较大的内存空间，对于各文件的所有盘块号，需调入整个 FAT 才能找到其所有盘块号
索引分配方法为每个文件分配一个索引表，吧分配给该文件的所有盘块号都记录在该索引快中，建立文件时只需在为之建立的目录项填上指向该索引块的指针
主要优点是支持直接访问
主要问题是每当建立一个索引文件，应为该文件分配一个索引块，记录所有分配该文件的盘块号，对中小型文件对索引块的利用率较低
2. 多级索引组织方式
在为大文件分配磁盘空间时，若所分配的盘块的盘块号已经装满一个索引，则需再分配一个索引块……文件太大索引块太多时低效
引入多级索引
如果每个盘块大小 1KB，每个盘块号 4B，则一个索引块可存放 256 个盘块号
这样，二级索引时，最多存放文件的盘块号总数为
若盘块大小 4KB，则两级索引下最大文件长度为
3. 增量式索引组织方式
基本思想
为了全面照顾小中大及特大型作业，采取多重组织方式构成文件的物理结构
UNIX System V 的组织方式
索引节点有 13 个地址项，即 i.addr(0)~i.addr(12)
直接地址：10 个直接地址项，即 i.addr(0)~i.addr(9) 存放直接盘块号，即 direct blocks，当文件不大于 40KB 时可以直接读出
一次间址：i.addr(10) 提供一次间址，在一次间址块中存放 1K 个盘块号，允许文件长达 4MB
多次间址：i.addr(11) 提供二次间址，允许文件长达
i.addr(12) 提供三次间址，允许文件长达
二、文件存储空间的管理
2.1 空闲表法与空闲列表法
1. 空闲表法
- 空闲表：空闲表发属于连续分配方式，为每个文件分配一个连续的存储空间
- 存储空间的分配与回收：同样采用首次适应和最佳适应算法等
2. 空闲链表法
空闲盘块连
将磁盘上所有空闲空间以盘块为单位拉成一条链
每次请求分配空间时从链首开始摘下适当数目盘块分配给数目，删除文件时回收的盘块一次挂载末尾
优点是分配和回收一个盘块简单，但效率低，空闲盘块链长
空闲盘区链
所有空闲盘区拉成一条链，每个盘区除了指向下一个盘区的指针还有本盘区大小（盘块数）的信息
优缺点与上一种相反
2.2 位示图法
1. 位示图
用二进制的一位表示一个盘块的使用情况
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| ... |
2. 盘块的分配
顺序扫描位示图，找出一个或一组值为
的二进制位 找到的一个或一组二进制位转换成相对应的盘块号
其中 表示每行位数 修改位示图，令
3. 盘块的回收
转盘块号为行列号
修改位示图，令
优点是很容易找到一个或一组相邻的空闲盘块
位数图很小，占用空间少，可以保存在内存中，节省了许多磁盘的启动操作