4.1_4 文件的物理结构

（一）文件块、磁盘块

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

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

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

（二）文件分配方式——连续分配

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

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

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

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

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

---

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

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

---

  若此时文件A要拓展，需要再增加一个磁盘块（总共需要连续的4个磁盘块）。

  由于采用连续结构，因此文件A占用的磁盘块必须是连续的。 因此只能将文件A全部“迁移”到绿色区域。

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

---

  结论：物理上采用连续分配， 存储空间利用率低，会产生难以利用的磁盘碎片。

  可以用紧凑来处理碎片，但是需要耗费很大的时间代价。

---

连续分配——总结

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

  优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快。

  缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片。

（三）文件分配方式——链接分配

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

（1）链接分配——隐式链接

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

  从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存 放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置……以此类推。

  因此，读入i号逻辑块，总共需要i+1次磁盘I/O。

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

---

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

（2）链接分配——显式链接

  把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（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号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。

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

---

链接分配-总结

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

  隐式链接——除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。

  优点：很方便文件拓展，不会有碎片问题，外存利用率高。

  缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

  显式链接——把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，File Allocation Table）。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

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

  缺点：文件分配表的需要占用一定的存储空间。

  考试题目中遇到未指明隐式/显式的“链接分配”，默认指的是隐式链接的链接分配。

（四）文件分配方式——索引分配

  索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

  假设某个新创建的文件“aaa”的数据依次存放在磁盘块2—>5—>13—>9。

  7号磁盘块作为“aaa”的索引块， 索引块中保存了索引表的内容。

  注：在显式链接的链式分配方式中，文件分配表FAT是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对应一张。

  可以用固定的长度表示物理块号（如：假设磁盘总容量为1TB=$2^{40}$B，磁盘块大小为1KB，则共有$2^{30}$个磁盘块，则可用4B表示磁盘块号），因此，索引表中的“逻辑块号”可以是隐含的。

  有点类似于页式存储管理当中进程的页表。

---

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

  从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可知i号逻辑块在外存中的存放位置。

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

---

  1.链接方案；

  2.多层索引；

  3.混合索引。

---

1.链接方案

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

  假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。

  若一个文件大小为256*256KB = 65,536 KB = 64MB。

  该文件共有256*256个块，也就对应256*256个索引项，也就需要256个索引块来存储，这些索引块用链接方案连起来。

  若想要访问文件的最后一个逻辑块， 就必须找到最后一个索引块（第256个索引块），而各个索引块之间是用指针链接起来的，因此必须先顺序地读入前255个索引块。

  这显然是很低效的。如何解决呢？

2.多层索引

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

  假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。

  若某文件采用两层索引，则该文件的最大长度可以到256*256*1KB = 65,536 KB = 64MB。

  可根据逻辑块号算出应该查找索引表中的哪个表项。

  如：要访问1026号逻辑块，则1026/256 = 4，1026%256 = 2。

  因此可以先将一级索引表调入内存，查询4号表项，将其对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号了。访问目标数据块，需要3次磁盘I/O。

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

  若采用三层索引，则文件的最大长度为256*256*256*1KB = 16GB。

3.混合索引

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

  上图这种结构的索引支持的最大文件长度为65800KB。

  若顶级索引表还没读入内存，

  访问0~7号逻辑块：两次读磁盘；

  访问8~263：三次读磁盘；

  访问264~65799：四次读磁盘。

  对于小文件，只需较少的读磁盘次数就可以访问目标数据块。（一般计算机中小文件更多）

---

索引分配-总结

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

  若文件太大，索引表项太多，可以采取以下三种方法解决：

  ①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点：若文 件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0 ~ i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下。

  ②多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。

  缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘。

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

  优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

---

超级超级超级重要考点：

  ①要会根据多层索引、混合索引的结构计算出文件的最大长度（Key：各级索引表最大不能超过一个块）；

  ②要能自己分析访问某个数据块所需要的读磁盘次数（Key：FCB中会存有 指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件——顶级索引块是否已调入内存）。

总结