对磁盘存储器管理的主要任务和要求：
- 有效地利用存储空间
- 提高磁盘的I/O速度
- 提高磁盘系统的可靠性
8.1 外存的组织方式
常用的外存组织方式：
- 连续组织方式
- 链接组织方式（不连续）
- 索引组织方式
在传统的文件系统中，通常一个系统中仅采用一种方式。
1 连续组织方式
为每一个文件分配一组相邻的盘块。
逻辑文件中的记录顺序与存储器中文件占用盘块的顺序一致。
优点：
- 顺序访问容易
- 读写速度快
缺点：
- 要求有连续的存储空间。
- 必须事先知道文件的长度。
- 不能灵活地删除和插入记录。
- 不便于动态增长的文件。
- 会产生外存碎片。可紧凑法弥补，但需要额外的空间，和内存紧凑相比更花时间。
- 存储空间利用率不高。
适用于变化不大顺序访问的文件，在流行的UNIX系统中仍保留了连续文件结构。如对换区。
2 链接组织方式
可以为每一个文件分配一组不相邻的盘块。
设置链接指针，将同属于一个文件的多个离散盘块链接成一个链表，这样形成的文件称为链接文件。会有链接成本。
链接分配的主要优点如下：
- 离散分配，消除外部碎片，提高利用率；
- 同时适用于文件的动态增长；对文件的增、删、改容易。
链接分配的主要缺点如下：
- 不能支持高效的直接存取;
- FAT占用较大的内存空间。
链接两种形式：隐式链接、显式链接。
隐式链接
文件空间信息的目录项中没有链接数据；链接信息隐含记录在盘块数据中；每个盘块拿出若干字节，记录指向下一盘块号的指针。
问题：只能顺着盘块读取，可靠性低。
显式链接
属于一个文件的盘块通过链接成为一体，每个链条的首地址作为文件地址记录在相应文件的FCB的“物理地址”字段中。
记录盘块链接的指针显式地记录为一张链接表。所有已分配的盘块号都记录在其中，称文件分配表（FAT）。
为了提高文件系统访问速度，FAT一般常驻内存。
3 FAT技术
在微软公司的早期MS-DOS中，所使用的是12 位的FAT12 文件系统，后来为16 位的FAT16文件系统；在Windows 95和Windows 98操作系统中则升级为32位的FAT32；WindowsNT、Windows 2000 和Windows XP 操作系统又进一步发展为新技术文件系统NTFS(New Technology File System)。上述的几种文件系统所采用的文件分配方式基本上都是类似于前一节所介绍的显式链接方法。
FAT12
每个FAT表项为12位。
所以FAT表中最多允许4K表项，盘块（扇区）512B，每一个磁盘分区的容量为：4K*512B=2MB。
一个物理磁盘能支持4个逻辑磁盘分区，所以磁盘最大容量为8MB。
为了增加容量，引入族的概念：一个族可以是512B、1KB 、2KB、4KB等。问题：族内碎片增加。
对于1.2 MB的软盘，每个盘块的大小为512 B，在每个FAT中共含有2.4 K 个表项，由于每个FAT 表项占12 位，故FAT 表占用3.6 KB的存储空间。
1.2MB/512B=2.4k
2.4K*1.5=3.6KB
FAT表的相关计算：
MS-DOS文件分配结构为例：一个1.2M的磁盘，盘块512B大小；若文件系统采用FAT格式，则FAT表大小如何？
表项个数 = 盘块个数 = 容量 / 盘块大小 = 1.2*2^20 / 2^9 = 1.2*2^11 个
表项大小，决定于盘块数量编号需要的位数=12 位；
FAT表大小 = 表项个数 * 表项大小 = 1.2*2^11 * 12 bit = 1.2*2^11 * 1.5B = 3.6KB
由上述公式，若容量为200M的磁盘，盘块仍为512B，FAT表大小如何？
FAT表表项有200K≈2^18 （个）
表项需20位，即2*8+4，2.5字节
FAT表需内存大小为2002.5=500KB
FAT16
每个FAT表项占16位。
FAT表的宽度增加到16位，长度增加到2^16。
如果族为4KB，分区容量为： 2^16 * 4KB。
FAT32
每个FAT表项占32位。
FAT表的宽度增加到32位，长度增加到2^32
如果族为4KB，分区容量为： 2^32 * 4KB。
缺点：
- 文件分配表大，运行速度慢；
- 不支持容量小于512MB的分区（仍然需使用FAT16）；
- 单个文件不能大于4GB；
- 不保持向下兼容。
4 NTFS的文件组织方式
NTFS(New Technology File System)是一个专门为Windows NT开发的、全新的文件系统，并适用于Windows 2000/XP及后续的Windows OS。
NTFS新特征
- 64位地址
- 可以很好地支持长文件名
- 具有系统容错功能
- 能保证系统中的数据一致性
磁盘组织
分区称为卷。
NTFS是以簇作为磁盘空间分配和回收的基本单位的，又称为卷因子。一个文件占用若干个簇，一个簇只属于一个文件。这样，在为文件分配磁盘空间时，就无须知道盘块的大小，只要根据不同的磁盘容量，选择相应大小的簇，即使NTFS具有了与磁盘物理块大小无关的独立性。
卷因子：卷上簇的大小。
文件的组织
在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(Master File Table)中，该表是NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1 KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。
5 索引组织方式 ★
链接的不足：
- 顺序检索的时间成本：不能支持高效的盘块直接存取。要对一个文件进行直接存取，仍需在FAT中顺序的查找许多盘块号。
- 链接信息的空间成本：FAT需占用较大的内存空间。当磁盘容量较大时，FAT可能要占用数MB以上的内存空间。这是令人难以忍受的。
改进：系统运行时只涉及部分文件，FAT表无需全部调入内存。
- 每个文件单独建索引表（物理盘块索引），记录所有分配给它的盘块号；
- 建立文件时，便分配一定的外存空间用于存放文件盘块索引表信息。
单级索引分配
索引形式适合大文件。
中、小型文件，只需若干链接即可。若用索引分配方式，用一个盘块存放少量索引信息反而不适用。
多级索引分配
若文件较大，存放索引表也需要多个盘块（索引盘块）。
索引盘块亦需要按顺序管理起来：若索引盘块数量较少用指针链接的方式即可；若索引盘块较多，需对索引盘块也采用索引方式管理，形成多级索引。
多级索引下的文件大小：
若两级索引，盘块1KB，盘块号占4字节
一个盘块可存放的盘块号数有多少个
1KB/4B = 210/4 = 28 = 256（个）
二级索引下的文件可分配的最大盘块数
256 * 256 =26×210=64 K（个）
文件最大长度为64K（个）*1KB=64MB
若盘块大小为4KB，单级索引允许文件最大长度为4MB（4K/4*4KB），二级索引则文件最大可达4GB（1K*1K*4KB）。
混合组织索引（增量式索引组织方式）★
多种索引方式相结合。
以UNIX system V的索引结点为例：一个索引结点定义为13个地址项：iaddr（0）~iaddr（12），总的来说分为两种：直接地址、间接地址。
- iaddr（0）~iaddr（9）存放直接地址，即存文件数据的盘块号；
- iaddr（10）存放单级索引的索引盘块号；
- 剩余的用于文件较大时存放多级索引数据。 iaddr（11）存放二级索引的主索引盘块号 iaddr（12）存放三级索引的主索引盘块号
8.2 存储空间的管理
典型的文件存储空间管理方法：
1）空闲表和空闲链表法 2）位示图法 3）成组链接法
1 空闲表和空闲链表法
空闲表法
空闲盘块表：
| 序号 | 第一空闲盘块号 | 空闲盘块数 |
|---|---|---|
| 1 | 2 | 4 |
| 2 | 9 | 3 |
| 3 | 15 | 5 |
| 4 | — | — |
常用于连续分配管理方式。
数据结构
- 系统为外存上的所有空闲区建立一张空闲表
- 每个空闲区对应一个空闲表项（表项包括序号、空闲区的第一个盘块号、空闲盘块数等）
- 将所有空闲区按其起始盘块号递增的次序排列
存储空间的分配与回收操作
- 与内存的动态分配类似，同样可采用首次适应算法、循环首次适应算法等。
- 回收主要解决对数据结构的数据修改。
- 应该说明，虽然很少采用连续分配方式，然而在外存的管理中，由于它具有较高的分配速度，可减少访问磁盘的I/O频率，故它在诸多分配方式中仍占有一席之地。（如实现虚拟用的部分外存就是连续分配方式）
空闲链表法
将所有空闲盘区拉成一条空闲链。
数据结构：链。
根据构成链所用基本元素的不同，可把链表分成两种形式：
空闲盘块链
- 将磁盘上的所有空闲空间，以盘块为单位拉成一条链。
- 因创建文件而请求分配空间时，系统从链首依次摘下适当数目的空闲盘块分配给用户。
- 因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。
- 优点：分配和回收一个盘块的过程非常简单，但为一个文件分配盘块时，可能要重复操作多次。
空闲盘区链
- 将所有空闲盘区拉成一条链。每个盘区上含有： 指示下一空闲盘区的指针、本盘区大小等信息
- 分配通常采用首次适应算法。回收盘区时，将回收区与相邻的空闲盘区相合并。 为提高检索速度，可以采用显式方法，为空闲盘区建立一张链表放在内存中。
- 分配、回收操作涉及的链式数据结构的处理方便
对比
- 空闲盘块链：分配回收简单。链表长，大量分配时需要操作的指针多。
- 空闲盘区链：链表长度不定，分配时操作的指针数量相对较少，但分配回收操作相对复杂。
2 位示图法 ★
位示图
利用二进制的一位来表示一个盘块的使用情况。
值为0表示对应的盘块空闲，为1表示已分配。有的系统则相反。
磁盘上的所有盘块都有一个二进制位与之对应，这样由所有盘块所对应的位构成一个集合，称为位示图。
总块数=m*n。可用m*n个位数来构成位示图，可看成是二维数组（数据结构）。
盘块的分配
- 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。
- 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算： b = n (i - 1) + j 式中， n代表每行的位数。
- 修改位示图， 令map［i,j］=1。
公式中的b、i、j都是从1开始的。
盘块的回收
- 将回收盘块的盘块号转换成位示图中的行号和列号。 转换公式为： i = (b-1) DIV n + 1 j = (b-1) MOD n + 1
- 修改位示图。 令map[i,j]=0。
例：如果利用20行，30列的位示图来标志空闲盘块的状态，在进行盘盘块分配时，当第一次找到的空闲盘块（即该位置为0）处于第11行，第18列，则相应的盘块号为_____。
b=n(i-1)+j=30(11-1)+18=318
优缺点
优点：从位示图中很容易找到一个或一组相邻接的空闲盘块。
缺点：但限于容量问题，常用于微型机和小型机中。
3 成组链接法
大型文件系统，空闲表或空闲链表太长不方便管理操作。
UNIX系统中采用成组链接法，这是将两种方法结合而形成的一种空闲盘块管理方法。
中心思想：
- 所有盘块按规定大小划分为组；
- 组间建立链接；
- 组内的盘块借助一个系统栈可快速处理，且支持离散分配回收。
空闲盘块的组织
空闲盘块号栈：用来存放当前可用的一组空闲盘块的盘块号（最多含100个号）。
栈中尚有的空闲盘块号数N。（N兼具栈顶指针用。栈底为S.free(0)，栈满时栈顶到达S.free(99)，N=100，表示有100个盘块供使用）
链接：每一组的第一个盘块记录下一组的盘块号，形成了一条链。
总将链的第一组盘块总数和所有的盘块号，记入栈，作为当前可供分配的空闲盘块号。
空闲盘块的分配与回收
① 分配盘块时，须调用分配过程来完成。
- 先检查空闲盘块号栈是否上锁，如没有，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。
- 若该盘块号已是栈底，即S.free(0)，到达当前栈中最后一个可供分配的盘块号。
- 读取该盘块号所对应的盘块中的信息：即下一组可用的盘块号入栈。
- 原栈底盘块分配出去。修改栈中的空闲盘块数。
② 回收
- 回收盘块号记入栈顶，空闲数N加1。
- N达到100时，若再回收一块，则将该100条信息填写入新回收块。