第八章 磁盘存储管理

(1) 不能支持高效的直接存取。要对一个较大 的文件进行直接存取，须首先在FAT中顺序地 查找许多盘块号。
链接分配方式存在的问题
(2) FAT需占用较大的内存空间。

由于一个文件所占用盘块的盘块号是随机 地分布在FAT中的，因而只有将整个FAT 调入内存，才能保证在FAT 中找到一个文 件的所有盘块号。


优点：
采取离散分配方式，消除了外部碎片提高了外存空 间的利用率 无须事先知道文件的大小 便于对文件的增、删、改

★ 链接方式又可分为隐式链接和显式链接两种形式。
8.1.2 链接组织方式（链接分配）
1．隐式链接 （见图8-2，P252）
每个盘块中都含 有一个指向下一 个盘块的指针.
8 -2
1．隐式链接
连续分配存在的问题

解决方法之一，系统定期或不定期采用 紧凑技术，将小分区合并为大的、连续 分区，将文件占用空间合并在一起。
0
FILE1
1
2
3
4
5
文件分配表
文件名 起始块号 文件长度 FILE1 FILE2
6
7
8
FILE2
9
10
11
0
4 13 17
4
9
12
13
FILE3
14
15
16
17
18
19
FILE4
图 8–10 位示图

位示图也可描述为一个二维数组map： Var map: array of bit；
8.2.2 位示图法
2．盘块的分配
（1）顺序扫描位示图，从中找出一个或一组其值 为“0”的二进制位
（2）将所找到的一个或一组二进制位；转换成与 之相应的盘块号（ b=（i-1）*n + j ）
（3）修改位示图，令map[ i,j ] = 1
8.3.1 磁盘高速缓存
指在内存中为磁盘盘块设置的一个缓冲区 ，在其中保存了某些盘块的副本。 当出现访问磁盘的请求时，先查看磁盘高 速缓冲区

设计磁盘高速缓存考虑的问题： （1）如何将磁盘高速缓存中的数据传送给 请求进程； （2）采用什么样的置换策略； （3）已修改的磁盘数据在何时被写回磁盘


(4) 将第一组的盘块总数和所有的盘块号记入空闲 盘块号栈中，作为当前可供分配的空闲盘块号。 (5) 最末一组只有99 个盘块，其盘块号分别记入 其前一组的S.free(1) ～S.free(99)中，而在 S.free(0)中则存放“0”，作为空闲盘块链的结束 标志。(注：最后一组的盘块数应为99，不应是 100，因为这是指可供使用的空闲盘块，其编号 应为(1～99)，0号中放空闲盘块链的结尾标志。)
8.1.5 索引组织方式(索引分配)

索引分配方法：
就是为每个文件分 配一个索引块
（表），再把分配
给该文件的所有盘 块号，都记录在该 索引块中，因而该 索引块就是一个含 有许多盘块号数组。
图8-6
单级索引分配

索引分配方式支持直接访问。当要读文件的第i 个盘块时 ，可以方便地直接从索引块中找到第i个盘块的盘块号；

隐式链接分配方式的主要问题在于：它只适合 于顺序访问，它对随机访问是极其低效的。
为了提高检索速度和减小指针所占用的存储空 间，可以将几个盘块组成一个簇，以簇为单位， 将会减小查找指定块的时间，而且也可减小指 针所占用的存储空间。

2．显式链接

这是指把用于链接文 件各物理块的指针， 显式地存放在内存的 一张链接表中，该表 在整个磁盘仅设置一 张
8.2.2 位示图法
1．位示图

位示图是利用二进制的一位来表示磁盘中一个盘 块的使用情况。当其值为“0”时，表示对应的盘 块空闲；为“1”时，表示已分配。 磁盘上的所有盘块都有一个二进制位与之对应， 这样，由所有盘块所对应的位构成一个集合，称 为位示图。

8.2.2 位示图法
1．位示图

通常可用m × n 个位数来构成位示图，并使m × n等于磁盘的总块数
1.数据交付方式

（1）数据交付：直接将高速缓存中的数据传达到 请求者进程的内存工作区中；

（2）指针交付：只将指向高速缓存中某区域的指
针交付给请求者进程，传送的数据量少。
2.置换算法
除了考虑最近最久未使用外，还需要考虑：

（1）访问频率 （2）可预见性 （3）数据的一致性
8.2.2 位示图法
3．盘块的回收
（1）将回收盘块的盘块号转换成位示图中的行号 和列号:
i = (b - 1)DIV n + 1 j = (b - 1)MOD n + 1
（2）修改位示图。
令map[i,j] =0
8.2.2 位示图法
位示图的主要优点: (1)是从位示图中很容易找到一个或一组相邻 接的空闲盘块 (2)由于位示图很小，占用空间少，因而可将 它保存在内存中, 从而节省了许多磁盘的启 动操作。
20
FILE3
21 22 23
4
5
FILE4
24
25
26
27
28
29
…
…
…
30
31
32
33
34
35
图 磁盘 连续分配（紧凑以后）
8.1.2 链接组织方式（链接分配）

采用链接分配方式时，可通过在每个盘块上的链接 指针，将同属于一个文件的多个离散的盘块链接成 一个链表，把这样形成的物理文件称为链接文件。


2. 空闲链表法
空闲链表法 ：是将所有空闲盘区拉成一条空闲链。 把链表分成两种形式：空闲盘块链和空闲盘区链。
（1）空闲盘块链：将磁盘上的所有空闲空间，以盘 块为单位拉成一条链，当用户因创建文件而请求 分配存储空间时，系统从链首开始，依次摘下适 当数目的空闲盘块分配给用户。当用户因删除文 件而释放存储空间时，系统将回收的盘块依次插 入空闲盘块链的末尾。 （2）空闲盘区链：将磁盘上的所有空闲盘区（每个 盘区可包含若干个盘块）拉成一条链 。
2．空闲盘块的分配与回收

由于在该盘块号所对应的盘块中记有下一组可用 的盘块号，因此，须调用磁盘读过程，将栈底盘
块号所对应盘块的内容读入栈中，作为新的盘块
号栈的内容，并把原栈底对应的盘块分配出去(其
中பைடு நூலகம்有用数据已读入栈中)。然后，再分配一相应
的缓冲区(作为该盘块的缓冲区)。最后，把栈中
的空闲盘块数减1 并返回。
1. 空闲表法 ：属于连续分配方式，它为每个文 件分配一块连续的存储空间。

系统为外存上的所有空闲区建立一张空闲表， 每个空闲区对应于一个空闲表项 。
图8-9
1. 空闲表法

存储空间的分配与回收可采用首次适应算法、循 环首次适应算法等。
回收区是否与空闲表中插入点的前区和后区相邻 接，对相邻接者应予以合并。 采用连续分配方式具有较高的分配速度，可减少 访问磁盘的I/O频率，
计算机操作系统
第八章 磁盘存储管理
上章回顾
理解：文件系统的基本概念、目录管理、 文件共享、文件保护的方法。 掌握：文件逻辑结构、文件目录

本章内容
8.1 外存的组织方式 8.2 文件存储空间的管理 8.3 提高磁盘I/O速度的途径

8.1 外存的组织方式
目前常用的外存组织方法有：连续组织方式、 链接组织方式和索引组织方式三种。
2．空闲盘块的分配与回收
在系统回收空闲盘块时，须调用盘块回收 过程进行回收。 它是将回收盘块的盘块号记入空闲盘块号 栈的顶部，并执行空闲盘块数加1 操作。 当栈中空闲盘块号数目已达100 时，表示栈 已满，便将现有栈中的100个盘块号记入新 回收的盘块中，再将其盘块号作为新栈底 。

本章内容
2．显式链接

在该表中，凡是属于某一文件的第一个盘块号， 均作为文件地址被填入相应文件的FCB 的“物 理地址”字段中。 由于查找记录的过程是在内存中进行的，因而不 仅显著地提高了检索速度，而且大大减少了访问 磁盘的次数。 由于分配给文件的所有盘块号都放在该表中，故 把该表称为文件分配表FAT (File Allocation Table)。
8.1.1 连续组织方式
1．连续组织方式 ：又称为连续分配方式。要求为每 一个文件分配一组相邻接的盘块；

在采用连续分配方式时，可把逻辑文件中的记录 顺序地存储到邻接的各物理盘块中，这样所形成 的文件结构称为顺序文件结构，此时的物理文件 称为顺序文件。
8-1
2．连续分配的主要优点:

连续分配的主要优点
8.1 外存的组织方式 8.2 文件存储空间的管理 8.3 提高磁盘I/O速度的途径

8.3 提高磁盘I/O速度的途径
三方面着手 （1）改进文件的目录结构以及检索目录的 方法减少对目录的查找时间； （2）选取好的文件存储结构，提高对文件 的访问速度； （3）提高磁盘的I/O速度，能将文件中的数 据快速地从磁盘传到内存或相反。
2．空闲盘块的分配与回收

当系统要为用户分配文件所需的盘块时，须调用 盘块分配过程来完成。该过程首先检查空闲盘块 号栈是否上锁，如未上锁，便从栈顶取出一空闲 盘块号，将与之对应的盘块分配给用户，然后将 栈顶指针下移一格。若该盘块号已是栈底，即 S.free(0)，这是当前栈中最后一个可分配的盘块 号。

方式。
2．多级索引分配
图8-7
3．混合索引分配方式

所谓混合索引分配方 式，是指将多种索引 分配方式相结合而形 成的一种分配方式。 在索引结点中可设置 10个直接地址项。
（1）直接地址。
（2）一次间接地址。 （3）多次间接地址。