6.1 文件系统概述

• 文件系统的功能
• 有效地管理文件的存储空间；
• 管理文件目录；
• 完成文件的读/写操作；
• 实现文件共享与保护；
• 为用户提供交互式命令接口和程序调用接口。

• 定义：操作系统中的各类文件、管理文件的软件，以及管理文件所涉及到的数据结构等信息的集合。
• 有少数实时操作系统没有文件系统功能。绝大多数操作系统都包含文件管理系统部分。

6.1.1 文件、记录和数据项

• 数据项:是最低级的数据组织形式，可把它分成以下两种类型：
• 基本数据项：这是用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。
• 组合数据项：它是由若干个基本数据项组成的，简称组项。

• 记录：记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。

• 文件：文件是指由创建者所定义的、 具有文件名的一组相关元素的集合。
• 在有结构的文件中，文件由若干个相关记录组成；
• 而无结构文件则被看成是一个字符流。
• 文件在文件系统中是一个最大的数据单位，它描述了一个对象集。
• 文件属性
• 文件类型。
• 文件长度。
• 文件的物理位置。
• 文件的建立时间。

6.1.2 文件类型和文件系统模型

6.1.2.1 文件类型

• 按用途分
• 系统文件：这是指由系统软件构成的文件。大多数的系统文件只允许用户调用，但不允许用户去读，更不允许修改；有的系统文件不直接对用户开放。
• 用户文件:由用户的源代码、目标文件、可执行文件或数据等所构成的文件。
• 库文件：这是由标准子例程及常用的例程等所构成的文件。这类文件允许用户调用，但不允许修改。

• 按文件中数据的形式分类
• 源文件：指由源程序和数据构成的文件。
• 目标文件：指把源程序经过相应语言的编译程序编译过，但尚未经过链接程序链接的目标代码所构成的文件。它属于二进制文件。
• 可执行文件：指把编译后所产生的目标代码再经过链接程序链接后所形成的文件。

• 按存取控制属性分类
• 只执行文件：该类文件只允许被核准的用户调用执行，既不允许读，更不允许写。
• 只读文件：该类文件只允许文件主及被核准的用户去读，但不允许写。
• 读写文件：这是指允许文件主和被核准的用户去读或写的文件

• 按组织形式和处理方式分类
• 普通文件：由ASCII码或二进制码组成的字符文件。一般用户建立的源程序文件、数据文件、目标代码文件及操作系统自身代码文件、库文件、实用程序文件等都是普通文件，它们通常存储在外存储设备上。
• 目录文件：由文件目录组成的，用来管理和实现文件系统功能的系统文件，通过目录文件可以对其它文件的信息进行检索。由于目录文件也是由字符序列构成，因此对其可进行与普通文件一样的种种文件操作。
• 特殊文件：特指系统中的各类I/O 设备。为了便于统一管理，系统将所有的输入/输出设备都视为文件，按文件方式提供给用户使用。

6.1.2.2 文件系统模型

• 文件管理系统管理的对象即属性
• 文件。它作为文件管理的直接对象。
• 目录。为了方便用户对文件的存取和检索，在文件系统中必须配置目录。对目录的组织和管理是方便用户和提高对文件存取速度的关键。
• 磁盘(磁带)存储空间。 文件和目录必定占用存储空间，对这部分空间的有效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。

• 对对象操纵和管理的软件集合
• 这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的，其中包括：
• 对文件存储空间的管理
• 对文件目录的管理
• 用于将文件的逻辑地址转换为物理地址的机制
• 对文件读和写的管理
• 以及对文件的共享与保护等功能

• 文件系统的接口
• 为方便用户使用文件系统，文件系统通常向用户提供两种类型的接口：
• 命令接口。这是指作为用户与文件系统交互的接口。 用户可通过键盘终端键入命令，取得文件系统的服务。
• 程序接口。这是指作为用户程序与文件系统的接口。 用户程序可通过系统调用来取得文件系统的服务。

6.2 文件的物理结构

• 文件是由一系列的记录组成的。

• 对于任何一个文件，都存在着以下两种形式的结构：
• 文件的逻辑结构：从用户观点出发所观察到的文件组织形式。
• 文件的物理结构：指文件在外存上的存储组织形式。

6.2.1 文件存储空间分配的有关问题

• 从逻辑组织的角度看，文件由若干记录构成；

• 从物理组织的角度看，文件由若干数据块组成.

• 操作系统或文件管理系统负责为文件分配和管理数据块。

• 常用的外存分配方法
• 连续分配
• 链接分配
• 索引分配

6.2.1.1 连续分配

• 连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。

• 把逻辑文件中的数据顺序地存储到物理上邻接的各个数据块中，这样形成的物理文件可以进行顺序存取。

• 文件目录中为每个文件建立一个表项，其中记载文件的第一个数据块地址及文件长度。

• 对于顺序文件，连续读/写多个数据块内容时，性能较好。

• 连续分配的优点
• 顺序访问容易
• 例如，如果一个文件的第一个数据块的序号为x，需要检索文件的第y块，则该数据块在外存中的位置为x+y-1。
• 顺序访问速度快：磁头移动距离短，效率最高

• 连续分配的缺点
• 要求有连续的存储空间。
• 该分配方案可能会导致磁盘碎片，严重降低外存空间的利用率。解决方法之一，系统定期或不定期采用紧凑技术，将小分区合并为大的、连续分区，将文件占用空间合并在一起。
• 必须事先知道文件的长度
• 空间利用率不高；不利于文件尺寸的动态增长。

6.2.1.2 链接分配

• 连续分配的文件分区太大，不利于存储空间的有效利用。

• 如果在将一个逻辑文件存储到外存上时，可以考虑将文件装到多个离散的盘块中。

• 链接文件：采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。

• 隐式链接
• 在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。
• 每个盘块中都含有一个指向下一个盘块的指针。
• 隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效的。如果要访问文件所在的第i个盘块，则必须先读出文件的第一个盘块……，就这样顺序地查找直至第i块。
• 为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)。比如，一个簇可包含4个盘块，在进行盘块分配时，是以簇为单位进行的。在链接文件中的每个元素也是以簇为单位的。减少查找时间和指针所占空间，但增大了内部碎片这种改进也是非常有限的。

• 显示链接
• 这是指把用于链接文件所有物理块的指针，显式地存放在内存的一张链接表中。
• 整个磁盘仅设置一张文件分配表（FAT）。
• 在该表中，凡是属于某一文件的第一个盘块号，均作为文件地址被填入相应文件的FCB 的“物理地址”字段中。
• 查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。
• 由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表FAT (File Allocation Table)。

6.2.1.2.3 索引分配

• 单级索引分配
• 索引分配能解决连续分配和链接分配存在的诸多问题。
• 原理：为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。
• 在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。



• 优点：索引分配方式支持直接访问。当要读文件的第i 个盘块时，可以方便地直接从索引块中找到第i个盘块的盘块号；基于数据块的分区能消除外部碎片
• 缺点:大文件索引项较多，可能使一个数据块容纳不了一个文件的所有分区的索引。索引块可能要花费较多的外存空间。每当建立一个文件时，便须为之分配一个专门的索引块，将分配给该文件的所有盘块号记录于其中。对于小文件如果采用这种方式，索引块的利用率将是极低的。

• 二级索引分配
• 即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块……等索引块的盘块号填入到此索引表中。
• 二级索引记录一级索引的第一个盘块号。一级索引记录文件第一个盘块的盘块号。
• 优点:大大加快了对大型文件的查找速度。缺点:在访问一个盘块时，其所需要启动磁盘的次数随着索引级数的增加而增多。即使对于小文件也如此

• 混合索引

6.3 文件存储空间的管理

• 存储空间的基本分配单位是磁盘块。

• 其分配方法与内存的分配有许多相似之处，即同样可采取连续分配方式或离散分配方式。

6.3.1 空闲分区表

• 空闲表法属于连续分配方式，它为每个文件分配一块连续的存储空间，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项。

• 其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。见表 :

• 适合于可变大小分区的连续分配方式



• 实现简单。对于最佳适应分配算法，可以将各空闲分区按照（长度）从小到大的顺序进行排列，再利用有效的查找算法，能很快找到需要大小的空闲分区。
• 但是，当存储空间中的空闲分区分布较分散且数量较多时，空闲分区表将会很大。需要很大的内存空间，会降低空闲分区表的检索速度。

• 对交换分区一般都采用连续分配方式

• 对于文件系统，当文件较小(1～4个盘块)时，仍采用连续分配方式，为文件分配相邻接的几个盘块；

• 当文件较大时，便采用离散分配方式。

6.3.2 空闲链表法

用专门的空闲分区表登记空闲分区信息会浪费一定的存储空间，而且不适合登记分散且数目很多的空闲分区，不利于基于存储块的链接文件和索引文件的存储空间分配。

• 空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：
• 空闲盘块链：将磁盘上的所有空闲空间，以盘块为单位拉成一条链。
• 当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。
• 空闲盘区链：将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。
• 在每个盘区上含有用于指示下一个空闲盘区的指针和能指明本盘区大小(盘块数)的信息。
• 分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。
• 显式链接方法，亦即，在内存中为空闲盘区建立一张链表。每个分区结点内容：起始盘块号、盘块数、指向下一个空闲盘区的指针。

6.3.3 位示图

• 利用二进制位0、1表示存储空间中存储块的使用状态。空闲分区:0，已分配分区:1（或者相反）。

• 磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。

• 通常可用m × n 个位数来构成位示图，并使m × n等于磁盘的总块数。

• 位示图也可描述为一个二维数组map：Var map: array of bit；

• 盘块的分配
• 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。
• 将所找到的一个或一组二进制位转换成与之相应的盘块号。
• 假定找到的其值为“0”的二进制位位于位示图的第i 行、第j列，则其相应的盘块号应按下式计算：b = n(i- 1) + j（n代表每行有多少个）
• 修改位示图，令map[i,j]=1。

• 盘块的回收
• 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：
• i = (b - 1)DIV n + 1
• j = (b - 1)MOD n + 1
• 修改位示图。令map[i,j] =0。

• 位示图的优缺点

6.3.4 成组链接法

6.4 文件目录

6.4.1 文件目录管理

• 文件控制块（FCB）：用于描述和控制文件的数据结构

• 文件目录：文件控制块的有序集合。

• FCB的内容

6.4.2 目录

• 目录项的两种组织方式
• FCB存储全部目录内容
• FCB存储部分目录信息，如文件名、索引节点指针等，其余部分保存在索引节点（i节点）。打开文件时将索引节点从磁盘读到内存中。

• 目录文件及操作
• 目录文件：一个文件目录也被看做是一个文件，即目录文件。是多个文件的目录项构成的一种特殊文件。
• 搜索目录/创建目录/删除目录/显示目录/修改目录

• 目录结构
• 单级目录结构：所有用户的全部文件目录保存在一张目录表中，每个文件的目录项占用一个表项。存在下述一些缺点：查找速度慢，不允许重名，不便于实现文件共享。
• 两级目录结构：主文件目录MFD，用户文件目录UFD



• 一定程度解决了重名问题，提高了文件目录检索效率，简单的文件共享。
• 问题：不便用户文件的逻辑分类；进一步解决重名、共享、检索效率等问题
• 层次目录结构（多级目录结构）
• 多级目录结构又称为树型目录结构，主目录在这里被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点。



• 路径名：从树的根（即主目录）开始，把全部目录文件名与数据文件名，依次地用“/”连接起来，即构成该数据文件的路径名（path name）。
• 系统中的每一个文件都有惟一的路径名。
• 当前目录：为每个进程设置一个“当前目录”，又称为“工作目录”进程对各文件的访问都相对于“当前目录”而进行。
• 相对路径名，绝对路径名
• 增加和删除目录
• 增加目录：在用户要创建一个新文件时，只需查看在自己的UFD及其子目录中，有无与新建文件相同的文件名。若无，便可在UFD或其某个子目录中增加一个新目录项。
• 目录删除采用下述两种方法处理
• 不删除非空目录
• 可删除非空目录

• 索引结点
• 当查找文件时，需要把磁盘上的目录文件逐个取出，逐个对比文件名，会造成大量磁盘操作。在检索目录文件的过程中只用到了文件名，仅当找到一个目录项(即其中的文件名与指定要查找的文件名相匹配)时，才须从该目录项中读出该文件的物理地址。而其他对该文件进行描述的信息，在检索目录时一概不用。
• 所以可以采用把文件名和文件描述信息分开的方法。使文件描述信息单独形成一个称为索引节点(iNode)的数据结构，简称为i节点。文件目录中的每个目录项，仅由文件名和指向该文件所对应的索引节点的指针所构成。

6.4.3 目录查询技术（***）

6.4.3.1 线性检索法

• 在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件目录中找到指名文件的目录项。

• 在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进行查找。

• 路径名：从树的根（即主目录）开始，把全部目录文件名与数据文件名，依次地用“/”连接起来，即构成该数据文件的路径名（path name）。

• 目录：多个文件目录构成调度文件。内容是一张表：文件名+索引结点号
• 索引结点（inode）：存放文件信息
• 目录本质上是：文件名 ➜ inode号 的映射表。

6.4.3.2 Hash方法

• Hash方法: 建立了一张Hash索引文件目录，系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找。

• Hash方法将显著地提高检索速度。

• 在文件名中使用了通配符“* ”、“？”等，系统便无法利用Hash法检索目录，因此，需要利用线性查找法查找目录。

• 在进行文件名的转换时，有可能把多个不同的文件名转换为相同的Hash值，称谓的“Hash冲突”。

• Hash查找过程
• 在利用Hash值查找目录时，如果目录表中相应的目录项是空的，则表示系统中并无指定文件。
• 如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找的文件所对应的目录项，故而可从中找到该文件所在的物理地址。
• 如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“Hash冲突”。
• 解决Hash冲突的方法 ：将其Hash值再加上一个常数（该常数应与目录的长度值互质），形成新的索引值，再返回到第一步重新开始查找。

6.5 文件共享和访问控制

6.5.1 文件共享

• 同时存取（Simultaneous Access）

• 存取权限（Access Rights）

• 控制同时存取
• 允许多个用户同时读文件内容，但不允许同时修改，或同时读且修改文件内容。
• 共享用户之一修改文件内容时，可以将整个文件作为临界资源，锁定整个文件，不允许其他共享用户同时读或写文件。
• 也可以仅仅锁定指定的一条记录，允许其他共享用户读/写该文件的其它记录。后者的并发性能更好。
• 控制对文件的同时存取涉及进程的同步与互斥问题。

• 控制存取权限
• 执行（Execution） — 用户可以装载并执行程序，但不允许拷贝程序内容。
• 读（Reading）— 允许用户读文件内容，包括拷贝和执行文件。某些系统严格地将浏览文件内容和拷贝权限分开，可以控制文件只能被浏览（显示），不能被拷贝。
• 追加（Appending）— 允许用户向文件添加数据，通常只能将数据添加到文件尾。但是，不能修改或删除文件内容。例如，超市收银员只能将新结帐的数据添加到文件中，不允许其修改或删除已有的数据。
• 更新（Updating）— 允许用户修改、删除、增加文件内容。包括创建文件、重写文件的全部或部分内容、移动文件的全部或部分数据等操作。
• 更改权限 (Changing protection) —一般只有文件主才能更改共享该文件的其他用户对该文件的存取权限。有的系统允许文件主将更改文件存取权限赋予其他某个用户，但必须限制授权用户更改的权限范围。
• 删除 (Deletion) 允许用户删除文件

• 文件共享的实现



• 在树型结构的目录中，当有两个(或多个)用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个(或多个)用户的目录中，才能方便地找到该文件。此时该文件系统的目录结构已不再是树型结构，而是个有向非循环图。
• 实现文件共享的实质就是可以从不同地方打开同一个文件
• 打开文件的首要步骤就是找到文件的目录项，读取文件在外存的起始地址。

6.5.2 链接目录项实现文件共享

• 文件目录项中设置一个链接指针，用于指向共享文件的目录项。

• 访问文件时，根据链接指针内容找到共享文件的目录项，读取该目录项中文件起始位置等信息，操作该文件。

• 每当有用户（进程）共享文件时，共享文件目录项中的“共享计数”加1；当用户不再共享该文件，撤消链接指针时，“共享计数”减1。

• 只有当共享文件用户数为1时，才能删除共享文件。

6.5.3 利用索引节点实现文件共享

• 文件的物理地址及其它的文件属性等信息，不再是放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。

• 由任何用户对文件进行Append 操作或修改，所引起的相应结点内容的改变(例如，增加了新的盘块号和文件长度等)，都是其他用户可见的，从而也就能提供给其他用户来共享。

• UNIX操作系统的文件目录项中只包含文件名和指向索引节点的指针，文件的物理地址及其它说明信息保存在索引节点中。

• 可以通过共享文件索引节点来共享文件，即当用户需要共享文件时，在自己的文件目录中新建一个目录项，为共享文件命名(也可用原名)，并将索引节点指针指向共享文件的索引节点。

• 在索引结点中还应有一个链接计数count，用于表示链接到本索引结点(亦即文件)上的用户目录项的数目。



• 只能删除硬链接，但不能删除里面实际的内容。当所有的硬链接都删除后，才能删除其内容和索引节点。

6.5.4 利用符号链实现文件共享

• 为使B能共享C的一个文件F，可以由系统创建一个LINK类型的新文件，也取名为F并将F写入B的目录中，以实现B的目录与文件F的链接；在新文件中只包含被创文件F的路径名。这样的链接方法被称为符号链接。

• 新文件中的路径名，则只被看作是符号链。当B要访问被链接的文件F且正要读LINK类新文件时，将被OS截获，OS根据新文件中的路径名去读该文件，于是就实现了用户B对文件F的共享。

• 在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针,而共享该文件的其它用户，则只有该文件的路径名，并不拥有指向其索引结点的指针。

• 符号链方式优点：能连接任何机器上的文件。每增加一个连接，就增加一个文件名，各用户使用自己的名字去共享文件。

• 缺点：备份可能会产生多个拷贝。

6.5.5 利用URL实现文件共享

• 统一资源定位器URL (Uniform Resource Locator)是Internet上用来链接超文本文件的一种方法。

• 它可以链接同一台计算机中的本地文件，也可链接Internet中任何主机上的远程文件。

• 一个完整的URL包括访问文件的方法（协议）、文件所在的主机域名、目录路径名和文件名几部份。例如， http://www.uestc.edu.cn/templates/index2k3/index.html

• 当通过该URL地址连接到电子科技大学www服务器时，用户计算机就会收到该服务器传来的index.html文件。

6.6 文件保护

• 不同对象允许实施的操作各不相同。例如，文件可施加读、写、执行等操作，信号量只能施加wait()和signal()操作。

• 因此，系统为所有对象设置一个允许进程实施操作的操作集，任何对对象的操作必须符合操作集中的规定，防止未授权进程访问对象。

6.7 练习

• 例1

• 直接地址，就是数据项的地址，也就是磁盘的地址

• 一次间址项/二次间址项/n次间址项
• 存放在FCB的地址特征，指向n次间址块

• 一次间址块：存放指向数据项的指针，即存放数据项的地址，即磁盘的地址。（170个地址，那么就是170个磁盘块）

• 二次间址块，存放的是一次间址块的地址。（170块一次间址块，每个间址块有170个数据，那么就是170*170磁盘块）

• n次间址块存放n-1次间址块的地址。

• 每个盘块512字节，盘块号3字节，那么就能放170个盘块地址。

• 由于间址块从0开始编号，所以10+170，这个170是第0个一次间址块，第二个间址块的第一个一次间址块，并从该间址块的112项得到物理盘块号

• 这里需要最近的字节数表示，2.5字节/3字节

• 单级索引：为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。
• 在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。

• 二级索引：

• 混合索引

• 分配盘块
• 比如说要分配第i行第j列的盘块，0表示空闲，1表示已经分配。计算空闲盘块号，b=（i-1）*N+J;但由于这里行号和列号都是从0开始，所以盘块号=i*n+j+1.这里是根据图来找的。
• 然后再修改对应位为1.map[i, j]=1

• 释放盘块号
• 因为这里是从0开始的，所以/即为行号，mod余数-1即为列号

• 1024/4=2^8个地址(10+2^8+2^16+2^24)*2^10

• 一次间址块的234块