OS复习笔记ch12-2

辅存管理

文件分配问题

创建文件一次性分配最大空间吗？
分配连续的分区空间，分区多大？
用什么数据结构记录？
（1）分配方式

类似于#ch8-3调页机制，文件分配也有预分配和动态分配的形式。
一般拷贝/备份文件的时候，我们明确得知文件的大小，可以采用预分配，其他基本都是动态分配。

（2）分区大小
portion size 分区/簇大小（连续分区）

如果采用固定分区，存在两个极端

分配可以容纳全部文件大小的分区（内碎片很多，浪费严重）
一次分配一块（跟文件大小无关，管理开销很大）
实际上，辅存分配与内存分配类似
分区较大：提高I/O访问性能，减小管理开销；但分区内碎片浪费问题较严重；
分区较小：分区内的碎片浪费较小，特别是大量小文件时有利；但管理开销大（如FAT12、16、32）；

如果采用动态分区，I/O访问的性能确实较好，不过管理开销随之也更大了。

文件的存储/物理结构

文件的物理结构和文件存储的组织形式和存储介质有关。文件分配一般有以下三种分配方式

连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块（文件分配表中只一个表项）。

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

链接分配

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

（1）隐式链接：除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针，一般用于顺序文件。

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

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

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

举个🌰，早期的DOS中采用FAT32，就是一种显示链接分配（用4个字节存放盘块号，启动之后在内存中），现在的DOS一般采用NTFS。

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

索引分配

目前常见的主流的文件分配形式——索引分配。

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

索引表存放的磁盘块称为索引块。文件数据存放的盘块称为数据块。

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

链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下。
多层索引：建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘。
混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。优点: 对于小文件来说，访问一个数据块所需的读磁盘次数更少。

举个🌰，在Linux类操作系统中文件系统ext2会使用混合索引的模式

一般来说，像hello.c这种小文件是direct访问（无需建立索引），而single indirect是一级索引，往往存放的是音频文件，double indirect是二级索引，往往是视频文件。

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

举个🌰，若盘块大小为1KB，一个盘块号需4个字节存放。那么一级、二级索引方式各支持的最大文件是多大？

一级索引方式：
在一级索引方式中，每个文件的索引项占用一个盘块（1KB），其中每个索引项存储一个盘块号。因此，一级索引可以直接引用的盘块数为1KB / 4B = 256个。由于每个盘块大小为1KB，所以一级索引支持的最大文件大小为256 * 1KB = 256KB。
二级索引方式：
在二级索引方式中，除了使用一级索引外，还使用了一个二级索引表。每个文件的索引项仍占用一个盘块（1KB），其中每个索引项存储一个盘块号，指向二级索引表。二级索引表中的每个索引项也占用一个盘块（1KB），其中每个索引项存储一个盘块号，指向文件的数据块。因此，二级索引可以引用的盘块数为256（一级索引） * 256（二级索引表） = 65,536个。由于每个盘块大小为1KB，所以二级索引支持的最大文件大小为65,536 * 1KB = 65,536KB = 64MB。

知识点总结

空闲空间的管理

（1）Bit Tables 位图（内存空间+磁盘空间）

位示图：每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每一位对应一个盘块。因此可以用(字号，位号)对应一个盘块号。
（2）空闲区链
每个空闲区有指针、长度，通过指针链接。每次分配一个块，需要读取指针等信息并写入新首块后才能写数据到此块。分配/回收多个块时，需多次指针修改。
优点：适用于所有的文件分配方法，少量的空间开销
缺点：产生碎片，且多次修改指针不方便。
（3）空闲块表

可以用栈/对于队列去存一部分空闲盘块作为空心啊盘块表，然后读进内存用于分配和回收，适用于连续分配的方式

知识总结：

文件系统的全局结构

在文件系统中，对于OS和进程都有一个文件表，便于各自的管理：

全局打开文件表：包含所有打开文件的信息，每个条目指向一个具体的FCB。全局文件表跟踪哪些文件当前被打开，以及它们被打开的模式和状态。
进程文件表：每个进程有自己的文件表，文件表中的每个条目包含一个指向全局打开文件表的指针和一个引用计数。

这张图详细描述了在文件管理系统中打开（open）和读取（read）文件的过程。图中的步骤与数据流程图配合，展示了从用户命令到文件系统操作的详细步骤。以下是各个步骤的详细解释：

（1）打开文件

用户执行open命令：用户通过输入一个文件路径和打开模式（如只读、读写等），请求打开一个文件。例如 open(/.../M/A, R)。
检索FCB（文件控制块）：系统首先检索文件控制块FCB，它包含了文件的元数据，如文件名、类型、权限、大小、修改时间等。在这个例子中，文件A的FCB被检索出来，复制到系统全局的打开文件表。
分配文件描述符：系统为打开的文件分配一个文件描述符（fd），文件描述符是一个索引，指向进程文件表中的一个条目，该条目链接到系统打开文件表。

（2）读取文件

用户执行read命令：用户通过read(fd, buffer, size)命令请求读取文件，其中fd是文件描述符，buffer是数据存储的内存地址，size是请求读取的字节数。
定位文件数据：系统使用文件描述符定位全局打开文件表中的条目，从而获取FCB。FCB中包含文件数据的位置信息，系统利用这些信息找到文件数据的实际物理位置。（对应从fd出发的红色箭头指向）
数据传输：系统将数据从存储设备读入到指定的内存缓冲区。

更为具体的🌰，在Linux0.1x中打开文件的流程图示：

这张图展示了Linux 0.1X版本中文件管理系统的核心组件与其工作方式。
图中的左部是文件描述符表，对应上述进程文件表，中部文件表对应全局文件表。下面是对这些组件和它们之间联系的详细解释：