408王道操作系统强化——文件管理及大题解构

目录

1.基本概念

2.FAT文件系统

2.1.FAT文件系统的基本概念

2.2.FAT文件系统打开文件的过程（OPEN系统调用）

3.UFS文件系统

3.1.UFS文件系统的基本概念

3.2.UFS文件系统打开文件的过程

4.小结

5.真题

---

1.基本概念

1.文件目录 = 目录文件

2.文件的逻辑结构有①无结构文件（由记录组成） ②有结构文件

3.MP3文件格式：

①Mp3Frame（Mp3帧）是文件记录（相当于一个Struct结构体）：Mp3Fream由Mp3Header（头信息）和Mp3Data（数据信息）组成，即Mp3文件是记录式文件，即Mp3属于有结构文件

②Mp3Header大小固定，而Mp3Data不一定

③使用Mp3文件时，用户提供的是逻辑地址，操作系统根据MpHeader中的各种信息将逻辑地址转换为物理地址

3.DOS采用FAT文件分配表（显示链接）；UFS采用混合索引

2.FAT文件系统

2.1.FAT文件系统的基本概念

1.目录文件：即我们打开文件时所看到的各文件夹

2.每个文件系统都有可能作为系统的启动盘，因此，每个文件系统的第一个块为启动块存放自举程序（ROM引导程序，作用是完成一系列开机的动作；区别于BIOS：BIOS存放在ROM中，自举程序是BIOS的最重要的组成部分）

3.FAT采用显示链接的文件物理结构，即FAT文件分配表（类似操作系统中的静态链表）：说明第1 - n块分别在磁盘的什么地方

（隐式链接（类似链表）：每个文件FCB中只记录文件的起始块号和结束块号；只支持从起始块号开始的顺序访问；使用指针表示块之间的关系）

4.FAT文件分配表采用连续存放的方式：FAT文件系统中会使用在引导块后的若干连续块存放FAT文件分配表（开机时操作系统将FAT文件表读入内存中，即查询和访问FAT文件分配表无需进行度磁盘操作）

5.根目录存放在FAT表之后的固定位置：操作系统在完成一系列开机操作时以根目录为起点逐层往下寻找相应文件并执行（开机时操作系统将根目录读入内存中，并且常驻内存，即查询和访问根目录无需进行度磁盘操作）

6.①一行即为一个目录项（FCB）

②FAT文件分配表的每个目录项大小（位数）决定FAT文件系统的总块数：每个FAT表项16bit，则最多只能表示2^16个 块号

③FAT文件分配表的每个目录项大小（位数）决定FAT文件分配表的总大小：每个表项的大小*表项的数量 = FAT表的大小，即FAT文件分配表的总大小 = 2 ^ 16 * 16 bit

7.文件类型即文件格式

2.2.FAT文件系统打开文件的过程（OPEN系统调用）

1.①进程使用open系统调用打开某个文件时需指明该文件的存储路径（例如：/x/y/z.exe）

②因此，打开某个文件时，先需要找到该文件的目录项（FCB，该文件的FCB中记录了该文件的存储路径）

③该文件存储在哪个目录下，则该文件的目录项（FCB）就存放在这级目录中（通过对比这级目录中是否有与该文件名相同的文件的方式）

④该文件FCB上记录了该文件的起始块号，通过该起始块号操作系统就可以在FAT表中查到存储该文件所使用的每一个块的块号和存储位置（从起始块号出发，逐块查找，直到最后一个块）

⑤操作系统找到该文件后，将会给进程返回一个fd（文件描述符，相当于指向该文件的指针；作为对进程发出open系统调用的回应）

⑥进程接下来对该文件的操作可以转化为对该fd的操作（例如read（fd））

⑦用户可以指定读取具体哪个块，即用户不需要每次都从头开始读；同样的，操作系统也可以只将用户指定的具体该进程的第几个块读入内存，读入内存后，操作系统还要建立起该文件虚拟地址到物理地址转换的映射关系，即修改页表

2.FAT文件系统下打开文件的过程：

①根据文件路径找到文件的FCB

②根据文件FCB中的找到该文件的起始块号

③根据起始块号在FAT文件分配表中通过逐块查找，找到任何一个逻辑块对应的物理块（需要逐块查找；但可以指定某个特定的块读入）

③修改页表，完善逻辑地址到物理地址的映射关系

3.例：进程通过OPEN（/A/Dm）打开Dm文件

即打开存放在目录A下的文件Dm；目录A的n个FCB共占用三个物理块，并且占用的三个物理块号为5、6、7，设Dm的FCB在第七个物理块

①在根目录下查找名为A的目录文件，即在内存中存放根目录的页框查找（任何文件的存储路径都可以从根目录出发找到，而操作系统开机时已经将根目录入读内存，且常驻内存）

②步骤①中只能找到目录A的起始块号；并且目录A由n个FCB（所有存放在目录A下的文件/目录文件）组成，这些FCB的总大小为3个物理块（即这n个FCB被存放在这3个物理块中），故需要查找FAT文件表就需要将目录A的目录项读入内存（可以每读入一个块就进行查询，该块没有目标文件的FCB则继续读入下一个块；该块有目标文件的FCB，则不必继续读入剩余块）

③操作系统依次将（磁盘中的）物理块5、6、7读入内存（分开读入，读入后立即查询；该块没有，则读入下一块；该块有，则不用读入下一块），然后逐一查找A的FCB中是否有同名的文件Dm；找到Dm后，就可以知道它的起始块号和所占用的块数

④找到Dm的FCB后，返回给进程fd，供其接下来使用，然后进程就可以使用READ系统调用读入Dm的两个块

OPEN系统调用和READ系统调用期间一共发生5次读磁盘：

①根目录已经在内存中，因此查询根目录不需要访存

②OPEN系统调用：Dm存放在目录A的FCB的第三个块中，因此，需要读入5、6、7块磁盘，磁盘读写以块为单位，故需要访存三次（不同策略下OPEN系统所需要的读磁盘次数不同：①一次性将目标目录的所有FCB全部读入        ②每读入一个物理块的FCB就查询，这个磁盘块上没有目标FCB才读入下一个物理块，这样能有效减少读磁盘操作）

③READ系统调用：将Dm的两个块读入内存，需要2次读磁盘

4.FCB确定起始块的位置，FAT文件分配表确定后续块的位置

5.例：OPEN（/C/F/G），READ

①查找根目录下的目录文件C的起始块号 → 9

②将9号块入读内存，查找目录文件F的起始块号 → 14

③将14号块读入内存，查找文件G的起始块号 → G的文件大小和起始块号

④根据FAT文件分配表、G的文件大小和起始块号 → G的每一个块

3.UFS文件系统

3.1.UFS文件系统的基本概念

1.采用混合索引的方式将FAT文件系统中FCB的占用空间过大的问题进行优化：因此每个目录项只需包含 “文件名、inode号”，文件的具体属性包含在 inode 中

2.INODE区：磁盘中专门划分出存放所有INODE的区域，即所有INODE有共同的起始地址

3.每个INODE（索引结点）大小固定（类似数组）

4.2和3的特性可以根据INODE编号迅速找到指定INODE

5.UFS文件系统下，所能支持的最大容量为：

①直接索引下 = 每个直接索引结点代表一个完整的数据块

②一级间接索引 = 物理块大小 / FCB大小 = 每个物理块所能容纳多的FCB数，设为x

③二级间接索引下 = x * x

索引块：该磁盘块用于存储索引表，且每张索引表需要刚好占满一个磁盘块

若每个磁盘块大小为4KB，每个索引项4B，则一张索引表包含1024个索引项

数据块：该磁盘块用于文件数据

6.位示图中，每个bit对应⼀个磁盘块，因此，若磁盘块共有 n 个， 则位示图也⾄少要有 n bit

设⼀个磁盘块大小为4KB，即 32K bit，因此这个位示图能支持的磁盘大小上限为 32K 个块

7.每个文件必须对应⼀个inode结点，而inode结点的总数是有上限的

设8KB作为inode区， 假设每个inode大小为64B，则该文件系统最多只能存储8KB/64B=128个 inode结点，即该系统最多只能支持128个文件

3.2.UFS文件系统打开文件的过程

1.每次先读入INODE，再根据INODE内容读入FCB，再根据FCB的内容读入下一级目录文件的INODE，循环（查询INODE和FCB交替进行）直到找到目标文件的FCB

2.INODE的作用是指明目标文件的实际存放地址，即INODE并非目标文件

3.OPEN系统调用找到的是目标文件的INODE，且将该INODE读入内存，并向进程返回指向该INODE的fd后，OPEN系统调用即完成；之后可以通过该INODE找到目标文件的所有物理块

1.UFS文件系统和FAT文件系统打开文件的过程本质上是一致的，都是查找目标文件的FCB

2.例：OPEN系统调用（/A/Dm）

①查找根目录（开机时已经读入内存，并且常驻内存，访问无需读磁盘）→ 目录文件A的INODE号为1

②将存放1号INODE读入内存（只有读入内存，才能对INODE的信息进行各种操作，此时发生一次读磁盘操作）

③根据INODE结点可知，目录文件A的FCB总共占用两个块，此时有两种查找策略：

1.两个块全部读入后再查找Dm文件的FCB（2个块，固定2次读磁盘） 

2.每读入一个块就立即对该块查询Dm的FCB，没有才读入下一块（最少1次，最多2次读磁盘）

④设Dm的FCB存放在7号块中（此时1、2策略都需要2次读磁盘）；将目录文件A的FCB读入内存后，查询可知Dm所对应的INODE号为5，即需要读入5号INODE

⑤读入5号INODE后（需要1次读操作），即获得Dm的FCB，完成OPEN系统调用

3.在混合索引方式下，支持随机访问，即可以根据文件的逻辑块号只读入文件的某个块

4.例：读文件H的第11.5KB：OPEN（/ C / F / H）→ READ（11.5KB）

①查询根目录 → 文件目录C所对应的INODE号 → 7 → 将7号INODE读入内存

②查询7号INODE → 文件目录C所对应的FCB为9号块 → 将9号块读入内存

③查询文件目录C → 文件目录C所对应的INODE号 → 4 → 将4号INODE读入内存

④查询4号INODE → 文件目录F所对应的FCB为14号块 → 将14号块读入内存

⑤查询文件目录F → 文件H所对应的INODE号 → 10 → 将10号INODE读入内存，并向进程返回指向该INODE的FD → OPEN系统调用完成

⑥开始READ系统调用：前10个直接索引只能找到该文件的前10个块，即前10KB，10KB之后的数据就要通过间接索引得到 → 一级间接索引表存放在21号物理块中 → 读入21号块

⑦查询读入内存的21号块 → 得到12号块的物理块号为23

4.小结

1.READ/WRITE系统调用之前先要进行OPEN系统调用

2.OPEN系统调用的本质是找目标文件的FCB

3.FAT文件系统下根据文件的起始块号和FAT文件分配表逐一开始查询

4.UFS文件系统下先找到文件的INODE结点，并将该INODE读入内存，之后就可以根据其索引信息知道该文件的物理块分配情况

5.真题

（1）文件系统能支持的最大文件长度 =

①直接地址项 = 8个块

②一级间接地址 = 4KB / 4B = 1024 个块 即每个块可以存放的地址项共1K个

②二级间接地址 = 1024 * 1024

③三级间接地址 = 1024 * 1024 * 1024

（2）①一个索引结点对应一个文件，即文件数量的上限受到索引结点个数的制约

②每个文件5600B，每个簇4KB，每个文件需要2个蔟保存，即文件数量的上限受到簇数量的制约

①②取最小值

（3）直接索引方式下，可以直接通过INODE结点的信息读入相应的数据块，即一次就可以读入数据；

一级间接索引方式下，INODE结点的信息保存的是存放该文件的索引信息的物理块，需要把该物理块读入后，才能知道存放数据块信息的INODE，即第一次读入的是INODE，第二次读入的才是数据

（1）目录文件的每个目录项包括文件名和文件的第一个簇号

 （2）FAT表项存放的是下一个块的块号，16bit能表示2^16个磁盘块号；每个块号需要2B的表项，即FAT的最大长度为2 ^ 16 * 2B = 2 ^ 17B；

共2^16个磁盘块全部分配给1个文件，每个磁盘块4KB，即文件的最大长度为2 ^16 * 4KB

（3）通过FAT表项100得到106，通过FAT表项106得到108（FAT表项108为-1）

（4）根据根目录找到dir1的目录项，读入48簇；根据dir1的目录项找到file1的FCB，根据FCB中file1的初始块号到FAT文件分配表中查找，先找到100，然后找到106的块号，读入106