文件管理

文件也属于系统资源，其就是一组有意义的信息、数据集合。

计算机中存放了各种各样的文件：

一个文件具有哪些属性？文件内部的数据应该被怎样组织起来？文件之间又应该怎么组织起来？从下往上看Operation System应该提供哪些功能才能方便用户、应用程序使用文件？从上往下看，文件数据应该怎么存放在外存（磁盘）上？

1一个文件具有哪些属性？

文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件标识符：文件名并不唯一，因为在不同文件夹中可以使用相同文件名。一个系统的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称类型：指明文件的类型。操作系统可以根据文件的类型设定一个默认的打开的应用程序位置：文件的存放路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）大小创建时间上次修改时间文件所有者信息文件的保护信息：对文件进行保护的访问控制信息。同一个文件对于不同的用户可能有不同的权限

2文件内部的数据应该被怎样组织起来？

无结构文件（例如文本文件）：由一些二进制或者字符流组成，又称“流式文件”有结构文件（例如数据库表）：有一组相似的记录组成，又称为“记录式文件”，记录是一组相关数据项的集合，数据项是文件系统中最基本的数据单位

具体如何组织起来，是文件的逻辑结构要讨论的问题

3文件之间又应该怎么组织起来？

树状结构，根目录下有很多目录，也有一些普通文件，而这些目录下，还可以创建更深一层的目录，以及存放一些普通文件...所谓目录，就是熟悉的文件夹。普通用户自己可以创建一层一层的目录，各层目录中存放相应的文件。系统中的各个文件就通过一层一层的目录合理有序地组织起来了。目录其实也是一种特殊的结构文件，由记录组成。

4Operation System应该向上提供哪些功能？

以创建一个txt文件并向其写数据、读数据为例

可以创建文件，点击新建之后，GUI进程在背后调用了“create系统调用”可以读文件，将文件数据读入内存，才能让CPU处理。双击文件后，记事本应用程序通过操作系统提供的读文件功能，即“read系统调用”，将文件数据从外存读入内存，并显示在屏幕上。可以写文件，将更改过的文件数据写回外存。在记事本应用程序中编辑文件内容，点击保存后，记事本应用程序将通过操作系统提供的写文件功能，即“write系统调用”将文件数据从内存写回外存…

向上提供的几个最基本功能：

创建文件：create系统调用删除文件：delete系统调用读文件：read系统调用写文件：write系统调用打开文件：open系统调用关闭文件：close系统调用

在读写文件之前，需要打开文件。这里的打开关闭文件不是常规的那种打开关闭有一点赋予相应权限的含义

很多操作可以使用这些基本操作组合完成

5从上往下看，文件应该怎么存放在外存中？

和内存一样，外存也是由一个个存储单元组成的，每个存储单元可以存储一定量的数据。每个存储单元对应一个物理地址。

类似于内存分为一个个“内存块”，外存会分为一个个“块/磁盘块/物理块”，每个磁盘的大小是相等的，每块一般包含2的整数幂个地址，同样类似的是，文件的逻辑地址也可以分为（逻辑块号，块内地址），操作系统同样需要将逻辑地址转换为外存的物理地址（物理块号，块内地址）的形式。块内地址的位数取决于磁盘块大小。

操作系统以“块”为单位为文件分配存储空间，因此即使一个文件大小只有10B，但他依然需要占用1KB的磁盘块。外存中的数据读入内存时同样以块为单位。

这里类比进程的调度，只不过此时对象是文件。

6其他需要有操作系统实现的文件管理功能

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

文件的逻辑结构

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

类似于数据结构中的逻辑结构和物理结构。例如线性表就是一种逻辑结构，在用户角度看来，线性表就是一组有先后关系的元素序列。

线性表这种逻辑结构可以用不同的物理结构实现，如顺序表/链表，顺序表的各个元素在逻辑上相邻，在物理上也相邻；而链表的各个元素在物理上可以是不相邻的。因此顺序表可以实现“随机访问”，而链表无法实现“随机访问”

可见，算法的具体实现与逻辑结构、物理结构都有关。文件也一样，文件的操作的具体实现与文件的逻辑结构、物理结构都有关。

按文件是否有结构进行分类，可以分为无结构文件、有结构文件两种

无结构文件

文件内部的数据就是一系列二进制流或字符流组成，又称“流式文件”。例如windows系统中的.txt文件。文件内部的数据实际就是一系列的字符流，没有明显的结构特性，因此也不需要讨论无结构文件的逻辑结构问题

有结构文件

有一组相似的记录组成，又称“记录式文件”。每条记录由若干个数据项组成。例如数据库表文件。一般来说，每条记录都有一个数据项可以作为关键字，作为识别不同记录的ID。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。可变长记录更为灵活，能更好地利用内存空间。

有结构文件的逻辑结构

顺序文件索引文件索引顺序文件

顺序文件

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

在物理上采用顺序存储额基础上，根据记录是否按照关键字顺序排列可分为串结构和顺序结构

串结构：记录之间的顺序和关键字无关顺序结构：记录之间的顺序按照关键字顺序排列

索引文件

对于可变长记录文件，要查找第i个记录，必须先顺序地查找前i-1个记录，这个时间复杂度为O(n)。而可变长记录文件却是在很多场景中都有应用，所以应当想办法去解决这个问题，让可变长文件中的记录也能被随机访问。由此引入了索引表

通过建立一张索引表来加快文件检索速度。每条记录对应一个索引项。包括索引号、记录的长度、指向逻辑文件中记录的指针。

索引表本身是定长记录的顺序文件。因此可以快速地找到第i个记录对应的索引项。

可将关键字作为索引号内容，若按照关键字顺序排列，对应的索引表还可以支持按照关键字折半查找。

每当需要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，所以主要用于对信息处理的及时性要求比较高的场合。索引表检索方便，修改复杂。

另外，可以用不同数据项作为关键字建立多个索引表。

索引顺序文件

因为如果一个记录就对应一个索引表项的话，那很可能索引表项需要的存储空间会比文件所需要的存储空间还大，这就带来了资源的浪费。所以由此引出了索引顺序文件。

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是，并不是每一个记录都对应一个索引表项，而是一组记录对应一个索引表项。也就是先将文件中的各个记录按照关键字进行分组，然后让索引表的表项对应一组记录，注意一个索引表项对应的是一组记录，不再是一个记录，这就大大地节省了存储空间。同时，每一个分组内的记录不需要按照关键字排序，所以一个分组就相当于是一个串结构的顺序文件。

可知这种策略可以让索引表瘦身，同时这种方式也是具有很高的检索效率的。

为了进一步提高检索效率，可以为顺序文件建立多级索引表。

文件目录

使用文件目录使得文件之间的组织结构清晰，易于查找；编程时也可以很方便地使用文件路径找到一个文件，用户可以很轻松地实现按名存取

文件控制块

文件控制块是用于实现文件目录的关键数据结构。

目录本身就是一种有结构文件，由一条条记录组成。每条记录对应一个放在该目录下的文件。每条记录包括了文件名、类型（txt、目录…）、存取权限（只读、只写、读/写…）、物理位置（外存x号块）等数据项。

当我们打开某一个文件夹（目录）时，操作系统会在当前所在的目录表中找到该文件夹名称的关键字对应的目录项，也就是记录。然后从外存中将该目录的信息读入内存，于是打开的目录中的内容就可以显示出来了。

一个文件目录项，也就是文件目录表中的一条记录，就是一个FCB，一个文件对应一个FCB（这个说法没问题，因为目录本身也是一个文件）。FCB的有序集合称为文件目录。FCB中包含了文件的基本信息（文件名、物理地址、逻辑地址、物理结构等等），存取控制信息（是否可读/可写，禁止访问的用户名单等等），使用信息（文件的建立时间、修改时间等等）

最重要的、最基本的是文件名、文件存放的物理地址。因为FCB实际上实现了文件名和文件之间的映射，使用户（用户程序）可以实现按名存取

操作系统需要对目录进行那些操作

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

目录结构

单级目录结构

整个系统只有一张目录表，每个文件占一个目录项。文件名也为目录项的一个属性。单级目录实现了按名存取，但是不允许文件重名。

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

显然，单级目录结构不适用于多用户操作系统

两级目录结构

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

主文件目录记录用户名及相应用户文件目录的存放位置，用户文件目录则是有FCB组成。

两级目录结构允许不同用户的文件重名，也可以通过检查此时登陆的用户名是否匹配得以在目录上实现访问限制，但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类

多级目录结构

又称为树形目录结构，不同目录下的文件可以重命名

用户或用户进程要访问某个文件时要用文件路径名标识文件，文件路径名是一个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。

例如：Me.jpeg的绝对路径是/Photos//Me.jpeg

系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表；找到“Photos”目录的存放位置后，从外存读入对应的目录表；再找到“”目录的存放位置，再从外存读入对应的目录表；最后找到文件“Me.jpeg”的存放位置。

注意，目录本身就是一个有结构文件，所以其也是存放在外存中，需要的时候获取进入内存。

很多时候，用户会连续访问同一目录内的多个文件。显然，如果每次都从根目录开始查找，是很低效的，所以可以设置一个当前目录。例如，此时已经打开了“Photos”的目录文件，也就是说，这张目录表已经调入内存，那么就可以把它设置为当前目录。当用户想要访问某个文件时，可以使用从当前目录出发的相对路径。

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。

由此提出了无环图目录结构

无环图目录结构

无环图目录结构实际上就是在树形目录结构的基础上多了指向同一个文件的有向边。树本身就是特殊的图。因为指向了同一个文件，所以就能实现文件的共享了。这种结构在删除文件时会有所不同，不一定是直接删除相应的文件本身，因为它可能还被其他目录所指向，所以借助每个文件的计数器存储指向该文件的目录数，来帮助删除文件操作的实现。

注意共享文件和复制文件是不同的，共享文件中，不同目录指向的是同一个文件，而复制文件则是不同目录指向各自不同的文件。虽然它们内容相同

索引结点

索引结点是在FCB的基础上进行改进，可以视为进一步地瘦身。因为是记载查找各级目录的过程中只需要用到文件名这个属性，只有文件名匹配的时候，才需要读出文件的其他信息。所以可以考虑对目录表精简后得到索引结点表来提升效率。

正是因为对目录表精简得到索引结点表，所以相应的用于检索的索引表所占用的内存空间减小了，一个磁盘内能包含的目录项增加了，也就是说对于目录项固定的情况，所需要的磁盘数减少了，那么在检索的过程中启动磁盘的次数也就减少了。因为IO操作是十分耗时的，所以启动磁盘的次数越少，就越能够提高效率。

只有当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据这个位置能够找到文件。

存放在外存中的索引结点称为磁盘索引结点，当索引结点放入内存后称为内存索引结点。

相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。