CS408/Operate-System/3-file-management.md

文件管理

文件系统

文件系统不仅管理普通文件，对于$UNIX$系统所有设备都被视为特殊文件。

文件系统基础

文件基本概念

用户输入输出以文件为基本单位。

• 数据项：最低级数据组织形式。
  • 基本数据项：用于描述一个对象的某种属性的一个值，是数据中可命名的最小逻辑数据单位，即原子数据。
  • 组合数据项：多个基本数据项构成。
• 记录：一组相关数据项的集合，用于表述一个对象在某方面的属性。
• 文件：一组有意义的信息/数据的集合。
• 操作系统以“块”为单位为文件分配存储空间，外存中的数据读入内存同样以块为单位。

文件基本属性

操作系统通过文件控制块$FCB$来保护文件元数据：

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

文件控制块

• 目录本身就是一种有结构文件，由一条条记录组成。每条记录对应一个在该放在该目录下的文件。
• 目录文件中的一条记录就是一个文件控制块（$FCB$）。$FCB$的有序集合就是文件目录，一个$FCB$就是一个文件目录项。
• $FCB$中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。最重要最基本的就是文件名和文件存放物理地址。
• $FCB$实现了文件名与文件之间的映射，使得用户（用户程序）可以实现按名存取。

索引结点

• 其实在查找各级目录的过程中只需要用到“文件名”这个信息，只有文件名匹配时，才需要读出文件的其他信息。因此可以考虑让目录表“瘦身”来提升效率。
• 所以目录只包含文件名与索引结点指针，除了文件名之外的文件描述信息都存放在索引结点之中。索引结点是对$FCB$的改进。
• 当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。
• 假设一个$FCB$是$64B$，磁盘块的大小为$1KB$，则每个盘块中只能存放$16$个$FCB$。若一个文件目录中共有$640$个目录项，则共需要占用$640\div16=40$个盘块。因此按照某文件名检索该目录，使用折半查找平均需要查询$320$个目录项，平均需要启动磁盘$20$次（每次磁盘$I/O$读入一块)。
• 若使用索引结点机制，文件名占$14B$，索引结点指针站$2B$，则每个盘块可存放$64$个目录项，那么按文件名检索目录平均只需要读入$320\div64=5$个磁盘块。显然，这将大大提升文件检索速度。
• “磁盘索引结点”：存放在外存中的索引结点，每个文件有一个唯一的磁盘索引结点。
  • 文件主标识符。
  • 文件类型。
  • 文件存取权限。
  • 文件物理地址。
  • 文件长度。
  • 文件链接计数。
  • 文件存取时间。
• “内存索引结点”：存放在内存中的索引结点，文件打开后将磁盘索引结点复制到内存中。
  • 相比之下内存索引结点中需要增加一些信息：
  • 索引结点编号。
  • 状态。
  • 访问计数。
  • 逻辑设备号。
  • 链接指针。

文件操作

文件基本操作

• 创建$create$。
  1. 文件系统为文件找到空间。
  2. 在目录中为新文件创建条目，记录文件名称、位置和其他信息。
• 删除$delete$：找到对应目录项，使其为空，并回收该文件所占存储空间。
• 截断：允许文件所有属性不变，删除文件内容，即设置长度归零并释放空间。
• 读文件$read$：执行一个系统调用，指明文件名和位置。系统维护一个读位置的指针，读时就更新读指针。需要的参数：
  1. 文件描述符。
  2. 缓冲区首址。
  3. 传输字节数。
• 写文件$write$：执行一个系统调用，指明文件名和内容。系统通过文件名搜索位置。系统需要为文件维护一个写位置的指针，当写时就更新写指针。
• 文件重定位（文件寻址）：按条件搜索目录，将当前文件位置设置为给定值，不读写。

文件打开

• 开文件操作是将该文件的$FCB$存入内存的活跃文件目录表。
• 在很多操作系统中，在对文件进行操作之前，要求用户先使用$open$系统调用“打开文件”，需要提供的几个主要参数：
  1. 文件存放路径。
  2. 文件名。
  3. 要对文件的操作类型（如：$r$只读；$rw$读写等）。
• 操作系统在处理$open$系统调用：
  1. 将文件名传递给逻辑文件系统。
  2. 搜索系统打开文件表。
  3. 如果已打开，则在进程打开文件表种创建新目录指向系统打开文件表对应条目。
  4. 如果未打开，根据文件名搜索目录结构，并检查该用户是否有指定的操作权限。（部分文件目录会缓存到内存中以加快检索）
  5. 找到文件后将目录项$FCB$复制到系统打开文件表（活跃文件目录表）中。
  6. 进程打开文件表中创建一个条目，然后通过指针将系统打开文件表条目和其他域相联。
  7. 返回一个指向进程打开文件表条目的指针，通过指针操作文件。
  8. 打开文件后内核不能通过文件名访问文件，只能通过文件描述符（文件句柄）访问。
• 打开文件表分为两种：
  1. 系统打开文件表，只有一张，包括编号、文件名、外存地址、打开计数器（多少个进程打开了次文件）等。
  2. 每一个进程的打开文件表，包括编号、文件名、读写指针、访问权限、系统表索引号等。
• 打开文件时并不会把文件数据直接读入内存，而是提供索引号。“索引号”也称“文件描述符”或“文件句柄”。

每个打开文件都有如下关联信息：

• 文件指针。系统跟踪上次的读写位置作为当前文件位置的指针，这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存。
• 文件打开计数。文件关闭时，操作系统必须重用其打开文件表条目，否则表内空间会不够用。因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件。计数器跟踪打开和关闭的数量，计数为$0$时，系统关闭文件，删除该条目。
• 文件磁盘位置。绝大多数文件操作都要求系统修改文件数据。该信息保存在内存中，以免为每个操作都从磁盘中读取。
• 访问权限。每个进程打开文件都需要有一个访问模式（创建、只读、读写、添加等）。该信息保存在进程的打开文件表中，以便操作系统能够允许或拒绝之后的$I/O$请求。
• 系统范围的打开文件表，包括每个打开文件的$FCB$复制和其他信息。
• 单个进程的打开文件表，包括一个指向系统范围内已打开文件表中合适条目和其他信息的指针。

文件关闭

• 用户使用$close$系统调用“打开文件”，需要提供的几个主要参数：
  1. 文件存放路径。
  2. 文件名。
• 操作系统在处理$close$系统调用时，主要做了几件事：
  1. 将进程的打开文件表相应表项删除。
  2. 回收分配给该文件的内存空间等资源。
  3. 系统打开文件表的打开计数器$count$减$1$，若$count=0$，则删除对应表项。

文件保护

口令保护和加密保护是为了防止用户文件被他人存取，而访问控制用于控制用户对文件的访问方式。

口令保护

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

加密保护

• 使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
• 系统并不保存原始数据，而是加密过的数据。
• 加密方式有异或加密等。
• 优点：保密性强，不需要在系统中存储“密码”。
• 缺点：编码/译码，或者说加密/解密要花费一定时间。

访问控制

• 在每个文件的$FCB$（或索引结点）中增加一个访问控制列表（$AccessControl,List$，$ACL$），该表中记录了各个用户可以对该文件执行哪些操作。
• 访问类型包括：
  • 读：从文件中读数据。
  • 写：向文件中写数据。
  • 执行：将文件装入内存并执行。
  • 添加：将新信息添加到文件结尾部。
  • 删除：删除文件，释放空间。
  • 列表清单：列出文件名和文件属性。
• 优点：可以使用复杂的访问方法。
• 缺点：长度无法余集且可能导致复杂的空间管理。
• 有的计算机可能会有很多个用户，因此访问控制列表可能会很大，可以用精简的访问列表解决这个问题。
• 精简的访问列表：以“组”为单位，标记各“组”用户可以对文件执行哪些操作。当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限。所以系统也需要管理分组的信息。
• 用户类型：
  • 拥有者：创建文件用户。
  • 组：一组需要共享文件且拥有类似访问的用户。
  • 其他：系统内其他所有用户。
• 若想要让某个用户能够获取某种权限，需要把该用户放入有该权限的分组即可。
• 如果对某个目录进行了访问权限的控制，那也要对目录下的所有文件进行相同的访问权限控制。

Linux文件权限

命令格式chmod 权限 文件名。

一共九位，从左至右分为三组，$1-3$位数字代表文件所有者的权限，$4-6$位数字代表同组用户的权限，$7-9$数字代表其他用户的权限。每一组的第一位表示可读，第二位表示可写，第三位表示可执行。

如$755$，第一组的$7=4+2+1$表示所有者可读可写可执行，$5=4+0+1$表示同组用户和其他用户可读可执行但是不可写。

文件逻辑结构

分为无结构文件与有结构文件。

• 无结构文件（如文本文件）：
  • 由一些二进制或字符流组成，又称“流式文件”。
  • 以$Byte$为单位。
  • 只能通过穷举进行搜索。
  • 管理简单，适用于字符流的无结构方式，如源程序文件、目标代码文件等。
• 有结构文件（如数据库表）：由一组相似的记录（每条记录又若干个数据项组成，数据项又包含多个属性，是文件系统中最基本的数据单位）组成，又称“记录式文件”。每条记录有一个数据项可作为关键字（如$ID$）。

有结构文件可以根据各条记录的长度（占用的存储空间）是否相等，可分为定长记录和可变长记录两种。

有结构文件的逻辑结构：

• 顺序文件。
• 索引文件。
• 索引顺序文件。
• 散列文件。

顺序文件

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

根据关键字与顺序之间的关系：

• 串结构：记录之间的顺序与关键字无关。一般按记录存入时间决定记录的顺序。
• 顺序结构：记录之间的顺序按关键字顺序排列。

如何访存顺序文件：

• 链式存储：无论是定长/可变长记录，都无法实现随机存取，每次只能从第一记录开始依次往后查找。
• 顺序存储：
  • 可变长记录：无法实现随机存取。每次只能从第一个记录开始依次往后查找。因为需要显式地给出记录长度。
  • 定长记录：
    • 可实现随机存取。记录长度为$L$，则第$i$个记录存放的相对位置是$i\times L$。
    • 若采用串结构，只能从头开始查找，无法快速找到某关键字对应的记录。
    • 若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）。

顺序文件插入删除文件比较麻烦。一般实际实现时会隔一个时间段集中将修改写入到文件中。

索引文件

• 为了解决顺序文件查找问题，建立一张索引表存放每个文件所存放的块盘地址，以加快文件检索速度。每条记录对应一个索引项。
• 记录可以离散存放，而索引表必须连续存放。
• 索引表包含索引号，长度，指针三个部分。其本身是定长长度的顺序文件，所以可以快速找到索引，通过指针随机访问。
• 可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。
• 每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。
• 可以使用不同的数据项对一组数据建立多个索引表。
• 索引表其实是索引顺序结构的。
• 对于$N$条记录的顺序文件，查找关键字记录需要$N/2$次，在索引顺序文件中，将其分为$\sqrt{N}$组，每组$\sqrt{N}$条记录，所以索引表查找需要$\dfrac{\sqrt{N}}{2}$次，主文件顺序查找也需要$\dfrac{\sqrt{N}}{2}$次，所以一共需要查找$\sqrt{N}$次。

索引顺序文件

类似于字典。

• 因为每个记录对应一个索引表项，因此索引表可能会很大。同时若数据长度本身远小于索引表项长度，则空间利用率会很低。
• 索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。
• 每个分组就是一个顺序文件（组间有序），分组内的记录不需要按关键字排序（组内无序）。
• 索引项页不需要按关键字顺序排列，从而能便利插入删除。
• 索引表其实是索引串结构的。
• 为了进一步提高索引效率，可以建立多级索引表。

散列文件

也称为直接文件。给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件，没有顺序的特性。

散列文件有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值相同。

文件物理结构

文件物理结构即文件分配方式，是对非空间磁盘块的管理。

文件块与磁盘块

• 类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同。
• 内存与磁盘之间的数据交换（即读/写操作、磁盘I/O)）都是以“块”为单位进行的。即每次读入一块，或每次写出一块。
• 在内存管理中，进程的逻辑地址空间被分为一个一个页面。同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。
• 用户通过逻辑地址来操作自己的文件， 操作系统要负责实现从逻辑地址到物理地址的映射，即文件的物理结构或文件分配方式。

记录成组分解技术

由于磁盘块的大小是预先划分好的，大小固定，而逻辑记录的大小是用户文件性质决定的，不一定和块大小一致，如果逻辑记录比物理块小得多时，可以把多个逻辑记录存放在一个块中，这就是记录的成组，用户使用时再把读取的一块信息中分离出所需的记录，这就是记录的分解。

连续分配

• 每个文件在磁盘上占有一组连续的块。
• （逻辑块号，块内地址）→（物理块号，块内地址）。只需转换块号就行，块内地址保持不变。
• 文件目录中记录存放的起始块号和长度（总共占用几个块）。
• 用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（$FCB$），物理块号=起始块号＋逻辑块号。
• 优点：
  • 可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（即随机访问）。
  • 连续分配的文件在顺序读写时速度最快。
• 缺点：
  • 不便于拓展。
  • 存储利用率低，产生大量外部碎片。

链接分配

• 采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
• 隐式链接：
  • 类似链表。
  • $FCB$目录中记录了文件存放的起始块号和结束块号，当然也可以增加一个字段来表示文件的长度。
  • 除了文件的最后个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的。
  • 优点：
    • 方便文件拓展。
    • 不会有硬盘碎片。
  • 缺点：
    • 只支持顺序访问，不支持随机访问，查找效率低。
    • 指向下一个盘块的指针也需要耗费少量的存储空间。
    • 存储稳定性不足，若是中间毁坏后面的数据也会丢失。
• 显式链接：
  • 类似静态链表。
  • 把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（$FAT$，$File,Allocation,Table$）。$FAT$包含物理块号和下一块指针两项。
  • $FCB$目录中只需记录文件的起始块号。
  • 一个磁盘仅设置一张$FAT$。开机时，将$FAT$读入内存，并常驻内存。所以地址转换不需要读取内存，从而效率更高。
  • $FAT$的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。
  • 地址转换：目录项中找到起始块号，若$i>0$，则查询内存中的文件分配表$FAT$，往后找到$i$号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。
  • 优点：
    • 很方便文件拓展。
    • 不会有外部碎片问题，外存利用率高。
    • 支持随机访问。
    • 相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
  • 缺点：文件分配表的需要占用一定的存储空间。

索引分配

• 允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
• 索引表包含逻辑块号和物理块号两项。逻辑块号可以是隐含的。
• 每一个文件都有一个索引表。
• 地址转换：从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只$i$号逻辑块在外存中的存放位置。
• 优点：
  • 很方便文件拓展，不会有碎片问题，外存利用率高。
  • 支持随机访问。
• 缺点：文件索引表的需要占用一定的存储空间。

索引块必须不能太大，但是索引块太小就无法支持大文件，解决方案：

• 链接方案：
  • 分配多个索引块并链接起来。
  • 文件$FCB$中只需要记录第一个索引块的块号。
  • 缺点：查找效率低。
• 多层索引：
  • 建立类似多级页表的多层索引，使上层索引块指向下一层的索引块。
  • $FCB$中只需要记录顶层索引块就可以了。
  • 若采用多层索引，则各层索引表大小不能超过一个磁盘块。理由同多级页表。
  • 采用$K$层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要$K+1$次读磁盘操作。
  • 缺点：即使是小文件页需要$K+1$次读磁盘操作。
• 混合索引：
  • 多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）等。
  • 优点：对于小文件，只需较少的读磁盘次数就可以访问目标数据块。（一般计算机中小文件更多）。

如一共十三个地址项，前十个为直接地址，后面三个为一级间址、二级间址、三级间址。每个盘块的大小为$4KB$，索引块大小为$4B$。

所以文件不大于$4\times10=40KB$时可以直接读出。一个一级间址块中能包含$4KB\div4B=1K=2^{10}$个索引，所以能索引出$2^{10}\times4KB=4MB$的空间。同理，若文件长度大于$4MB+40KB$时可以使用二级间址块，索引出$4GB$的空间，三级间址能索引出$4TB$的空间。

	访问第n条记录	优点	缺点
连续分配	需访问磁盘1次	顺序存取时速度快，文件定长时可根据文件起始地址及记录长度进行随机访问	文件存储要求连续的存储空间，会产生碎片，不利于文件的动态扩充
链接分配	需访问磁盘n次	可解决外存的碎片问题，提高外存空问的利用率，动态增长较方便	只能按照文件的指针链顺序访问，查找效率低，指针信息存放消耗外存空间
索引分配	m级需访问磁盘m+1次	可以随机访问，文件易于增删	索引表增加存储空间的开销，索引表的查找策略对文件系统效率影响较大

目录系统

目录结构

单级目录结构

整个系统中只建立一张目录表，每个文件占一个目录项。

• 实现了“按名存取”，但是不允许文件重名。
• 在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。
• 不适用于多用户操作系统。

两级目录结构

分为主文件目录（$MFD$，$Master,File,Directory$）和用户文件目录（$UFD$，$User,Flie,Directory$）：

• 主文件目录记录用户名及相应用户文件目录的存放位置。
• 用户文件目录由该用户的文件$FCB$组成。
• 允许不同用户的文件重名。文件名虽然相同，但是对应的其实是不同的文件。
• 两级目录结构允许不同用户的文件重名，也可以在目录上实现实现访问限制（检查此时登录的用户名是否匹配）。
• 两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类。

多级目录结构

即树形目录结构：

• 不同目录下的文件可以重名。
• 用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。
• 从根目录出发的路径称为绝对路径。
• 很多时候，用户会连续访问同一目录内的多个文件，显然，每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”出发的相对路径。
• 树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。
• 但是，树形结构不便于实现文件的共享，且查找文件需要逐级访问影响速度。为此，提出了“无环图目录结构”。

无环图目录结构

• 在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享。
• 可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。
• 需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的$FCB$、并使共享计数器减$1$，并不会直接删除共享结点。
• 共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。
• 实现了文件共享，但是使得文件管理更复杂。

目录操作

目录基本操作

• 搜索：首先要找到对应目录项。
• 创建文件。
• 删除文件。
• 创建目录。
• 删除目录：包括不删除非空目录和可删除非空目录两种。
• 移动目录。
• 显示目录。
• 修改目录。

目录实现

• 线性列表。
• 哈希表。

文件目录共享

多个用户共享同一个文件或目录，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。

文件共享方式分为：

• 基于索引结点的共享方式：硬链接。
• 基于符号链的共享方式：软链接。

索引结点中设置一个链接计数变量$count$，用于表示链接到本索引结点上的用户目录项数。

硬链接

• 在文件目录中提到，索引结点，是一种文件目录瘦身策略。由于检索文件时只需用到文件名，因此可以将除了文件名之外的其他信息放到索引结点中。这样目录项就只需要包含文件名、索引结点指针。
• 不同目录下对于同一个文件的索引结点的命名可以是不同的。

创建硬链接时：

• 创建硬链接时$count+1$。

删除文件时：

• 则只是要把用户目录中与该文件对应的目录项删除，且索引结点的$count$值减$1$。
• 若$count>0$，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。
• 若$count=0$，则系统需要删除文件。

软链接

• 软链接就是共享时建立一个$Link$类型的文件，文件记录了要共享的文件的存放路径或任意一条硬链接路径，类似$Windows$系统的快捷方式。
• 文件拥有者才拥有指向其索引结点的指针，而共享该文件的其他用户只有该文件的路径名。
• 当访问共享文件时，先判断这个文件属于$Link$类型文件，然后根据其中记录的路径层层查找路径找到索引结点。

创建软链接时：

• $count$直接复制。
• 计算$count$值时忽略所有软链接。

若决定“删除”该文件：

• 由于删除操作对软链接不可见，所以$count$值不变。
• 当以后通过符号链接再次访问时发现文件不存在再直接删除软链接。

优点：

• 网络共享只用提供文件所在机器的网络地址和文件路径。
• 若共享文件被删除了，则软链接失效。删除软链接则无影响。

缺点：

• 当共享文件删除，而其他用户新建一个相同路径的文件则原链接指向的是新文件而不是原文件。
• 因为软链接访问共享文件时需要查询多层目录，所以有多层$I/O$操作，从而软链接访问速度慢于硬链接。

硬链接和软链接都是静态共享方式，都存在一个共同的问题，每个共享文件都有几个文件名，从而每增加一条文件名，当遍历整个文件系统时会多次遍历到该共享文件。

多个进程同时对同一个文件操作称为动态共享。

文件系统管理

系统层次结构

1. 设备。
2. $I/O$控制：
   • 包括设备驱动程序和中断处理程序，在内存和磁盘系统之间传输信息。
   • 设备驱动程序将输入的命令翻译成底层硬件的特定指令，硬件控制器利用这些指令使$I/O$设备与系统交互。
   • 设备驱动程序告诉$I/O$控制器对设备的什么位置采取什么动作。
3. 相关模块：
   • 辅助分配模块：管理辅存空间。即负责分配和回收存储空间。
   • 设备管理模块：管理设备。直接与硬件交互，负责和硬件直接相关的一些管理工作。如分配设备、分配设备缓冲区、磁盘调度、启动设备、释放设备等。
4. 物理文件系统：物理地址转换。这一层需要把上一层提供的文件逻辑地址转换为实际的物理地址。
5. 逻辑文件系统与文件信息缓冲区：逻辑地址转换。用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址。文件信息缓冲区用来在调入索引表到内存时暂存索引表的内容。
6. 存取控制模块：文件保护。为了保证文件数据的安全，还需要验证用户是否有访问权限。
7. 文件目录系统：管理文件目录。用户是通过文件路径来访问文件的，因此这一层需要根据用户给出的文件路径找到相应的$FCB$或索引结点。所有和目录、目录项相关的管理工作都在本层完成，如管理活跃的文件目录表、管理打开文件表等。
8. 用户接口：向用户提供文件目录相关功能接口。这层就是用于处理用户发出的系统调用请求（$read$、$write$、$open$、$close$等系统调用）。
9. 用户/应用程序。

假设某用户请求删除文件“$D:$/工作目录/学生信息.$xlsx$”的最后$100$条记录：

1. 用户需要通过操作系统提供的接口发出上述请求——用户接口。
2. 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项――文件目录系统
3. 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限―-存取控制模块（存取控制验证层）。
4. 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址――逻辑文件系统与文件信息缓冲区。
5. 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址――物理文件系统。
6. 要删除这条记录，必定要对磁盘设备发出请求――设备管理程序模块。
7. 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收――辅助分配模块。

文件系统分布

文件系统存放在磁盘上，多数磁盘划分分区，每个分区都有独立的文件系统。

文件系统磁盘结构

• 主引导记录（$Master,Boot,Record$，$MBR$），位于磁盘的0号扇区，用来引导计算机，$MBR$后面是分区表，该表给出每个分区的起始和结束地址。表中的一个分区被标记为活动分区，当计算机启动时，BIOS读入并执行$MBR$。$MBR$做的第一件事是确定活动分区，读入它的第一块，即引导块。
• 引导块（$boot,block$），$MBR$执行引导块中的程序后，该程序负责启动该分区中的操作系统。为统一起见，每个分区都从一个引导块开始，即使它不含有一个可启动的操作系统，也不排除以后会在该分区安装一个操作系统。$Windows$系统称之为分区引导扇区。除了从引导块开始，磁盘分区的布局是随着文件系统的不同而变化的。
• 超级块（$super,block$），包含文件系统的所有关键信息，在计算机启动时，或者在该文件系统首次使用时，超级块会被载入内存。超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的$FCB$数量和$FCB$指针等。
• 文件系统中空闲块的信息，可以使用位示图或指针链接的形式给出。后面也许跟的是一组i结点，每个文件对应一个结点，i结点说明了文件的方方面面。接着可能是根目录，它存放文件系统目录树的根部。最后，磁盘的其他部分存放了其他所有的目录和文件。

文件系统内存结构

内存中的信息用于管理文件系统并通过缓存来提高性能。

• 内存中的安装表（$mount,table$），包含每个已安装文件系统分区的有关信息。
• 内存中的目录结构的缓存包含最近访问目录的信息。对安装分区的目录，它可以包括一个指向分区表的指针。
• 整个系统的打开文件表，包含每个打开文件的$FCB$副本及其他信息。
• 每个进程的打开文件表，包含一个指向整个系统的打开文件表中的适当条目的指针与其他信息。

外存空闲空间管理

包含文件系统的分区称为卷。

同一个卷中存放数据的空间（文件区）和$FCB$的空间（目录区）是分离的。

存储空间划分与初始化

• 将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）。
• 将各个文件卷初始化为：
  • 目录区：主要存放文件目录信息$FCB$、用于磁盘存储空间管理的信息。
  • 文件区：用于存放普通文件数据。
• 有的系统支持超大型文件，支持由多格物理磁盘组成一个文件卷。

空闲表法

是连续分配方式。

• 拥有一个空闲盘块表，包括空闲区间的起始位置（第一个空闲盘块号）和空闲空间长度（空闲盘块数）。
• 适用于连续分配方式。
• 如何分配磁盘块：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
• 如何回收磁盘块：与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况：
  1. 回收区的前后都没有相邻空闲区。
  2. 回收区的前后都是空闲区。
  3. 回收区前面是空闲区.
  4. 回收区后面是空闲区。
  5. 总之，回收时需要注意表项的合并问题。

空闲链表法

• 空闲盘块法：
  • 以盘块为单位组成一条空闲链。空闲盘块中存储着下一个空闲盘块的指针。
  • 操作系统保存着链头、链尾指针。
  • 如何分配：若某文件申请$K$个盘块，则从链头开始依次摘下$K$个盘块分配，并修改空闲链的链头指针。
  • 如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。
  • 适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作。
• 空闲盘区法：
  • 以盘区为单位组成一条空闲链。由连续的几个盘块组成一个盘区。每一个盘区内的第一个盘块内记录了盘区的长度和下一个盘区的指针。
  • 操作系统保存着链头、链尾指针。
  • 如何分配：若某文件申请$K$个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
  • 如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。
  • 离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。

位示图法

• 每个二进制位对应一个盘块。如“$0$”代表盘块空闲，“$1$”代表盘块已分配。
• 位示图一般用连续的“字”来表示，如一个字的字长是$16$位，则一共有$16$列，字中的每一位对应一个盘块。因此可以用（字号，位号）对应一个盘块号。当然有的题目中也描述为（行号，列号）。
• 若盘块号、字号、位号从$0$开始，若$n$表示字长，则(字号,位号)=$(i,j)$的二进制位对应的盘块号$b=ni+j$。
• $b$号盘块对应的字号$i=b\div n$，位号$j=b%n$。
• 如何分配：若文件需要$K$个块，
  1. 顺序扫描位示图，找到$K$个相邻或不相邻的“$0$”。
  2. 根据字号、位号算出对应的盘块号，将相应盘块分配给文件。
  3. 将相应位设置为“$1$”。
• 如何回收：
  1. 根据回收的盘块号计算出对应的字号、位号。
  2. 将相应二进制位设为“$0$”。
• 离散分配、连续分配都适用。

成组链接法

• 空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。$UNIX$系统中采用了成组链接法对磁盘空闲块进行管理。
• 文件卷的目录区中专门用一个磁盘块作为超级块，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的超级块数据一致。
• 将空闲块分成若干组，如每$100$个空闲块为一组，每组的第一空闲块登记了下一组空闲块的物理盘块号和空闲块总数。组内索引，组间链接。
• 一个分组的块号不需要连续。
• 如何分配：
  1. 检测第一个分组的块数是否足够。
  2. 若足够则分配空闲块并修改对应数据。
  3. 若刚好相等或不足，则分配时要先将其数据复制到超级块中，超级块充当链头的作用。
• 如何回收：
  1. 如果块内回收后余留，则修改数据。
  2. 若回收数量大于等于余下，需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。

虚拟文件系统

即$VFS$，为用户程序提供了文件系统操作的统一接口（统一调用函数）屏蔽了不同文件系统的差异。

$Linux$实现$VFS$提供四个对象：

• 超级块对象：表示已安装或挂载的特定文件系统。
• 索引结点对象：表示一个特定的文件。
• 目录项对象：表示特定的目录项。
• 文件对象：表示一个与进程相关的已打开文件。

$VFS$可以提高系统性能，只存在内存中，系统启动建立，关闭时消亡。