文件存储与基本操作

文件的物理结构

文件块，磁盘块

外存中的文件存储方式我们前面提到过实际上和内存中的分页存储类似，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”，甚至在许多操作系统中，磁盘块的大小和内存块，页面的大小是相同的。

所以I/O操作的时间开销较大，一般要避免I/O操作（例如内存中页面调度优先淘汰干净页面以避免写回）或者降低I/O的操作次数例如上面讲到的PCB索引节点机制。因为在外存中也是分成一个个外存块，所以文件的逻辑地址也是逻辑块号+块内地址拼接的形式。用户给出的是逻辑地址而操作系统转换为物理地址进行映射。

连续分配

连续分配要求每个文件在磁盘上占有一组连续的块。如下图：

并且对应的文件目录中也需要记录起始块号，占据的块的长度：

并且由于逻辑地址->物理地址的方法相似，所以当用户给出逻辑块号后，只需要操作系统根据目录项FCB找到对应的物理块号=起始块号+逻辑块号即可，然后在检验合法后在拼接上块内地址即可完成，因此连续分配支持顺序访问和直接访问（随机访问）。

思考：连续分配存储的好处？

当读取一个磁盘块时，需要移动磁头。那么访问的磁盘块距离越远，移动磁头所需要的的时间也就越长。所以连续分配时块号相邻，那么文件再顺序读/写时速度最快。

思考：连续分配的缺点是什么？

我们考虑一种情况，比如下图：

A此时是占用了连续的3个黄色的磁盘块，但是现在A要进行拓展，需要在增加一个磁盘块并且由于要连续存储，因此此时A放不下了，又因为后面的连续块都已经被橙色所占用，所以A只能全部迁移到绿色区域。这无疑会造成很大的开销。所以物理上采用连续分配的文件不方便拓展。

并且还会造成如上图的情况，这是连续分配存储的共性问题，大量的外部碎片会降低空间的利用率，当然那我们同样可以使用紧凑技术来处理碎片，但是很明显会有大量的开销。

链接分配

隐式链接

为了解决上面的外部碎片问题，我们采用链接分配磁盘块，这里先给出隐式链接的方法，还是如上图，我们此时把文件离散存储并记录起始块号和结束块号（中间块号不记录），每一个中间块都有一个尾指针指向下一个存储文件信息的磁盘块并且对用户开放，这样就不要紧凑技术仍然可以充分利用外部碎片了。如下图：

并且貌似文件拓展也就不是什么难事了所以不会有外部碎片，但是此时却产生了另一个缺点。

思考：这种链接方法的缺陷？

我们发现此时实际上并不是连续存储了，那么就产生了非连续存储的一个常见问题，就是假设现在用户要访问逻辑块号i，那么操作系统找到对应的FCB然后从起始块开始一个一个查找直至找到所需块号，这样假设要读入逻辑块号i，那么需要i+1次磁盘I/O。这种采用隐式链接的方法，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要移动很长距离的磁头，时间开销较大。

显式链接

为了解决上面所遇到的问题，可以把用于链接文件各物理块的指针显式的存放在一个表中，即文件分配表（FAT,File Allocation Table)。同样目录中只需要记录起始块号即可，会另有FAT用来存储这些指针如下：

此时我们为每一个磁盘设置一张FAT，开机时，将FAT放入内存并常驻内存。因为此时按物理块号递增排列，所以物理块号可以隐含不需要占用额外的空间。

此时我们在观察目录表和FAT可以轻松得知文件aaa的磁盘块有2->5->0->1，bbb的文件一次存放在4->23->3中。此时如果我们得到了逻辑块号i，那么找到其实块号，如果i>0,则查询内存中的文件分配表FAT，往后查找第i个物理块号即可。所以此时逻辑块号转换成物理块号不需要再进行读磁盘操作。

所以采用显式链接方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~i-1号逻辑块），由于块号的转换也不需要访问磁盘，所以相比于隐式链接来说，显式链接访问速度更快。并且显式链接也不会产生外部碎片，可以很方便的进行文件的拓展。

索引分配

这就是分页存储思想在外存中的应用，索引分配允许文件离散的分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表–建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

假设某个新创建的文件aaa的数据依次存放在磁盘块2->5->13->9,7号磁盘块作为aaa的索引块，即7号块存放aaa的索引表存放aaa文件的逻辑块号与物理块号的映射关系。所以我们注意到与FAT不同，索引分配中，索引表是一个文件对应一张。

同样我们也涉及到索引表项的字节大小的问题，我们假设磁盘总容量为1TB=2^40B，磁盘块大小为1KB，那么总共有2^30个磁盘块，所以索引表项即可以用4B来表示磁盘块号（同样我们也争取凑成2的整数次幂），因此索引表的逻辑块号也是可以隐含的。

所以，索引分配中逻辑块->物理块的转换就是通过查表得知，并且索引分配也是可以支持随机访问的，稳健拓展同样容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）但是索引表需要占用一定的空间。

思考：一个磁盘块装不下文件的整张索引表时，此时如何解决？

假设如果每个磁盘块1KB，一个索引表项4B，那么一个磁盘块只能存放256个索引项，但是如果一个文件的大小超过了256块，那么很明显此时一个磁盘块装不下文件的整张索引表，该怎么办。我们有以下几种解决策略：

链接方案

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

看似问题有效解决了，但是考虑一种情况：假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。如果一个文件大小为256*256KB=64MB，那么这个文件一共需要256*256块,也就是256个索引块来存储，那么如果真的是按照链接形式存放，如果想要访问最后一个索引块就需要先将前面的255个全部访问一遍，这样顺序查找时间开销太大。

多层索引

建立多层索引（类似于多级页表），是第一层索引块指向第二层索引块，还可根据需要再建立第三层，第四层索引块。

如果采用这种二层索引，那么该文件的最大程度可以到达64MB，并且还可以根据逻辑块号算出应该查找索引表中的哪个表项。例如现在要查找1026号逻辑块：

1026/256=4,1026%256=2。所以先将第一层索引表调入内存，查询4号表项，然后在对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号了。这样访问数据块，需要3从I/O操作，那块采用K级索引结构，且顶级索引表未调入内存（一定要注意，一般顶级索引表常驻内存），那么访问一个数据块只需要K+1次读磁盘操作。同理如果是三层索引，那么文件最大长度就是256*256*256KB=16GB,并且查找到一个物理块需要4次磁盘读操作。

混合索引

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

这样需要经常被访问的就放在直接地址索引，对于不经常使用的放在多级地址索引，高效同时长度拓展的也很大。非常合理，同时我们也可以进行文件的大小估计。例如上图中的最大文件长度就是65800KB，其实计算和多级索引类似。

三种索引分配的总结

索引策略	策略规则	缺点
链接方案	一个索引块装不下可以多个索引块链接存放	I/O次数过多，查找效率极低
多层索引	建立多级索引表，类似于多级页表	即便是小文件也需要K+1次读磁盘
混合索引	多种索引方式的结合，既有直接地址索引也有多级间接索引	对于小文件访问次数少，查找高效

❗超级重点：一定要回根据多层索引和混合索引的结构（各级索引表必须放在一个磁盘块中）计算文件的最大长度，公式是：

个数*索引块的大小

要回分析所需要的读磁盘次数，并且一定要注意题目条件–顶级索引块是否已经掉入内存。

总结

分配方式	怎样实现	目录项内容	优点	缺点
顺序分配	为文件分配的块必须是连续的磁盘块	起始块号、文件长度	顺序存取速度快，支持随机访问	会产生碎片，不利于文件拓展
链接分配（隐式链接）	除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针	起始块号，结束块号	可解决碎片问题，外存利用率高，文件拓展实现方便	只能顺序访问，不能随机访问
链接分配（显式链接）	建立一张文件分配表FAT显式记录盘块的先后关系（开机后FAT常驻内存）	起始块号	除了拥有隐式链接的优点之外，还可以通过查询内存中的FAT实现随机访问	FAT需要占用一定的存储空间
索引分配	为文件数据块建立索引表，索引表存储在索引块中，如果文件太大，可采用链接方案，多层索引或者混合索引策略	链接方案记录第一个索引块的块号，多层/混合索引记录的是顶级索引块的块号	支持随机访问，易于实现文件的拓展	索引表需占用一定的存储空间，访问数据块前需要先读入索引块。如果采用的是链接方案，查找索引块时可能需要很多次读磁盘操作

混淆点：什么是支持随机访问？

假设现在这个文件的逻辑结构是“顺序文件”，并且是定长记录，每个记录的长度是16B，那么i号记录的逻辑地址是多少？（从0开始编号）

每块大小为1KB，定长记录时16B，所以一各磁盘块可以存放64个记录，则：

“文件的某种逻辑结构支持随机存取/随机访问”是指：采用这种逻辑结构的文件，可以根据记录号直接算出该记录对应的逻辑地址（逻辑块号，块内地址）。

文件存储空间管理

存储空间的划分与初始化

安装windows操作系统的时候必须经历的步骤–为磁盘分区（C盘，D盘等）。

存储空间管理–空闲表法

空闲表法主要适用于连续分配方式，这里是用一张空闲盘块表进行对空闲物理块的记录，如下：

如何分配磁盘块：其实和内存管理的动态分区分配很相似，为一个文件分配连续的存储空间，同样可以采用首次适应，最佳适应，最坏适应等算法来决定为文件配到那个区。

所以毋庸置疑回收磁盘块时肯定是情况也类似有以下几种情况：

回收区的前后都没有相邻空闲区
回收区的前后都是空闲区
回收区前面是空闲区
回收区后面是空闲区

所以我们也需要注意合并的问题。

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

空闲盘块链

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

空闲盘区链

操作系统保存着链头，链尾指针。

分配时若某文件申请K个盘块，则可以采用首次适应，最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。

回收时若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

这种方法离散分配和连续分配都适用，为一个文件分配多个盘块时效率更高。

存储空间管理–位示图法

其实就类似于矩阵存储，但是又不是完全一样，如下图：

这是磁盘的情况，那么我们可以列出一种特殊的矩阵形式，如下：

他是由字号和位号来表示的，因为这个矩阵时16列，所以一个字号就是代表几个16，而位号就是几个1，优点类似于满16进1的表示意味。

位示图：每个二进制位对应一个盘块，在本例中，“0”代表空闲，“1”代表盘块已分配。位示图一般用连续的“字”来表示，如本例题中一个字的字长是16，字中的每一位对应一个盘块。因此可以用（字号，位号）对应一个盘块号。当然有的题目中也描述为（行号，列号）。但是总之就是要自己会推算出每个盘块的空闲状态。这里主要要注意开头的号码是0还是1千万要注意一个字是多少位。

(字号,位号)=(i,j)的二进制位对应的盘块号b=n*i+j

所以如下图我们可以推出：

同理我们也可以一直盘块号反推出字号和位号

b号盘对应的字号i=b/n

b号盘块对应的位号j=b\%n

所以我们可以反推出：

所以分配时：若分配需要K个块，

①顺序扫描位示图，找到K个相邻或不相邻的“0”

②根据字号、位号算出对应的盘块号，将相应盘块分配给文件

③将相应位设置为“1”

回收时：

①根据回收的盘块号计算出对应的字号、位号

②将相应二进制位设为“0”

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

空闲表法和空闲链表法都不适用于大型文件系统，因为空闲表或者空闲链表会过大。所以UNIX系统采用了成组链接法对磁盘空闲块进行管理。

文件卷的目录区中专门有一个磁盘块为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。

超级块记录的是下一组的空闲块数，然后底下表示的就是空闲块号，并且这些空闲块不是连续的，而是离散存储使用指针相连的，这里只是为了方便表示。所以现在上图中的情况是表示超级块表示下一组有100个空闲块分别是201~300号同时发现300号，即此时300号是空的，但是同时300号有表示下一组有100个空闲块分别是301~400号，同时400号表示下一组7801~7900是空闲块，但是当遇到-1表示这个是空闲块的末尾了即使空闲块此时显示一个正整数但是此时也表示没有空闲块了。