操作系统——文件系统

笔记内容及图片整理自XJTUSE “操作系统” 课程ppt，仅供学习交流使用，谢谢。

文件系统是操作系统中以文件方式管理计算机软件资源的软件和被管理的文件和数据结构（如目录和索引表等）的集合。从系统角度来看，文件系统是对文件存储器的存储空间进行组织、分配和回收，负责文件的存储、检索、共享和保护。从用户角度来看，文件系统主要是实现“按名取存”，文件系统的用户只要知道所需文件的文件名，就可存取文件中的信息，而无需知道这些文件究竟存放在什么地方。

文件系统具有以下功能：

1）提供对文件的各种操作，实现按名存取

2）提供合适的访问方式

3）提供目录管理和操作

4）实现文件的共享、保护

5）统一管理文件的存储空间，实现存储空间的分配和回收

6）实现逻辑文件与物理文件间的转换

文件概念

文件是记录在外存上的具有名字的相关信息的集合，具有连续的逻辑地址空间。通常，文件表示程序（源形式和目标形式）和数据（数字、字符、二进制）。

按照用途分类——系统文件（系统软件构成的文件，大多数系统文件只允许用户调用而不允许修改）、库文件（系统提供给用户使用的各种标准子程序库，这类文件允许用户调用，而不允许修改）、用户文件（用户委托文件系统保存的文件，如源程序、原始数据等）。

按照信息保存期限分类——临时文件、永久文件、档案文件。

按照文件保护方式分类——只读文件、读写文件、执行文件。

按照逻辑结构分类——流式文件和记录式文件。

按照物理结构分类——顺序文件（连续文件）、链接文件、索引文件。

按照信息流向分类——输入文件、输出文件、输入/输出文件。

按照文件数据分类——源文件、目标文件、执行文件。

按照文件性质分类——普通文件、目录文件、特殊文件。

文件属性

文件的属性信息保存在磁盘上的目录结构中，以下是基本属性信息。

文件名：唯一的以人们可以理解的方式保存的信息

类型：需要可以支持多种类型的系统

位置：指向文件在设备上的存储位置的指针

大小：当前文件的大小

保护：控制对文件的读取，改写和执行的权限

时间，日期和用户身份：保护和安全需要的数据

文件操作

文件系统包含逻辑存储单元和相关信息的集合。文件控制块（FCB）是由文件相关信息组成的存储结构，它用于描述和控制文件的数据结构，至少包括文件名和存放文件的盘物理地址。文件控制块的有序集合称为文件目录，即一个文件控制块FCB就是一个文件目录项。文件系统具有以下6个基本文件操作。

1）创建文件——建立文件FCB、分配必要的外存空间、在目录中创建文件条目

2）写文件——在目录搜索文件目录项、利用文件指针将信息写入文件。

3）读文件——在目录搜索文件目录项、得到被读文件外存地址、从外存将数据读入内存。

4）重新定位文件——搜索目录以寻找适当条目并将当前文件位置指针重新定位到给定值。

5）删除文件——在目录搜索文件目录项、使之成为空闲目录项、回收文件所占存储空间。

6）截断文件——用户删除文件的内容但是保留文件的属性。

目录结构中的共享——静态共享

打开文件结构中的共享——动态共享

1）系统打开文件表：整个系统一张，存放在内存中，用于保存已打开文件的FCB

2）用户打开文件表：每个进程一张，进程PCB记录了用户打开文件表的位置

3）为文件读写做准备

4）将文件目录项读到内存，获得文件描述符，fd=open（文件路径名，打开方式）

①根据文件名查系统打开文件表，看文件是否已被打开

是→共享计数加1

否→根据文件路径名在目录找到FCB主部，根据打开方式和用户身份检查访问合法性

将外存中的FCB主部等信息填入系统打开文件表空表项，共享计数置为1

②在用户打开文件表中取一空表项，填写打开方式等，并指向系统打开文件表对应表项

5）返回信息：文件描述符，（是一个非负整数，用于以后读写文件）

文件结构

用户和文件系统往往从不同的角度对待同一个文件：

用户——从使用的角度，按信息的使用和处理方式组织文件。

文件系统——从文件的存储和检索的角度，根据用户对文件的存取方式和存储介质的特性组织文件，决定用户文件存放在存储介质上的方式。

文件有逻辑结构和物理结构两种结构：

逻辑结构——用户对文件的组织结构，分为无结构的流式文件和有结构的记录式文件。

物理结构——文件在外存上的存储结构，直接影响存储空间的使用和检索文件信息的速度。

逻辑文件保存到存储介质上的工作由文件系统来做，这样可减轻用户的负担。根据用户对文件的存取方式和存储介质的特性，文件在存储介质上可以有多种组织形式。用户按逻辑结构使用文件，文件系统按物理结构管理文件。因此当用户请求读写文件时，文件系统必须实现文件的逻辑结构与物理结构之间的转换。

顺序文件：所有记录按键值的约定次序组织，记录可以是定长的也可以是变长的。顺序文件常用于批量记录读取，对于访问某个记录的请求则处理性能不佳。对于定长记录文件，若要查找第i个记录，可根据下式得到相对于第一个记录首址的地址：Ai=i*d（d为记录的长度）。对于非定长记录文件，若要查找第i个记录，则需要有每个记录的长度：Ai=∑di（d为记录的长度）。

索引文件：建立一张索引表，记录每个记录的长度及指向记录的指针，从而便于直接存取。索引文件本身是顺序文件组织，它对主文件中的记录按需要的数据项建索引表，为每个记录设置一个表项。

索引顺序文件：基于键的约定顺序组织。将顺序文件中的所有记录分为若干个组，再为顺序文件建立一张索引表，表中记录每个组的第一个记录，该索引项包含记录的键值和指向该记录的指针。索引顺序文件是顺序文件和索引文件的结合，检索时先根据关键字去检索索引表，找到该记录所在组的首个记录的位置，然后再利用顺序查找法查找主文件，找到所需记录。

索引顺序文件实现结构如下：

访问方法

顺序访问

顺序访问是最简单的访问方法。文件信息按照逻辑顺序依次存取：记录文件中按记录排列的顺序来存取，流式文件中按当前读写指针的变化顺序来存取。

读和写构成文件的大部分操作，读操作能读取文件的下一部分并自动前移文件指针以便跟踪I/O位置；写操作会对文件的结尾附加内容并前移到写后文件的新结尾。存取完一段信息后，读写指针自动加上这段信息的长度，以便指出下次开始存取时的位置，它不但适用于顺序访问设备，也适用于直接访问设备。

直接访问

直接访问是根据记录的编号来直接存取文件中的任意一个记录，而无需存取其前面的记录。

对于固定长度的连续文件，第i个记录的地址为rptr = addr0 + I * L，addr0为首记录地址，L为记录长度；对于索引文件，先随机查找索引表，再根据所查结果取地址。

对于直接访问方法，必须修改文件操作以便包括块号作为参数，如read(n)和write(n)。

目录与磁盘的结构

存储设备

文件存储设备主要有磁带，磁盘，光盘等，存储设备的特性决定于存取方法。文件存储设备常常划分为若干大小相等的物理块，以物理块为单位进行信息的存储、传输和处理。

磁带：可以永久保存大容量数据，是一种顺序存取设备，即前面的物理块被存取访问之后，才能存取访问后面的物理块。但磁带存取速度较慢，主要用于后备存储、存储不常用的信息或用于传递数据的介质。

磁盘：是直接访问设备，三种文件物理结构都可以采用。若文件顺序访问，则采用顺序结构和链接结构都可行，若采用直接访问且文件大小不固定，则应采用索引结构。

存储结构

磁盘一般可分为多个分区，分区可以是“生”的即没有文件系统，也可以是”熟”的即有格式化的文件系统。卷是包含文件系统的分区，每个卷都保存该卷中文件的信息，这些信息保存在设备目录或者卷目录表中，设备目录记录着分区上所有文件的各种信息。

目录概述

文件目录是一个包含所有文件信息的节点的集合，是文件控制块的有序集合，目录结构和文件放在磁盘中，备份放在磁带中。目录拥有名称、类型、地址、当前长度、最大长度、数据最后更新时间、所有者ID等。为了实现对文件目录的管理，将文件目录以文件形式保存在外存，这个文件是目录文件。目录结构关系着文件存取速度和文件的共享性、安全性。

考虑特定目录结构时，不能忘记可对目录执行的操作：

搜索文件——需要能够搜索目录结构以查找特定文件的条目。

创建文件——需要创建新的文件并添加到目录。

删除文件——当不再需要文件时，需要能够从目录中删除它。

遍历目录——需要能够遍历目录内的文件及文件的目录条目的内容。

重命名文件——当文件内容和用途改变时，需要能够改变其名称和在目录结构内的位置。

遍历文件系统——需要能够访问每个目录和目录结构内的每个文件。

单级目录

单级目录是最简单的目录结构，所有文件都包含在同一目录中。然而当文件数量增加或系统存在多个用户时，由于所有文件位于同一目录内，它们必须具有唯一的名称，这是单级目录的重要限制。

两级目录

两级目录能解决一级目录的文件命名冲突，并提高对目录文件的检索速度。目录分为两级：一级称为主文件目录（MFD），给出用户名和用户子目录所在的物理位置；二级称为用户文件目录（UFD），给出该用户所有文件的FCB。两级目录解决了文件的重名问题（使用“用户名|文件名”的格式）并降低了查找时间。

树形目录

两级目录可以视为两级的树，自然的推广就是将目录结构扩展到任意高度的树，这种推广允许用户创建自己的子目录并相应地组织文件。树是最常见的目录结构，有一个根目录，系统内的每个文件都有唯一的路径名。

优点：

1）层次结构清晰，便于管理和保护

2）有利于文件分类

3）解决重名问题

4）提高文件检索速度

缺点：

1）查找一个文件按路径名逐层检查，由于目录文件都放在外存，多次访盘影响速度

无环图目录

树形结构禁止共享文件或目录。无环图即没有循环的图，允许目录共享子目录和文件。同一文件或子目录可出现在多个不同目录中，无环图目录是树形目录的自然扩展。

文件别名实现：

1）基于索引结点——也称为硬链接，是基于改进的多级目录结构，将目录内容分为文件名和索引结点两部分。前者包括文件名和索引结点编号，后者包括文件的其他内容（包括属主和访问权限）。通过多个文件名链接到同一个索引结点，可建立同一个文件的多个彼此平等的别名。别名的数目记录在索引结点的链接计数中，若其减至0，则文件被删除。

2）基于符号链接——特殊类型的文件，其内容是到另一个目录或文件路径的链接。建立符号链接文件，并不影响原文件，实际上它们各是一个文件。可以建立任意的别名关系，甚至原文件是在其他计算机上。

通用图目录

采用无环图目录的重要问题是要确保没有环，若从两级目录开始允许用户创建子目录则产生了树形目录。然而当添加链接时，会破坏树结构，从而形成了通用图结构。

由于存在环，即使不再引用一个目录时，引用计数也可能不为0。这种异常源自目录中可能存在自我引用的缘故，因此需要使用垃圾收集方案，以确定何时最后引用已被删除并重新分配磁盘空间。当然垃圾收集方案开销较高，因此创建新链接时需要尽可能避免环。

目录实现

在多级目录结构中，根目录或子目录中的目录项可能指向文件，也可能指向下一级子目录。由于每个目录项都有相同的形式，因此要在目录项中用一个二进制位区分该目录项所指向的是文件（当二进制位取值为“0”时）还是子目录（当二进制位取值为“1”时）。

目录检索指系统按照用户给出的文件名，根据路径名进行检索（全路径名——从根目录开始，相对路径——从当前目录开始）寻找目录项。

文件寻址指根据FCB中文件物理地址等信息，求出文件的任意记录或字符在存取介质上的地址。

线性列表

实现目录的最简单方法是采用文件名称和数据块指针的线性列表，此方法容易编程但CPU执行费时。目录条目线性列表的真正缺点是查找文件需要线性搜索，导致频繁使用目录信息时访问较慢，影响用户使用体验。

哈希表

哈希表是用于文件目录的另一个数据结构，它根据文件名获得一个值并返回线性列表内的一个元素指针，此方法能大幅减少目录的搜索时间，做出避免碰撞的特定规则后能直截了当地插入和删除。哈希表的真正缺点的固定大小和对其的依赖性。

分配方法

磁盘直接访问的特点在文件实现时提供了灵活性，由于很多文件都是存储在同一个磁盘上，如何为它们分配空间以便有效使用磁盘空间、快速访问文件比较重要。磁盘空间分配的主要方法有连续、链接和索引。通常情况下，一个系统只对同一文件系统类型的所有文件采用一种磁盘空间分配方法。

连续分配

连续分配是最简单的物理文件结构，它将逻辑上连续的文件信息依次存放在外存连续的物理块中，每一个文件占用一个连续的磁盘块的集合。文件连续分配用首块的磁盘地址和连续的块数来定义，若文件有n块长并从位置b开始，则该文件将占有块b，b+1，……，b+n-1。每个文件的目录条目包括起始块的地址和该文件所分配区域的长度。

优点：

1）简单，支持随机存取和顺序存取

2）顺序存取速度快

3）所需的磁盘寻道次数和寻道时间最少

缺点：

1）要求连续的存储空间

2）会产生外碎片

3）不利于文件的动态扩充（要求用户给出文件最大长度）

4）不利于文件的插入和删除

链接分配

链接分配解决了连续分配的所有问题。采用链接分配，每个文件是一个磁盘块的链接列表；磁盘块可以分散在磁盘的任何地方。目录包括文件第一块和最后一块的指针。例如一个有5块的文件可能从块9开始，然后是块16、1、10，最后是块25，每块都有下一块的指针。用户不能使用指针，若每块有512字节，地址指针需要4字节，则用户可以使用508字节。

隐式链接：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。

显式链接：整个磁盘只有一张文件分配表FAT，用以存放各块链接指针。

优点：

1）提高了磁盘空间利用率，不存在外碎片

2）有利于文件插入和删除

3）有利于文件动态扩充

缺点：

1）存取速度慢，不适于随机存取

2）可靠性问题，如指针出错

3）更多的寻道次数和寻道时间

4）指针占用空间

索引分配

链接结构没有外碎片但不能直接存取，文件分配表FAT方式需要占用较大的内存空间，而事实上，打开某个文件只需知道该文件所在的盘块号，因此可以通过将所有指针放在一起形成索引块解决此问题，即索引分配。索引分配的文件信息存放在若干不连续物理块中，系统为每个文件建立索引表并将这些块的块号存放在索引表中，索引表是磁盘块地址数组，其中第i个条目指向文件的第i块。

优点：

1）既能顺序存取又能随机存取

2）满足了文件动态增长/插入/删除的要求

3）能充分利用外存空间

缺点：

1）寻道次数和寻道时间较多

2）索引表本身的系统开销，如内存空间、外存空间、存取时间

索引表组织

链接模式——索引表占了若干个盘块，一个盘块一个索引表，多个索引表链接起来

多级索引——将一个文件的所有索引表（二级索引）地址放在另一个索引表（一级索引）中

两级索引分配方式中，若每个盘块大小为1KB，每个盘块号占4字节，则一个索引块可存放256个盘块号，故两级索引最多可包含64K个（256*256）盘块号，因此所允许文件的最大长度为64MB（64K*1KB）。

存储设备、访问方式和文件物理结构之间的关系：

空闲空间管理

磁盘空间有限，释放的空间可以再利用，因此需要记录和维护磁盘的空闲空间。创建文件时，搜索空闲空间得到所需空间以分配；删除文件时，释放磁盘空间并将其记为空闲空间。

位图/位向量

用一串二进制位反映磁盘空间中分配使用情况, 每个物理块对应一位。如果块是分配的，位为0；如果块是空闲的，位为1。申请物理块时，可以在位图中查找值为1的位，返回对应物理块号；归还物理块时，将对应位图中值为1的位。

优点是查找磁盘的第1个空闲块和n个连续空闲块时相对简单和高效。

空闲块表

将所有空闲块记录在一个表中，即空闲块表，它拥有两项内容：该空闲区的第一个盘块号、该空闲区的空闲盘块总数。

空闲块链表

将所有空闲块用链表链接起来，将指向第一个空闲块的指针保存在磁盘的特殊位置上，同时也将其缓存在内存中。空闲块链表中，第一个块存储下一个空闲块的指针并如此继续下去。空闲块链表能扩展成组链接法，即第一个块存储n个空闲块的地址指针，此方法保证了可以较快速地找到大量空闲块的地址。

效率与性能

效率

磁盘空间的使用效率取决于磁盘分配、目录算法和保存在文件目录项中的数据类型。在设计文件系统时，必须平衡优点和性能代价，例如考虑用于访问数据的指针大小如何影响效率。对于采用32位或64位指针的操作系统，采用32位指针将文件大小限制为2^32即4GB，采用64位指针允许更大的文件但也占有更多空间。

性能

关于磁盘空间的使用性能，可以通过磁盘高速缓存、马上释放和预先读取来优化顺序存取、用内存模拟磁盘（即RAM）等方法提高性能。

磁盘高速缓存指利用内存中的存储空间暂存从磁盘中读出的一系列盘块中的信息。其形式包括专用（在内存中开辟一个大小固定的单独存储空间来作为磁盘高速缓存）和公用（把所有未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘I/O共享）。

磁盘缓存位置包括块缓存（在内存中将文件数据作为块来缓存）和页缓存（将文件数据作为页来缓存）。

优化数据分布包括优化文件物理块的分布和优化索引结点分布，目的都是使每次访问文件时磁头的移动距离减少。

统一缓冲区缓冲指采用页面缓存来缓存进程页面和文件数据，它考虑文件打开和访问的两种方法：采用内存映射、采用标准系统调用read（）和write（）。

下图是缺少统一缓冲区缓存的I/O：

下图是采用统一缓冲区缓存的I/O：

提高I/O性能的方法还包括提前读（用户进程对文件进行顺序访问的情况下，在读当前块的同时提前将下一个盘块读入缓冲区）、延迟写（在缓冲区A中的数据，本应立即写回磁盘，但考虑到该缓冲区中的数据不久后可能还会被访问，因而并不立即将该缓冲区A中的数据写入磁盘，而是将它挂在空闲缓冲区队列的末尾）、虚拟盘（利用内存空间仿真磁盘，即RAM）。

恢复

一致性

重复文件的一致性：为保证文件系统的可用性，有些系统中为关键文件设置了多个重复拷贝，将它们分别存储在不同的地方。在有重复文件时，若一个文件拷贝被修改，则必须同时修改其它几个文件拷贝以保证该文件中数据的一致性。

盘块号一致性检查：用于描述盘块使用情况的数据结构有空闲盘块表、位示图、文件分配表FAT等。在每次启动机器时应检查这几个数据结构，它们是否保持了数据的一致性。

链接数一致性检查：一个共享文件的索引结点号会在目录中出现多次。在共享文件的索引结点中有一个链接计数count，用来指出共享文件的用户进程数。共享某文件的索引结点号在目录中出现的次数与该索引结点中的链接计数count应该一致。例如当5个用户进程共享某文件时，该文件的索引结点号将会在目录中出现5次。