AlgerFan | Blog

一、文件的物理结构

几个基本概念

类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同。
内存与磁盘之间的数据交换(即读/写操作、磁盘 I/O) 都是以“块”为单位进行的。即每次读入一块，或每次写出一块。

在内存管理中，进程的逻辑地址空间被分为一个一个页面。
同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件。“块”。于是文件的逻辑地址也可以表示为(逻辑块号，块内地址)的形式。

操作系统为文件分配存储空间都是以块为单位的用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑：地址到物理地址的映射。

1. 连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块。

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项(FCB)
物理块号 = 起始块号 + 逻辑块号
当然，还需要检查用户提供的逻辑块号是否合法(逻辑块号 ≥长度就不合法)
可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问(即随机访问)。

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。
结论：连续分配的文件在顺序读/写时速度最快

若此时文件 A 要拓展，需要再增加一一个磁盘块(总共需要连续的 4 个磁盘块)。由于采用连续结构，因此文件 A 占用的磁盘块必须是连续的。因此只能将文件 A 全部“迁移”到绿色区域。
结论：物理上采用连续分配的文件不方便拓展。

结论：物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片。
可以用紧凑来处理碎片，但是需要耗费很大的时间代价。

连续分配总结

优点：支持顺序访问和直接访问(即随机访问) ;连续分配的文件在顺序访问时速度最快；
缺点：不方便文件拓展;存储空间利用率低，会产生磁盘碎片。

2. 链接分配

链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

隐式链接分配

用户给出要访问的逻辑块号 i,操作系统找，到该文件对应的目录项(FCB)

从目录项中找到起始块号( 即 0 号块)，将 0 号逻辑块读入内存，由此知道 1 号逻辑块存放的物理块号，于是读入 1 号逻辑块，再找到 2 号逻辑块的存放位....以此类推。因此，读入 i 号逻辑块，总共需要 i+1 次磁盘 I/O 。

链式分配(隐式链接)总结

优点：很方便文件拓展，不会有碎片问题，外存利用率高。
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

显式链接方式

把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表(FAT, File Allocation Table )
假设某个新创建的文件“aa”依次存放在磁盘块 2>5>0>1
假设某个新创建的文件“bbb”依次存放在磁盘块 4>23>3

**注意：一个磁盘仅设置一 张 FAT。开机时，将 FAT 读入内存，并常驻内存。**FAT 的各个表项在物理。上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。

用户给出要访问的逻辑块号 i,操作系统找到该文件对应的目录项(FCB)

从目录项中找到起始块号，若 i>0， 则查询内存中的文件分配表 FAT,往后找到 i 号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。

链式分配(显式链接)总结

优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
缺点：文件分配表的需要占用一定的存储空间。

3. 索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表， 索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表--- 建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

索引分配方式可以支持随机访问。文件拓展也很容易实现(只需要给文件分配一个空闲块，并增加一一个索引表项即可)但是索引表需要占用一定的存储空间。

① 链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

② 多层索引：建立多层索引( 原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

③ 混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。

索引分配总结

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表一 建立逻辑页面到物理页之间的映射关系)。 索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
若文件太大，索引表项太多，可以采取以下三种方法解决：
① 链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到 i 号索引块，必须先依次读入 0~i-1 号索引块，这就导致磁盘 I/O 次数过多，查找效率低下。
② 多层索引：建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要 K+1 次读磁盘操作。缺点：即使是小文件，访问一个数据块依然需要 K+1 次读磁盘。
③ 混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块)，又包含一级间接索引( 指向单层索引表)、还包含两级间接索引(指向两层索引表)。优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

超级超级超级重要考点： ① 要会根据多层索引、混合索引的结构计算出文件的最大长度(Key: 各级索引表最大不能超过一一个块) ; ② 要能自己分析访问某个数据块所需要的读磁盘次数(Key: FCB 中 会存有指向顶级索引块的指针，因此可以根据 FCB 读入顶级索引块。每次读入下- -级的索引块都需要一次读磁盘操作。另外，要注意题目条件---顶级索引块是否已调入内存)

总结

二、文件存储空间的管理

存储空间的划分与初始化

存储空间管理一一空闲表法

适用于“连续分配方式”

存储空间管理一一空闲链表法

空闲链表法分为两种

• 空闲盘块链：以盘块为单位组成一条空闲链；
• 空闲盘区链：以盘区为单位组成一条空闲链。

空闲盘块链

操作系统保存着链头、链尾指针。
如何分配：若某文件申请 K 个盘块，则从链头开始依次摘下 K 个盘块分配，并修改空闲链的链头指针。
如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。
适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作。

空闲盘区链

操作系统保存着链头、链尾指针。
如何分配：若某文件申请 K 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到-一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给-一个文件， 注意分配后可能要修改相应的链指针、盘区大小等数据。
如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

存储空间管理一一位示图法

位示图：每个二进制位对应一一个盘块。在本例中，“0” 代表盘块空闲，“1”代表盘块已分配。
如何分配：若文件需要 K 个块，① 顺序扫描位示图，找到 K 个相邻或不相邻的“0”; ② 根据字号、位号算出对应的盘块号，将相应盘块分配给文件; ③ 将相应位设置为“1”
如何回收： ① 根据回收的盘块号计算出对应的字号、位号; ② 将相应二进制位设为“0’

存储空间管理一一成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX 系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保。证内存与外存中的“超级块”数据一致。

如何分配？
Eg:需要 1 个空闲块
① 检查第一个分组的块数是否足够。1<100，因此是足够的。
② 分配第一个分组中的 1 个空闲块，并修改相应数据

Eg:需要 100 个空闲块
① 检查第一个分组的块数是否足够。100=100， 是足够的。
② 分配第一个分组中的 100 个空闲块。但是由于 300 号块内存放了再下一组的信息，因此 300 号块的数据需要复制到超级块中。

如何回收？
Eg:假设每个分组最多为 100 个空闲块，此时第一一个分组己有 99 个块，还要再回收一块。

Eg:假设每个分组最多为 100 个空闲块，此时第一个分组已有 100 个块，还要再回收一块。需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。

总结