本系列文章为408考研操作系统知识点整理仅涉及到一些重要的考研知识点并不是完全系统全面的知识，参考书目和视频资料：汤小丹 计算机操作系统（第四版），操作系统考研复习指导，B站王道考研操作系统视频课。

4.1.1 文件的基本概念

文件:是以计算机硬盘为载体的存储在计算机上的信息集合，可以是文本文档、图片、程序等等。在用户进行输入和输出时，以文件为基本单位进行。正如管理进程一样，这么多的文件也需要被管理起来，所以操作系统中的文件系统(File System)的作用正在于此

4.1.2 文件的操作

读文件

双击某个文件背后实则调用了read系统调用。在调用read时需要指明是哪一个文件(open返回该文件的编号)，还需要指明要读入多少数据，以及读入的数据应该放在内存什么位置等问题。
操作系统在处理read时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中

写文件

在编辑完文件按下ctrl+s或者点击保存按钮时其背后实则是调用了write系统调用。在调用write时需要指明是哪个文件，还需要指明需要写出多少数据，以及写回外存的数据放在什么位置等问题
操作系统在处理wirte时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存区域中

删除文件

在进行delete系统调用时，需要提供如下主要的参数
文件存放路径
文件名
操作系统在处理delete系统调用时，主要做了如下事情
根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项
根据目录项记录的文件在外存的存放位置、文件大小的等信息，回收文件占用的磁盘块
从目录表中删除文件对应的目录项

打开文件

在很多操作系统中，对文件进行操作之前是要求必须先使用open系统调用打开文件的，需要提供以下主要参数
文件存放路径
文件名
权限信息（在linux中，r为读权限，w为写权限，x为执行权限）

根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，并检查该用户是否有指定的操作权限
将目录项复制到内存中的“打开文件表'中，并将对应表目的编号返回给用户。之后用户则使用打开文件表的编号来操作对应文件

需要注意的是，打开文件表有两种
进程的打开文件表：“读写指针"”这一列记录的是进程对文件的读写位置；“访问权限”记的是某进程对文件的操作权限；“系统表索引号”记录了该文件在系统的打开文件表中的位置
系统的打开文件表：“打开计数器”记录了当前有多少进程正在使用或者是占用该文件

关闭文件

操作系统在处理close系统调用时，主要做了如下事情
将进程的打开文件表对应的表项删除
回收分配给该文件的内存空间等资源
系统打开文件表的打开计数器count减一，若count=0,则删除对应表项

4.1.3 文件保护

为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，因此必须在文件系统中建立相应的文件保护机制。方法主要有：
口令保护
加密保护
访问控制

口令保护

可以文件设置一个“口令”，当用户请求访问该文件时必须提供“口令”。口令一般会存放在文件的对应的FCB或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比，只有正确才允许用户访问文件
优点：保存口令的空间开销并不大，验证口令的时间开销也很小
缺点：正确的“口令”存储在系统内部，不够安全

加密保护

对于口令来说，它存储在系统里是没有经过任何掩饰的。而对于加密，它分为明文和密文
明文：一组有意义的字符，或可由某种开发编码标准获得的信息。是我们一般影响中的密码
密文：由密码系统产生的信息和信号，明文采用一定的加密手段或者映射机制转换为密文。如果加密手段世漏那么密码就不安全了

优点：保密性强，不需要再系统中存储“密码”
缺点：加密解密耗费时间

访问控制

在每个文件的FCB中增加一个问控制列表(ASL),该表记录了各个用户可以对文件执行哪些操作

当用户太多时就不便于管理了，所以可以进行成组管理，标记各组用户对文件的权限

4.1.4 文件的逻辑结构

无结构文件

无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。比如Windows中的.txt文件就是无结构文件

有结构文件

有结构文件：由一组相似的记录组成，又称为“记录式文件”。每条记录又由若干数据项组成，同时每条记录有一个数据项可以作为关键字，以区分不同记录的ID。

顺序文件：逻辑上，让文件中的记录一个接着一个排列。记录可以是定长也可以是变长的。在物理上，记录可以顺序存储也可以链式存储

然后根据记录是否具有次序，顺序文件通常有以下两种结构
串结构：记录之间的顺序与关键字无关，通常的办法是由时间决定
顺序结构：文件中的所有记录按照关键字顺序排列

注意：

如果采用链式存储，那么无论是定长还是可变长记录，都无法实现随机存取
如果采用顺序存储且是可变长记录那么也无法实现随机存取
如果采用顺序存储且是定长记录那么可以实现随机存取，同时如果能够保证记录的顺序结构，则可以利用某些查找算法（例如二分查找)快速检索

索引文件：对于可变长记录文件，要找到第i个记录，就必须要顺序查找前i-1个记录，效率很低。所以对于可变长记录文件，可以建立一张索引表，索引表中的每一个索引项对应文件中的一条记录。同时索引表本身是一个定长记录的顺序文件，因此可以快速找到第i个记录对应的索引项。
可以将关键字作为索引号内容，若按照关键字顺序排列，则还可以支持关键字的二分查找
每当要增加或删除一个记录时，也需要对索引表进行修改
主要应用于对信息处理的及时性要求比较高的场合中
可以用不同数据项建立多张索引表

索引顺序文件：索引文件的缺点在于当记录数太多时将会导致索引表很大，甚至大于文件本身。而索引顺序文件是索引文件和顺序文件思想的结合，与索引文件不同的是，索引顺序文件在建立索引表时并不是每个记录都对应一个索引项，而是一组记录对应一个索引项
比如某个顺序文件有10000条记录，那么可以分为100组，每组100个记录。查找时需要先顺序查找索引表找到分组，找到分组后再在分组中顺序查找记录
索引顺序文件的索引项也不需要按照关键字顺序排列，这样可以极大地方便新表项的插入

4.1.5 文件的物理结构

前面得逻辑结构是文件内部的逻辑结构，下面介绍的是多个文件在逻辑上是如何组织的。

类似于内存分页，磁盘中的存储单元也会被划分为一个个的块，很多操作系统中，块的大小与内存块、页面的大小相同

内存与磁盘之间的数据交换都是以块为单位进行的，也即每次读入一块或每次写入一块

连续分配

连续分配：连续分配要求每个文件在磁盘上占有一组连续的块。支持顺序访问和直接访问，也即随机访问。且在顺序读/写时速度最快(因为磁头移动时间短)

由于是连续分配，所以各个块的相对地址是没有改变的，因此当用户给出要访问的逻辑块号时，只要操作系统找到该文件对应的目录项那么物理块号=起始块号+逻辑块号
所以文件目录中需要记录起始块号和长度（也即整个文件占用多少个块）

不过，由于连续分配要求每个文件占用的块是连续的，所以在拓展时如果剩余连续的块不够了就会产生迁移，十分不方便。另外连续分配还会使存储空间利用率变低，产生一些很难利用的细小磁盘碎片

链接分配

链接分配：链接分配采取离散分配的方式，可以为文件分配离散的磁盘块

隐式链接

隐式链接中，每个文件对应一个磁盘块的链表；磁盘块分布在磁盘的任何地方，除最后一个块外，其余块都有指向下一个块的指针，这些指针对用户来说是透明的。目录中则会记录文件存放的起始块号和结束块号。该种方式易于文件拓展，并且所有空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高

采用这种方式，当用户想要访问逻辑块号时，就必须从0号块开始依次顺序地访问到第i-1块，所以它不支持随机访问

显式链接

在显式链接中，会把所有指针从每个物理块中提取出来，显式的存放在内存的一张链接表中，该表在整个磁盘中仅设置一张，开机时将其读入内存，并常驻内存，称之为文件分配表(FAT)。同时在目录中仅需要记录文件的起始块号。FAT的各个表项在物理上是连续分配的，因而物理块号字段是隐含的。采用这种分配方式的文件，即支持顺序访问也支持随机访问，同时也不会产生外部碎片

当用户想要访问逻辑块号时，操作系统先找到FCB,然后从目录项中查找起始块号，然后查询FAT,就能找到号逻辑块对应的物理块了。并且逻辑块号转换为物理块号的过程不需要读磁盘操作

索引分配

索引分配：索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块，索引表的功能就像书的目录一样，需要哪个章节的内容，顺着目录查就可以了。索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块
FAT是个磁盘对应一张，而索引表是一个文件对应一张

由于可以用固定的长度表示物理块号，所以索引表中的逻辑块号可以是隐含的。

在该种方式下，当用户想要访问某逻辑块时，操作系统首先找到该文件对应的FCB,然后从目录项中可查得索引表的存放位置，将索引表读入内存后，再查索引表即可找到该逻辑块号在外存中的存放位置。所以索引分配方式支持随机访问，并且文件拓展也很容易实现

索引分配方式最大的一个问题就是索引块的大小，索引块理应尽可能的小，但是索引块太小的话就无法支持大文件了（反过来的意思就是当文件太大时，一个磁盘块是装不下索引表的)，所以常常会采用下面的机制来解决这个问题

链式索引块：如果索引表太大，那么可以将多个索引块链接起来存放，除最后一个索引块外，每个索引块最后都会留有一个指向下一个索引块的指针

当然这种方式的缺点也显而易见，由于是靠指针来维护，无非会产生以下问题
如果索引块太多，那么访问最后一个索引块就必须要前面的所有索引块都加载进来
如果某个指针损坏了，那么后面的数据自然就无法读取了

多层索引：类似以于多级页表。使第一层索引块指向第二层的索引块。如有需要，还可以建立更高层的索引块

混合索引：是多种索引分配方式的结合体。在混合索引中，一个文件的顶级索引表中，即包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表），还可能包含两级间接索引（指向两层索引表）

此外，访问文件需两次访问外存，先读取索引块的内容，然后访问具体的磁盘块，因而降低了文件的存取速度。为了解决这一问题，通常将文件的索引块读入内存，以提高访问速度。

混合索引分配

为了能够较全面地照顾到小型、中型、大型和特大型文件，可采用混合索引分配方式。对于小文件，为了提高对众多小文件的访问速度，最好能将它们的每个盘块地址直接放入FCB,这样就可以直接从FCB中获得该文件的盘块地址，即为直接寻址。对于中型文件，可以采用单级索引方式，需要先从FCB中找到该文件的索引表，从中获得该文件的盘块地址，即为一次间址。对于大型或特大型文件，可以采用两级和三级索引分配方式。UNIX系统采用的就是这种分配方式，在其索引结点中，共设有13个地址项，即i.addr(0)~i.addr(12),如下图所示

1)直接地址。为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用i.addr(O)~i.addr(9)来存放直接地址，即文件数据盘块的盘块号。假如每个盘块的大小为4KB,当文件不大于40KB时，便可直接从索引结点中读出该文件的全部盘块号。
2)一次间接地址。对于中、大型文件，只采用直接地址并不现实的。为此，可再利用索引结点中的地址项i.addr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1024个盘块号，因而允许文件长达4MB。
3)多次间接地址。当文件长度大于4MB+40KB(一次间接地址与10个直接地址项)时，系统还需采用二次间接地址分配方式。这时，用地址项i.add(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时在二次间址块中记入所有一次间址块的盘号。地址项i.addr(11)作为二次间址块，允许文件最大长度可达4GB。同理，地址项iaddre(I2)作为三次间址块，其允许的文件最大长度可达4TB。