OS-Revision--文件系统_顺序文件记录寻址方式

27号还有最后一个实验报告要交。
“综合实验二”要实现的是基于C语言的文件系统设计。
那么我们肯定要先了解文件系统概念，架构，功能才行啦。

文件、记录和数据项

这三个概念需要理解一下后面会频繁涉及。

我们用一个班级的概念来形象解释各项的含义。
文件：是指具有文件名的若干相关元素的集合。对应于班级的概念，我们可以把一个文件视为包含所有学生信息的集合体-----正好是一个班级。

记录：一组相关数据项的集合，包含了一个对象的某个方面的属性。对应于上述，我们可以把一个学生视为一条记录。
这其中还有一个概念是“关键字”，表示的是能唯一地表示此条记录的数据项。比如对于某一条“学生记录”，学号就可以成为关键字。

数据项：是最低级的数据组织形式。就比如刚刚说的一条“学生记录”，里面有学号，姓名等等数据项。

文件和文件系统的一些概念

虽然刚刚提到了三个概念，但着重讲的一定是文件，毕竟是“文件系统”呗。
这些也都是一些繁琐的概念，如下图所示：

上图简单介绍了文件属性，文件按照不同条件可以划分为不同类型。
最后的文件操作可以说极大多数都是接触到过的。

文件系统的架构可以抽象成下图：

接口距离我们最近，我们接触的也最频繁，如open、close、create……
刚刚只是程序接口，我们还会在终端上运行很多命令。

中间和最下层的内容ppt都没提到，我也忘了老师上课有没有说。
可以简要了解，毕竟怕选择题：

逻辑系统层：处理和记录与文件相关的操作。
基本I/O管理层：完成与磁盘I/O相关操作，我们接触过的将逻辑编号转换为物理块号。
基本文件系统层：内存与磁盘数据交换。
I/O控制层：由磁盘驱动程序构成。

对象及属性管理的内容如下：
文件，不同类型的文件都被管理。
目录。目录项中包含了文件名、文件属性和文件的物理地址信息，方便索引存取。
磁盘存储空间，提高外存利用率，对文件和目录进行存储的分配。

书上讲了一段文件打开的过程。
根据用户需求，将文件从外存调入文件表进行打开并返回用户一个文件表的表号。
这样下次用户只要告知表号，系统自动去打开的表帮查找，就省去了从外存到文件表这个费时操作了。
相当于建立了一条连接，以后就靠连接进行访问。

文件结构

同样内容较多，可以直接看下表：

就比如一个文件夹是被我们用户所看到且能进行操作的，就是我们感知到的逻辑结构。
如上图所示逻辑结构可以分为有结构和无结构两种类型。
有结构文件说明：在记录式的文件中，每一条记录都描述了一个实体。根据记录的长度又可以分为定长记录和变长记录两种类型！

定长和变长概念是比较容易的。

记录中各数据项长度相同，所有记录中各数据项处于记录的相同的位置。这种结构易检索，方便做处理，数据处理中常用这样的格式。

变长就是不满足定长，虽然格式会不严格很多，但也适用于很多场合(假如医院是一个文件，病人就是一条记录，病因就是其中的一个数据项，显然病因不同，数据长度不同)所以还是得到了广泛应用。

无结构文件可以参照下图：
应该都很好理解，可以稍微记一下我们系统中的典型的无结构文件。

顺序文件

上上张图展示了有结构文件的组织形式划分。

顺序文件是比较常见的一种组织形式，比较简单易于实现。
顺序文件中的记录按照不同顺序进行排列，其实就是我们说的排序：
1.串结构。记录按存入时间进行排序，与关键字无关。所以我们在检索时基本需要一条一条地往下找，是比较耗时的一种方式。
2.顺序结构。用户指定关键字，按照关键字(如按英文字母顺序排列、按数值大小的升序和降序排列)进行排序。可以利用二分法等优秀的检索算法降低时间复杂度。

顺序文件的寻址方式：
一张简单的图示如下：

有两种寻址方式：

1.隐式寻址方式。
对于定长记录，已知当前记录的逻辑地址的话只要加上一个定长长度值L就可以跳转到下一个记录。上图a中指的是我们的读指针Rptr指向一个记录的首地址，要想读下一条记录，只要加上L即可。 对于读指针Wptr是一样的操作。

对于变长记录，我们需要先做的是得到当前这条记录的长度L。
如上图中的(b)，其中Li就是我们刚刚读完或者写完的长度。所以我们只要将指针从原先的位置加上Li就可以到下一条记录的首地址。

2.显示寻址方式。只对定长记录生效。
对于定长记录。假如长度是L，我们要查找第i块的话，相对于首地址的位置就是L × i。 通过此方式可以实现随机访问。

仅作了解，扩展知识吧
对于变长记录，我们需要增加一个字段，即在记录头用1Byte指明记录长度。
这样的话，我们要找到第i条记录的首地址就是：
对（Li+1）让i从 0 ～ i - 1进行求和，原理也是求出i - 1块的大小，计算相对位置大小。
这样一来也能进行随机访问。

我们还可以利用关键字，按关键字顺序一个个检索直到匹配。

顺序文件的性能如下表所示：

我们易知道，顺序搜索需要从头搜到尾来判定是否检索到。
平均时间复杂度是O(N/2)，因此有10000条记录平均查找是5000次。

索引文件

由于我们也想为变长文件设立比较好的随机访问方式，于是便有了索引表。
我们建立一张索引表，将每条记录进行保存，保存的是记录的首地址，记录的长度。索引表会有一个索引号，其实就是我们设立一个关键字，整张索引表按关键字排序。
按照上述规则，看懂下图示：

索引表本身就会成为一个定长记录文件，那么就可以进行随机访问。同时由于我们利用关键字排序，就可以在检索时利用折半算法等高效的算法。

多个索引表的索引文件。
建立多张索引表可以更好地满足实际的需求。
假如有一个图书馆文件，里面的记录是图书，图书有很多数据项，如名字、编号、作者……显然，书名不等长，作者有些有多个，是不定长的记录。

假如现在我们取每条记录的编号为关键字，构建一张索引表。显然得这是一个可行的方案，人们能高效地使用编号检索到图书的信息。
但人们不一定记得编号，有些人只记得名字的话就没办法了？
最简单的就是我们说的建立多张索引表，可以从你的记录中挑选多个数据项作为关键字进行索引表的构建。

索引顺序文件

顾名思义，这是一种综合了顺序文件关键特征–即记录按照关键字排序，又继承了索引文件的好处—可以为变长记录做随机访问。

一级索引顺序文件可以按下图理解：

从图上不难理解一些内容。
比如我们的顺序文件以名字为关键字，排序是首字母从小到大。
每50条记录为一组，并取组首记录构建一张索引表，此索引表的键指向的就是组的首地址。

以上图为例，用户给定一个关键字–名字。首先得到是在哪个组，再从组首地址进行顺序检索，也就是我们平均复杂度为O(N/2)的朴素检索方式。

接下来就是对各种检索算法的一个分析：

主要看一下最后那个“二级索引表”。
其实道理和一级索引表是一样的，无非对组概念上又增加了一个群。

对于检索次数的话由于假设索引表也是通过顺序检索的，那么每100个元素平均查找次数为50次，查找三轮。

外存分配方式

下图是外存分配的简要图：

我们着重来看的就是分配方式。

连续分配真的太好理解了，如下图所示：

比如有100个块，分配给A头5个块，B要100个块的话由于要求连续，A后面的95块直接就给浪费了。
还有除了上图的缺点就是，动态文件会动态改变大小，我们也很难决断。

在此基础上，引申出了链接分配方式。
上图是隐式链接方式，可以从左表看出我们需要保存文件占用的首盘块地址和结束盘块位置。其实就是我们数据结构中的链表，不难理解，盘块上的标号就代表着下一盘块。

有隐式就有显式，图示如下：

此技术主要的是我们需要维护一张链接表，就是我们上图里的FAT（文件分配表）表。
序号是物理块号，内容是指针，指向下一个盘块号。

但仅仅这样显然是不够的，我们无法知道首地址哈。所以我们需要填充信息到文件中，我们把首块的地址当作文件的起始物理地址填入文件信息即可。

上面的FAT表还有一个缺点就是我们想要检索一个文件时需要将整张表导入内存。实际上我们只要将某文件自己的所有盘块导入即可。
那么索引分配就如下图所示：

可以看到每个文件都有一张属于自己的索引表，表中记录自己所有盘块。
然后也对索引分配进行简单的性能分析：

对分配地址大小进行计算，先看图，后进行推导：
我们用i.addr(0) ~ i.addr(9)进行直接地址的分配。
基于我们知道的块大小为4KB，共10块，则地址范围就是 0 ～ 4 × 10KB。

一次间接寻址就是我们用一个4KB大小的盘块来索引盘块号，而不是直接存放内容。由于从上上图得知一个盘块号占4B，所以一个盘块可以索引 4KB / 4B = 1K个盘块！ （可以简单理解成一个4KB大小的盘块，每4B记录划分出一个号，这个才是真正的用于索引盘块的盘块号。）
所以文件大小最大为 1K × 4KB = 4MB。（1K个索引号可以映射1K个盘块，每个盘块4KB，直接相乘即可）

二级索引是类似的，就是在1级的基础上再次乘1K。
1K × 1K × 4KB = 4GB。

需要注意一点就是上面的1K，不是我们拿来看工资的1000哈，我们还是得从计算机的角度来理解，应该是 2¹⁰。

文件系统

讲了这么多文件的内容。
讲了文件的分类，着重讲了顺序文件、索引文件。也分析了有结构文件中的定长记录和变长记录两种类型。
然后还讲了外存的分配：
连续分配、链接分配、索引分配等。
索引分配我们还深入进行了多级索引求解可存放的最大文件长度的探讨。

首先要说的是文件目录的概念。文件目录是一种数据结构，标志了文件及其物理地址，对文件目录管理我们提出了下列要求：

我们为文件设立了一个可以用于描述和控制文件的数据结构称为FCB，长得和第一章的PCB进程控制块很像，这里就称为文件控制块。
文件控制块中包含了下图中的信息：

存储控制类信息有类似用户使用权限等。
还列出了MS文件系统的具体的FCB结构。无需背，了解即可。

我们设立FCB的主要目的就是对文件的管理。比如当我们检索某文件时，将盘块调入内存逐一对盘块中的文件目录进行用户提供关键字的比对，不成功的话调入下一块。我们调入盘块是耗时的！
可以看一个简单的小例子：

我们设定了FCB大小、盘块大小、以及一个目录文件包含的文件数量，根据这些内容我们求出需要多少盘块来存放，最后求平均调盘块次数。

我们对上述的一种改进措施就是让一个盘块能存放更多的信息！
在此优化思路上我们采用了一种索引节点的数据结构，看起来和之前变长记录采取的索引文件、外存的索引分配等很像。确实，我自己都怕搞混。

如下图所示：

当我们要打开某文件时，会将存放在磁盘的索引节点拷贝至内存。
同时内存索引节点还会新增一些信息：
标志内存索引节点的编号、
状态，用以表示此节点是否上锁或其他行为、
访问计数等等。

下图所示就是较完整的磁盘索引节点和内存索引节点的区别：

简单文件目录

单级目录特简单，如下图所示：

就是为每一个文件在目录中留下一条记录。
上图中文件创建和删除的流程可能需要稍微关注一下：
创建需要先检索目录看看有没有重名文件，没有就申请空目录项进行填入。
正因如此决定了单级目录无法实现文件重名。

且其是顺序查找，N个项平均要查找N/2个项。我们认为这是比较慢的。
不便于共享的原因是，每个用户都有自己的命名习惯所以本应当允许不同的用户按照不同的文件名访问同一文件才对，在这儿是不能实现的。

为了克服上述那么多缺点，设计了二级目录。
两级目录多了一级存放用户名和对应用户名目录指针的一张索引表。如下：

速度简述：
放单级目录，这些个文件需要 n × m个目录项，最多也就是访问n×m次。
两级目录会成为加法操作，如果m = n，速度会提高 n / 2倍。

树形目录。

根目录可以视为A、B、C三个用户。
为了保持灵活性目录项可以既是目录的FCB也可以是数据的FCB。
如用户A，其总目录下的A是目录项的FCB，因为其链接到目录项A C。
而总目录下的B D 则是数据6 7的数据文件FCB。
要做到上面的功能只要在FCB中设置一个位来进行辨别即可。

还有一些琐碎的知识如下图所示：

其中删除非空目录的第二种方案很危险，因为其不经过你询问直接剪枝。
相比起来递归删除虽说麻烦但更安全。

文件存储空间管理

第一种是空闲表法，很容易：

理解一下表的内容是：第一块空闲盘块以及从此盘块开始的空闲盘块数。
我们的malloc或者new也是这样的方式，是来连续分配的。
空间分配时的算法如上图所示，这两个算法很简单但没复习到先不说。

第二种是空闲链表法。
没有图，都是文字：但对链表知识掌握得扎实，理解和实现都不困难。

第一种方法的缺点是链表太长，分配虽然简单但要执行多次分配。回收也是多次，较为麻烦。

第二种方法分配和回收过程复杂。但链表短一些，且可以为文件分配多个连续块。因此效率会比较高。

再就是位示图法。
考点！老师说的！
但其实真的很简单，如下图所示：
ppt的位示图和书上位示图公式有一点出入，原因很简单，书上的二维数组是从1开始的。

此方法需要用于综合实验二？还没写，助教说的。

成组链接法，会稍微困难一些。
也是考点！

先看一下组织的规则：

配合规则我们对例图进行解读：

可以看到我们这儿其实有好多栈空间。
每个栈最多能保存100个盘块号，当栈满时我们的栈顶指针就是S.free(99)，因为从0开始。实际上除了盘块号，我们还会保存当前栈长度。

链接规则按照ppt来看有些难懂：
实际是把每一组，实际就这个栈的内容和上一组栈底盘块（正向看的话也可以说是第一个？）链接。

上图中实际上是我们假设了我们的第 201 ～ 7999号盘块是空闲的可以用于存放文件内容。

每100个会被分为一组。
那么我们的第一组就是201 ～ 300
第二组就是301 ～ 400，这里就利用到我们的链接规则，第二组会被链到第一组的最后一个盘块号上（就是ppt说的）。

需要看到的是最后一组是 7901 ～ 7999只有99个元素，会在free(0)标记一个0，表示链表的结束。

针对此方法的内存分配回收也不轻松，规则如下：

看规则可能又是懵得一批，看一道例题：

手画一下简图：

文件共享和文件保护

这里主要就是提了一下硬链接和软链接，这两个东西实验的时候实现一下就基本知道什么东西了。

如下图所示是硬链接的概念图：

索引节点我们在上面讲到过，其包含了文件的一些基本信息。
我们的硬链接就相当于一个指针指向文件的这些信息，从而将文件展示出来。

硬链接有一个特点就是，共享一个索引节点，就是我们Linux下的inode，所以即使我们的源文件被删除了 ，这些硬链接仍然还能够保持，你依旧能够打开它。

上面的表述并不精确，如果文件创始者删掉了文件，删掉了inode号明显共享者的指针就变空，会出现问题，那么在实验中为什么会出现上述现象？即我们以为删掉了源文件但打开硬链接仍旧没问题，实际上是这样的：

我们保留了一个count就是连接数，只要count不为0就只是在连接数上做处理，直到没有连接了，才会由系统进行彻底删除，这也就是为什么会产生上述现象的原因。

与之相对应的就是软链接：