文章目录

1. 文件系统基础
2. 文件系统实现
- 2.1 文件系统层次结构
3. 磁盘组织与管理
4. 补充
- 4.1 文件的逻辑结构vs文件的物理结构

1. 文件系统基础

1.1 文件管理概述

引入文件系统的目的：

从系统角度：实现对文件的管理。
从用户角度：实现对文件的按名存取。

1.2 文件的逻辑结构

注意：记录指类似于数据库中表的一行数据，而记录的关键字就类似于数据库表的关键字(唯一ID)

1.2.1 顺序文件

顺序文件：

注意：

链式存储的顺序文件无法实现随机存取，顺序存储的顺序文件如果是可变长记录也无法实现随机存取。只有为顺序存储且为定长记录时才能实现随机存取。

重点注意：一般顺序文件默认指的顺序存储的顺序文件，做题的时候特别注意。

顺序文件的缺点：增删比较麻烦。

1.2.2 索引文件

索引文件：
由于只有定长记录的顺序文件才能实现随机访问【随机访问能提高对文件的访问速度】，对于非定长的顺序文件不能，所以引出索引文件。它对定长和非定长记录的文件都能实现随机访问。

当文件很多时，会使得索引表非常的大。此时，我们需要将索引表分割存储。根据分割方式的不同，分为索引顺序文件和多级索引文件两类。

1.2.3 索引顺序文件

索引顺序文件：

1.2.3 多级索引顺序文件

多级索引顺序文件：

1.3 文件目录(表)

文件目录：把所有的FCB组织在一起，就构成了文件目录，即FCB的有序集合，它是一张表；
目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保持在外存，这个文件就叫目录文件。
可以这样去理解：文件目录和目录文件是同一事物的两种称谓。从用途角度来看称其为文件目录，从实现角度来看称其为目录文件。

1.3.1 文件控制块（别名：文件的目录）

注意：

文件目录本身是一个有结构的文件，由一条条记录组成。每一条记录对应一个文件的FCB。

文件目录：是一组FCB的有序集合。

FCB实现了文件名和文件之间的映射。使用户可以实现“按名存取”。

1.3.2 文件目录的结构

1.3.2.1 单级目录结构

* 单级目录结构：指整个系统中只有一个文件目录。用于早期的单用户操作系统。
	* 优点：能够实现“按名存储”
	* 缺点：不允许文件重名，不适用于多用户操作系统。

1.3.2.2 两级目录结构

* 两级目录结构：有“主文件目录”和“用户文件目录”两级文件目录。前者记录用户名和用户文件目录地址。后者由该用户的文件FCB组成。
	* 优点：允许不同用户的文件重名；能够适用于多用户系统
	* 缺点：缺乏灵活性，用户不能对自己的文件分类。

1.3.2.3 多级目录结构（数形目录结构）

* 多级目录结构：有多级文件目录组成。像一颗树一样。
	* 优点：
		1. 比较灵活，用户能够将自己的文件分类。
		2. 能够通过“相对路径”和“绝对路径”(当前工作目录)减少用户对磁盘的I/O操作，从而提高对文件的访问速度。
	* 缺点：无法实现文件的共享。

1.3.2.4 无环图目录结构

* 无环图目录结构：在多级目录结构下，添加了指向同一个文件的边，从而方便实现文件共享。
	* 优点：能够实现文件的共享
	* 缺点：删除一个文件会变的复杂。
* 注意：只有共享计数器为0时，才能将该文件删除。

1.3.3 索引结点（对文件控制块的优化）

* 文件索引：将文件目录中，除文件名之外的信息统一存放到一个位置，让文件目录存放更多的目录项。而这个位置就叫“文件索引”
		   【注意：每一个文件都有一个文件索引】
	* 分类
		1. 内存文件索引
		2. 磁盘文件索引
	* 优点：用更少的盘块存放文件目录，从而减少**查找文件**时磁盘的I/O次数，提高访问效率。

1.3.4 小结

1.4 文件的物理结构(文件分配方式：已用块)

1.4.1 连续分配(顺序分配)

* 连续分配：磁盘为该文件分配连续的块来存放整个文件。
	* 关键字段：起始块号和长度
	* 地址转换： (物理块号=起始地址+逻辑块号，块内地址)
	* 优点：
		1. 支持顺序访问和直接访问(即随机访问)
		2. 连续分配的文件在顺序读/写时速度最快。
	* 缺点：
		1. 会产生难以利用的磁盘碎片，导致存储利用率低（可以通过“紧凑”技术解决）
		2. 不利于文件扩展。

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

1.4.2 链接分配

1.4.2.1 隐式链接

* 隐式链接：除文件的最后一个块之外，每个块中都存放下一个块的指针。
	* 关键字段：起始块号、结束块号
	* 地址转换： (物理块号=遍历链表到i号块的地址，块内地址)
	* 优点：
		1. 不会产生碎片，存储空间利用率高
		2. 方便文件扩展
	* 缺点：
		1. 只支持顺序访问，不支持直接访问(随机访问), 查找效率低
		2. 指向下一个盘块的指针也需要耗费空间。

* 注意：
	1. 访问i号盘块，需要 i+1 次磁盘I/O
	2. 如果没有说明，默认链式分配方式指的是隐式的链式方式。

1.4.2.2 显式链接

* 显式链接：链接各物理块的指针显式的放在一张表中，即`文件分配表(FAT)`。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。
	* 关键字段：起始块号
	* 地址转换： (物理块号=访问文件分配表，块内地址)
	* 优点：
		1. 不会产生碎片，存储空间利用率高
		2. 方便文件扩展
		3. 支持随机访问
		4. 地址转换不需要访问磁盘，因此文件的访问效率更高
	* 缺点：
		1. 文件分配表需要占一定的存储空间。

* 注意：“随机访问”指的是能否根据记录号直接访问某个盘块，并不是指是否能直接访问我们想要访问的盘块，因为链式分配方式是有前后逻辑关系的。

1.4.3 索引分配

如果文件过大，会导致索引表过大，一个盘块无法存放整个索引表。解决方法是将索引表拆分为几个小的索引表，而小的索引表直接的联系方式不同，导致索引分配的不同类别：

链接索引分配
多层索引分配
混合索引分配

1.4.3.1 链接索引分配

优点：能够解决大索引表无法存放的问题。
缺点：访问磁盘I/O次数多，导致查找效率很低。

1.4.3.2 多层索引分配

优点：查找的效率高
缺点：

大小文件的访问磁盘次数相同。
会产生更多的索引表，占更多的存储空间。

1.4.3.3 混合索引分配

优点：查找效率高，小文件访问磁盘的I/O次数会更少。

1.4.4 小结

1.5 文件存储空间管理（空闲块）

1.5.1 存储空间的划分与初始化

注意：

一个文件卷（逻辑卷）可以由一个磁盘的某部分组成，也可以由多个磁盘组成。

每个文件卷分为：目录区与文件区

目录区存放的是FCB、用于磁盘管理的一些信息。

文件区用于存放文件数据。

1.5.2 几种管理方法

1.5.2.1 空闲表法

1.5.2.2 空闲链表法

1.5.2.3 位示图法

1.5.2.4 成组链接法

例题：

（1）该磁盘中目前还有多少个空闲盘块？
（2）在为某个文件分配3个盘块后，系统要删除另一文件，并回收它所占的5个盘块，它们的盘块号依次为700、711、703、788、701，请画出回收后的盘块链接情况。
解答：
（1）：301；首先看空闲盘块号栈，此时N=2，表示有两个空闲盘块299、300，而盘块300号上面又写着有100个空闲盘块：301-400，它还有下一个链接的盘块400；在盘块400中，记录有100个空闲盘块401-500；然后又链接到500号盘块，在500号盘块中，虽然N=100，但是第一个是0，它表示空闲盘块链的结尾。因此，总共的空闲盘块有：299、300、301-400、401-500、501-599；即301个空闲盘块。
（2）：

步骤1：分配三个空闲盘块
首先看空闲盘块号栈，发现N=2，那么到达栈顶即S.free[2-1]=299，即把299号盘块分配出去了，这时磁盘状态如下：

然后分配第二个盘块，这时N=1，如果再分配就会变成空栈了，因为S.free[N-1]=S.free[0]!=0,所以需要将300号盘块的内容拷贝到空闲盘块号栈，并分配300号盘块（如果S.free[0]=0，则表示没有空闲盘块，将会阻塞进程），分配300块后的示意图：

接下来分配301号盘块：/
步骤二：回收700、711、703、788、701号盘块
回收的过程也是从栈顶开始的，首先看N=99，然后回收700，会将700放在S.free[N]的位置，然后将N加1变成100：

然后回收711号盘块，因为此时空闲栈的N=100，已经满了，如果再回收，需要将空闲盘块栈的内容移动到711号盘块上，然后将空闲盘块栈的S.free[0]设置为711，N设置为1；接着回收703、788、701，最终结果图如下：

1.5.3 小结

注意：文件分配表：其表项与物理盘块一一映射，以及块的先后链接关系。其不仅包含了已分配的块，还包含了空闲块。所以其不仅能管理空闲磁盘块，还能管理已配的块。

1.6 文件的基本操作

1.6.1 创建文件

1.6.2 删除文件

1.6.3 打开文件

注意：

用户的“打开文件表”与系统的“打开文件表”不一样，但是其都在内存中【用户在表就在】。

打开计数器是系统的“打开文件表”所特有的。

打开文件是将文件的FCB也就是该文件的目录复制到内存指定区域，具体是内存中的“打开文件表“中。注意是FCB，而不是不是整个文件。

打开一个进程，获得对应的文件描述符是指向用户的”打开文件表“中的某一项，而不是指向系统”打开表“【简单想，如果指向系统表，指针会相同，不同用户应该不同】。

注意”读写指针“、”访问权限“是在用户的”打开文件表“中，所以如果多用户共享某个文件，用户都打开该共享文件，则其”读写指针“、”访问权限“可能相同，也可能不同。

1.6.4 关闭文件

1.6.5 读文件

1.6.6 写文件

1.6.7 小结

1.7 文件共享

1.7.1 基于索引结点的共享方式（硬链接）

1.7.2 基于符号链的共享方式（软链接）

如果某个共享文件被删除，点击对应的“link”文件，会提示“xxx以删除”。

1.7.3 小结

注意：建立符号链时，引用计数器的值直接复制；建立硬链接时，count+1。

1.8 文件保护

1.8.1 口令保护

1.8.2 加密保护

如果没有正确的加密密码，那就是一串没有意义的乱码。

1.8.3 访问控制(又叫：存取控制)

1.8.4 小结

注意：

加密保护的安全性比访问控制的安全性高，因为访问控制的基本和力度小，但是灵活性高。

只有访问控制是由系统实现，其他都是由用户实现。

用户权限表属于访问控制实现方式之一。

2. 文件系统实现

2.1 文件系统层次结构

3. 磁盘组织与管理

3.1 磁盘的结构

磁盘、磁道、扇区的概念
盘面、柱面
如何在磁盘中读/写
磁盘的分类
1. 按磁头分：
1. 按磁盘是否可更换分：
小结

3.2 磁盘调度算法

3.2.1 一次磁盘读/写操作需要的时间

注意：在寻道时间、延迟时间、传输时间中，影响最大的是寻道时间，因为移动磁盘臂很非时间。

延迟时间和传输时间与转速r有关，是无法用算法优化的。只能优化寻找时间，下面介绍对于寻找时间的几种优化算法。

3.2.2 磁盘调度算法（减少寻找时间）

3.2.2.1 先来先服务(FCFS)

3.2.2.2 最短寻找时间优先(SSTF)

3.2.2.3 扫描算法(SCAN)(又叫电梯算法)

3.2.2.4 循环扫描算法(C-SCAN)

3.2.2.5 LOOK调度算法（SCAN算法的改良）

3.2.2.6 C-LOOK调度算法（C-SCAN算法的改良）

3.2.3 小结

注意：
1. 磁臂黏着: 指系统总是访问磁盘的某个磁道，而不响应对其他磁道的访问请求。
2. 磁臂黏着不是“饥饿”
3. 除了FCFS都会发生磁臂黏着现象。（因为其他算法都要从小到大排序）

3.2.4 减少延迟时间

磁头读取完一个扇区后，需要大约一个扇区的时间来准备，才可以读取下一个扇区的内容。但是，磁盘是连续转动的，这就使得如果读取的两个扇区在物理上是相邻的，就不能一圈读取完，需要读取两圈。比如：

解决的方法：

交替编号
错位命名

3.2.4.1 交替编号

注意：交替编号是针对同一盘面的。

3.2.4.2 错位命名

注意：错位命名是针对不同盘面的。

3.2.4.3 小结

盘面内采用交替编号，盘面间采用错位命名。能够极大的减少对磁盘I/O的延迟时间。

3.2.5 磁盘的管理

4. 补充

4.1 文件的逻辑结构vs文件的物理结构

1. 文件的逻辑结构是为了方便用户而设计的，而文件的物理结构是为了方便操作系统组织盘块。（角度不同）
2. 文件中逻辑结构中引入的索引和物理结构中的索引目的不同。
	* 前者是为了加快文件的定位，实现随机访问，是从用户角度出发
	* 后者目的是为了管理不连续的物理块，是从系统管理角度出发的。

1. 当前工作目录指的是“相对路径”，目的是加快文件的检索速度。

2. UNIX系统中，输入/输出设备视为特殊文件。

3. 打开文件操作的主要工作是该文件目录项(即FCB)复制到打开文件表中。
	将文件内容从外存加载到内存是读文件操作。

4. 文件的逻辑结构是方便用户而设计的；
	文件的物理结构是操作系统设计者对硬件结构采取的策略，即方便OS管理。

5. 目录文件存放的信息：该目录下中的所有子目录和数据文件的目录，即所有文件的FCB信息。

6. 文件分配表(FAT)与文件目录(FDT)的区别与联系：
	1. 区别：FAT是用于表示磁盘空间的分配信息。FDT是记录文件或子目录的FCB信息的表格。
	2. 联系：FDT和FAT里面都有文件的FCB信息，前者是为了实现对文件的”按名存储“，后者是为了管理文件占用的存储空间，都需要文件的FCB信息。

7. 对于文件的访问，常由用户访问权限和文件属性决定。

8. 判断：一个文件在同一个系统、不同的存储介质上的复制文件，应采用同一种物理结构。
	错。同一系统复制文件，则两个文件的物理结构不一定相同。因为物理结构是从OS角度出发，OS针对存储介质会使用合适的物理结构进行管理。

9. 判断：为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件。
	 错。为防止系统故障造成系统内文件受损，常采用备份的方式保护文件。而存取控制矩阵的方法只适用于多用户之间的存取权限保护。

10. 判断：read系统调用的参数应包含文件的名称。
	错误。文件的名称和路径应该是作为打开文件操作时的参数。

11. 文件目录项不包括( )
	A. 文件名		B.文件访问权限说明		C.文件控制块的物理位置		D.文件所在的物理位置
	选C。文件目录项就是文件的FCB，FCB不包含FCB的位置信息。

12. 文件描述符：是打开文件操作中的概念。打开一个文件，会在系统打开表和用户打开表中将立相应的文件项，而文件描述符是指向该用户打开文
		件表中的该文件项。

13. 判断：两个文件建立硬连接，其读写指针位置相同
		错误。因为读写指针位于用户打开文件表中，而两个进程对于的文件打开表项肯定不同，所以无法确定读写指针位置是否相同。

14. 加密保护的安全性比访问控制机制安全性高，而访问控制比加密保护的灵活性好。
	访问控制必须由系统实现。

15. 对一个文件访问，常由( )限制。
	①用户访问权限和文件属性
	②口令和文件属性
	选①。现在计算机常用的是①不是②。

16. 文件系统中，用户类别有4类，访问权限有5类。若FCB中用二进制位串表示文件权限，为表示不同类别用户对一个文件的访问权限，则描述文件
	的尾数至少为___位。
	20位。容易写成5位，比如11111，它只能表示某个用户拥有什么权限，并不能表示所有用户。这里有4个用户，4*5=20才能表示所有用户的权限。
	（这个4*5可以理解称一个矩阵，称位：存取控制矩阵或访问控制矩阵）

17. 下列能够提高文件访问速度的是( )
	①提前读		②为文件分配连续的簇		③延迟写		④采用磁盘高速缓存
	①②③④都对。
	提前读：指在读当前块时，将下一个可能要访问的盘块数据读入缓冲区，以便需要时直接从缓冲区读取，提高了文件访问速度。
	延迟写：指先将数据写入缓冲区，并置上“延迟写”标志，以备不久之后访问，当缓冲区需要再次被分配出去时，才将缓冲区数据写入磁盘，
		   减少了对磁盘的访问次数，提高了文件的访问速度。
	根据程序的局部性原理，所有如果分配连续的簇，访问速度会增加。

18. 为支持CD-ROM中视频文件的快速随机播放，播放性能最好的文件数据组织方式是( )
	A.连续结构		B.链式结构		C.直接索引结构		D.多级索引结构
	选A。ROM是只读存储器，不会进行文件扩展，又要能随机存储，所以连续分配结构最快。

19. 若某文件系统索引结点(inode)中有直接地址和间接地址项，则下列与单个文件长度无关的因素是( )
	A.索引结点的总数		B.间接地址索引的级数		C.地址项的个数		D.文件块大小
	选A。索引结点总数与文件大小无关，它代表的是文件个数。
	文件大小 = 总的地址项个数 * 文件块大小

20. 关于目录检索，正确的是( )
	A.由于散列法具有较快的检索速度，因此现代操作系统中都用它来代替传统的顺序检索。
	B.在利用顺序检索时，对树形目录应采用文件的路径名，且应从根目录出发开始逐级检索。
	C.在利用顺序检索时，只要路径名的一个分量未找到，就应该停止查找。
	D.利用顺序检索后，得到文件的物理地址。
	选C。散列法(就是索引表)虽然速度很快，但是其无法实现顺序检索和枚举检索，现在更多的是采用多级索引顺序文件。
	树形目录可以使用相对路径。顺序检索后得到的是文件的逻辑地址。

21. 设逻辑文件的固定长度为100B，采用连接分配方式。盘块长度为512B。若该文件的目录项已经读入内存，则对第
	22个逻辑修改后，共启动了磁盘__次
	6次。查找 = 22*100/512上取整 = 5次。修改完后，由于知道其地址，则只需要再对磁盘进行1次I/O，所以共6次。

22. 顺序文件、索引文件、索引顺序文件都是文件的逻辑结构，其表项存放的是记录的逻辑地址。
	  顺序结构、链接结构、索引结构的文件是文件的物理结构，其表项存放的是对应的物理块号。

23. 判断：文件分配表可用于文件系统管理空闲磁盘块。
	正确。文件分配表：其表项与物理盘块一一映射，以及块的先后链接关系。其不仅包含了已分配的块，还包含了空
	闲块。所以其不仅能管理空闲磁盘块，还能管理已配的块。

24. 某文件系统的簇和扇区大小分别是1KB和512B。若一个文件的大小为1026B，则系统分配给该文件的磁盘大小为__
	答:2KB.  因为系统以簇为单位进行资源分配。但是读写单位是盘块。

25. 光盘可以随机访问也可以顺序访问。而磁带只能顺序访问。

26. 下列选项中，磁盘逻辑格式化程序所作的工作是( )
	①对磁盘进行分区
	②建立文件系统的根目录
	③确定磁盘扇区校验码所占位数
	④对保存空闲磁盘块选项的数据结构进行初始化
	选②④。
	* 空白磁盘处理	
		1. 物理格式化：将磁盘分成各个扇区。并为磁盘的每个扇区采用特别的数据结构，包括校验码
		2. OS将自己的数据结构写在磁盘上，分为两步。
			1. 将磁盘分为由一个或多个柱面组成的分区，每个分区可以做为一个独立的磁盘
			2. 逻辑格式化(创建文件系统)OS将自己的数据结构写在磁盘上，并初始化信息。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/84599.html

【操作系统-chapter4】文件管理