第 4 章 文件管理

文件系统基础

文件的基本概念

1. 文件的定义

• 数据项（理解为属性）
• 记录（理解为对象）
• 文件。有结构（含有若干记录对象） 无结构（字符流）

2. 文件的属性

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

3. 文件的分类

1）按用途分类

1）系统文件 （2）用户文件 （3）库文件

2）按文件中数据的形式分类

（1）源文件 由 ASCII 码或汉子构成 （2）目标文件 把源程序编译后 且未经过链接的目标代码所构成文件 （3）可执行文件

3）按存取控制属性分类

（1）只执行文件 （2）只读文件 （3）读写文件

3）按组织形式和处理方式分类

（1）普通文件 （2）目录文件 （3）特殊文件

文件控制块和索引节点

与进程管理一样，为便 于文件管理，引入了文件控制块的数据 结构

1. 文件控制块

文件控制块(File Control Block，FCB)是用来存放控制文件需要的各种信息的数据结构，以实现按名存取。 文件与FCB一一对应，FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。通常，一个文件目录也被视为一个文件，称为目录文件。每当创建一个新文件，系统就要为其建立一个FCB，用来记录文件的各种属性

文件名
类型
文件权限（读写）
文件大小
文件数据块指针

FCB 主要包含以下信息:

• 基本信息，如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
• 存取控制信息，包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。
• 使用信息，如文件建立时间、上次修改时间等。

2. 索引节点

在检索目录的过程中，只用到了文件名，仅当找到一个目录项(其中的文件名与要查找的文件名匹配时），才需从该目录项中读出该文件的物理地址。也就是说，在检索目录时，文件的其他描述信息不会用到，也不需要调入内存。

因此，采用文件名和文件描述信息分离的方法，使文件描述信息单独形成一个称为索引节点的数据结构，简称i节点(inode)。在文件目录中的每个目录项仅由文件名和相应的索引节点号(或索引节点指针)构成。

（1）磁盘索引节点

是指存放在磁盘上的索引节点。每个文件有一个唯一的磁盘索引节点，主要包括以下内容:

• 文件主标识符，拥有该文件的个人或小组的标识符。
• 文件类型，包括普通文件、目录文件或特别文件。
• 文件存取权限，各类用户对该文件的存取权限。
• 文件物理地址，每个索引节点中含有13个地址项，即iaddr(O)~iaddr(12)，它们以直接或 间接方式给出数据文件所在盘块的编号(见4.1.6节)。
• *文件长度，*指以字节单位的文件长度。
• 文件链接计数，在本文件系统中所有指向该文件的文件名的指针计数。
• 文件存取时间，本文件最近被进程存取、修改的时间及索引节点最近被修改的时间

（2）内存索引节点

是指存放在内存中的索引节点。当文件被打开时，要将磁盘索引节点复制到内存的索引节点 中，便于以后使用。在内存索引节点中增加了以下内容:

• 索引节点号，用于标识内存索引节点。
• 状态，指示i节点是否上锁或被修改。
• 访问计数，每当有一进程要访问此i节点时，计数加1:访问结束减1。
• 逻辑设备号，文件所属文件系统的逻辑设备号。
• 链接指针，设置分别指向空闲链表和散列队列的指针。

文件的基本操作

1. 文件的基本操作

• 创建文件。创建文件有两个必要步骤:一是新文件分配外存空间;二是在目录中为之创建一个目录项，目录项记录了新文件名、文件在外存中的地址等信息。

• 删除文件。为了删除文件，根据文件名查找目录，删除指定文件对应的目录项和文件控制块，然后回收该文件所占用的存储空间(包括磁盘空间和内存缓冲区)。

• 读文件。为了读文件，根据文件名查找目录，找到指定文件的目录项后，从中得到被读文件在外存中的地址;在目录项中，还有一个指针用于对文件进行读操作。

• 写文件。为了写文件，根据文件名查找目录，找到指定文件的目录项后，再利用目录项中的写指针对文件进行写操作。每当发生写操作时，便更新写指针

2. 文件的打开与关闭

文件的打开过程（2014）

当用户对一个文件实施多次读/写等操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，大多数操作系统要求，当用户首次对某文件发出操作请求时，须先利用系统调用open将该文件打开。系统维护一个包含所有打开文件信息的表，称为打开文件表。所谓“打开”，是指系统检索到指定文件的目录项后，将该目录项从外存复制到内存中的打开文件表的一个表目中，并将该表目的*索引号(也称文件描述符)*返回给用户。当用户再次对该文件发出操作请求时，可通过文件描述符在打开文件表中查找到文件信息，从而节省了大量的检索开销。当文件不再使用时，可利用系统调用close关闭它，则系统将会从打开文件表中删除这一表目。

多进程同时打开文件的分析 (2017、2020) 文件关闭的过程 (2023)

在多个进程可以同时打开文件的操作系统中，通常采用两级表:整个系统表每个进程表。整个系统的打开文件表包含与进程无关的信息，如文件在磁盘上的位置、访问日期和文件大小。每个进程的打开文件表保存的是进程对文件的使用信息，如文件的当前读写措针、文件访问权限，并包含指向系统表中适当条目的指针。

一旦有进程打开了一个文件，系统表就包含该文件的条目。当另一个进程执行调用open时，只不过是在其打开文件表中增加一个条目，并指向系统表的相应条目。通常，系统打开文件表为每个文件关联一个打开计数器(OpenCount)，以记录多少进程打开了该文件。当文件不再使用时，利用系统调用close关闭它，会删除单个进程的打开文件表中的相应条目，系统表中的相应打开计数器也会递减。当打开计数器为0时，表示该文件不再被使用，并且可从系统表中删除相应条目

文件名和文件描述符的应用场景 (2012、2017、2024)

文件名不必是打开文件表的一部分，因为一旦完成对FCB在磁盘上的定位，系统就不再使用文件名。对于访问打开文件表的索引号，UNIX称之为文件描述符，而Windows称之为文件句柄。因此，只要文件未被关闭，所有文件操作都是通过文件描述符(不是文件名)来进行。

note: 只要完成了文件打开open()系统调用，后面再使用read()、Write()、Lseek()、close()等文件 操作的系统调用，就不再使用文件名，而使用文件描述符。该考点已反复考过多次。

每个打开文件都具有如下关联信息:

• 文件指针。系统跟踪上次的读写位置作为当前文件位置的指针，这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存。

• 文件打开计数。计数器跟踪当前文件打开和关闭的数量。因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件。

• 文件磁盘位置。大多数文件操作要求系统修改文件数据。查找磁盘上的文件所需的信息保存在内存中，以便系统不必为每个操作都从磁盘上读取该信息。

• 访问权限。每个进程打开文件都需要有一个访问模式(创建、只读、读写、添加等)。该信息保存在进程的打开文件表中，以便操作系统能够允许或拒绝后续的1/O请求。

文件保护

为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用 户对文件的存取，即解决对文件的读、写、执行的许可问题。

1. 访问类型

• 读。从文件中读。
• 写。向文件中写。
• 执行。将文件装入内存并执行。
• 添加。将新信息添加到文件结尾部分。
• 删除。删除 文件，释放空间。
• 列表清单。列出文件名和文件属性。

2. 访问控制

解决访问控制最常用的方法是根据用户身份进行控制，为每个文件和目录增加一个访问控制列表(Access-ControlList,ACL)，以规定每个用户名及其所允许的访问类型。

文件访问控制表的结构(2017)

精简的访问控制列表可采用拥有者 、组和其他 三种用户类型。

• 拥有者。创建文件的用户。

• 组。一组需要共享文件且具有类似访问的用户。

• 其他。 系统内的所有其他用户。

文件的逻辑结构

文件的逻辑结构是指从用户角度出发所看到的文件的组织形式。而文件的物理结构(又称存储结构)是指将文件存储在外存上的存储组织形式，是用户所看不见的。文件的逻辑结构与存储介质特性无关，它实际上是指在文件的内部，数据在逻辑上是如何组织起来的。

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

1. 无结构文件

无结构文件是最简单的文件组织形式，它是由字符流构成的文件，所以又称流式文件，其长度以字节为单位。对流式文件的访问，是通过读/写指针来指出下一个要访问的字节的

2. 有结构文件

有结构文件是指由一个以上的记录构成的文件，所以又称记录式文件。各记录由相同或不同数目的数据项组成，根据各记录的长度是否相等，可分为定长记录和变长记录两种。

1️⃣ 定长记录 。文件中所有记录的长度都是相同的，各数据项都在记录中的相同位置，具有相同的长度。检索记录的速度快，方便用户对文件进行处理，广泛用于数据处理中。

2️⃣ 变长记录。文件中各记录的长度不一定相同，原因可能是记录中所包含的数据项数目不同，也可能是数据项本身的长度不定。检索记录只能顺序查找，速度慢。

（1）顺序文件

文件中的记录一个接一个地顺序排列，记录可以是定长记录或变长记录。

（2）索引文件

可以建立一张索引表，为主文件的每个记录在索引表中分别设置一个索引表项，其中包含指向记录的指针和记录长度，索引表按关键字排序，因此其本身也是一个定长记录的顺序文住。

（3）索引顺序文件

索引顺序文件是顺序文件和索引文件的结合。

最简单的索引顺序文件只使用了一级索引，先将变长记录顺序文件中的所有记录分为若干组，然后为文件建立一张索引表，并为每组中的第一个记录建立一个索引项，其中包含该记录的关键字和指向该记录的指针。

（4）直接文件和散列文件

给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址

文件的物理结构

文件数据在物理存储设备上是如何分布和组织的。

不同物理结构的特点和比较(2009、2011、2013、2020)

1. 连续分配

连续分配方法要求每个文件在磁盘上占有一组连续的块，磁盘地址定义了磁盘上的一个线性排序，这种排序使进程访问磁盘时需要的寻道数和寻道时间最小。采用连续分配时，逻辑文件中的记录也顺序存储在相邻的物理块中

优点：

1️⃣ 支持顺序访问和直接访问

2️⃣ 顺序访问容易且速度快，文件所占用的块 可能位于一条或几条相邻的磁道上，磁头的移动距离最小

缺点：

1️⃣ 要为一个文件分配连续的存储空间，与内存分配类似，为文件分配连续的存储空间会产生很多外部碎片。

2️⃣ 必须事先知道文件的长度，也无法满足文件动态增长的要求，否则会覆盖物理上相邻的后续文件。

3️⃣ 为保持文件的有序性，删除和插入记录时，需要对相邻的记录做物理上的移动

2. 链接分配

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

1️⃣ 消除了磁盘的外部碎片，提高了磁盘的利用率。

2️⃣ 便于动态地为文件分配盘块，因此无须事先知道文件的大小。

3️⃣ 文件的插入、删除和修改也非常方便。链接分配又可分为隐式链接和显式链接两种形式

（1）隐形链接

目录项中含有文件第一块的指针(盘块号)和最后一块的指针。每个文件对应一个磁盘块的链表，磁盘块分布在磁盘的任何地方。除文件的最后一个盘块外，每个盘块都存有指向文件下一个盘块的指针，这些指针对用户是透明的。

缺点：

1️⃣ 只支持顺序访问，若要访问文件的第i块，则只能从第1块开始 ，通过盘块指针顺序查找到第i块，随机访问效率很低。

2️⃣ 稳定性问题，文件盘块中的任何一个指针出问题，都会导致文件数据的丢失。

3️⃣ 指向下一个盘块的指针也要耗费一定的存储空间

为了提高查找速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇，按簇而不按块来分配，可以大幅地减少查找时间，也可以改善许多算法的磁盘访问时间，增加了内部碎片。

（2）显式链接

显式链接是指将用于链接文件各物理块的指针，显式地存放在内存的一张链接表中，该表在整个磁盘中仅设置一张，称为文件分配表(FileAllocationTable,FAT)。每个表项中存放指向下一个盘块的指针。文件目录中只需记录该文件的起始块号，后续块号可通过查FAT找到

不难看出，FAT的表项与全部磁盘块一一对应，并且可以用一个特殊的数字-1表示文件的最后一块，可以用-2表示这个磁盘块是空闲的(当然也可指定为-3，-4)。因此，FAT还标记了空闲的磁盘块，操作系统可以通过FAT对磁盘空闲空间进行管理。当某进程请求系统分配一个磁盘块时，系统只需从FAT中找到-2的表项，并将对应的磁盘块分配给该进程即可。

优点： 1️⃣ 支持顺序访问，也支持直接访问，要访问第i块，无须依次访问前i - 1 块

2️⃣ FAT在系统启动时就被读入内存，检索记录是在内存中进行的，因而不仅显著提高了检索 速度，而且明显减少了访问磁盘的次数

缺点： FAT需要占用 一定的内存空间

3. 索引分配

（1）单级索引分配方式

事实上，在打开某个文件时，只需将该文件对应的盘块的编号调入内存即可，完全没有必要将整个FAT调入内存。为此，应该将每个文件所有的盘块号集中地放在一起，当访问到某个文件时，将该文件对应的盘块号一起调入内存即可，这就是索引分配的思想。它为每个文件分配一个索引块(表)，将分配给该文件的所有盘块号都记录在该索引块中

优点：

1️⃣ 支持直接访问，当要访问第i块时，索引块的第i个条目指向的便是文件 的第i个块。索引分配也不会产生外部碎片

缺点： 不适合大文件

（2）多级索引分配方式

当文件太大而索引块太多时，应该为这些索引块再建立一级索引，称为主索引，将第一个索引块的盘块号、第二个索引块的盘块号...填入该主索引表，这样，便形成了二级索引分配方式，其原理类似于内存管理中的多级页表

（3）混合索引分配方式

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

文件系统的层次结构

文件操作

1. 最基本的文件操作

   （1）创建文件 （2）删除文件 （3）读文件 （4）写文件 （5）设置文件的读/写位置

2. 文件的“打开”和“关闭”操作 每次用户对文件的读写，都要从检索目录开始，为了避免重复检索，引入“open”文件系统调用，将指定文件的属性从外存拷贝到内存打开文件表的一个表目中，可通过“关闭”系统调用来关闭此文件

3. 其它文件操作

文件的逻辑结构

文件逻辑结构的类型

1. 按文件是否有结构分类

   1）有结构文件 由一个个的记录项组成，也称为记录文件 （1）定长记录 （2）变长记录 2）无结构文件 在系统中运行的大量的源程序、可执行文件、库函数等，都是无结构的文件形式，即流式文件。其文件的长度是以字节为单位的。对它的访问，则是利用读、写指针指出下一个要访问的字符

2. 按文件的组织方式分类 把有结构的文件分为三类： （1）顺序文件 （2）索引文件 （3）索引顺序文件

顺序文件

1. 顺序文件的排列方式 （1）串结构。按存入时间的先后进行排序，各记录之间的顺序与关键字无关 （2）顺序结构 由关键字指定顺序排列

2. 顺序文件的优缺点 优点：在进行批量存取，顺序文件的效率最高 缺点：查找单个记录性能很差，增加或删除困难

   定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取。

记录寻址

1. 隐式寻址方式
2. 显式寻址方式 （1）通过文件中记录的位置 （2）利用关键字

索引文件

1. 按关键字建立索引
2. 具有多个索引表的索引文件 索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，支持随机存取

索引顺序文件

1. 索引顺序文件的特征 索引文件和顺序文件的结合
2. 一级索引顺序文件
3. 两级索引顺序文件

直接文件和哈希文件

1. 直接文件 根据给定的关键字直接获得指定记录的物理地址，（关键字本身决定了记录的物理地址），这种由关键字到记录物理地址的转换称为键值转换
2. 哈希文件 利用 hash 函数可将关键字转换为相应记录的地址

文件目录

文件控制块和索引结点

1. 文件控制块 FCB 实现文件名和文件之间的映射，以实现按名存取 1）基本信息 文件名 文件物理地址 文件逻辑结构（流还是记录） 文件的物理结构（顺序文件、链接式文件 索引文件） 2）存取控制信息类 包括文件的存取权限、核准用户的存取权限一级一般用户的存取权限 3）使用信息类 建立时间、修改时间、当前使用信息、打开该文件的进程数、是否被其它进程锁住，在内存中是否被修改
2. 索引结点 1）索引结点的引入 文件名和文件信息拆开 检索过程中只使用到了文件名 2）磁盘索引结点 存放在磁盘上的索引结点。包括以下： 文件标识符、文件类型、文件存取权限、文件物理地址、文件长度、文件连接计数、文件存取时间 3）内存索引结点 存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中 索引结点编号 状态（是否上锁）访问计数 文件所属文件系统的逻辑设备号 链接指针

简单的文件目录

1. 单级文件目录 不允文件重名
2. 两级文件目录 主文件目录 和 用户文件目录 允许不同用户的文件重名 不允许对文件进行分类

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

1. 树形目录 方框代表目录文件，圆圈代表文件
2. 路径名和当前目录 1）路径名 /B/F/J 2）当前目录 为每个进程设置一个“当前目录”，又称为“工作目录”。进程对各文件的访问都相对于“当前目录”而进行。 从当前目录开始的路径名称为相对路径名 从树根开始的路径名称为绝对路径名
3. 目录操作 （1）创建目录 （2）删除目录 （3）改变目录 （4）移动目录 （5）链接操作 （6）查找

目录查询技术

当用户要访问一个已存文件时，系统首先利用用户提供的文件名对目录进行查询。找过该文件的文件控制块或对应索引结点。然后根据 FCB 或索引结点中的记录的文件物理地址（盘块号），换算出文件在磁盘上的物理位置。最后根据磁盘驱动程序将所需文件读入内存。

1. 线性检索法（顺序检索法）
2. hash 方法 建立 hash 索引文件目录，系统利用用户提供的文件名，并将它变换为文件目录的索引值，再利用该索引值到目录中去查找 如果使用了通配符“ * ？ ”便无法通过 hash 检索。

文件共享

指系统应允许多个用户共享同一份文件 ，只需保存一份文件的副本。

基于有向无循环图实现文件共享

1. 有向无循环图 DAG 树形结构目录不适合文件共享。
2. 利用索引结点（硬链接） 索引结点：文件目录瘦身策略，由于检索文件时只需要用到文件名，因此可以将除文件名之外的信息放到索引结点中，这样子目录项就只包含文件名、索引结点指针 索引结点中设置一个链接计数变量，用于表示本索引结点上的用户目录项数 利用索引结点，将文件的物理地址及其它的文件属性等信息，不再放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及其指向相应索引结点的指针。在索引结点中还应有一个链接计数，表示链接到本索引结点上的用户目录项的数目。

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

如 win 的快捷方式

1. 利用符号链接的基本思想 基本思想：允许一个文件或子目录有多个父目录，但起哄仅有一个作为主父目录，其它几个父目录都是通过符号链接方式与之相链接的
2. 如何利用符号链实现共享
3. 利用符号链实现共享的优点 只有文件主才拥有指向其索引结点的指针，而共享该文件的其它用户只有该文件的路径名，并不拥有指向其索引结点的指针。
4. 利用符号链的共享方式存在的问题 根据文件名去访问，可能要多次地读磁盘

文件共享总结 硬链接： 各个用户的目录项指向同一个索引结点 索引结点需要有链接计数 count 某用户想删除文件时，只是删除该用户的目录项，且 count-- 只有 count==0 时 才能真正删除文件数据和索引结点，否则会导致指针悬空

软连接（符号链接）： 在以 link 型文件中记录共享文件的存放路径（windows 快捷方式） OS 根据路径一层层查找目录、最终找到该共享文件 即使软链接指向的共享文件已被删除、link 文件依然存在，只是通过 link 文件中的文件路径区查找共享文件会失效（找不到对应目录项） 由于用软连接的方式访问共享文件时要查询多级目录，会有多次磁盘 I/O

文件保护

保护域

进程只能在保护域内执行操作，而且只允许进程访问它们具有“访问权”的对象。

1. 访问权 把一个进程能对某对象执行操作的权利，称为访问权，每个访问权可以用一个有序对（对象名，权集）来表示。
2. 保护域 为了对系统中的资源进行保护而引入了保护域的概念，简称为“域”。域是进程对一组对象访问权的集合，进程只能在指定域内执行操作，这样域也就规定了进程所能访问的对象和能执行的操作。
3. 进程和域间的静态联系 进程和域之间 一一对应
4. 进程和域间的动态练习方式 一对多关系

访问矩阵

1. 基本的访问矩阵 用矩阵来描述系统的访问控制，把该矩阵称为访问矩阵
2. 具有域切换权的访问矩阵 为了实现进程和域之间的动态练习，应能将进程从一个保护域切换到另一个保护域

访问矩阵的修改

1. 拷贝权
2. 所有权
3. 控制权

访问矩阵的实现

1. 访问控制表
2. 访问权限表

王道补充 口令保护： 为文件设置一个“口令”，用户想要访问文件时需要提供口令，由系统验证口令是否正确 实现开销小，但“口令”一半存放在 FCB 或索引结点中（也就是存放在系统中）因此不太安全

加密保护： 用一个“密码”对文件加密，用户想要访问文件时，需要提供相同的“密码”才能正确的解密。 安全性高，但加密/解密需要耗费一定的时间（异或加密）

访问控制： 用一个访问控制表（ACL）记录哥哥用户（或各组用户）对文件的访问权限 对文件的访问类型可以分为：读/写/执行/删除等 实现灵活，可以实现复杂的文件保护功能