【操作系统】文件的物理结构

1. 文件的物理结构

1. 文件块、磁盘块

在内存管理中，进程的逻辑地址空间被分为一个一个页面。

同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。

于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。

2. 文件分配方式——连续分配

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

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

物理块号=起始块号+逻辑块号

当然，还要检查用户提供的逻辑块号是否合法（逻辑块号>=长度 就不合法）

注意：可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（即随机访问）。

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。

结论：连续分配的文件在顺序读/写时速度最快。

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

结论:物理上采用连续分配的文件不方便拓展。

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

3. 文件分配方式——链接分配

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

隐式链接

用户给出要访问的逻辑块号i,操作系统找到该文件对应的目录项(FCB) ...从目录项中找到起始块号(即0号块)，将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置...以此类推。因此，读入i号逻辑块，总共需要i+1次磁盘I/O。

结论:采用链式分配(隐式链接)方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。

若此时要拓展文件，则可以随便找一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的FCB。

结论:采用隐式链接的链接分配方式，很方便文件拓展。另外，所有的空闲磁盘块都可以被利用，不会有碎片问题,外存利用率高。

显示链接

把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配 表(FAT，File Allocation Table )。

假设某个新创建的文件“aaa”依次存放在磁盘块2->5->0->1

假设某个新创建的文件“bbb”依次存放在磁盘块4->23->3

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

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB) ... 从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT,往后找到i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。

结论:采用链式分配(显式链接)方式的文件，支持顺序访问，也支持随机访问(想访问i号逻辑块时，并不需要依次访问之前的0~i-1号逻辑块),由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。

显然，显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。

注意：如果没有说明，则默认是隐式链接的方式。

4. 文件分配方式——索引分配

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

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB) 从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只i号逻辑块在外存中的存放位置。

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

若每个磁盘块1KB，一个索引表项4B，则一个磁盘块只能存放256个索引项。

如果一个文件的大小超过了256块，那么一个磁盘块是装不下文件的整张索引表的，如何解决这个问题?

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

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

说明：采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。

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

2. 小结