操作系统(4)文件管理

文件属于抽象数据类型。为了正确定义文件，需要考虑对文件的操作。操作系统提供系统调用，创建、写入、读取、重定位、删除和截断文件。

所谓“逻辑结构”，是指文件内部的数据在用户眼中应该如何组织。而“物理结构”指的是从操作系统的角度来看，文件的数据是如何存储在外部存储器中的。

非结构化文件:文件内部的数据由一系列二进制流或字符流组成。也称为“流文件”

文件内部的数据实际上是一系列字符流，没有明显的结构特征。因此，没有必要讨论非结构化文件的“逻辑结构”。

结构化文件:由一组相似的记录组成，也称为“记录文件”。每个记录由几个数据项组成。[1]一般来说，每条记录都有一个可以作为关键字的数据项。根据每条记录的长度(占用的存储空间)是否相等，可以分为定长记录和变长记录。结构化文档可以分为:

对于一个有N条记录的顺序文件，平均需要N/2次才能找到某个关键字值的记录。在索引顺序文件中，假设N条记录分为√N组，索引表中有√N个条目，每组有√N条记录。在搜索具有某个关键字值的记录时，需要先搜索索引表，然后在主文件中的对应组中，也需要搜索√N /2次，所以* *需要查找√N /。显然，索引顺序文件提高了搜索效率。如果有许多记录，可以使用两个或多个索引。

一组有序的FCB称为“文件目录”，FCB是一个文件目录条目。FCB包含文件的基本信息(文件名、物理地址、逻辑结构、物理结构等。)、访问控制信息(是否可读/写、禁止访问的用户列表等。)，以及使用信息(如文件的建立时间和修改时间等。最重要和最基本的是文件名和文件存储的物理地址。

目录的操作如下:

操作时，可以有以下目录结构:

早期的操作系统不支持多级目录。整个系统只建立一个目录表，每个文件占用一个目录条目。

单级目录实现“按名称访问”，但文件不允许重命名。创建文件时，需要先检查目录表中是否有重名的文件，确认没有重名后才允许创建文件，并将新文件对应的目录项插入目录表中。显然，单级目录结构不适合多用户操作系统。

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

允许不同用户的文件被重命名。虽然文件名相同，但实际上对应的是不同的文件。两级目录结构允许对不同用户的文件进行重命名，还可以在目录中实施访问限制(检查此时登录的用户名是否匹配)。但是，两级目录结构仍然缺乏灵活性，用户无法对自己的文件进行分类。

当用户(或用户进程)想要访问一个文件时，他们应该用文件路径名来标识该文件，路径名是一个字符串。所有级别的目录都用“/”分隔。根目录的路径称为绝对路径。

系统根据绝对路径逐层查找下一个目录。刚开始从外存读取根目录的目录表；找到目录的存储位置后，从外部存储器中读取相应的目录表；然后找到目录的存储位置，再从外存储器中读取对应的目录表；最后，我找到了文件的存储位置。整个过程需要3次磁盘读I/O操作。

很多时候，用户会连续访问同一个目录中的多个文件。显然，每次都从根目录开始搜索效率很低。所以你可以设置一个“当前目录”。此时已经打开的目录文件，也就是这个目录表已经被调入内存，可以设置为“当前目录”。当用户想要访问一个文件时，他们可以使用当前目录的“相对路径”。

可以看出，引入“当前目录”和“相对路径”后，磁盘I/O数量减少。这提高了访问文件的效率。

树形目录结构可以方便地对文件进行分类，层次结构清晰，也可以更有效地管理和保护文件。但是树形结构不方便实现文件的* * *享受。因此，提出了“无环图目录结构”。

可以用不同的文件名指向同一个文件，甚至可以指向同一个目录(* * *享有同一个目录下的所有内容)。需要为每个* * *享受节点设置一个* * *享受计数器，用来记录此时* * *中有多少个地方正在享受该节点。当用户请求删除一个节点时，只删除该用户的FCB，并将* * *享受计数器减1，而不直接删除* * *享受节点。只有当* * *享受计数器减为0时，才能删除该节点。

实际上，在各级目录的查找过程中只需要“文件名”的信息，只有当文件名匹配时，才需要读出文件的其他信息。所以可以考虑“瘦身”目录，提高效率。

当找到对应于文件名的目录条目时，需要将索引节点转移到内存中。索引节点记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”可以找到文件。存储在外存中的索引节点称为“磁盘索引节点”，放入内存时称为“内存索引节点”。相比之下，需要在内存索引节点中添加一些信息，比如文件是否被修改过，此时有多少个进程正在访问该文件。

为文件设置“密码”(例如:abc112233)，用户在请求访问文件时必须提供“密码”。

优点:保存密码的空间成本不多，验证密码的时间成本也很小。

缺点:系统中存储了正确的“密码”，不够安全。

用“密码”加密文件，访问文件时需要提供正确的“密码”才能正确解密文件。[3]

优点:保密性强，无需在系统中存储“密码”。

缺点:编码/解码，或者加密/解密需要一些时间。

在每个文件的FCB(或索引节点)中添加访问控制列表(ACL ),记录每个用户可以对文件执行哪些操作。

一些计算机可能有许多用户，因此访问控制列表可能非常大。我们可以用简化的访问列表来解决这个问题。

紧凑访问列表:以“组”为单位，标记每个“组”用户可以对文件进行哪些操作。当用户想要访问一个文件时，系统会检查用户所属的组是否有相应的访问权限。

索引节点是一种文件目录瘦身策略。因为检索文件时只需要文件名，所以除了文件名以外的其他信息都可以放在索引节点中。这样，目录条目只需要包含文件名和索引节点指针。

索引节点中设置了一个链接计数变量，用于表示链接到该索引节点的用户目录项的数量。

当User3访问ccc时，操作系统判断文件ccc属于链接型文件，于是会根据其中记录的路径逐层搜索目录，最终在User1的目录表中找到“aaa”条目，进而找到文件1的索引节点。

与内存分页类似，磁盘中的存储单元也会被划分为“块/磁盘块/物理块”。在许多操作系统中，磁盘块的大小与内存块和页面的大小相同。

内存和磁盘之间的数据交换(即读写操作和磁盘I/O)是以块为单位进行的。即一次读取一个块或一次写入一个块。

在内存管理中，进程的逻辑地址空间被划分为页面。同样，在外存管理中，为了方便文件数据的管理，文件的逻辑地址空间也被划分为文件“块”。那么文件的逻辑地址也可以用(逻辑块号，块内地址)的形式表示。用户通过逻辑地址操作自己的文件，操作系统负责逻辑地址到物理地址的映射。

连续分配要求每个文件占用磁盘上一组连续的块。用户给出要访问的逻辑块号，操作系统找到文件对应的目录项(FCB)——可以直接计算出逻辑块号对应的物理块号，物理块号=起始块号+逻辑块号。还需要检查用户提供的逻辑块号是否合法(逻辑块号≥长度为非法)，所以连续分配支持顺序访问和直接访问(即随机访问)。

读取磁盘块时，需要移动磁头。两个被访问的磁盘块相距越远，移动磁头所需的时间就越长。连续分配的文件在按顺序读写时速度最快，物理上不方便扩展，存储空间利用率低，产生难以使用的磁盘碎片，可以紧凑处理，但耗费大量时间。。

链接分配采取离散分配的形式，可以为文件分配离散的磁盘块。有隐式链接和显式链接两种。

用户给出要访问的逻辑块号I，操作系统找到对应于该文件的目录项(FCB)...从目录项中找到起始块号(即块0)，将逻辑块号0读入内存，从而知道逻辑块1中存储的物理块号，于是读取逻辑块1，然后找到逻辑块2的存储位置...诸如此类。因此，读取逻辑块I需要i+1次磁盘I/O时间..

链式分配(隐式链接)的文件只支持顺序访问，不支持随机访问，所以搜索效率较低。另外，指向下一个磁盘块的指针也需要消耗少量的存储空间。而使用隐式链接的链接分配方式，可以方便地对文件进行扩展。另外，所有空闲的磁盘块都可以使用，不会出现碎片问题，所以外存利用率高。

用于链接文件的物理块的指针被明确地存储在一个表中。也就是文件分配表(FAT)。

一个磁盘只能设置一个FAT。启动时，将FAT读入内存，并驻留在内存中。FAT的条目在物理上是连续存储的，并且每个条目具有相同的长度，因此可以隐含“物理块号”字段。

如果I >，从目录条目中查找起始块号；0，查询内存中的文件分配表FAT，稍后找到逻辑块I对应的物理块号。将逻辑块号转换成物理块号的过程不需要读盘操作。

链式分配(显式链接)的文件同时支持顺序访问和随机访问(当你要访问逻辑块I时，不需要依次访问前面的逻辑块0 ~ i-1)。因为块号转换的过程不需要访问磁盘，所以访问速度比隐式链接快很多。显式链接显然不会产生外部碎片，也方便文件的扩展。

索引分配允许文件离散分布在每个磁盘块中，系统会为每个文件建立一个索引表，其中记录了文件每个逻辑块对应的物理块(索引表的作用类似于内存管理中的页表——建立逻辑页和物理页的映射关系)。存储在索引表中的磁盘块称为索引块。存储文件数据的磁盘块称为数据块。

在显式链接的链式分配模式下，文件分配表FAT对应一个磁盘。在索引分配方法中，索引表对应于一个文件。物理块号[4]可以用固定长度表示，所以可以隐含索引表中的“逻辑块号”。

用户给出要访问的逻辑块号I，操作系统找到对应于该文件的目录项(FCB)...从目录项可以知道索引表的存储位置，索引表可以从外存读入内存，只能找到逻辑块I的存储位置。

可以看出，索引分配方法可以支持随机访问。文件扩展也很容易实现(只需给文件分配一个空闲块，添加一个索引表项)，但是索引表需要占用一定的存储空间。

索引块的大小是一个重要的问题。每个文件必须有一个索引块，所以索引块应该尽可能小，但是索引块太小，无法支持大文件。可以采用以下机制:

空闲列表法适用于“连续分发模式”。分配磁盘块:类似于内存管理中的动态分区分配，为一个文件分配连续的存储空间。类似地，诸如首次适配、最佳适配和最差适配之类的算法可以用于决定为文件分配哪个间隔。回收磁盘块:类似于内存管理中的动态分区分配，回收一个存储区域有四种情况:①回收区域前后没有相邻的空闲区域；(2)回收区前后有闲置区；③回收区前面是自由区；④恢复区之后是自由区。总之，回收时需要注意表项的合并。

操作系统存储链头和链尾指针。如何分配:如果一个文件申请k个磁盘块，k个磁盘块的分配将依次从链头中取出，并修改空闲链的链头指针。如何回收:回收的磁盘依次挂在链尾，修改空闲链的链尾指针。适合离散分配的物理结构。向一个文件分配多个块时，可能需要多次重复该操作。

操作系统存储链头和链尾指针。如何分配:如果一个文件申请k个磁盘块，可以使用先适应、最佳适应等算法，从链头开始搜索，根据算法规则找到所需大小的空闲磁盘块，分配给该文件。如果没有合适的连续空闲块，您还可以同时将不同范围的块分配给一个文件。注意，在分配之后，可能需要修改相应的数据，例如链指针和盘区大小。如何回收:如果回收区域与自由区相邻，则需要将其合并到自由区中。如果恢复区不与任何空闲区相邻，则将恢复区作为单独的空闲磁盘区挂在链的末尾。离散分布和连续分布都适用。将多个块分配给一个文件会更有效。

位图:每个二进制位对应一个磁盘块。在本例中，“0”表示磁盘块空闲，“1”表示磁盘块已被分配。位图一般用连续的“字”来表示。例如，本例中一个字的字长为16位，字中的每一位对应一个磁盘块。因此，(字体大小，位置号)可以用来对应一个磁盘块号。当然，有些主题也描述为(行号，列号)

磁盘块号、字体大小和标签号从0开始。如果n代表字长，那么

如何分配:如果文件需要k个块，①依次扫描位图，寻找k个相邻或不相邻的“0”；(2)根据字体大小和位数计算相应的磁盘块号，并将相应的磁盘块分配给文件；③将相应的位设置为“1”。如何回收:①根据回收的磁盘块数计算出对应的字体大小和位置号；②将相应的二进制位设置为“0”

自由列表法和自由链表法不适合大型文件系统，因为自由列表或自由链表可能太大。UNIX系统采用组链接方法管理磁盘空闲块。在文件卷的目录区专门用一个磁盘块作为“超级块”，超级块需要在系统启动时读入内存。并确保内存与外部存储器中的“超级块”数据一致。

当进行创建系统调用时，需要提供几个主要参数:

当操作系统处理创建系统调用时，它主要做两件事:

当进行删除系统调用时，需要提供几个主要参数:

当操作系统处理删除系统调用时，它主要做几件事。

事情:

在很多操作系统中，用户在操作一个文件之前，需要使用开放系统调用“打开文件”，需要提供几个主要参数:

当操作系统处理开放系统调用时，它主要做几件事:

当进程使用完文件后，需要“关闭文件”。

当操作系统处理关闭系统调用时，它主要做几件事:

该进程使用读系统调用来完成写操作。你需要指定是哪个文件(在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号)，读取多少数据(比如读取1KB)，读取的数据放在内存的什么位置。操作系统在处理read系统调用时，会将用户指定大小的数据从read指针指向的外部存储器读入用户指定的内存区域。

当一个进程使用write系统调用完成一个写操作时，需要指明是哪个文件(在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号)，还需要指明要写多少数据(例如，write 1KB)以及写回外存的数据放在内存的什么地方。当操作系统处理write系统调用时，它将从用户指定的内存区域写回指定大小的数据。

寻道时间(seek time) T S:在读/写数据之前，将磁头移动到指定磁道所需的时间。

延迟时间T R:通过旋转磁盘将磁头定位到目标扇区所需的时间。设磁盘速度为r(单位:rpm，或rpm)，则需要平均延迟时间。

传输时间T t:从磁盘读取数据或向磁盘写入数据所需的时间。假设磁盘速度为R，这次读/写的字节数为B，每个磁道的字节数为N..规则

总平均访问时间ta

延迟时间和传输时间都与磁盘速度有关，并且它们是线性相关的。转速是硬件固有的属性，操作系统无法优化延迟时间和传输时间，但操作系统的磁盘调度算法会直接影响寻道时间。

根据进程请求访问磁盘的顺序进行调度。

优点:公平；如果所请求的轨迹是集中的，则该算法的性能是可接受的。

缺点:如果大量进程争用磁盘，请求磁道分散，FCFS性能差，寻道时间长。

SSTF算法将优先选择最接近当前磁头的磁道。你可以保证每次寻道时间最短，但不能保证总寻道时间最短。(其实就是贪心算法的思想，只选择眼前的最好，整体不一定是最好的。)

优点:性能更好，平均寻道时间短。

缺点:可能会出现“饥饿感”。

SSTF算法会饿的原因是磁头可能在小范围内来回移动。为了防止这个问题，可以规定磁头移动到最外磁道时只能向内移动，移动到最内磁道时只能向外移动。这就是扫描算法的思想。因为磁头移动的方式很像电梯，所以也叫电梯算法。

优点:性能好，平均寻道时间短，无饥饿感。

缺点:①磁头的移动方向只能在到达最外轨道时改变；②②扫描算法对各位置轨迹的响应频率不均匀。

在扫描算法中，磁头的移动方向只能在它到达最外面的磁道时改变。事实上，在处理完磁道184的访问请求后，没有必要将磁头向右移动。看起来调度算法就是解决这个问题的。如果头部运动方向没有其他要求，可以立即改变头部运动方向。(边移动边观察，所以叫看)

优点:与扫描算法相比，不需要每次都移动到最外侧或最内侧来改变磁头的方向，进一步缩短了寻道时间。

扫描算法对不同位置轨迹的响应频率不均匀，C扫描算法就是为了解决这个问题。规定只有磁头向某个方向移动才会处理磁道访问请求，返回时直接快速移动到起始端，不处理任何请求。

优点:与扫描相比，各个位置的轨迹响应频率非常平均。

缺点:磁头的移动方向只能在到达最外面的轨道时改变。此外，与扫描算法相比，平均寻道时间更长。

C-SCAN算法的主要缺点是，磁头的移动方向只能在到达最外层磁道时改变，磁头返回时不一定需要返回最外层磁道。C-LOOK算法就是为了解决这个问题。如果在磁头的移动方向上没有磁道访问请求，磁头可以立即返回，磁头只需要返回到有磁道访问请求的位置。

优点:与C扫描算法相比，无需每次都移动到最外侧或最内侧来改变磁头的方向，进一步缩短了寻道时间。

磁盘地址结构的设计；

问:磁盘的物理地址是(柱面号，磁盘号，扇区号)而不是(磁盘号，柱面号，扇区号)。

答:在读取具有连续地址的磁盘块时，地址结构(柱面号、磁盘号和扇区号)可以减少磁头移动所消耗的时间。

减少延迟时间的方法:

步骤1:执行低级格式化(物理格式化)并将磁盘的每个磁道划分为扇区。一个扇区通常可以分为三个部分:头、数据区(如512B大小)和尾。管理扇区所需的各种数据结构一般存储在头尾部分，包括扇区校验码(如奇偶校验、CRC循环冗余校验码等。校验码用于检查扇区中的数据是否有错误)。

第二步:对磁盘进行分区，每个分区由若干个柱面组成(即分为大家熟悉的c盘、D盘、E盘)。

步骤3:进行逻辑格式化并创建文件系统。包括创建文件系统的根目录和初始化用于存储空间管理的数据结构(如位图和空闲分区表)。

计算机开机时，需要一系列的初始化工作，这些工作是通过执行初始化程序(bootstrap程序)来完成的。

初始化程序可以放在ROM(只读存储器)中。ROM中的数据是在工厂写的，以后不能修改。ROM中只存储了一个很小的bootloader，完整的bootloader放在磁盘的引导块(boot block/boot partition)上，位于磁盘的固定位置。电脑开机时先运行bootloader，通过执行程序可以找到引导块，将完整的bootloader读入内存完成初始化。带有引导分区的磁盘称为引导磁盘或系统盘(C: disk)。

对于简单的磁盘，可以在逻辑格式化期间(当建立文件系统时)检查整个磁盘的坏块，以指示哪些扇区是坏的，例如在FAT表上。这样，坏块对操作系统是不透明的。

对于复杂的磁盘，磁盘控制器(磁盘设备内部的硬件组件)将维护一个坏块链表。当磁盘在出厂前经过低级格式化(物理格式化)时，坏区块链被初始化。将保留一些“备用扇区”来替换坏块。这种方案称为扇区备份。这样，坏块对操作系统是透明的。