文件系统基础与目录

初识文件管理

那么我们现在要了解一席文件内部的数据的组织方式与文件之间的组织方式。并且思考从下往上看OS是提供哪些服务方便用户、应用程序使用文件，而从上往下看文件数据又要怎么存放到外存（磁盘）的问题。

文件属性（文件构成）

文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。
标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用来区分各文件的一种内部名称（同样的，操作系统为各个进程是通过PID来识别的）。
类型：文件的类型
位置：文件存放的路径（让用户使用），在外存中地址（操作系统使用，对用户不可见）
大小：文件的大小
创建时间，上次修改时间，文件所有者信息等
保护信息：对文件进行保护的访问控制信息

文件内部的组织方式

无结构文件：如文件文件，就是一些由二进制或者字符流组成，又称“流式文件”
有结构文件：如数据库表，由一组相似的记录组成，又称"记录式文件"，这里要注意记录是一组相关数据项的集合，而数据项才是文件系统中最基本的数据单位。

文件之间的组织组织方式

实际上就是通过目录来实现分层，这里的层最好不要太少（这样会造成目录下文件密度过大），同时也不要太多，否则分层太多，搜索查找文件时间开销大。

思考：文件夹是有结构文件吗？

当然是，用过电脑的都知道文件夹可以以文件项排列各文件的详细信息，很明显每一个文件此时都是一个记录，而每一个文件的具体文件名，大小，创建时间等就是文件夹这一个记录式文件的数据项。

OS向上提供的服务

创建文件：可以“创建文件”，点击新建后，图形化交互进程在背后使用“create系统调用”
删除文件：可以“删除文件”，点击删除操作之后，图形化交互进程通过操作系统提供的“删除文件”功能，即delete系统调用，将文件数据从外存中删除
读文件：将文件数据从外存中读入内存，这样才能让CPU处理，使用的是read系统调用
写文件：将更改过的数据写回外存，使用的是write系统调用
打开文件：读/写之前需要打开文件
关闭文件：读/写文件结束之后需要关闭文件

基本上更多复杂的功能都是通过上面的基本功能组合实现的。

文件如何存放至外存

我们发现其实这个就是分页存储的思想，所以外存中与内存一样也是分成一个一个存储单元然后将文件切割离散存储，当然如果文件特别小，那么一个存储单元就可以放下整个文件，所以明显外存中也会有内部碎片。

思考：这里我们思考是不是外存中也会有连续存储的方式？

肯定是有的，这里也有固定分区分配的存储思想和分页存储思想两种方式存储文件。

操作系统需要完成的其他文件管理的操作

文件共享：使多个用户共享一个文件
文件保护：保证不同的用户对文件有不同的操作权限

总结

大部分都是概念性知识点，记住即可

文件的逻辑结构

类似于数据结构的“逻辑结构”和“物理结构”，如线性表就是一种逻辑结构，在用户看来，线性表就是一组有先后顺序的元素序列。而线性表这种逻辑结构可以通过许多种物理结构实现，不如顺序表和链表均可以，顺序表是元素在逻辑和物理上都是连续相邻的，而链表是物理上不相邻但是逻辑上相邻的数据结构。所以顺序表的线性表可以随机访问，而链表形式的线性表就不可以了。所以算法的具体实现与逻辑结构和物理结构都有关（文件也是一样，文件操作的具体实现和文件的逻辑结构，物理结构有关)

无结构文件

首先无结构文件前面也提到过了就是“流式文件”是一组二进制或者字符流，所以没有明显的结构，也就不用讨论“逻辑结构”的问题。

有结构文件

前言：记录的分类

记录式文件，每条记录都是由若干个数据项组成的集合。一般来说，每一条记录的一个数据项都是一个关键字（可以作文识别不同记录的ID）。

根据各条记录的长度我们可以将记录分为定长记录和可变长记录：

定长记录：一般每条记录的长度是必须等长的，每一个数据项所在位置也都是相同不变的。
可变长记录：数据项的长度不一定相同因此记录的长度也是各不相同的，甚至某一个数据项没有是可以删掉的即下图中如果无特长可以直接删掉。

顺序文件

文件中的记录一个一个的地顺序排列（逻辑上），记录可以是定长或者变长的。各个记录在物理上可以是顺序存储或者链式存储。

根据记录之间的顺序是否与关键字有关我们分成：

思考：加入现在知道文件的起始位置，那种文件可以快速找到第i个记录的位置？那种文件又可以找到某个关键字对应的记录的位置？

首先链式存储肯定是不可能实现随机随机存放的，所以每次都需要从头开始查找这样很难快速找到第i个文件的位置。所以快速查找只能在顺序存储中，又由于可变长记录长度不相同不能使用X+i*M的连续查找公式所以也不能和实现快速查找，所以只有定长记录的顺序存储才可以实现，同时只有采用顺序结构即存储的顺序和关键字有关的才可以找到关键字对应的记录的位置。

很明显从上图我们就可以看出可变长记录不能随机存取的原因了，由于长度不同，连续查找公式是不能使用的。定长记录的顺序文件，如果采用物理上的顺序存储那么就可以实现随机存取。如果还能保证记录的顺序结构那么就可以关键字快速检索了。一般上，考试题中的“顺序文件”指的是逻辑结构和物理结构上都是顺序存储的文件。所以顺序文件一般如果不说都是默认定长记录所以可以随机存放，但是缺点是增加/删除一个记录就很复杂，需要整体记录前移或者后移，但是如果是串结构那么就相对简单。

索引文件

对于很多场景都需要快速查找都第i个记录的位置，但是又是可变长记录文件，那么这时就需要索引文件的逻辑结构形式，即建立一张索引表，每个索引表都有唯一的索引号，长度m(毕竟是可变长的需要记录)以及一个指针ptr指向文件再外存中存放的地址，所以索引文件在结构上还顺序的，但是物理结构上是可以离散存储的，当然如果你非得在物理结构上也顺序存储也可以。

其实感觉就是分页存储的思想，只不过那个是讨论内存存放时提出的方法，现在这种思想应用在了文件管理上，实际上思想类似。索引表本身是定长记录的顺序文件（这里指的是物理结构上也顺序存储，否则不能实现随机存取），因此可以快速找到第i个文件的索引项。并且可以在索引表中以关键字作为索引号内容，若按照关键字顺序排列，那么还可以实现按照关键字折半查找。这是我们在尝试删除/增加一个记录时就是对索引表进行修改。因为索引表有很快的检索速度，所以主要用于对信息处理的及时性要求很高的场合。并且，可以用不同的数据项建立很多个索引表，如：学生信息表可以用关键字“学号”“姓名”都各建立一张索引表。这样就可以根据不同的关键字检索文件了。

索引顺序文件

我们思考一个问题，每个记录都会对应一个索引表项，因此索引表可能会非常巨大。比如：文件的每个记录平均只占8B，而每个索引表项占32个文件，那么索引表都要比文件本身还要大4倍，这样就降低了空间利用率。所以提出了索引顺序文件。

我们可以看出索引顺序文件的索引项不需要按关键字顺序排列，这样就极大方便新表项的插入，同时在上图中我们发现学生记录按照学生的姓名开头字母进行分组，每一个分组就是一个顺序文件，分组内的记录不需要按关键字排序。索引顺序文件就是索引文件和顺序文件思想的结合。索引顺序文件同样会为每个文件建立一个索引表，但是不是每一个记录对应一个索引表项，而是每一组数据对应一个索引表项。然后每一组文件中顺序存储，这样就大大瘦身了。

思考：三种文件的区别？

顺序文件就是顺序存放，那么查找时如果是不定长就只能逐一查找并且顺序存放不好增删所以出现索引文件每一个记录对应索引表一定长个表项，索引表是物理顺序存放那么查找时就可以很快找到并且增删只需要修改索引表项，但是空间会很大毕竟索引表项和文件各占用很大的空间，所以索引顺序文件是将整个文件组按某些标准分成许多组然后为每个组建立一个索引表这样就实现了瘦身。

思考：用这种索引顺序策略能否解决不定长记录的顺序文件检索速度慢的问题？

我们假设现在有一个10000个记录的顺序文件（不定长记录的物理结构顺序存储的顺序文件），那么如果根据关键字检索文件，只能从头开始顺序查找，平均需要查找5000个记录。

如果是索引文件，虽然表项定长，但是索引文件只是在已知起始地址查找第i个文件时加快了速度，现在是要查找某个关键字的搜索，那么也只能从头开始顺序查找，所以最终也是5000次平均查找。

如果使用的是索引顺序文件结构，可以把10000个记录分成100组每组100个记录，那么先顺序查找索引表找到分组（共100个分组，所以平均需要查找50次）然后找到分组后再在分组中顺序查找记录也是平均需要50次，那么最终只需要100次。很明显确实相较于顺序文件和索引文件有了检索速度的提升。

思考：但是如果现在是10^6的记录怎么办？

我们发现如果是10^6个记录，那么此时索引顺序文件的查找次数还是很大，所以此时多建几层次级索引表就好了（毕竟每建一层索引表理论上会减少查找没有必要的多组文件），所以此时就是多级索引顺序文件如下：

此时对于一个10^6记录的文件(注意还是可变长记录文件），可以先为该文件建立一张低级索引表，每100个记录为一组，所以总共会有10000个表项，即10000个定长的表项，然后再把这10000个定长记录再次分组为每组100个再为其建立顶级索引表，那么顶级索引表就有100个定长表项。

这里有个公式：N个记录的文件建立K级索引，则最优的分组是每组N^(1/K+1)个记录。这样检索一个记录的平均查找次数是

(N^{1/K+1}/2)*(K+1)

次，例如上面我们分成了2级，那么每组就是(10^6)^1/3=100个记录，并且平均查找次数就是（100/2)*(2+1)=150次。

总结

文件目录

文件控制块

思考当我们双击照片这个文件夹后OS是如何找到文件夹下的文件和显示到我们屏幕上的呢？

实际上此时是借助文件控制块实现的，我们双击“照片”后，操作系统会在这个目录表中找到关键字“照片”对应的目录项（也就是记录，毕竟记录就是存得许多不同的数据项也就是关键字），然后从外存中将“照片”目录的信息读入内存，于是“照片”目录中的内容就可以显示出来了。所以我们所说的目录实际上就是一个索引表。

那么目录文件中每一条记录实际上就是一个文件控制(FCB),FCB实现了文件名和文件之间的映射，使得用户(用户程序)可以实现“按名存取”。FCB的有序集合就成为“文件目录”，一个FCB就是一个文件目录项。FCB中包含了一个文件的基本信息，存取控制信息使用信息等。当然最重要的就是文件名和文件存放的物理位置。

那么通过文件控制块FCB我们可以实现哪些功能呢？

搜索：当用户使用一个文件时，系统根据文件名搜索目录，找到该文件对应的目录项。
创建文件：当创建一个文件时，需要在所属的目录中增加一个记录项。
删除文件：当删除一个文件时，需要在目录中删除相应的目录项。
显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应的属性。
修改目录：某些文件属性保存在目录中，因为这些属性变化时需要修改相应的目录项（如：文件重命名等）。

目录结构

单机目录结构

早期的操作系统不支持多级目录，所以整个系统只建立一张目录表，每个文件占据一个目录项，单机目录实现“按名存取”，不允许有任何文件重名。在创建一个文件时，需要先检查目录中有没有重名文件，只有确定不重名后才能建立文件，并将新文件对应的目录项插入到目录表中。

很显然，不适合多用户(这里的用户值得是多程序,应用软件)操作系统。想一想也知道现在的应用程序肯定都有许多重名文件例如：data,dist.source,js等

两级目录结构

早期的多用户操作系统采用两级目录结构，分为主目录(MFD,Master File Directory)和用户文件目录(UFD,User File Directory)。

此时就允许有重名文件了只要不在一个FCB下，但是此时还是不够灵活，毕竟用户文件夹可能也需要有自己的目录，所以就有了多级目录结构。

多级目录结构

又称树形目录结构，灵活高效，解决了上面两种目录结构的缺陷。

此时因为有许多可能重名的文件但是他们所在的位置是不同的，所以要访问某个文件时要用文件路径标识文件，文件路径是一个字符串。各级目录之间用"/"隔开，从根目录出发的就是绝对路径，从当前位置或者当前位置的父目录出发就是相对路径。例如：./就是相对路径表示从现在的位置出发，…/是从当前位置的父文件开始出发明显也是相对路径，但是…/或者/就是根目录出发就是绝对路径了。

思考：为什么要用相对路径？

考虑一个问题现在我们要对某个文件夹下的许多文件进行操作，那么如果使用绝对路径，那么每一次都要输入很长的根目录路径明显低效，而如果此时使用相对路径./就很方便简洁。同时不仅仅是为了输入简便，如果我们使用绝对路径，那每一次都需要从根目录开始逐一从外存读入对应的目录表，然后在找到该文件夹下的文件，而是用相对路径就可以直接一次性将这个文件夹读入内存然后访问文件。可以见到，在引入“当前目录”和“相对路径”以后，磁盘的I/O次数减少了，这样就提升了访问文件的效率。所以相对路径是常用的文件路径方式，当然对于某些特殊的情况是必须使用绝对路径的。

所以树形目录结构不仅可以很方便的对文件进行分类，层次结构清晰，而且也能够更加有效的进行文件的管理和保护。但是树形结构不便于实现文件的共享，所以提出了“无环图目录结构”。

无环图目录结构

可以用不同的文件名指向一个文件，甚至可以指向同一个目录（共享一个目录下的所有内容）。需要为每一个共享节点设置一个共享计数器，用于记录此时有多少个地方在共享该节点。用户提出删除节点的请求时，只是删除该用户FCB、并且使共享计数器减1，并不会直接删除共享节点。直至共享计数器为0时，才删除节点。

我们发现共享文件不是赋值文件。在共享文件中，由于各用户指向的都是同一个文件，因此只要其中一个用户修改了文件数据，其他所有用户都可以看到文件数据的变化。

FCB的改进

我们之前进行的瘦身策略，实际上是对目录项进行分组然后多级索引表的存储，但是对于同一个目录下的目录项最好是对应一个目录表，那么该怎样实现瘦身呢？我们可以对FCB进行修改，毕竟查找时只是按照“文件名”进行查找，只有文件名匹配才能读出文件的信息，所以可以考虑让目录表瘦身吗，如下：

瘦身前：

瘦身后：

思考：好处是什么？

假设一个FCB是64B，磁盘块大小为1KB=2^10B，那么每个盘块只能存放16个FCB，如果一个文件目录中共有640个目录项，那么需要占640/16=40个盘块。因此按照某文件名检索目录平均需要查找320个目录项，平均需要启动磁盘20次（每次磁盘I/O读入一块）。但是如果瘦身后即使用索引节点机制那么文件名占14B，索引节点指针占2B，一个FCB只占用16B，那么一个盘就可以放64个目录项，那么按文件名目录平均只需要读入320/64=5个磁盘块。显然这就大大提升了文件检索速度。

只有找到文件名对应的目录项才会将索引节点放到内存中，索引节点中记录了文件的各种信息，包括在文件再外存中的位置，根据“存放位置”即可找到文件。存放在外存中的索引节点就叫做“磁盘索引节点”而当索引节点放入到内存后就称为“内存索引节点”。相比之下内存索引节点需要增加一些信息，比如：文件是否被修改，此时有几个进程正在访问该文件等。