OS-文件

文件基本概念

需求：能够长期保存，进程终止后数据依然存在；能够存储大量数据，突破地址空间限制；可以共享数据。为了解决这些需求，我们提出了“文件”概念，用文件作为数据的存储和访问单位。

文件的定义

课程组对于文件的定义为“带标识的、在逻辑上有完整意义的信息项的序列”。文件提供了一种抽象机制，能够让用户将信息保存在磁盘等存储设备上，以便之后进行访问，而同时用户又不需要关心具体的实现细节。

将定义拆分，“信息项序列”即为文件所记录的数据，除了数据，文件还包括有“标识”，即文件相关的信息，如所有者、创建时间等文件属性。

这里有必要提出另一种定义方式：自底向上的定义方式。这样的定义能够让我们更好的了解文件的结构。

• 数据项：是文件中最低级的数据组织形式，可分为基本数据项和组合数据项
• 记录：是一组相关的数据项的集合，用于描述一个对象在某方面的属性
• 文件：指由创建者定义的，具有文件名的一组相关元素的集合。可分为有结构文件和无结构文件，其中有结构文件由若干个相似的记录组成，无结构文件就是一个字符串流。

我们可以这样理解这一定义：对于一个学生成绩管理系统来说，其中的基本数据项就是学生的学号、姓名等某一对象的基本属性，组合数据项可能是由多个成绩相加而来的总分；记录作为一个中层结果，可能是一个类似json格式的结构体，存储了一个学生的完整个人信息，有结构文件可能是类似csv文件那样的由多条结构相同的记录组成、由逗号进行分隔的顶层结构。

文件系统

从用户角度来说，希望文件系统提供定义文件及其属性、操作文件、组织文件的目录结构等接口；从操作系统角度来讲，文件系统需要包含创建文件的算法、管理文件的数据结构，以便映射逻辑文件系统到物理外设。

文件控制块 FCB

为了便于管理文件，我们引入了文件控制块的数据结构

文件控制块是用来存放控制文件所需要的各种信息的数据结构，以实现按名存取，即一个FCB管理一个文件。一个FCB集合被称为文件目录，那么一个FCB自然就是一个文件目录项。

FCB存储了以下信息：

• 基本信息：文件名、物理位置、文件逻辑结构（记录文件、流式文件）、文件物理结构
• 访问控制信息：文件所有者（属主）、访问权限
• 使用信息：创建时间、上次修改时间等

文件目录

目录功能

我们对目录管理提出几点基本要求：

• 目录需要提供“文件 - 文件名”的映射关系，即实现“按名存取”（FCB已经做到了）
• 目录的存取效率直接影响到系统的性能，因此要提高对目录的检索速度
• 应给用户提供命名功能；允许重名，即对不同的用户文件可使用相同的名字；允许别名，即对同一个文件允许不同的多个名字
• 分组：能够把不同文件按照某种属性进行分组

目录结构

1. 单级目录结构

在整个文件系统中，只建立一张目录表，每个文件占用一个目录项。由于“按名存取”的性质，单级目录结构显然是无法做到“重名”的。查找文件时需要遍历整个目录，因此效率也是比较低的。

2. 两级目录结构

将文件目录分为主文件目录和用户文件目录两级。主文件目录记录用户名以及相应的用户文件目录所在位置，用户文件目录记录用户所有文件的FCB。

两级目录结构提高了检索的速度，解决了多用户之间的文件重命名问题。但是依然没有解决分类问题

3. 多级目录（树形目录结构）

树形结构目录其实就是我们最熟悉的目录结构

在树形结构目录中访问文件时，由多种指定访问文件的方式：

• 绝对路径名：从根目录开始依次经由各级目录名，再最终加上文件名。一个文件的绝对路径是唯一的
• 相对路径：结合当前路径进行使用

树形目录由于其结构层次清晰，能够方便的对文件进行分类管理；不同目录下的文件允许重名；可为每类文件建立一个子目录，每次查找目录时只在该子目录下进行查找，所以搜索速度要快于一级和二级目录。但目录级别过多时会增加路径检索时间

目录实现

根据目录项存储的内容，我们可以将目录的实现分为两类：

• 直接法：目录项存储文件名+FCB
• 间接法：目录项存储文件名+FCB地址（索引号）

无论哪种方法，给定一个文件名都能够返回响应的FCB。那么如何在目录中查找文件名呢？我们有顺序查询法和Hash方法。

文件结构

文件逻辑结构指的是从用户角度出发看到的文件的组织形式，指在文件内部，数据在逻辑上是如何组织起来的。文件物理结构又称存储结构，是指文件存储在外存上的储存组织形式。

由于课程组的ppt对于文件逻辑结构一笔带过了，因此我们这里仅着重记录文件物理结构

文件物理结构

按逻辑结构可将文件分为两种：无结构文件，是由字符流构成的文件，所以又称流式文件；有结构文件，是指由一个以上的记录构成的文件。我们主要讨论有结构文件。

有结构文件按记录的组织形式可分为顺序文件、索引文件。

有结构文件的存取基本单位是记录

1. 顺序文件

顾名思义就是文件中的所有记录按照顺序的方式进行排列，按排列方式又可以分成两种：顺序结构， 记录按关键字顺序排列，检索时可采用折半查找的方式，查找效率是较高的，同时显然的，连续存取时效率较高，但文件长度固定后就不易改变了，不易于文件动态的增删；串结构，通常按照存储的时间先后顺序进行排列，同时采用链表的数据结构进行存储，将文件的不同记录存储在不同物理块，因此检索时必须从头依次检索。这样的好处是不需要连续存储内容，使得空间利用率较高，同时也支持文件的动态增删，顺序访问的效率也是较高的，但如果要访问文件最后的内容，实际上需要遍历整个文件，同时随机访问的效率也是较低的。

2. 索引结构（重点）

一个文件的内容存储在若干个不连续的物理块中，这和一个进程存储在不连续页中的存储方式是非常相似的，那么我们可以仿照页表为一个文件建立一个索引表，其中第i项表项的内容就是该记录对应的物理块号

索引表也需要占据空间，那么它到底存储在哪里呢？首先课程组的ppt告诉我们它肯定不存在FCB中，FCB只有索引表的地址。事实上，索引表的存储方式也有许多种，例如FAT32采用文件头部内联，Unix文件系统采用块间分散索引，还有数据库采用的独立物理文件方式。但总的来说，索引文件在存储区中占据了两个区：索引区和数据区，索引区用来存放索引表，数据区存放数据本身。

由于索引表的存在，访问文件内容需要经过两步：由逻辑块号查的物理块号，访问物理块获得数据。

索引文件能够顺序存储、随机存储，且能够动态增删文件，还能充分利用外存空间，但是索引表本身带来了额外的内存空间开销以及存取时间开销。

索引分配方式可以是单级索引，即一个文件一个索引表，但当文件很大时，索引块会变多，索引表就会变的很大，这时应该为这些索引块再建立一个索引表，就形成了二级索引分配方式。如果要访问两级间接索引的文件内容，需要访问4次磁盘：将inode读入内存、访问一级索引块、访问二级索引块、访问数据块得到内容。如此看来，和多级页表一样，如果没有缓存技术，通过多级索引访问数据的速度将会大大下降。

另外，根据inode的结构，我们可以计算出一个inode能够管理多大的文件。对于每个直接索引，其管理的数据大小就为数据块大小，对于间接索引，我们需要计算每个数据块能够存储多少个数据块地址 （因为每个间接索引块一定存满了数据块地址），那么 级索引块管理的数据大小为

磁盘访问次数

我们可以通过一个具体的例子来理解一个文件系统是如何进行磁访存的。对于一个采用索引结构的文件系统，如果其要访问/usr/owpeter/readme.md这个文件，要经过以下过程：

• 访问/root目录的数据块，获得目标目录的索引结点号
• 访问/usr目录的索引结点，获得数据块的地址
• 访问/usr目录的数据块，获得目标目录索引结点号
• 访问/usr/owpeter目录的索结点，获得数据块地址
• 访问/usr/owpeter目录的数据块，获得目标文件的索引结点号
• 访问/usr/owpeter/readme.md文件的索引块，获得目标数据块的地址
• 访问文件中的目标数据块

外存空间管理

文件系统布局

我们可以将一个磁盘划分为多个分区，每个分区中有一个文件系统。下图是一个可能的文件系统布局：

其中，MBR存储在磁盘的0号扇区，其存储了最基础的引导程序（Boot Loader），作用是引导计算机启动，MBR后面的是分区表，给出每个分区的起始地址。

引导块位于每个分区的开头，其主要作用为“加载操作系统内核”，即使它不含有一个可启动的操作系统，也不排除以后会在该分区安装一个操作系统。

超级快通常位于文件系统的开头，它包含了文件系统的元数据，包括分区总块数、空闲块数、块大小、Inode数量和位置等

磁盘空间管理方法

1. 空闲表法

空闲表法是连续分配方式，看其表头就能明白了：序号、第一个空闲盘块号、空闲盘块数量，那么显然，它能够分配的空闲块都是连续的。该方法对于空闲盘区的分配算法与内存的动态分配类似，也可采用首次适应、最佳适应等算法。

2. 空闲链表法

将磁盘上所有空闲空间以盘块为单位用链表串在一起。在分配时从表头开始依次摘下适当数量的盘块分配给用户，用户释放的盘块将依次插入队尾。该方法的有点是分配和回收操作都较为简单，缺点是为一个文件分配空闲块时可能需要多次操作，效率较低。

3. 位示图法

磁盘上所有盘块都与一个二进制位相对应，已分配的物理块记为1，未分配的物理块记为0。优点是易于查找一个或一组相邻的空闲盘块，缺点是当磁盘较大时，位示图本身所占的空间也较大

4. 成组链接法

如果以盘块为单位组成链表，当磁盘空间较大时，这个链表会非常长。成组链表法为了解决这个问题，将空闲的盘块分为若干组，并在每组的第一个盘块中存储下一组的空闲盘块数量与首个空闲盘块的块号，这样每组的第一个盘块就可以连成一条链。

将第一组的空闲盘块总数和空闲盘块号存储在一个专用的空闲盘块号栈中。在需要分配时，根据空闲盘块号栈的指针，将指针所指的块分配给用户，同时移动指针。如果指针指向的是当前栈的栈底（第一个盘块），由于其中存储的是下一个盘块组的信息，因此需要将该组盘块内容读入栈中，然后再将原栈底内容分配出去。

这种方法的优点在于：空白块号的登记不占用额外空间，同时采用了后进先出的栈结构进行管理。

文件系统实例

FAT

其核心思想是通过一个文件分配表来管理文件，一般来说，一个FAT系统中包含两个文件分配表，它们互为备份。我们所说的FAT16、FAT32中的数字指的是文件分配表中表项的大小，也是簇（块）大小，数字是多少，就代表该文件系统中，一个块是由多少个扇区组成的

FAT表：

FAT表项所占位数是其簇编号的位数。其值有：0（该表项对应的块空闲），0xff7（该表项对应的块损坏），0xff8-0xfff（文件对应的最后一个块），其他值（表示该表项对应的簇被占用了，且表项中的值是下一个簇的编号）。