操作系统——文件管理

 (仅作个人学习使用)

1.   概述

1.1          文件和文件系统

从用户的角度，文件系统是操作系统的一个重要部分，它提供了与二级存储相关的资源抽象。文件系统特性集合主要有：

• 长期存在：用户注销不会消失；
• 进程间共享：具有相关的可控制共享权限；
• 结构：对应特定应用的文件结构，并可反映文件关系。

 

文件系统提供一系列功能接口，典型操作有：创建、删除、打开、关闭、读和写。

1.2          文件结构

域是基本数据单元，一个域包含一个值。

 

记录是一组相关域的集合，可以看作是应用程序的一个单元。

 

文件是一组相似记录的集合，被用户看作是一个实体，并通过名字访问。

1.3          文件系统管理

文件管理系统是一组系统软件，为使用文件的用户和应用程序提供服务。

1.3.1              文件系统架构

不同的系统有不同的组织方式，但下图中的结果很具有代表性。

 

 

 

最底层，设备驱动程序直接与外围设备通信。设备驱动程序负责启动该设备上的I/O操作，处理I/O请求的完成。

 

接下来的是基本文件系统或物理I/O层，这是与计算机系统外部环境的基本接口，处理在磁盘间或磁带系统间交换的数据块，它关注的是这些块在二级存储和内存缓冲区中的位置，通常是操作系统中的一部分。

 

基本I/O管理程序负责所有文件I/O的初始化与终止，这一层需要一定的控制结构来维护设备的输入/输出，调度和文件状态，也是操作系统的一部分。

 

逻辑I/O使得用户和应用程序能够访问到记录。基本文件系统处理的是数据块，而逻辑I/O模块处理的是文件记录，提供了一种通用记录I/O的能力，维护文件的基本数据。

1.3.2              文件管理功能

 

用户和应用程序通过使用创建文件、删除文件以及执行文件操作的命令，与文件系统进行交互。在执行任何操作之前，文件系统必须确认和定位所选择的文件。

 

虽然用户和应用程序关注的是记录，但I/O是以块为基础来完成的。因此，文件中的记录必须组织成一组块的序列来输出，在输入后将各块组合起来。

 

文件管理系统是一个单独的系统实用程序，和操作系统关注的大不相同。

2.   文件组织和访问

组织指文件中记录的逻辑结构，由用户访问记录的方式确定。文件在二级存储中的物理组织取决于分块策略和文件分配策略。在选择文件组织时，有五项基本原则：访问快速、易于修改、节约存储空间，维护简单、可靠性。

 

大多数实际使用的系统都属于如下五种组织：堆，顺序文件，索引顺序文件，索引文件，直接或散列文件。

2.1          堆

 

 

堆是最简单的文件组织形式。数据按照它们到达的顺序被采集，每个记录由一串数据组成，堆的目录仅仅是积累大量的数据并保存数据。

 

堆文件没有结构，对记录的访问是通过穷举查找的方式。

 

当数据在处理前采集并存储时，或者数据难以组织时会用到堆文件。当保存的数据大小和结构不同时，这类的文件空间使用情况很好，能很好地用于穷举查找，且易于修改。但是除开这些限制，对大多数应用都是不适用的。

2.2          顺序文件

 

 

顺序文件是最常用的文件组织形式，每个记录都使用一种固定的格式。所有记录都具有相同的长度，并由相同数目、长度固定的域按特定的顺序组成。

 

一个特殊的域被称为关键域，通常是每个记录的第一个域，唯一地标识这个记录，记录按照关键域顺序来存储。

 

顺序文件通常用于批处理应用中，并且如果这类应用涉及对所有记录的处理，顺序文件通常是最佳的，顺序文件是唯一可以很容易地存储在磁盘和磁带的文件组织。

 

对于查询或更新记录的交互式应用，顺序文件表现出很差的性能。

2.3          索引顺序文件

 

 

克服顺序文件的缺点的一种常用方法是索引顺序文件。索引顺序文件保留了顺序文件的关键特征：记录按照关键域的顺序组织起来。而且还增加了两个特征：用于支持随机访问的文件索引和溢出文件。索引提供了快速接近目标记录的查找能力；溢出文件类似于顺序文件中使用的日志文件，但溢出文件可以根据前面记录的指针进行定位。

 

索引文件中的每个记录由两个域组成：关键域和指向主文件的指针。为查找一个特定域，首先查找索引，查找关键字值等于目标关键域值或者位于目标关键域值之前最大的索引，然后在该索引的指针所指的主文件的位置处开始查找。

 

文件可以按照以下方式处理：主文件中的每个记录包含一个附加域（对应用程序不可见），指向溢出文件的一个指针。当向文件中插入一个新记录时，被添加到溢出文件，然后修改主文件中逻辑顺序位于这个新记录之前的记录，使其包含指向溢出文件中新记录的指针。

 

索引顺序文件极大地减少了访问单个记录的时间，同时保留了文件的顺序特性。为顺序处理整个文件，需要顺序处理主文件的记录，直到遇到一个指向溢出文件的指针，继续访问溢出文件的记录，直到遇到一个空指针，然后恢复在主文件中的访问。

2.4          索引文件

 

 

索引顺序文件保留了顺序文件的一个限制：基于文件的一个域进行处理。当需要基于其他属性而不是关键域查找一个记录时，这两种形式的顺序文件都是不能够胜任的。

 

为实现这一点，需要一种采用多索引的结构，每种可能成为查找条件的域都有一个索引。索引文件一般摒弃了顺序性和关键字的概念，只能通过索引来访问记录。对记录的放置位置不再有限制。

 

索引文件大多用于对信息的及时性要求比较严格并且很少会对所有数据进行处理的应用程序中。

2.5          直接文件或散列文件

直接文件或散列文件开发直接访问磁盘中任何一个地址已知的块的能力。和顺序文件以及索引顺序文件一样，每一条记录都需要一个关键域，使用基于关键字的散列。

 

直接文件常在要求快速访问时使用，并且记录的长度是固定的，通常一次只访问一条记录。

3.   文件目录

3.1          内容

与任何文件管理系统或和文件集合相关联的是文件目录，目录包含关于文件的信息，包括属性，位置和所有权，大部分都是由操作系统管理的。目录自身也是一个文件，可以被各种文件管理例程访问。

3.2          结构

最简单的目录结构形式是一个目录项列表，每个文件一个目录项。这种结构用来表示最简单的顺序文件，文件名作为关键字。但多个用户共享一个系统或单个用户使用多个文件时就远远不够了。

 

考虑可能在目录上执行的操作类型：查找、创建、删除文件，显示、修改目录。简单列表难以支持这些操作。

 

 

 

两级方案：每个用户都有一个目录，还有一个主目录。主目录有多个用户目录的目录项，并提供地址和访问控制信息。功能更强大，更灵活的方法是层次或树状结构方法，也是普遍采用的一种方法。有一个主目录，下面是许多用户目录，每个用户目录又依次存在目录项和文件项，并且任何一级都是这样。

3.3          命名

用户通过符号名字来引用文件。为了保证文件引用无二义性，系统中每个文件都必须具有唯一的名字。对用户而言，要求为文件提供唯一的名字是一个难以接受的负担，特别是在共享系统中。

 

使用树状结构目录减小了提供唯一名字这方面的困难。系统中任何文件可以找到从根目录到主目录向下到各个分支，直到该文件的路径用来定位，组成该文件的路径名。

4.   文件共享

在多用户系统中，几乎总是要求允许文件在多个用户之间共享。这产生了两个问题：访问权限和对同时访问的管理。

 

4.1          访问权限

文件系统应该提供一些选项，使得访问某个特定文件的方式可以被控制。下面是一些可以给某个特定用户以访问某个特定文件的具有代表性的访问权限：无，知道（存在），执行，读，追加，更新，改写保护，删除。这些权限包含了一些层次，每项权限都隐含着它前面的那些权限。

4.2          同时访问

如果允许多个用户追加或更新同一个文件，操作系统或文件管理系统必须强加一些规范。一种蛮力的方法是当用户修改文件时，允许用户对整个文件加锁。比较好的控制粒度是在修改时对单个记录加锁。

5.   记录组块

记录是访问结构化文件的逻辑单元，而块是与二级存储进行I/O操作的基本单位。为了执行I/O，记录必须组织成块。

 

大多数系统中，块是固定长度的，这可以简化I/O、内存中缓冲区的分配和二级存储中的块的组织。块越大，一次I/O操作所传送的记录就越多，如果是顺序地处理或查找文件，这显然是个优点；但如果随机访问文件，太大的块会导致对并没有使用的记录不必要的传输。综合考虑顺序访问的频率和访问的局部性潜能，大块能减少I/O传送时间，大的块需要更大的I/O缓冲区，从而使得缓冲区的管理更加困难。

 

 

 

对于给定的块大小，有三种组块方法：

固定组块：使用固定长度的记录，若干个完整的记录被保存在一个块中，每个块中可能存在内部碎片。

可变长度跨越式组块：使用长度可变的记录，并紧缩在块中，某些记录可能会跨越两个块，使得块中没有未使用空间。

可变长度非跨越式组块：使用可变长度的记录，但并不采用跨越的方式。大多数块中都会有未使用的空间。

 

固定组块是记录长度固定的顺序文件最常用的方式；可变长度跨越式组块的存储效率高，并且对文件大小没有限制，但难于实现，跨越两个块的记录需要两次I/O操作，使得文件难以修改；可变长度非跨越式组块会导致空间的浪费，并限制记录不能超过块的大小。

6.   二级存储管理

二级存储中，一个文件是由多个块组成的。操作系统或文件管理系统负责给文件分配块。

 

6.1          文件分配

文件分配表（File Allocation Table, FAT）

预分配与动态分配

预分配策略要求在发出创建文件的请求时，声明该文件的最大大小。但对于很多应用程序不能可靠地估计文件可能的最大文件大小，很难使用这种策略，用户和应用程序都会多估计一些文件的大小以避免分配的空间不够用，这显然是十分浪费的。因此，采用动态分配要好一些，动态分配只有在需要时才给文件分配空间。

 

分区大小

在选择一个分区大小时，需要折中考虑单个文件的效率和整个系统的效率。

1）  邻近空间可提高性能；

2）  数目较多的小分区会增加用于管理分配信息的表大小；

3）  使用固定分区可简化空间的再分配；

4）  使用可变大小的分区或固定大小的小分区可减少由于超额分配而未使用存储空间的浪费。

 

这几项内容相互影响，必须统一考虑，结果有两种选择：

可变的、大规模连续分区：可提供较好的性能。大小可变避免了浪费，并使得文件分配表比较小，但导致空间很难再次利用；

块：小的固定分区提供了更大的灵活性，但为了分配，可能需要较大的表或更复杂的结构。

 

每种选择都适用于预分配和动态分配。对于可变的、大规模连续分区，一个文件被预分配给一组连续的块，消除了对文件分配表的需求，仅仅需要指向第一块的指针和分配的块数目。

文件的分配方法

通常使用三种方法：连续、链接和索引。

 

 

 

连续分配是指在创建文件时，给文件分配一组连续的块，这是一种使用大小可变分区的预分配策略。每个文件只需要一个表项，用于说明起始块和文件的长度。从单个顺序文件的角度看，连续分配是最好的，可同时读入多个块来提高I/O的性能；连续分配也存在一些问题，会出现外部碎片，时常需要紧缩算法来释放磁盘中额外空间，因为是预分配，需要在创建文件时声明文件大小。

 

链接分配基于单独的块，每一块中包含指向下一块的指针。文件分配表中的每个文件同样只需要一个表项用于声明起始块和文件的长度。尽管可以是预分配，但更常用的是根据需要来分配块，任何一个空闲块都可以加入到链中，不会产生外部碎片。最适合顺序处理的顺序文件；后果就是局部性原理不再适用，如果需要顺序处理一次取入一个文件中的多个块，需要一连串地访问磁盘中的不同部分，为克服这个问题系统需要周期性地进行文件合并。

 

索引分配解决了连续分配和链接分配的许多问题。每个文件在文件分配表中有一个一级索引，文件索引并不是作为文件分配表的一部分存储的，文件的索引保存在一个单独的块中，文件分配表中该文件的表项指向这一块。分配可以基于固定大小的块，也可以基于可变大小的分区。基于块来分配可以避免外部碎片，而按大小可变的分区可以提高局部性。任何一种情况下都需要不时地对文件进行整理，使用大小可变的分区情况下，文件整理可减少索引的数目，但对于基于块的分配却不能。索引分配支持顺序访问文件和直接访问文件，是最普遍的一种文件分配形式。

6.2          空闲空间的管理

正如分配给文件的空间需要管理，当前未分配给任何文件的空间也必须管理起来，必须在文件分配之前首先知道磁盘中的哪些块是可用的。除了文件分配表之外，还需要一个磁盘分配表（Disk Allocation Table）。

6.2.1              位表

使用一个向量，向量中每一位对应磁盘中的每一块。0表示空闲块，1表示已使用块。0101001100……

 

位表的优点是通过它可以相对容易地找到一个或一组连续的空闲块，而且比较小。一个位块图需要的存储器容量为：

磁盘大小（字节数） /  （8×文件系统块大小）

 

位表需要驻留在内存中，穷举地查找这个表会使文件系统的性能降低到难以接受的程度，当磁盘空间剩下很少的空闲块时这个问题尤其严重。因此，大多数使用位表的文件系统都有一个辅助数据结构用于汇总表的子区域内容。

 

6.2.2              链接空闲区

通过使用指向每个空闲区的指针和它们的长度值，空闲区可以被链接到一起。如果一次只分配一块，只要简单地选择链头上的空闲块，调整指针或长度值即可。

 

这个方法具有其自身的问题。在使用一段时间之后，磁盘会出现很多碎片，许多空闲区都变成了只有一个块那么长，导致分配和删除块都会比较耗时。

6.2.3              索引

索引方法将空闲空间看作是一个文件，并使用一个在文件分配时介绍过的索引表。基于效率的考虑，索引应该基于可变大小的分区而不是块。

6.2.4              空闲块列表

每个块指定一个顺序号，所有空闲块的顺序号保存在磁盘中的一个保留区中。空闲块列表的大小比较大，因此只能保存在磁盘上而不是内存中，这是一种非常令人满意的方法，考虑到下面几点：

1）  磁盘上用于空闲块列表的空间小于磁盘空间的1%；

2）  尽管空闲块列表过大不能保存在内存中，但可以采取下推栈或队列的方式保存在内存部分数据以提高效率。

6.3          卷

不同的操作系统和不同的文件系统使用的卷的概念会有所不同，但本质上讲卷是一个逻辑磁盘。一个单独的磁盘可能是一个卷，通常一个磁盘会被划分成几个分区，每个分区都会作为一个单独的卷来工作。

 

6.4          可靠性

当系统为了提高效率而在内存中保留磁盘分配表和文件分配表的副本时会产生一些问题，为避免这些问题，当请求一个文件分配时，需要执行以下步骤：

1)         磁盘中对磁盘分配表加锁，防止在分配完成以前另一个用户修改表；

2)         查找磁盘分配表得到可用空间。

3)         分配空间，更新磁盘分配表，更新磁盘。

4)         更新文件分配表和磁盘。

5)         对磁盘分配表解锁。

 

这种技术可防止错误。但当频繁分配比较小的块时，会对性能产生重要影响。为减少这种开销，可使用一种批存储分配方案。为了分配，可以先获得磁盘上的一批空闲块，其相应部分被标记为已用。使用这一批的块分配在内存中进行，这一批用完后再更新磁盘分配表并获得新的一批，如果发生了系统崩溃，磁盘中被标记为已用的部分在它们被重新分配之前，必须通过某种方式清空。

6.5          文件系统安全

经常在文件或数据库管理系统中运用的访问控制模型叫做访问矩阵，这个模型的基本元素如下：

主体：有能力访问对象的实体，比如用户，角色等。

对象：可以被访问和控制的任何实体，比如文件或其局部数据，程序内存块等。

访问权限：主体访问对象的方式，比如读，写，执行等。

 

访问矩阵通常是稀疏的。矩阵可以按照列来划分，就生成了访问控制列表，对于每个对象列出了用户以及他们的访问权限；按照行来进行划分的话就生成了权能入场券，指定了用户被授权的对象和操作。