操作系统-第四章-文件管理

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 7.5k 阅读时长 ≈ 7 分钟

需要重点对概念的理解，重点掌握文件系统的结构及其实现，文件分配和空闲空间管理等。要掌握文件系统的文件控制块，物理分配方法，索引结构，树形结构， 树形目录结构，文件共享原理，文件系统的布局，虚拟文件系统原理等。

4.1 文件系统基础

4.1.1 基本概念

文件是以硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档，图片，程序等。

在系统运行时，计算机以进程为基本单位进行资源的调度和分配；在用户进行输入，输出时，则以文件为基本单位

文件的结构：

  1. 数据项。是文件系统中最低级的数据组织形式。可以分为
    • 基本数据项。用于描述一个对象的某种属性的一个值，是数据中的最小逻辑单位
    • 组合数据项。有多个基本数据项组成
  2. 记录。是一组相关的数据项的集合，用于描述一个对象在某方面的属性
  3. 文件。是指由创建者所定义的，具有文件名的一组相关元素的集合，可以分为有结构文件和无结构文件两种。

有结构文件：文件由若干个相似的记录组成

无结构文件则被视为一个字节流，比如一个二进制文件或字符文件

4.1.2 文件控制块和索引结点

与进程管理一样，为便于文件管理，在操作系统中引入了文件控制块的数据结构。

1. 文件的属性

除了文件数据，操作系统还会保存与文件相关的信息，如所有者，创建时间等，这些附加信息称为文件属性或文件元数据。文件属性在不同系统中差别很大，但通常都包括如下属性

  1. 名称。文件名称唯一，以容易读取但形式保存
  2. 类型。被支持不同类型的文件系统所使用
  3. 创建者。文件创建者的ID
  4. 所有者。文件当前所有者的ID
  5. 位置。指向设备和设备上文件的指针
  6. 大小。文件当前大小（用字节，字或块表示），也包含文件所允许的最大值
  7. 保护。对文件进行保护的访问控制信息
  8. 创建时间，最后一次修改时间和最后一次存取时间。文件创建，上次修改和上次访问的相关信息，用于保护和跟踪文件的使用

操作系统通过文件控制块（FCB）来维护文件元数据

2. 文件控制块(!!!)

文件控制块（FCB）是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。

FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。

目录文件永远不会为空，它至少包含两个目录项：

  • 当前目录项“.”和父目录项".."

为了创建一个新文件，系统将分配一个FCB并存放在文件目录中，称为目录项。

一个典型的FCB

文件时间
文件权限（创建，访问，写）
文件所有者，组，ACL
文件大小
文件数据块

FCB主要包含以下信息：

  • 基本信息，如文件名，文件的物理位置，文件的逻辑结构，文件的物理结构等
  • 存取控制信息，如文件存取权限等
  • 使用信息，如文件建立时间，修改时间等

3. 索引结点

UNIX系统采用了文件名和文件描述信息分开的方法，使文件描述信息单独形成一个称为索引结点的数据结构，简称i结点（inode），在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。

在UNIX操作系统中，所有设备都被视为特殊文件，因为UNIX操作系统控制和访问外部设备的方式和访问一个文件的方式是一样的。

4.1.3 文件的操作

1. 文件的基本操作

文件属于抽象数据类型！！！

2. 文件的打开与关闭

许多系统要求在首次使用文件时，使用系统调用open

打开文件操作是将该文件的FCB存入内存的活跃文件目录表。

4.1.4 文件保护

系统级管理包括注册和登陆。

为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取。

文件保护方式：

  • 口令保护
  • 加密保护
  • 访问控制

口令和加密是为了防止用户文件被他人存取或窃取

访问控制则用于控制用户对文件的访问方式

4.1.5 文件的逻辑结构

从用户观点出发看到的文件的组织形式

文件的逻辑结构与存储介质特性无关，它实际上是指在文件的内部，数据逻辑上是如何组织起来的。

按逻辑结构，文件可分为无结构文件和有结构文件两大类

1. 无结构文件（流式文件）

最简单的文件组织形式。以字节为单位。

对记录的访问只能通过穷举搜索的方式。所以，那些对基本信息单位操作不多的文件较适合采用字节流的无结构方式，如源程序文件，目标代码文件等。

2. 有结构文件（记录式文件）

  1. 顺序文件
  2. 索引文件
  3. 索引顺序文件
  4. 直接文件或散列文件

索引文件和索引顺序文件都提高了存取的速度，但因为配置索引表而增加了存储空间

散列文件有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值相同

4.1.6 文件的物理结构

文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。

常用的磁盘空间分配方法有三种：

  1. 连续分配
  2. 链接分配
  3. 索引分配

1. 连续分配

连续分配要求每个文件在磁盘上占有一组连续的块，其文件的FCB包含第一块的磁盘地址和连续块的数量。

  1. 支持顺序访问和直接访问
  2. 实现简单，访问文件时需要的寻道数和寻道时间最小，存取速度快
  3. 文件长度不宜动态增加
  4. 反复增删文件后会产生外部碎片，只适用于长度固定的文件

第3点是因为一个文件末尾的盘块可能已分配给其他文件，一旦需要增加，就需要大量移动盘块

2. 链接分配

链接分配是一种采用离散分配的方式。

隐式链接

目录项中含有文件第一块的指针和最后一块的指针。每个文件对应一个磁盘块的链表；

除了最后一个盘块外，每个盘块都有指向文件下一个盘块的指针，这些指针对用户是透明的。

  1. 只能顺序访问文件
  2. 消除了外部碎片，显著提高了外存空间（磁盘）的利用率
  3. 可动态地按需分配盘块，无须事先知道文件的大小
  4. 对文件的增，删，改很方便
  5. 稳定性存在问题，一旦断链将导致文件数据的丢失

解决方法： 将几个盘块组成簇，按簇而不按块来分配，可以成倍地减少查找时间，这样指针所占的磁盘空间比例也要小得多，这种方法的代价是增加了内部碎片。

显式链接

显式链接是指把用于链接文件各物理块的指针，显示地存放在内存的一张链接表中。该表在整个磁盘中仅设置一张，称为文件分配表FAT，在每个表项中存放链接指针，即下一个盘块号。

文件的第一个盘块号记录在目录项“物理地址”字段中，后序的盘块可通过FAT找到。

例如，某磁盘共有100个磁盘块，存放了两个文件：

文件“aaa”占三个盘块，依次是2->8->5;

文件“bbb”占两个盘块，依次是7->1

其余盘块都是空闲盘块，则该磁盘的FAT如图：

FAT表在系统启动时就会被读入内存，因此查找记录的过程是在内存中进行的，因此不仅显著地提高了检索速度，而且明显减少了访问磁盘的次数。

3. 索引分配

链接分配解决了连续分配的外部碎片和文件大小管理问题。但依然存在问题；

  1. 链接分配不能有效支持直接访问（FAT除外）
  2. FAT需要占用较大的内存空间

事实上，在打开某个文件时，只需要将该文件对应的盘块的编号调入内存即可，完全没必要将整个FAT调入内存。 为此，索引分配将每个文件所有的盘块号都集中放在一起构成索引块（表）

每个文件都有索引块，这是一个磁盘块地址的数组，索引块的第i个条目指向文件的第i个块。目录条目包括索引块的地址

  1. 索引分配支持直接访问，且没有外部碎片
  2. 增加了系统分配存储空间的开销

每个文件必须有一个索引块，因此索引块应尽可能小，但索引块太小就无法支持大文件。所以需要采用以下机制来处理问题：

  • 链接方案。一个索引块通常为一个磁盘块，因此它本身可以直接读写，为了支持大文件，可以将多个索引块链接起来
  • 多层索引。
  • 混合索引。

单级索引分配方式或多级索引分配方式为高频考点！！！！！

4. 混合索引分配

为了能够较全面地照顾到小型，中型，大型和特大型文件，可采用混合索引分配方式。

即把所有地址分为两类，直接地址和间接地址

直接地址

每项中所存在所存放的是该文件数据所在盘块的盘块号

一次间接地址

每项一次间接地址指向一个一次间址块（索引块），一次间址块中存放着文件的多个盘块号

二次间接地址

每项二次间接地址指向一个二次间址块，二次间址块中记入所有一次间址块的盘号。

在采用混合索引分配方式时，假如有\(N_0\)个直接地址项，\(N_1\)个一次间接地址项，\(N_2\)个二次间接地址项，每个盘块的大小为M字节，盘块号占m个字节。其所允许的文件最大长度为（字节）

\[ \left(N_0 + N_1 * \frac{M}{m} + \left(\frac{M}{m}\right)^2 \right) * M \]

小结

  • read系统调用

read只需要open返回的文件描述符，不需要包括文件的名称

  • 创建的文件数量的上限 = 索引结点数量的上限

4.2 目录

4.1.2 目录的基本概念

FCB的有序集合称为文件目录，一个FCB就是一个文件目录项

目录管理的基本要求：

  • 用户角度 -- 实现“按名存取” -- 提高对目录的检索速度
  • 多用户系统中 -- 提供用于控制访问文件的信息 -- 允许不同用户对不同文件采用相同的名字

4.2.2 目录结构

1. 单级目录结构

在整个文件系统中只建立一张目录表，每个文件占一个目录项

  • 当访问一个文件时，先按文件名在该目录中查找到对应的FCB，经合法性检查后执行相应的操作
  • 当建立一个新文件时，必须先检索所有目录项，以确保没有“重名”的情况，然后在该目录中增设一项，把新文件的属性填入
  • 当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后消除该目录项

单机目录结构实现了“按名存取”，但是存在查找速度慢，文件不允许重名。不便于文件共享等缺点，而且对于多用户的操作系统显然不适用。

一级目录平均访盘次数为\(\frac{1}{2}\)盘块数

2. 两级目录结构

为了克服单级目录所存在的缺点，将文件目录分成主文件目录（MFD）和用户文件目录（UFD）

  • 主文件目录项记录用户名即相应用户文件目录所在的存储位置
  • 用户文件目录项记录该用户文件的FCB信息

当某用户欲对其文件进行访问时，只需要搜索该用户对应的UFD，这既解决了不同用户文件的“重名”问题，又在一定程度上保证了文件的安全

两级目录结构提高了检索速度，解决了多用户之间的文件重名问题，文件系统可以在目录上实现访问限制。但是两级目录结构缺乏灵活性，不能对文件分类。

3. 树形目录结构

可以明显提高对目录的检索速度和文件系统的性能

绝对路径和相对路径

用户要访问某个文件时用文件路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件的通路上的所有目录名与数据文件名用分隔符“/”链接起来

  • 绝对路径：从根目录出发的路径
  • 相对路径：从用户（进程）的当前目录出发到所找文件通路上所有目录名与数据名用分隔符“/”链接而成。进程对各文件的访问都是相对于当前目录进行的，设置当前目录有利于加快文件的检索速度

设置当前工作目录的主要目的是加快文件的检索速度

树形目录结构优点：

  • 可以方便地对文件进行分类，层次结构清晰
  • 能够有效的进行文件的管理和保护

4. 无环图目录结构

树形目录结构能便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上增加了一些指向同一结点的有向边，使整个目录成为一个有向无环图。

4.2.3 目录的操作

4.2.4 目录的实现

  1. 线性列表
  2. 哈希表

4.2.5 文件共享！！！

文件共享使多个用户共享同一个文件，系统中只需要保留该文件的一个副本。

1. 基于索引的共享方式（硬链接）

在树形结构的目录中，当有两个或多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个或多个用户的目录中，才能方便地找到该文件。

文件的物理地址及其他的文件属性等信息不再放在目录项中，而是放在索引结点中。

在文件目录中只设置文件名及指向相应索引结点的指针

在索引结点中还应有一个链接计数count，用于表示链接到本索引文件结点（即文件）的用户目录项的数目。当count = 2时，表示有两个用户目录项链接到本文件上，或者说有两个用户共享此文件

用户A创建一个新文件时，他便是该文件的所有者，此时将count置为1.用户B要共享此文件时，在B的目录中增加一个目录项，并设置一个指针指向该文件的索引结点。此时，文件主仍然是用户A，count = 2,如果用户A不再需要此文件，不能直接删除，因为如果删除了该文件，也必然删除了该文件的索引结点，这样会使用户B的指针悬空，而B可能正在此文件上执行写操作，此时将因此半途而废，只是将该文件的count减1，然后删除自己目录中的相应目录项。用户B仍可以使用该文件。当count = 0时，表示没有用户使用该文件，才会删除该文件。

2. 利用符号链实现文件共享（软链接）

为使用户B可以共享用户A的一个文件F，可以由系统创建一个LINK类型的新文件，也取名为F，并将该文件写入用户B的目录中，以实现用户B的目录与文件F的链接。在新文件中只包含被链接文件F的路径名。

在利用符号链方式实现文件共享时，只有文件主才拥有指向其索引结点的指针。而共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也就不会发生在文件主删除一共享文件后留下一悬空指针的情况了。当文件主把一个共享文件删除后，若其他用户又试图通过符号链去访问它，则会出访问失败。

优点： 文件拥有者可以删除被他人共享的文件

缺点： 当其他用户读共享文件时，需要根据路径名多次读盘，访问开销大

4.3 文件系统

4.3.1 文件系统结构

文件系统是提供高效和便捷的磁盘访问，以便允许存储，定位，提取数据。

4.3.2 文件系统布局

1. 文件系统在磁盘中的结构

文件系统存放在磁盘上，多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统。

简单描述如下：

  1. 主引导记录（MBR）：位于磁盘的0号扇区，用来引导计算机，MBR后面是分区表，该表给出每个分区的起始和结束地址。表中的一个分区被标记为活动分区，当计算机启动时，BIOS读入并执行MBR，MBR做的第一件事是确定活动分区，读入它的第一块，即引导块
  2. 引导块：MBR执行引导块中的程序后，该程序负责启动该分区中的操作系统。为统一起见，每个分区都从一个引导块开始，即使它不含有一个可启动的操作系统，也不排除以后会在该分区安装一个操作系统。Windows系统称之为分区引导扇区。
  3. 超级块：包含文件系统的所有关键信息，在计算机启动时，或者在该文件系统首次使用时，超级块会被载入内存。超级块中的典型信息包括分区的块的数量，块的大小，空闲块的数量和指针，空闲的FCB数量和FCB指针等
  4. 文件系统中空闲块的信息，可以使用位示图或指针链接的形式给出。

2. 文件系统在内存中的结构

内存中的信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载，在文件系统操作期间被更新，在卸载时被丢弃。

这些结构的类型可能包括

  1. 内存中的安装表，包含每个已安装文件系统分区的有关信息
  2. 内存中的目录结构的缓存包括最近访问目录的信息。对安装分区的目录，它可以包括一个指向分区表的指针
  3. 整个系统的打开文件表，包括每个打开文件的FCB副本及其他信息
  4. 每个进程的打开文件表，包括一个指向整个系统的打开文件表中的适当条目的指针，以及其他信息。

为了创建新的文件，应用程序调用逻辑文件系统。逻辑文件系统知道目录结构的格式，它将为文件分配一个新的FCB。然后，系统将相应的目录读入内存，使用新的文件名和FCB进行更新，并将它写回磁盘。

一旦文件被创建，它就能用于I/O。不过，首先要打开文件。系统调用open()将文件名传递给逻辑文件系统。找到文件以后，它的FCB会复制整个系统的打开文件表，该表不但存储FCB，而且跟踪打开该文件的进程的数量。然后，在单个进程的打开文件表中创建一个条目，并且通过指针将整个系统打开文件表的条目与其他域相连。调用open()返回的是一个指向单个进程的打开文件表中的适当条目的指针。以后，所有的文件操作都通过该指针执行。一旦文件被打开，内核就不再使用该文件名来访问文件，而使用文件描述符。

4.3.3 外存空闲空间管理

一个存储设备可以按整体用于文件系统，也可以细分。例如，一个磁盘可以划分为4个分区，每个分区都可以有单独的文件系统。

包含文件系统的分区通常称为卷，卷可以是磁盘的一部分，也可以是整个磁盘，还可以是多个磁盘组成的RAID集。

在一个卷中，存放文件数据的空间（文件区）和FCB的空间（目录区）是分离的。

卷在提供文件服务之前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放卷信息的超级块

文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织，分配与回收等问题。

1. 空闲表法

空闲表法属于连续分配方式，与内存的动态分配方式类似

系统为外存上的所有空闲区建立一张空闲盘块表，每个空闲区对应一个空闲表项。

空闲盘块的分配与内存的动态分配类似，同样采用首次适应算法和最佳适应算法等

2. 空闲链表法

将所有空闲盘区拉成一条空闲链。

  • 空闲盘块链：将系统上的所有空闲空间以盘块为单位拉成一条链
  • 空闲盘区链：将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链

3. 位示图法

位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。

当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。这样，一个m*n位组成的位示图就用来表示m*n个盘块的使用情况

notice:

位示图的行和列都从1开始编号，如果从0开始编号，需要自行调整

盘块的分配：

  1. 顺序扫描位示图，从中找出一个或一组值为“0”的二进制位
  2. 将找到的一个或一组二进制位，转换成与之对应的盘块号。

n为每行位数，b为盘块号

\[ b = n(i - 1) + j \]

  1. 修改位示图，令map[i,j] = 1

盘块的回收：

  1. 将回收盘块的盘块号转换成位示图中的行号和列号

\[ i = (b - 1) / n + 1 \\ j = (b - 1) % n + 1 \]

  1. 修改位示图，map[i,j] = 0

空闲表法和空闲链表法都不适用于大型文件系统。

4. 成组链接法

在UNIX系统中采用的是成组链接法，这种方法结合了空闲表和空闲链表两种方法

用来存放一组空闲盘块号的盘块称为成组链块，

4.3.4 虚拟文件系统

虚拟文件系统（VFS）为用户程序提供了文件系统操作的统一接口，屏蔽了不同文件系统的差异和操作细节。

为了实现VFS，Linux主要抽象了四种对象类型，每个VFS对象都存放一个适当的数据结构中，其中包括对象的属性和指向对象方法（函数）表的指针。

  • 超级块对象： 表示一个已安装（或称挂载）的特定文件系统。
  • 索引结点对象： 表示一个特定的文件
  • 目录项对象： 表示一个特定的目录项。
  • 文件对象： 表示一个与进程相关的已打开文件。

VFS还有一个重要作用，即提高系统性能

4.3.5 分区与安装

一个磁盘可以划分为多个分区，每个分区都可以用于创建单独的文件系统，每个分区还可以包含不同的操作系统。