第七章：文件管理

💡整理不易，先赞后看，养成习惯💡 ![O%F}9UA4W_8LRQDVU{%A3Q.png

7.1 文件和文件系统

文件的基本组成

文件的基本概念

💡文件是一组有意义的数据/信息的集合。

生活中常见的文件有很多中，例如图片、文档、表格等。
文件的存储就可以理解为在计算机中数据的存储，对于一个文件至少需要一下几个属性：

文件根据组织方式进行划分大致可以分为两类：

• 无结构文件：类似图片和文本文件，前者通过二进制流，后者通过字符流组成，又叫做流式文件。

• 有结构文件：类似Excel表格，通过一个个记录组成，又叫做记录文件。

  有结构文件

  对于有结构文件需要知道两个概念：

• 数据项：组成一条记录的基本单位

• 记录：多个数据项构成一条记录
• 关键词：一条记录中能唯一的标识出记录的基本/组合数据项

有结构文件通过多条记录组成，可以理解为多条记录的集合：

以上表格就可以理解为一个有结构文件。

文件名和类型

文件的名字一般分成两块：

其中文件名就是用户对于文件的命名，扩展名用于表示哦文件的类型。
文件的实际名称就需要两块加在一起。
文件类型有以下几种：

文件系统的功能

1. 统一管理文件的存储空间，实施存储空间的分配与回收
2. 实现文件的按名存取 名字空间 映射 存储空间
3. 实现文件信息的共享，并提供文件的保护和保密措施
4. 向用户提供一个方便使用的接口（命令接口、程序接口）（提供对文件系统操作命令，以及提供对文件的操作命令：信息存取、加工等）
5. 系统维护及向用户提供有关信息
6. 文件系统的执行效率文件系统在操作系统接口中占的比例最大,用户使用操作系统的感觉在很大程度上取决于对文件系统的使用效果.
7. 提供与I/O的统一接口

   文件系统的层次结构

   文件系统需要管理的部分

   文件系统的层次结构如下：
   
   从上图中我们知道文件系统需要管理的部分如下：

• 文件对象
• 文件的目录
• 磁盘的空间

管理文件对象很容易理解，文件需要清晰的整理肯定需要目录，所以管理目录也容易理解，为什么需要管理磁盘的空间呢？
因为实际上来说，电脑上所有的数据都是存放在磁盘上的（比如C盘），CPU是不和磁盘打交道的，电脑屏幕上想要显示数据，必须先把磁盘的数据调到内存，基于这一点，对于用户来说，所有的文件都是以“逻辑形式”存在于电脑上，文件系统需要做的就是做一个“映射表”，实现CPU可以通过文件的逻辑名到文件的实际磁盘存放地址做转换，从而达到CPU可以从磁盘中调取到需要的数据。

对对象操纵和管理的软件集合

一般的，把与文件系统有关的软件分为四个层次：

1. I/O 控制层，是文件系统的最底层，主要由磁盘驱动程序等组成，也可称为设备驱动程序层。
2. 基本文件系统层，主要用于处理内存和磁盘之间数据块的交换。
3. 基本I/O管理程序，用于完成与磁盘I/O有关的事务。
4. 逻辑文件系统，用于处理与记录和文件相关的操作。

   文件系统的接口

   通常就是两种：

• 命令接口：用户与文件系统交互的接口，用户可通过键盘终端键入命令，取得文件系统的服务。

• 程序接口：用户程序与文件系统的接口，用户程序可通过系统调用来取得文件系统的服务。

  文件系统的优点

• 方便

• 安全
• 统一

  文件操作

  
  对于文件的复杂操作，比如复制文件，就可以用上述的基本操作实现。

  假设要复制A文件，大概流程如下： 创建B文件->打开A文件->读取A文件->关闭A文件->打开B文件->写入A文件数据进B文件->关闭B文件.

一般来说打开文件之后，后续一定要跟着关闭文件。

上述的图了解就行，不会考的很深入的。

7.2 文件的逻辑结构

逻辑结构类型

逻辑结构，就是在用户看来，文件内部的数据应该是如何组织起来的。对应物理结构，就是在操作系统看来，文件数据应该如何存放在外存当中的。

逻辑结构划分如下：

文件系统找寻文件的速度是文件系统一项重要的评价指标。用户希望的肯定是操作系统能更快的找到文件所在的位置，方便用户进行查找数据。
对于无结构文件，其本身属于二进制流或者字符流，其文件大小不固定，在磁盘中的位置也没办法直接确定，所以此处不讨论如何优化查找无结构文件。有结构文件由于各项记录大致都相等，所以方便查找。
举个例子，对于一下这个文件，假设所有的数据项都是字符类型构成：

一个字符按照4B大小进行计算，我们可以知道：

上述文件的记录占用内存的格式都是固定的，每个数据项大小也是固定的，所以很容易知道一条数据的大小是16 + 8 + 24 = 48B并且前16B一定就是学号，知道了每一个记录的大小和位置也就容易知道整体文件的大小以及位置。
但是上述文件有个很明显的地方在于，每项数据项存储内容大小都是统一的，但更多情况是以下这种情况，也就是数据项大小不统一：

所以记录实际上也分为两种：

• 可变长记录：数据项的长度不固定
• 定长记录：数据项的长度统一固定

  顺序结构

  基本概念

  顺序结构的文件中，记录按照逻辑上顺序的方式进行存储记录，记录可以是可变长的，也可以是定长的。每个记录在物理上可以是顺序存储也可以是链式存储。

就好比数据结构中链表和数组的关系。

• 顺序存储：要求记录的实际物理地址必须相邻连续

  • 串结构：按记录生成的先后顺序连续排列的逻辑结构。（每次检索都要从头开始，效率低）
  • 顺序结构：把文件中的键（关键字）按规定的顺序排列起来。（采用折半查找等提高检索效率）

    简单来说就是针对文件的记录是否进行排序之后存储进行进一步划分

• 链式存储：记录的实际物理地址可以不连续，但是需要花费额外的指针

  记录寻址

  寻找文件中记录的地址的方式有两种：

• 隐式寻址方式

对于变长顺序文件，与顺序读或写时的情况相似，只是每次从记录中读出该记录的长度。同样需要设置读写指针，但在每次读或写完一个记录后，须将读或写指针加上Li, 它是刚读或刚写完记录的长度。
也就是说想要知道第i条记录的起始位置，就必须知道文件起始位置以及前i-1条记录的大小。

• 显式寻址方式

该方式用于对定长顺序文件实现直接或随机访问。对于定长记录文件，如果要查找第i个记录， 可直接根据下式计算来获得第**i**个记录相对于第一个记录首址的地址：
Ai=i×L
如果有关键词，则无需匹配记录的所有数据项，仅需匹配关键词即可进行查找。

顺序文件小结

索引文件

在上述的讨论中，可变长记录文件通常都无法进行随机存取，但是通常情况下很多文件基本都是可变长记录文件，为了使得可变长文件可以进行随机存取，就可以对于每个可变长记录建立索引。

关键词建立索引

操作系统通常会根据记录的关键词建立一张如下的索引表：

此时如果想要查找文件的记录的地址，就无需从磁盘中查找，只需要查找这个对应的索引表即可。
优点：实现了随机访问、能够随意修改、增加、删除
缺点：需要存储空间来存储索引表

多个索引表的索引文件

索引文件与顺序文件一样，都只能按关键字进行检索。实际中：不同的用户，为了不同的目的，希望能按不同的属性（关键字）来检索一条记录。为此，需要为顺序文件建立多个索引表。
每个索引表中，按相应的一种属性或关键字进行排序。
优点：将需要顺序查找的文件改造成一个可随机查找的文件，提高文件的查找速度。同时利用索引文件进行记录的插入和删除也非常方便。

顺序索引文件

一级索引顺序文件

💡索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是:并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

建立过程
首先将变长记录顺序文件中的所有记录分成若干组。然后为顺序文件建立一张索引表，并为每组中的第一个记录在索引表中建立一个索引项，其中含有该记录的关键字和指向该记录的指针。
检索过程
利用用户程序提供的关键字以及某种查找算法去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置，再顺序查找主文件，从中找到所要求的记录。

简单来说就类似是一个二级索引

如上图所示，所有姓名是A开头的记录都用An Qi作为索引。
对于一级索引文件的查找效率，如果一个顺序文件包含的记录数为**N**，则普通顺序文件检索到具有指定关键字的记录，平均须要查找N/2次。但对于索引顺序文件，平均只要查找N1/2。
举个例子：
示例：10000个记录。

• 顺序文件：平均需要查5000个记录才能查找到。
• 索引顺序文件：设100个记录一组，索引表的找法设为顺序法的情况下，则查找次数为50+50=100。

索引顺序文件的过程是这样的：

1. 首先在100个索引中，按照顺序寻找记录块的索引，这个过程平均需要100/2 = 50次
2. 找到所在索引之后，查询到对应记录块的首地址
3. 记录块100个索引为一组，所以接下来再对这100个记录进行顺序查找，同样平均需要100/2 = 50次

   两级索引顺序文件

   对于一个非常大的文件，为找到一个记录而须查找的记录数目仍然很多，为了进一步提高检索效率，可以为顺序文件建立多级索引，即为索引文件再建立一张索引表，从而形成两级索引表。
   示例：106个记录。先建立一张低级索引表，每100个记录一组，低级索引表含有104个表项。然后为低级索引表建立一张高级索引表，同样是100个索引表项一组，故有102个表项。则查找次数为50+50+50=150。

7.3 文件目录

我们知道多个文件一般会用文件夹进行归纳存放，这里的文件夹其实本质上也是一种文件，系统通过文件目录对文件实现管理，文件目录也是一种数据结构，用户表示系统中的文件及其物理地址，供检索时使用，对目录管理的要求如下：

• 实现“按名存取”：用户只需要向系统提供所访问文件的名字，便能快速准确的找到指定文件在外存的位置
• 提高对目录的检索速度：通过合理组织目录结构加快对目录的检索速度
• 文件共享：允许多个用户共享一个文件
• 允许文件重名：允许对不同文件采用相同的名字

  文件控制块和索引节点

  文件控制块FCB

  💡文件控制块是一种描述和控制文件的数据结构

这个概念就类似PCB，操作系统可以接触FCB完成对文件的操作和管理，和PCB一样，FCB和文件是一一对应的关系，即一个文件对应一个唯一的文件控制块。
通常来说，文件目录就是文件控制块的有序集合，一个文件控制块就是一个文件目录项。
前文所说过，目录也是文件的一种，一般称之为目录文件。

文件控制块需要包含的基本信息：

1. 文件名：文件的唯一名字，实现“按名存取”
2. 文件物理位置：文件在外存上的存储位置，设备名、起始盘块号、盘块数、文件长度
3. 文件逻辑结构：流式文件或记录式文件
4. 文件物理结构：文件是顺序文件、链式文件、还是索引文件

文件的信息按照如下方式进行存储：

在以上目录文件中的一条记录，就是一个FCB。

索引结点

索引结点是对于上述存储方式的改进。
还是以这张表为例：

假设一个FCB是64B，磁盘块的大小为1KB，则每个盘块中只能存放16个FCB。若一个文件目录中共有640个目录项，则共需要占用640/16=40个盘块。因此按照某文件名检索该目录，平均需要查询320个目录项，平均需要启动磁盘20次（每次磁盘I/o读入一块)。
实际上在查找文件的时候，只需要知道文件名即可，不需要知道文件的其他信息，所以这里就可以把文件名建立一个索引：

查询的时候先从这个索引表中查询到相应的目录项，根据指针找到对应的FCB即可。
若使用索引结点机制，文件名占14B，索引结点指针站2B，一条记录总共占据16B，则每个盘块可存放64个目录项，那么按文件名检索目录平均只需要读入320/64=5个磁盘块。显然，这将大大提升文件检索速度。
文件大部分是存储在外存当中，当用户需要调用文件的时候，操作系统会把相关的文件调入内存当中，所以文件的索引结点也有两种：

• 磁盘索引结点：存放在磁盘上的索引结点，每个文件有唯一的一个磁盘索引结点
• 内存索引结点：存放在内存上的索引结点，当文件被打开时，将磁盘索引结点拷贝到内存索引结点

  如果文件已经在内存中，则直接查找内存索引结点，否则查找磁盘索引结点，同时将此节点拷贝至内存。

简单文件目录

单级文件目录

早起的操作系统不支持多级文件目录，所以整个文件系统只建立一张目录表，每个文件占一个目录项目录项包括文件名、扩展名、文件长度、文件类型、物理地址、其他文件属性。
这也意味着计算机的所有文件都在一个目录下，其优缺点如下：
优点：简单，实现“按名存取”
缺点：

1. 查找速度慢
2. 不允许重命名
3. 不便于实现文件共享：每个用户使用不同的名字访问同一文件。

在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。

二级文件目录

💡二级文件目录为每个用户建立一个单独的用户文件目录UFD，系统中建立一个主文件目录MFD，在主文件目录中，每个用户文件目录占一个目录项

左侧的目录就是主文件目录，用于记录用户信息，右侧的用户目录记录每一个用户的具体文件信息。
很明显在这种分层下，不同用户之间就可以有重命名的文件。同样不同用户还可以使用不同的文件名访问系统中的同一个共享文件。与此同时提高了检索的速度。如果主目录中有n个子目录，每个用户目录最多用m个目录项，最多只需检索n+m个目录项。
上述方法对用户进行了分层，但是用户本身还是不能对于自己的文件进行分类管理，所以出现了树形文件目录结构。

树形文件目录结构

树形结构

树形文件目录结构又叫多级目录结构。其结构如图所示：

💡上图中方框代表目录文件，圆圈代表数据文件。

文件的路径按照次序用`/`进行划分，比如这里的`文件8`，其路径为：`C/G/文件8`。用户在访问文件的时候实际上就是通过这**文件路径名标识**进行访问。<br />**优点**：层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；提高文件检索速度；能进行存取权限的控制 <br />**缺点**：查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度

相对路径和绝对路径

系统查找文件的时候一般按照绝对路径进行寻找，即C/G/文件8，也就是从根路径开始寻找。如果此时我处于G文件夹下，想要寻找文件9，如果还是从根路径开始寻找，明显就浪费时间了，所以引入了相对路径的概念，也就是直接从G文件夹下开始寻找，此时系统需要寻找的路径就是./文件9。其中.表示从当前目录下开始寻找。

目录操作

这一部分看过一遍就行了，很好理解。

（1）创建目录
在树形目录结构中，用户可以自己创建UFD，并可继续创建子目录。当用户创建一个新文件时，只需查看自己的UFD及其子目录中有无与新文件相同的文件名，若无，便可在UFD或其某个子目录中增加一个新的目录项。
（2）删除目录
当该目录不再有任何文件时，直接删除。否则，可采用以下两种方法处理：

1. 不删除非空目录。当目录(文件)不空时， 不能将其删除，而为了删除一个非空目录，必须先删除目录中的所有文件，使之先成为空目录， 后再予以删除。如果目录中还包含有子目录，还必须采取递归调用方式来将其删除， 在MS-DOS中就是采用这种删除方式。
2. 可删除非空目录。当要删除一目录时，如果在该目录中还包含有文件，则目录中的所有文件和子目录也同时被删除。

（3）改变目录
用户可以利用改变目录的命令，通过指定目录的绝对或相对路径名设置当前目录。
（4）移动目录
到了一个阶段，通常都需要对目录组织进行调整，即将文件或子目录在不同的父目录之间移动。移动后，路径名也随之改变。
（5）链接操作
对于树形结构目录，每个文件和每个目录只允许一个父目录，这不利于文件共享，可以利用链接操作让指定文件具有多个父目录，从而方便共享。
（6）查找
文件目录比较庞大时，要查找指定文件是有点困难的。所有OS中都支持以多种方式进行查找。

7.4 文件共享

基本概念

文件共享就是一个文件被多个用户或程序共同使用。

其目的如下：

• 节省存储空间
• 减少用户工作量
• 进程间通过文件交换信息

  注意:多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。

常用的两种文件共享方法：

1. 基于有向无环图实现文件共享
2. 利用符号链接实现文件共享

   有向无环图实现文件共享

   有向无环图

   传统意义的树结构中，每个文件只允许有一个父目录(被一个用户所拥有)，其他用户访问，需通过父目录。
   为了实现共享，允许一个文件有多个父目录。
   
   上图中文件F8就是一个共享文件，D1可以看做用户目录。
   在上述情况下，不同的用户可以用通过不同的路径访问同一个文件甚至目录。
   这种方式有个缺点，就是文件的更新其实并不一定能同步到所有的用户。比如这里的文件F8，父目录有三个：D5的p、D6的e、D3的p。在三个父目录的特点就是都直接存储文件物理地址和大小。
   也就是说虽然文件是共享的，但是文件的记录项对应三个父目录有三个。此时如果D5的p为文件F8新增了数据，导致文件的盘块数增加，文件大小也就增加了，此时可能会发生文件物理地址的改变。这一改变会在D5的p中进行记录，单不会再另外两个父目录同步更新。
   这就导致一个问题：当前用户修改文件，其余用户的共享文件并不同步。

利用索引结点

为了解决上述共享文件修改记录不同步的问题，可以在目录和共享文件中间添加一个索引结点：

索引结点只需要记录文件的物理地址，用于指向文件即可，其余文件目录只需要指向索引结点。这样文件的修改就不需要进行同步，只需要修改索引指针的指向即可。
索引结点通常会记录三个信息：

• count：拥有该共享文件的用户数量（数量为0的时候，此文件可以删除）
• onwer：创建该共享文件的主用户
• 文件物理地址

  符号链接实现文件共享

  符号链接思路

  所谓的符号链接，可以理解为windows系统的快捷方式，这种快捷方式叫做LINK类型的文件。实现文件共享的思路如下：

1. 允许一个文件或目录有多个父目录，但其中只有一个作为主父目录
2. 其他父目录通过符号链接方式与之相链接

这张图里面虚线就是通过Link的方式链接到F8的。

具体实现

上图中，文件F8作为共享文件，主父目录就是D6的e，如何让D5的p共享此文件？

1. 系统创建一个LINK类型的文件，命名也为F8
2. 这个LINK F8文件中只包含被链接文件F8的路径名(符号链)
3. 将这个LINK F8文件写入D5的目录
4. 用户访问D5中F8时，OS截获路径名去找文件F8

D5的p目录下如果想要查找这个文件，就通过F8的路径名从根路径开始寻找。如果查找的时候发现文件已经被删除了，则会给用户进行报错，系统会将符号链删除。

优点和问题

优点

1. 只有文件主才拥有指向索引结点的指针，其它共享用户通过路径名访问（可以解决指针悬空的问题）。
2. 当文件主删除共享文件后，其他用户再次访问该文件，发现文件已经删除，系统会将符号链删除。

问题
访问速度慢；链接文件也要建立索引结点而由于链本身实际上是一个文件，尽管该文件很简单，却仍要为它配置一个索引结点，所以要耗费一定的磁盘空间；同一文件有不同的文件名。

7.5 文件保护

基本概念

影响文件安全性的因素

1. 人为因素
2. 系统因素

3. 自然因素

   采取的措施

4. 通过存取控制机制防止人为因素造成文件不安全。

5. 采取系统容错技术防止系统部分故障造成文件不安全。
6. 建立后备系统防止由自然因素所造成的不安全性。

   保护域

   如果一个系统需要多个用户，那么除去共享文件之外，每个用户的文件应该都是私密的，为了保证用户数据的安全，所以需要设计保护域。

   访问权

   为了对系统中的对象加以保护，应由系统来控制进程对对象的访问。对象可以是硬件对象，也可以是软件对象。对不同对象所施加的操作也有所不同。

   💡访问权：一个进程能对某对象执行操作的权利。每个访问权可用一个有序对来表示 （对象名，权集）。

示例:：F1, {R/W}, 表示某进程对文件F1有读和写的权利。

访问域

💡域：进程对一组对象访问权的集合，进程只能在指定域内执行操作。规定了进程所能访问的对象和能执行的操作。

访问矩阵

基本访问矩阵

利用矩阵描述系统的访问控制方式。其中行代表域，列代表对象，矩阵中每一项访问控制权集。

具有域切换权的访问矩阵

实现进程和域的动态联系，能够将进程从一个域切换到另一个域，把这里的切换作为一种权力。

举个例子：普通运行切换成**管理员运行。

其余权限

访问矩阵的实现（了解）

问题

• 概念简单，实现困难

• 矩阵的规模太大，占用大量存储空间

  解决方法

  用户访问对象数量有限，矩阵按行或列划分形成

• 访问控制表（按列划分） ：每列建立一张访问控制表ACL，删除该列中的空项

• 访问权利表（按行划分）：把访问控制表按行划分是同列（对象）中的权限访问权限表中的内容