> For the complete documentation index, see [llms.txt](https://lewiszlw.gitbook.io/notebooks/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lewiszlw.gitbook.io/notebooks/blogs/history/wen-jian-xi-tong.md).

# 文件系统

信息（程序/ 数据）是计算机系统中的重要资源。操作系统的文件系统负责信息的组织、存储和访问。

## 文件系统的概念

### 文件和文件系统

文件

* 文件是一段程序或数据的集合
* 在计算机系统中，文件被解释为一组赋名的相关联字符流的集合，或是相关联记录的集合

文件系统

* 操作系统中与管理文件有关的软件和数据称为文件系统
* 文件系统负责为用户建立、撤消、读写、修改和复制文件；还负责完成对文件的按名存取和存取控制

### 文件的类型

按文件性质和用途分类

* 系统文件：OS及各种系统程序的信息所组成的文件。
* 用户文件：用户委托保存的文件，如源程序文件、用户数据库文件等。
* 库文件：标准子程序及常用应用程序组成的文件。

按文件的保护方式分类

* 只读文件 R
* 读写文件 RW
* 可执行文件 E
* 不保护文件

按文件组织和处理方式分类

* 普通文件：组织形式为一般格式的文件，如ASCII或二进制文件。
* 目录文件：由文件的目录信息构成的文件，用于检索普通文件。
* 特殊文件：所有输入输出设备都被看作特殊文件（UNIX系统）

按信息流分类

* 输入文件：如读卡机或键盘上的文件，只能读入。
* 输出文件：如打印机上的文件，只能写出。
* 输入/输出文件：如磁盘、磁带上的文件，既可读又可写。

按文件中的数据形式分类

* 源文件：指从终端或输入设备输入的源程序和数据所构成的文件。
* 目标文件：指源程序经过相应语言的编译程序进行编译后，但尚未经过连接处理的目标代码形成的文件，属于二进制文件。
* 可执行文件：经过编译、连接之后所形成的可执行目标文件。

### 文件系统的功能

系统的角度：

* 文件空间管理 为合理地存放文件，必须对文件空间进行统一管理。
* 逻辑结构 为了实现按名存取，需要有一个用户可见的文件逻辑结构，用户按照文件逻辑结构所给定的方式进行信息存取和加工。
* 物理结构 为了便于存放和加工信息，文件在存储设备上应按一定的顺序存放。这种存放方式被称为文件的物理结构。
* 信息查找 完成对存放在存储设备上的文件信息的查找。
* 信息共享与保护

用户的角度：

* 按名存取

## 文件的组织结构

从用户观点出发，所看到的文件组织形式称为文件的逻辑结构。从实现观点出发，文件在外存上的存放组织形式称为文件的物理结构。 文件的逻辑结构与存储设备的特性无关，但文件的物理结构与存储设备的特性有很大关系。

### 文件的逻辑结构和存取方法

#### 文件的逻辑结构

文件的逻辑结构：是用户的可见结构，它独立于在外存上的物理存储。

文件的逻辑结构有两种形式：

* 字符流式的无结构文件
* 记录式的有结构文件

字符流式文件：一个无结构字节序列

* 文件体为字节流（不划分记录，构成文件的基本单位是字节），是无结构的、一串相关的有序字符的集合。
* 文件的长度为所含字符数。
* 缺点：查找文件中的基本信息单位较困难，如单词
* 优点：管理简单、操作方便 是当前操作系统中常用的文件逻辑结构， 如UNIX、DOS、WINDOWS系统中的普通文件都是流式文件。

记录式文件：一种结构式文件，是记录的集合

* 可以把文件中的记录按各种不同的方式排列，构成不同的逻辑结构
* 每条记录由彼此相关的域构成
* 每个记录有一个键，可按键进行查找
* 如果文件中所有记录的长度都相同，则这种文件为定长记录文件

常用的记录式结构文件有4种：

* 连续结构
  * 把记录按生成的先后顺序连续排列
  * 特点：
    * 适用性强，可用于所有文件
    * 记录的排列顺序与其内容无关（利于记录的追加）
    * 搜索性能较差（若要找出某个指定键的记录时，系统必须对文件全体进行搜索）
* 多重结构
  * 一个包含n 个记录名、m 个键的文件构成一个m\*n 维行列式
    * 如果第i行和第j列所对应的位置上为1，则表示键ki 在记录R 中；反之，则表示键Ki不在记录Rj中
    * 同一个键可以同时属于不同的记录
  * 以键Ki（i=1,2,3,…,m)为队首，以包含键Ki的记录为队列元素构成一个记录队列
  * 对于一个有m个键的队列来说，这样的队列有m个，这m个队列构成了该文件的多重结构
* 转置结构
  * 把含有相同键的记录指针全部指向该键，即把所有与同一键对应的记录的指针连续地置于目录中该键的位置下
  * 适合于给定键后的记录搜索
* 顺序结构
  * 把文件的键按规定的顺序（如字母顺序）排列起来
  * 适合于按某种顺序来搜索、追加、删除记录

#### 文件的存取方法

文件的存取方法：指用户读写文件的方法。用户通过对文件的存取来完成对文件的修改、追加和搜索等操作。

通常有三种存取方法：

* 顺序存取方式 按照文件的逻辑地址顺序存取
  * 在记录式文件中，按记录的排列顺序来存取，例如：当前记录为Ri，则下一条记录为Ri+1
  * 在字符流文件中，反映为当前读写指针的变化，例如：当前指针为rPtr，则下一存取位置的指针为rPtr + 该段的信息长度
* 随机(直接)存取方式
  * 根据记录的编号来存取文件的任一记录，或者是
  * 根据存取命令把读写指针移动欲读写处来读写。
    * 如果文件是定长记录的，只要给出记录号就能求出该记录的首地址。
    * 如果文件是变长记录结构的，直接存取将是非常困难的。
* 按键存取方式
  * 根据给定的关键字或记录名进行存取 首先搜索到要进行存取的记录的逻辑位置，再将其转换到相应的物理地址后进行存取
  * 用在复杂的文件系统中，特别是数据库管理系统中

### 文件物理结构与存储设备

文件的物理结构：指文件在外存上的存储结构。它依赖于外存的物理存储介质。

文件的物理结构决定了文件信息在存储设备上的存储位置。因此文件信息的逻辑地址到物理地址的变换也是由文件的物理结构决定的。

* 在文件系统中，文件的存储设备通常划分为若干个相等的物理块
* 一般把文件信息也划分为与物理存储设备的物理块大小相等的逻辑块
* 从而，以块作为分配和传送信息的基本单位

常见的文件物理结构：

* 顺序结构（连续文件）
  * 把一个逻辑上连续的文件信息依次存放到连续的物理块中。
  * 优点：结构简单，存取速度块
  * 缺点：不能动态增长，部分删除后会有“零头”
* 链接结构（串联文件）
  * 串联文件结构用非连续的物理块来存放文件信息。这些非连续的物理块之间没有顺序关系
  * 其中每个物理块设有一个指针，指向其后续连接的另一个物理块，从而使得存放同一文件的物理块链接成一个串联队列。
  * 特点：
    * 文件长度可动态地增长（只需调整在连接指针）
    * 搜索效率较低（只能按串联指针顺序搜索）
    * 一般只适用于逻辑上连续的文件，且存取方法应该是顺序存取的
    * 不适宜随机存取
* 索引结构（索引文件）
  * 系统为每个文件建立一张索引表，表中每一栏目指出文件信息所在的逻辑块号及与之对应的物理块号
  * 索引表的物理地址则由文件说明信息项给出
  * 特点：
    * 既可以满足文件动态增长的要求，又可以较为方便和迅速地实现随机存取
    * 使用索引表增加了存储空间的开销
    * 至少二次访问存储器，多级索引访问次数更多

索引表的组织

* 链接模式：一个物理块一个索引表。当文件很大时，一个物理块放不下一个索引表，则需要多个物理块来存放索引表，若也按串联方式存放，则增加了存放索引表的时间开销。
* 多级索引：索引表所指的物理块中存放的不是文件信息，而是装有这些信息的物理块地址
* 综合模式：将索引表的头几项设计成直接寻址方式，也就是这几项所指的物理块号中存放的是文件信息，而索引表的后几项设计成多重索引，也就是间接寻址方式

### 文件结构、文件存取方式与存储设备的关系

文件存储设备：常用的存储设备有磁盘、光盘和磁带等。存储设备的特性决定了文件的存储设备和方法

* 顺序存取设备（如磁带）
  * 只有在前面的物理块被存取之后，才能存取后续的物理块的内容
  * 为了加速和停转，在物理块前后留有间隙
* 直接存取设备（如磁盘）
  * 磁盘设备允许文件系统直接存取磁盘上的任意物理块。为了存取一个特定的物理块，磁头将直接移动到所要求的位置上。

文件结构、文件存取方式与文件存储设备的关系

| 存取设备 |       | 磁盘    |       | 磁带   |
| ---- | ----- | ----- | ----- | ---- |
| 物理结构 | 连续文件  | 串联文件  | 索引文件  | 连续文件 |
| 文件长度 | 固定    | 固定、可变 | 固定、可变 | 固定   |
| 存取方法 | 顺序、直接 | 顺序    | 顺序、直接 | 顺序   |

### 磁盘调度算法

磁盘调度： 磁盘是可被多个进程共享的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高校。 公平：一个I/O请求在有限时间内满足 高校：减少设备机械运动所带来的时间浪费

磁盘调度算法

1. 先来先服务（FCFS）：按访问请求到达的先后次序服务。

* 优点：简单、公平
* 缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利

1. 最短寻道时间优先（SSTF）：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先。

* 优点：改善了磁盘平均服务时间
* 缺点：造成某些访问请求长期等待得不到服务

1. 扫描算法（电梯算法，SCAN）：当设备无访问请求时，磁头不动；当设备有访问请求时，磁头按一个方向移动，在移动的过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求。

调度算法的选择：

* 最短寻道时间优先算法：实际系统普遍采用
* 扫描算法：磁盘负担中的系统
* 先来先服务算法：磁盘负担很轻的系统

## 文件存储空间的管理

无论是程序还是数据，所有信息都是以文件形式存放在外存上。所以，外存也称为文件存储器。外存上文件存放的空间也叫作“文件存储空间”。

文件存储空间通常是分成若干个大小相等的物理块，并以块为单位来交换信息的。因此，文件存储空间的管理实质上是一个空闲块的组织、分配和回收等问题。

常用的空闲空间的管理方法有：

1. 空闲文件目录法
2. 空闲块链法
3. 成组链接法
4. 位示图法

外存空闲块管理

1. 空闲块表（空闲文件目录） 将所有空闲块记录在一个表中，即空闲块表
2. 空闲块链表 把所有空闲块链成一个链
3. 成组链接法（空闲块链的扩展） 把文件存储设备中的所有空闲块按50块分为一组
4. 位图法 用一串二进制位反映磁盘空间的分配使用情况, 每个物理块对应一位, 分配物理块为1，否则为0。

### 空闲文件目录

把一个未分配的区域称“空闲块” 。将所有空闲块记录在一个表中，即空闲块表，其中空闲文件目录的每个表项对应一个由多个连续的空闲块构成的空闲区，主要包括：空闲块号、空闲块数和第一个空闲块号。

分配空闲块：

* 首先，扫描空闲文件目录项，如找到合适的空闲区项，则分配给申请者，并把该项从目录中去掉。
* 如果一个空闲区项所含块数超过申请者要求，则为申请者分配了物理块之后，再修改该表项。
* 如果一个空闲区不能满足申请者要求，则接着把目录中另一项分配给申请者（连续文件结构除外）。

回收空闲块：

* 系统把被释放的块号、长度以及第一块号置入空闲目录文件的新表项中。
* 相邻空闲区可以拼接成更大的空闲区。

空闲文件目录法的特点：

* 仅当有少量的空白区时才有较好的效果
* 如果存取空间中有大量的小的空白区，则其目录变得很大，因而效率大为降低。
* 比较适用于连续文件。

### 空闲块链

原理：把外存上的所有空闲块链接在一起

分配：当申请者需要空闲块时，分配程序从链头开始摘取所需要的空闲块，然后调整链首指针。

回收：把释放的空闲块逐个插入链尾上。

特点：易于实现，只需要在内存中用一个单元保留链头指针，但工作效率低。

空闲链常用的链接方法：

* 按释放的先后顺序链接法
* 按空闲区大小顺序链接法
* 按成组链接法

### 成组链接法

* 将磁盘上文件区中的所有空闲块分成若干组（如每50块作为一组）。组的划分是从后往前进行的
  * 每组的第一块用来存放前一组的总块数和各块块号
  * 第一组的块数为49块（第一组前已无其它组存在）
  * 最后一组可能不足50块，该组的物理块号与总块数放在文件资源表中（分配与回收都从最后一组开始进行）
* 当OS启动时，将文件资源表拷入内存中（使得空闲块的分配和释放都在内存中进行，减少了每次都要启动I/O设备的压力）

### 位图法

从内存中划出若干个字节，为每个文件存储设备建立一张位示图。在位示图中，每个文件存储设备的物理块都对应一个比特位。用0和1表示对应物理块是空闲还是被占用。

### 文件存储空间的管理小结

* 空闲文件目录：适用于连续文件
* 空闲块链接：效率较低，链较长
* 空闲块成组链接：UNIX系统中常用
* 位示图：常用于微型机和小型机

## 文件目录的管理

文件目录是文件系统实现按名存取的一个有效方法：系统为每个文件编制一个目录表，内容包括：文件名、物理地址、存取控制信息。

文件目录管理需要解决存储空间的有效利用，文件的快速搜索，文件命名冲突及文件共享问题。

### 文件组成

一个文件包括两部分：文件体和文件说明。

* 文件体：文件本身的信息。
* 文件说明（文件控制块FCB）：存放了为管理文件所需的相关信息，包括文件名、第一个物理块的地址、存取控制和管理信息等。
  * FCB是操作系统为管理文件而设置的数据结构，是文件存在的标志。
  * 文件说明组成目录文件。文件系统利用目录文件完成按名存取和对文件信息的共享和保护。

### 文件的目录

把文件说明按一定的逻辑结构存放到物理存储块的一个表目中，该表目称为文件目录。

文件目录可分为单级目录、二级目录和多级目录。

#### 单级目录

系统为所有存入系统的文件建立一张表，每一文件有一个表目。

在单级目录表中，各文件说明项处于平等地位。文件名与文件一一对应。

优点：简单且能实现按名存取。 缺点：不允许重名；当目录项过多时，查找速度慢；不便于共享。

#### 二级目录

为了解决单级目录中文件命名冲突问题和提高对目录的搜索速度，单级目录被扩充成二级目录。

二级目录结构中，各个文件的说明信息被组织成目录文件，且以用户为单位把各自的文件说明划分为不同的组。

目录分为两级：

* 主文件目录(MFD，Main File Directory) ：存放不同的组名的有关存取控制信息，包括用户名，用户子目录所在的物理始址等
* 用户文件目录(UFD，User File Directory)：存放用户文件的文件说明，即该用户所有文件的FCB，包括文件名，文件的物理始址等。

优点：解决了文件的重名问题和文件共享问题，提高搜索速度，查找时间降低 缺点：不太适合大量用户和大量文件的大系统，增加了系统开销

#### 多级（树型）目录

产生于UNIX操作系统，已被现代操作系统广泛采用。目录与文件在一起，目录也做成文件。

在多级目录结构中，除了最低一级的物理块中装有文件信息外，其它每一级目录中存放的都是下一级目录或文件的说明信息。

优点：

* 层次结构清晰，便于管理和保护 （不同性质、不同用户的文件构成不同的子树）
* 解决重名问题 （路径名是由从根开始到文件名为止的各级文件名组成）
* 查找速度加快 （每次只需查找多级目录的一个子集）

### 便于共享的文件目录

文件系统的一个重要任务就是为用户提供共享信息的手段（共享可节省存储空间，更好地维护数据的一致）。

从系统管理的观点看，有3种实现共享的方法：

* 绕道法
* 链接法
* 基本文件目录表BFD

#### 绕道法

绕道法要求每个用户处在当前目录下工作（当前正在使用的目录称为当前目录），用户对所有文件的访问都是相对于当前目录进行的。

为了提高文件检索速度，文件系统向用户提供当前目录。当前目录一般存放在内存。

绕道法需要用户指定所有要共享文件的逻辑位置或到达被共享文件的路径。

#### 链接法

为了提高共享其它目录中文件的速度，链接法是在相应目录表之间进行链接，也即，将一个目录中的链接指针直接指向被共享文件所在的目录。

链接法仍然需要用户指定被共享的文件和被链接的目录。

#### 基本文件目录表BFD

把文件的目录分成2部分：

* 基本文件目录BFD（Basic File Directory）
  * 该目录包括：文件的结构信息、物理块号、存取控制和管理信息等。
  * 由系统赋予唯一的内部标识符来标识。
  * 此目录以连续文件的形式存于卷头部，其长度决定卷内允许的最大文件数。
* 符号文件目录SFD（ Symbol File Directory ）
  * 由用户给出的文件名和文件的内部标识符组成。（用来建立文件名与文件说明标识符的一一对应关系）

### 目录管理

* 目录文件：目录以文件的形式存储在外存上
  * 目录文件的目录项存放文件说明信息或目录管理说明信息
* 系统初始启动时，把当前正在使用的那些文件目录项复制到内存中
  * 避免了在存取一个文件时需要多次访问外存完成对各级目录的搜索，减少了I/O次数
  * 避免了把所有的目录文件读入内存，节省了内存空间。

OS以系统调用的方式提供两种特殊的文件操作:

* 打开文件(fopen)：把外存上的目录文件复制到内存
* 关闭文件(fclose)：删除文件相关目录的内存副本。

系统打开文件的方式：（按BFD和SFD方式排列的多级文件目录） （１）把主目录 MFD中与待打开文件（如文件a.c ）相关联的表目项(Wang)复制到内存 （２）根据(1)所得到的标识符（ id=3 ），再将此标识符所指明的基本文件目录表BFD 的有关表目项复制到内存（包括存取控制信息、结构信息以及下级目录的物理块号等） （３）根据(2)所得到的子目录说明信息搜索SFD，以找到与待打开文件相对应的目录表项。如果找到的表目仍然是子目录名，则系统将根据其对应的标识符id，继续上述复制过程，直到所找到的表目是待打开的文件名（a.c） （４）根据(3)所搜索到的文件名所对应的标识符（id=5 ），把相应的BFD 的表目项复制到内存。

## 文件存取控制

文件的存取控制与文件的共享、保护和保密问题紧密相关。

* 文件共享：指不同的用户共同使用一个文件。
* 文件保护：指防止文件内容的破坏。
* 文件保密：指未经文件拥有者许可，任何用户不得访问该文件。

文件的存取控制问题实质上是一个用户对文件的使用权（读、写、执行）的许可权问题。即：

* 对于拥有读、写或执行权限的用户，应允许其对文件进行相应的操作
* 对于没有读、写或执行权限的用户，应禁止他们对文件进行相应的操作
* 应防止一个用户冒充其他用户对文件进行存取
* 应防止拥有存取权限的用户误用文件

控制验证模块验证用户权限的方式：

* 存取控制矩阵
* 存取控制表
* 口令
* 密码术

## 文件的使用

文件系统以系统调用或命令方式为用户提供下列4种服务：

* 设置和修改用户对文件的存取权限
* 建立、改变和删除目录
* 文件共享、设置访问路径
* 创建、打开、读写、关闭以及撤消文件

### 建立文件

用户要建立一个新文件，应向系统请求执行一个creat系统调用。系统收到请求后将做如下工作：

1. 合法性检查：

* 检查参数的合法性；
* 文件名是否符合命名规则；
* 合法执行2；否则，错误返回。

1. 检查同一目录下有无重名文件

* 不重名执行3；否则，错误返回。

1. 检查在目录中有无空闲位置

* 有空闲，申请数据块空间，执行（4）；否则，不成功返回。

1. 填写目录项内容：

* 文件名，用户名等，存取权限，数据块首地址

1. 返回

### 删除文件

当一个文件不再使用时，用删除命令可将文件删除。在删除文件时，系统将将做如下工作：

1. 从目录中找到要删除文件的目录项，使之成为空闲目录项
2. 回收该文件所占用的存储空间
3. 返回

### 打开文件

是使用文件的第一步：任何一个文件使用前都要先打开，即把FCB送到内存。步骤如下：

1. 根据文件路径名查目录，找到FCB
2. 根据打开方式、共享说明和用户身份检查访问合法性
3. 根据文件号查系统打开文件表，看文件是否已被打开

* 文件已经被打开，共享计数加1；
* 否则，将外存中的FCB等信息填入系统打开文件表空表项，共享计数置为1。

1. 在用户打开文件表中取一空表项，填写打开方式等，并指向系统打开文件表对应表项。

* 返回文件描述符fd，它是一个非负整数，用于以后读写文件。

### 读文件

把文件中的数据从外存读入内存的用户区。

* 在读一个文件时，须在系统调用中给出文件名和存放读出内容的内存地址。
* 系统查找目录，找到指定文件的目录项，从中得到被读文件的外存地址，然后从外存将数据读入内存。

### 写文件

当用户要求对文件添加和修改信息时，可用该命令将信息写入文件。

* 在写一个文件时，须在系统调用中给出文件名和写入信息的内存地址。
* 系统查找目录，找到指定文件的目录项，再利用目录中的文件指针将信息写入文件。

### 关闭文件

若文件暂时不用，应将其关闭。

* 关闭文件的功能是撤消内存中有关该文件的目录信息，切断用户与该文件的联系
* 若文件在打开期间作过修改，则应将其写回外存
* 文件关闭之后，若要再次访问该文件，则必须重新打开。

***

> 《计算机操作系统教程（第3版）》张尧学 史美林 张高 著