文件定义

是由创建者所定义的，具有文件名的一组相关元素的集合

文件分类

【资料图】

按用途分：系统文件、用户文件、库文件

按存取控制属性分：只执行文件、只读文件、读写文件

按组织形式和处理方式分：普通文件、目录文件、特殊文件

按数据形式分：源文件、目标文件、可执行文件

文件的操作

建立（create系统调用）

找到文件所需的空间、

创建该文件对应的目录项

删除（delete）

找到文件名对应的目录项

回收文件占用的磁盘块

删除文件对应的目录项

打开（open）

找到文件名对应的目录项

将目录项复制到内存中的打开文件表中，用户使用打开文件表的编号来指明要操作的文件

每个进程都有打开文件表，系统有一张总的打开文件表

进程打开文件表特有属性：读写指针、访问权限

系统打开文件表中特有属性:打开计数器

关闭（close）

将进程打开文件表相应表项删除

回收分配给该文件的内存空间等资源

系统的打开文件表的打开计数器count减一，若count=0，则删除对应表项

读（read）

根据读指针，读入数据量、内存位置将文件数据从外存调入内存

写（write）

根据写指针，写出数据量、内存位置将文件数据从内存写出外存

文件的逻辑结构

无结构文件（流式文件）如文本文件

有结构文件（记录式文件）如数据库表

每条记录有一个数据项可作为关键字，根据各条记录的长度是否相等，可以分为定长记录和可变长记录。

根据有结构文件在逻辑上如何组织可以分为以下三类

顺序文件：存取速度快，插入或删除记录困难，不利于动态扩充。可变长文件无法实现随机存取，只能从第一个记录开始往后找。定长记录可以实现随机存取，采用顺序结构可以快速的找到关键字对应的记录。

串结构：记录之间的顺序与关键字无关。

顺序结构：记录之间调度顺序按关键字排序排列

索引文件：检索速度快，插入或删除记录方便，系统开销大。本身是定长记录的顺序文件，主要用于对信息处理的及时性要求比较高的场合。可以用不同的数据项建立多个索引表。

索引顺序文件：顺序存取速度快，随机访问，增、删、改记录方便。与索引文件不同的是，并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

在检索效率分析上，顺序文件由10000个记录，从头开始顺序查找，平均查找5000个记录。采用索引顺序文件，可以把10000个文件分为100组，每组100个记录，需要先顺序查找索引表扎到分组，平均50次，找到分组后再顺序查找记录，平均50次。一共平均查找次数为100次。

为了进一步提高查找效率，可以建立多级索引表，对于一个1000000个记录，可以建立一张低级索引表，每100个记录为1组，低级索引表中有10000个表项，再将这10000个记录分组，每组100个，建立顶级索引表。顶级索引表有100个表项。

为n个记录建立k级索引，最优的分组是每组。检索一个记录的平均查找次数为(/2)*(k+1)。

文件目录

文件控制块（FCB）：包含基本信息、存取控制信息、使用信息

FCB的有序集合被称为“文件目录”，一个FCB就是一个文件目录项。FCB包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息，使用信息。最重要最基本的还是文件名、文件存放的物理地址。

索引节点：包括磁盘索引节点和内存索引节点

目录结构：单级目录结构、两级目录结构、树形目录结构、图形目录结构

单级目录中，整个系统只建立一张目录表，每个文件占一个目录项，实现了按名存取，不允许文件重名。

早期多用户操作系统中，采用两级目录结构，分为主文件目录和用户文件目录。主文件目录记录用户名和相应的用户文件的存放位置。允许不同用户的文件重名，文件名相同但是对应的文件不同。可以再目录上实现访问限制。

多级目录结构（树形目录结构）用户访问某个文件要用文件路径名标识文件，各级目录之间用“/”分开，从根目录出发的路径被称为绝对路径。系统根据绝对路径一层一层找到下级目录，最开始从外存读入根目录的目录表，找到下级目录后，再从外存继续读入目录表。可以设置一个当前目录，使得不用每次从根目录查找。在linux中，“.”表示当前目录。引入当前目录和相对路径后，磁盘I/O的次数减少，提升了访问文件的效率。

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

在无环图目录结构中，可以使用不同的文件名指向同一个文件，甚至可以指向同一个目录。需要为每个共享结点设置一个共享计数器，记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB，并使得共享计数器减一。只有共享计数器减为0时，才删除结点。在共享文件中，各个用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。

索引结点改进：在FCB中只记录文件名和索引结点指针字段，其他文件描述信息全部存放到索引节点上。这样的话每个磁盘块可以多存放目录项，大大提升文件检索速度。存放在外存中的索引结点称为磁盘索引结点，放入内存后称为内存索引结点。内存索引结点需要增加一些信息，如文件是否被修改，当前有几个进程正在访问该文件。

文件共享

硬链接（基于索引结点）和软链接（符号链接）

硬链接：在索引结点上设置一个链接计数变量count，表示链接到本索引结点上的用户目录项目数。若某个用户需要删除该文件，则只需把用户目录中与该文件对应的目录项删除，且索引结点的count减一。若count>0,则不能把文件数据删除，当count=0时，系统负责删除文件。

软链接：当访问文件时，操作系统判断该文件属于link类型文件，会根据其中记录的路径层层查找目录，最终找到找到最终目录表的表项，类似于快捷方式。即使软链接指向的共享文件已被删除，link文件依然存在，只是通过link型文件中的路径区查找共享文件会失败。用软链接访问共享文件会查询多级目录，会有多次磁盘I/O，因此访问共享文件的速度要比硬链接慢。

文件的物理结构

磁盘块的大小与内存块，页面的大小相同

在外存管理中，文件的逻辑地址空间被分为了一个一个的文件块。文件的逻辑地址可以表示为（逻辑块号，块内地址）的形式。

连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）物理块号=起始块号+逻辑块号。还需要检查用户提供的逻辑块号是否合法（逻辑块号》=长度就不合法）

可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（随机访问）

连续分配的文件在顺序读写时速度最快

物理上连续分配的文件不方便拓展

物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片。可以用紧凑处理碎片，但是会耗费很大的时间代价。

链接分配（隐式链接、显式链接）

隐式链接：除了文件的最后一个磁盘块之外，每个磁盘块都会保存指向下一个盘块的指针，这些指针对用户是透明的。目录项记录起始块号和结束块号。采用链接分配（隐式链接）只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针页需要耗费少量的存储空间。

采用隐式链接的链接分配方式，很方便文件拓展，不会有碎片问题，外存利用率高。

显式链接：把用于链接文件各物理块的指针显示地存放在一张表中，即文件分配表（FAT）。一个磁盘仅设置一张FAT，开机时，将FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此物理块号字段时隐含的。

用户给出逻辑块号，操作系统找到该文件目录项FCB，FCB只记录起始块号，从目录项中找到起始块号，查找内存中的文件分配表FAT（开机后常驻内存），往后找i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。采用显式链接的方式的文件，支持随机访问，而且不需要访问磁盘，相比隐式链接来说快很多。显式链接也不会产生外部碎片，可以很方便对文件进行拓展。缺点是文件分配表会占用一定的存储空间。

索引分配

索引分配允许文件离散地分配在各个磁盘块中。系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块被称为索引块。文件数据存放的磁盘块称为数据块。目录中需要记录索引块是几号磁盘块

用户给出逻辑块号，操作系统找到该文件对应的目录项FCB。从目录项中可以得知索引表存放位置，将索引表从外存读入内存，并查找索引表即可看到逻辑块在外存中的存放位置。

索引分配方式可以支持随机访问，文件拓展也很容易实现。但是索引表需要占用一定的存储空间。

文件过大，导致磁盘块装不下索引表，可以采用下面方案

链接方案：如果索引表太大，一个索引块装不下，可以将多个索引块链接起来存放。但是只能顺序访问，低效。

多层索引：建立多层索引（类似于多级页表）。第一层索引块指向第二层索引块，还可以根据文件大小建立多层索引。如2级索引表，访问一次一级索引，再访问一次二级索引，最后访问目标数据块，需要3次读磁盘。k层索引，且顶级索引表未引入内存，只需要k+1次读磁盘操作。

混合索引：多种索引方式的结合，在顶级索引表中，既包含直接索引地址（直接指向数据块）还包含一级间接索引，两级间接索引。

超级重要考点：要会根据多层索引、混合索引的结构计算出文件的最大长度。要能分析访问某个数据块所需要的读磁盘次数（FCB中会存有指向顶级索引表的指针，可以根据FCB读入顶级索引块，每次读入下一级的索引块都需要一次读磁盘操作）要注意题目条件--顶级索引块是否已经调入内存。

文件系统层次结构

最高层：文件系统接口

中间层：对对象操纵和管理的软件集合

最底层：对象及其属性

在磁盘区中，分为目录区和文件区，目录区存放FCB，用于磁盘存储空间管理的信息。

外存空闲空间管理方法

空闲表法（适用于连续分配方式）

分配磁盘块：为一个文件分配连续的存储空间，可以采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。回收磁盘块也和内存管理中的动态分区类似，回收要注意表项的合并问题。

空闲链表法（适用于离散分配的物理结构）

空闲盘块链，以盘块为单位组成一条空闲链，空闲盘块存储者下一个空闲盘块的指针。某个文件申请k个盘块，从链头开始一次摘下k个盘块分配，并修改空闲链的链头指针。回收的盘块依次挂到链尾，并修改链尾指针

空闲盘区链，以盘区为单位组成一条空闲链，连续空闲的盘块组成一个盘区，空闲盘区的第一个盘块记录了盘区长度和下一个盘区的指针。某个文件申请k个盘块，可以采用首次适应，最佳适应算法，从链头开始检索，按照算法规则找到一个大小符合的空闲盘区分配给文件。若没有合适的连续空闲块，也可以将不同的盘区的盘块分配给一个文件。

位示图法

每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。位视图一般用连续的“字”来表示。如一个字的字长是16位，可以用（字号，位号）对应一个盘块号。有的题目也描述为（行号，列号）最重要的是自己能推出盘块号与（字号，位号）。注意题目中盘块号、字号、位号是从0开始还是1开始。n表示字长，字号，位号（i，j）的二进制位对应的盘块号b=ni+j。 b号盘块对应的字号i=b/n，位号j=b/n

若文件需要k个块，顺序扫描位示图，找到k个相邻或者不相邻的“0”。根据字号、位号计算出盘块号，并把盘块分配给文件。将相应位设置位“1”。回收时根据盘块号计算出对应的字号，位号。将相应的二进制位设为“0”

成组链接法（unix使用）

文件卷的目录区中专门用一个磁盘块作为超级块，当系统启动时需要将超级块读入内存，并且要保证内存与外存中的超级块数据一致。

文件保护

口令保护

为文件设置一个口令，用户想要访问文件时需要提供口令，系统验证口令是否正确

实现开销小，但口令一般存放在FCB或者索引结点中，不太安全

加密保护

用一个密码进行文件加密，访问文件需要提供相应的密码

安全性高，但加解密需要花费一定的时间

访问控制

用一个访问控制表（ACL）记录各个用户对文件的访问权限

对文件的访问类型可以分为：读写执行删除

实现灵活，可以实现复杂的文件保护功能。

虚拟文件系统

是对各种文件系统的一个抽象，为各种文件系统提供一个通用接口；存在于内存，运行在内核态

虚拟文件系统是向上层用户进程提供一个统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异。通俗来讲，这个虚拟文件系统VFS统一了UFS文件系统，NTFS文件系统，FAT文件系统等，对不同的设备进行了统一的调用。

VFS要求下层的文件系统必须实现某些规定的函数功能，如open/read/write等。一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统VFS的要求。

每打开一个文件，VFS就在主存中新建一个vnode，用统一的数据结构表示文件，无论该文件存储在哪个文件系统。（vnode只存在于主存中，inode既会调入主存，也会在外存中存储）

打开文件后，创建vnode，并将文件信息复制到vnode中，vnode的功能指针指向具体文件系统的函数功能。具体文件系统也就是UFS，FAT之类的，

文件系统挂载

文件系统挂载与文件系统通过挂载进行关联

文件系统挂载是指文件系统安装/装载，指的是如何将一个文件系统挂载到操作系统中。

文件系统挂载要做的事情（指的具体的文件系统）：

在VFS中注册新挂载的文件系统，内存中的挂载表（mount table）包含每个文件系统的相关信息，包括文件系统类型、容量大小等。新挂载的文件系统，要向VFS提供一个函数地址列表。将新文件系统加到挂载点，也就是将新文件系统挂载到某个父目录下。

文件系统的全局结构

原始磁盘（什么也没有，磁盘空空的）

物理格式化，也就是低级格式化。将磁盘划分扇区，检测坏扇区，并用备用扇区替换坏扇区。

逻辑格式化，磁盘分区（分卷）完成各分区的文件系统初始化。磁盘分区有主引导记录（MBR，包含磁盘引导程序和分区表），c盘，D盘，E盘等。

Open系统调用打开文件的背后过程。第一步先根据路径一级一级读入目录。找到目标文件的FCB，复制到系统打开文件表。在进程打开文件表中新建一个条目，并返回文件描述符。

关键词：