操作系统考研复习——第四章（文件管理）_有一个顺序文件含有10000

4. 文件管理

4.1 文件管理基础

4.1.1 文件的概念

1. 数据项、记录和文件

基于文件系统的概念，可以把数据组成分为数据项、记录和文件三级。

1. 数据项
   在文件系统中，数据项是最低级的数据组成形式，可把它分成以下两种类型：
   1）基本数据项。这是用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，又称为字段。例如，用于描述一个学生的基本数据项有：学号、姓名、年龄、所在班级等。
   2）组合数据项。是由若干个基本数据项组成的，简称组项。例如工资是个组项，它可由基本工资、工龄工资和奖励工资等基本项所组成。

2. 记录
   记录时一组相关数据项的集合，用于描述一个对象在某方面的属性。如一个学生的记录可以是学号、姓名、年龄以及所在班级等数据项组成的。而每个记录都需要有一个关键字来唯一标识。如学号就可以唯一标识一条记录。

3. 文件
   文件是指由创建者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构文件中，文件由一组相似的记录组成，报考某学校的所有考生的报考信息记录，又称为记录式文件；而无结构文件则被视为一个字符流，比如一个二进制文件或字符文件，又称流式文件。
   

   文件、记录和数据项之间的层次关系：
   
   

2. 文件属性

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

所有文件的信息都在保存目录结构中，而目录结构保持在外存上。文件信息在需要时才调入内存。通常，目录条目包括文件名称及其唯一的标识符，而标识符定位其他属性的信息。

3. 文件系统的接口

为方便用户的使用，文件系统以接口的形式提供了一组对文件和记录操作的方法和手段。通常是下面两种类型的接口：

1. 命令接口，是指作为用户与文件系统直接交互的接口，用户可通过键盘终端键入命令取得文件系统的服务。
2. 程序接口，是指作为用户程序与文件系统的接口，用户程序可通过系统调用取得文件系统的服务，例如，用于创建文件的系统调用Create，用于打开一个文件的系统调用Open等。

4. 文件的基本操作

1. 创建文件。创建文件有两个必要步骤：一是在文件系统中为文件找到空间；二是在目录中为新文件创建条目，该条目记录文件名称、在文件系统中的位置及其他可能的信息。
   

2. 删除文件。在删除时，应先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。
   

3. 读文件。在读文件时，根据用户给出的文件名去查找目录，从中得到被读文件在外存中的位置；在目录项中，还有一个指针用于对文件的读/写。
   

4. 写文件。在写文件时，根据文件名查找目录，找到指定文件的目录项，再利用目录中的写指针进行写操作。
   

5. 设置文件的读/写位置。前面所述的文件读/写操作，都只提供了对文件顺序存取的手段，即每次都是从文件的始端进行读或写；设置文件读/写位置的操作，通过设置文件读/写指针的位置，以便读/写文件时不再每次都从其始端，而是从所设置的位置开始操作，因此可以改顺序存取为随机存取。

这些基本操作可以组合起来执行其他文件操作。如一个文件的复制是由创建新文件、从旧文件读出并写入新文件中，这些基本操作来完成。

5. 文件的打开与关闭

当用户要求对一个文件实施多次读/写或其他操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，在大多数OS中都引入了“打开”（open）这一文件系统调用，当用户第一次请求时对某文件进行操作时，须先利用open系统调用将该文件打开。所谓“打开”，是指系统将指名文件的属性（包括该文件在外存上的物理位置），从外存拷贝到内存打开文件表（包含所有打开文件信息的表）的一个表目中，并将该表目的编号（或称为索引号）返回给用户。换言之，“打开”就是在用户和指定文件之间建立起一个连接。此后，用户可通过该连接直接得到文件信息，从而避免了再次通过目录检索文件，即当用户再次向系统发出文件操作请求时，系统根据用户提供的索引号可以直接在打开文件表中查找到文件信息。（注意，在open调用完成后，操作系统对该文件的任何操作都不再需要文件名，而只需要open调用返回的指针）这样不仅节省了大量的检索开销，也显著地提高了对文件的操作速度。

如果用户已不再需要对该文件实施相应的操作，可利用“关闭”（close）系统调用来关闭文件，即断开连接，OS将会把文件从打开文件表中的表目上删除掉。

4.1.2 文件的逻辑结构

在系统中的所有文件都存在着以下两种形式的文件结构：

1. 文件的逻辑结构。这是从用户观点出发所观察到的文件组织形式，即文件是由一系列的逻辑记录组成的，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。用户所看到的文件就是逻辑文件。
2. 文件的物理结构，又称为文件的存储结构。这是指系统将文件存储在外存上所形成的一种存储组织形式，是用户不能看见的。文件的物理结构不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。无论是文件的逻辑结构，还是其物理结构，都会影响对文件的检索速度。

按逻辑结构，文件可划分为无结构文件和有结构文件两种。

1. 无结构文件（流式文件）

无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。其文件的长度是以字节为单位的。如：Windows 操作系统中的 .txt 文件。

2. 有结构文件（记录式文件）

有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）。

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

有结构文件按记录的组织形式可以分为以下几种：

1）顺序文件

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

在顺序文件中的记录，可以按照各种不同的顺序进行排序。一般地，可分为两种情况：

• 串结构。在串结构文件中的记录，通常是按存入时间的先后进行排序的，各记录之间的顺序与关键字无关。在对串结构文件进行检索时，每次都必须从头开始，逐个记录地查找，直到找到指定的记录或查完所有的记录为止。显然，对串结构文件进行检索是比较费时的。
• 顺序结构。由用户指定一个字段作为关键字，文件中的所有记录按照这个关键字进行排序。
  

已经知道了文件的起始地址（也就是第一个记录存放的位置），如何进行记录寻址：

注：一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。之后提到的顺序文件也默认如此。 可见，顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单，不用按照关键字的顺序来）。为了解决这个问题，可以为顺序文件配置一个运行记录文件或称为事务文件，把试图增加、删除或修改的信息记录与其中，规定每隔一段时间，将运行记录文件与原来的主文件加以合并，产生一个按关键字排序的新文件。

顺序文件的最佳应用场合是在对文件中的记录进行批量存储时（即每次要读或写一大批记录）。所有逻辑文件中顺序文件的存储效率是最高的。但在交互应用的场合，如果用户（程序）要求查找或修改单个记录，系统需要在文件的记录中逐个地查找，此时，顺序文件所表现出来的性能就可能很差。

当对于一个含有N个记录的顺序文件，如果采用顺序查找法，查找到一个指定的记录，平均需要查找N/2次。

2）索引文件

变长记录文件只能顺序查找，系统开销较大。为此，可以建立一张索引表以加快检索速度，索引表本身是定长记录的顺序文件，因此可以快速找到第 i 个记录对应的索引项。索引表是按关键字进行排序的。

可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

对索引文件存取时，必须先查找索引表。索引项只包含每条记录的长度和在逻辑文件中的起始地址。因为每条记录都要有一个索引项，因此提高了存储代价。

另外，可以用不同的数据项建立多个索引表。如：学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。（Eg：SQL 就支持根据某个数据项建立索引的功能）

主要优点：它将一个需要顺序查找的文件改造称一个可随机查找的文件，极大地提高了对文件的查找速度。同时，利用索引文件插入和删除记录也非常方便。
缺点：除了有主文件外，还须配置一张索引表，而且每个记录都要有一个索引项，因此增加了存储开销。每个记录对应一个索引表项，因此索引表可能会很大。比如：文件的每个记录平均只占 8B，而每个索引表项占32个字节，那么索引表都要比文件内容本身大4倍，这样对存储空间的利用率就太低了。

3）索引顺序文件

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构的顺序文件），平均须查找 5000 个记录。

若采用索引顺序文件结构，可把 10000 个记录分为 √10000 = 100 组，每组 100 个记录。则需要先顺序查找 索引表找到分组（共100个分组，因此索引表长度为 100，平均需要查 50 次），找到分组后，再在分组中顺序查找记录（每个分组100 个记录，因此平均需要查 50 次）。可见，采用索引顺序文件结构后，平均查找次数减少为 50+50 = 100 次。

同理，若文件共有 10⁶个记录，则可分为 1000 个分组，每个分组 1000 个记录。根据关键字检索一个记录平均需要查找 500+500 = 1000 次。这个查找次数依然很多，如何解决呢？

4）多级索引顺序结构

为了进一步提高检索效率，可以为顺序文件建立多级索引表。例如，对于一个含 10⁶个记录的文件，可先为该文件建立一张低级索引表，每 100 个记录为一组，故低级索引表中共有 10000 个表项（即10000个定长记录），再把这 10000 个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有 100 个表项。

4.1.3 目录结构

文件目录也是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。对目录管理的要求如下：

1. 实现“按名存取。目录在用户（应用程序）所需要的文件名和文件之间提供一种映射。
2. 提高对目录的检索速度。
3. 文件共享。
4. 允许文件重名。

1. 文件控制块和索引控制块

1. 文件控制块
   文件控制块（FCB）是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。为了创建一个新文件，系统将分配一个FCB并存放在文件目录中，成为目录项。

   FCB主要包含以下信息：

   • 基本信息，如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
   • 存储控制信息，如文件存取权限等。
   • 使用信息，如文件建立时间、修改时间等。

   

2. 索引结点（FCB的改进）
   文件目录通常是存放在磁盘上的，当文件很多时，文件目录可能要占用大量的盘块。在查找目录的过程中，需要依次将目录文件的每个盘块中的目录调入内存，然后根据用户所给定的文件名与目录项中的文件名逐一比对，直到找到指定文件为止。

   而在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项（即其中的文件名与指定要查找的文件名相匹配）时，才需从给目录项中读出该文件的物理地址。而其他一些对该文件进行描述的信息在检索目录时一概不用。显然，这些信息在检索目录时不需调入内存。为此，在有的系统中，如UNIX系统，便采用了把文件名与文件描述信息分开的方法。使文件描述信息单独形成一个称为索引结点的数据结构。

   这样目录项就只需要包含文件名、索引结点指针。
   
   当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。
   存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。
   相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。

2. 目录结构

目录可以执行的操作：

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

1）单极目录结构

早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。

单级目录实现了“按名存取”，但是不允许文件重名。

在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。而重名问题在多道程序环境下却又是难以避免的，即使是在单用户环境下，当文件数超过数百个是，也难以记忆。所以单级目录结构不适用于多用户操作系统。

2）两级目录结构

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

该结构虽然能有效地将多个用户隔开，在各用户之间完全无关时，这种隔离式一个优点。但当多个用户之间要相互合作去完成一个任务，且一用户又需去访问其他用户的文件时，这种隔离便成为一个缺点，因为这种隔离会使诸用户之间不便于共享文件。

3）树形目录结构

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

例如：自拍.jpg 的绝对路径是 “/照片/2015-08/自拍.jpg”

系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表；找到“照片”目录的存放位置后，从外存读入对应的目录表；再找到“2015-08”目录的存放位置，再从外存读入对应目录表；最后才找到文件“自拍.jpg”的存放位置。整个过程需要3次读磁盘I/O操作。

很多时候，用户会连续访问同一目录内的多个文件（比如：接连查看“2015-08”目录内的多个照片文件），显然，每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”。

例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径” 。 在 Linux 中，“.”表示当前目录，因此如果“照片”是当前目录，则”自拍.jpg”的相对路径为：“./2015-08/自拍.jpg”。从当前路径出发，只需要查询内存中的“照片”目录表，即可知道”2015-08”目录表的存放位置，从外存调入该目录，即可知道“自拍.jpg”存放的位置了。

可见，引入“当前目录”和“相对路径”后，磁盘I/O的次数减少了。这就提升了访问文件的效率。

把从当前目录开始直到数据文件为止所构成的路径名成为相对路径名。
把从树根开始的路径名称为绝对路径名。

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

4）无环图目录结构

可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。
只有共享计数器减为0时，才删除结点。
注意：共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。

4.1.4 文件共享

注意：多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。
如果是多个用户都“复制”了同一个文件，那么系统中会有“好几份”文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并没有影响。

1. 基于索引结点的共享方式（硬链接）

索引结点中设置一个链接计数变量 count，用于表示链接到本索引结点上的用户目录项数。
若 count = 2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。
若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减 1。

若 count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。
当 count = 0 时系统负责删除文件。

2. 基于符号链的共享方式（软链接）

在利用符号链方式实现文件共享时，只有文件的拥有者才拥有指向其索引结点的指针。而共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也就不会发生在文件主删除一个共享文件后留下一个悬空指针的情况。

当文件的拥有者把一个共享文件删除后，其他用户通过符号链去访问它时，会出现访问失败，于是将符号链删除，此时不会产生任何影响。当然，利用符号链实现文件共享仍然存在问题。例如，一个文件采用符号链方式共享，当文件拥有者将其删除，而在共享的其他用户用其符号链接访问该文件之前，又有人在同一路径下创建了另一个具有同样名称的文件，则该符号链将仍然有效，但访问的文件己经改变，从而导致错误。

在符号链的共享方式中，当其他用户读共享文件时，需要根据文件路径名逐个地查找目录，直至找到该文件的索引结点。因此，每次访问时，都可能要多次地读盘，使得访问文件的开销变大并增加了启动磁盘的频率。此外，符号链的索引结点也要耗费一定的磁盘空间。

当 User3 访问“ccc”时，操作系统判断文件“ccc”属于 Link 类型文件，于是会根据其中记录的路径层层查找目录，最终找到 User1 的目录表中的“aaa”表项，于是就找到了文件1的索引结点。

可以这样说：文件共享，“软”“硬” 兼施。硬链接就是多个指针指向一个索引结点，保证只要还有一个指针指向索引结点，索引结点就不能删除；软链接就是把到达共享文件的路径记录下，当要访问文件时，根据路径寻找文件。可以想象。硬链接的查找速度要比软链接的快。

4.1.5 文件保护

文件保护通过口令保护、加密保护和访问控制等方式实现。其中口令保护和加密保护是为了防止用户文件被他人存取或窃取，而访问控制则用于控制用户对文件的访问方式。

1. 口令保护

优点：保存口令的空间开销不多，验证口令的时间开销也很小。
缺点：正确的“口令”存放在系统内部，不够安全。

2. 加密保护

优点：保密性强，不需要在系统中存储“密码”。
缺点：编码/译码，或者说加密/解密要花费一定时间。

3. 访问控制

在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-Control List, ACL），该表中记录了各个用户可以对该文件执行哪些操作。


注意：如果对某个目录进行了访问权限的控制，那也要对目录下的所有文件进行相同的访问权限控制。

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

4.1.6 补充

1. 设置当前目录的主要目的是加快文件的检索速度。
2. 文件的读/写速度取决于磁盘的性能。
3. 从系统角度看，文件系统负责对文件的存储空间进行组织、分配，负责文件的存储并对存入文件进行保护、检索。从用户角度看，文件系统根据一定的格式将用户的文件存放到文件存储器中适当的位置，当用户需要使用文件时，系统根据用户所给的文件名能够从文件存储器中找到所需要的文件。即从用户角度看，操作系统引入文件系统的目的是实现对文件的按名存取。
4. 一个文件对应一个FCB，而一个文件目录项就是一个FCB。文件系统在创建一个文件时，就是在为它建立一个文件目录项。
5. 打开文件操作的主要工作是把指定文件的目录复制到内存指定的区域（将该文件的FCB存入内存的活跃文件目录表，而不是将文件内容复制到主存）。找到指定文件目录是打开文件之前的操作。
6. 一个文件被用户进程首次打开即被执行了open操作，会把文件的FCB调入内存中，而不会把文件内容读到内存中，只有进程希望获取文件内容时才会读入文件内容。
7. 文件的逻辑结果是为了方便用户而设计的。物理结构是取决于存储介质特性和操作系统的管理方式。
8. 索引文件由逻辑文件和索引表组成。逻辑索引的目的是加快文件数据的定位，是从用户角度出发的，而物理索引的主要目的是管理不连续的物理块，是从系统管理的角度出发的。
9. 删除文件时，与此文件关联的目录项和文件控制块需要随着文件一同删除，同时释放文件关联的内存缓冲区。
10. 目录文件是FCB的集合，一个目录中既可能有子目录，又可能有数据文件，因此目录文件中存放的是子目录和数据文件的信息。
11. 文件系统采用多级目录结构的目的是解决命名冲突。采用多级目录结构后，符合了多层次管理的需要，提高了文件查找的速度，还允许用户建立同名文件。
12. 对一个文件的访问，常由用户访问权限和文件属性共同限制。
13. 加密保护和访问控制两种机制相比，访问控制机制必须由系统实现。访问控制机制的安全性较差，但灵活性相对较高。
14. 为了对文件系统中的文件进行安全管理，任何一个用户在进入系统时必须进行注册，这一级安全管理是系统级。系统级安全管理包括注册和登录。
15. 不同的文件系统存放的方法是不一样的。一个文件存放在磁带中时，通常采用连续存放方法，文件在硬盘上一般不采用连续存放方法。
16. 防止系统故障造成系统内故障可以采用备份的方法保护文件，而存取控制矩阵的方法用于多用户之间的存取权限保护。
17. 可以提高文件访问速度的方法有：为文件分配连续的簇、采用磁盘高速缓存、提前读和延迟写。提前读是指在读当前盘块时，将下一个可能要访问的盘块数据读入缓冲区，以便需要时直接从缓冲区中读取，提高了文件的访问速度。延迟写是指先将数据写入缓冲区，并置上“延迟写”标志，以备不久之后访问，当缓冲区需要再次被分配出去时，才将缓冲区数据写入磁盘，减少了访问磁盘的次数，提高了文件的访问速度。
18. 当多个进程共享一个文件时，
    

4.2 文件系统实现

4.2.1 文件实现——文件分配方式

对磁盘非空闲块的管理就是文件的分配方式；对磁盘空闲块的管理就是文件存储空间管理。

文件分配方式（文件的物理结构）有三种方式：

1. 文件块、磁盘块

在内存管理中，进程的逻辑地址空间被分为一个一个页面。
同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。
于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。

2. 连续分配

连续分配方法要求每个文件在磁盘上占有一组连续的块。通常，它们都位于一条磁道上，在进行读/写操作时，不必移动磁头。在采用连续组织方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。

优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快，由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，磁头的移动距离最少，因此，这种对文件访问的速度是几种存储空间分配方式中最快的一种。
缺点：不方便文件拓展，一旦需要增加，就需要大量移动盘块；存储空间利用率低，会产生磁盘碎片；且很难确定一个文件需要的空间大小，因而只适用于长度固定的文件。

3. 链接分配

链接分配采取离散分配的方式，消除了外部碎片，因此提高了磁盘空间的利用率。分为隐式链接和显式链接两种。

1）隐式链接

隐式链接——除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
优点：很方便文件拓展，不会有碎片问题，外存利用率高。
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇。比如，一个簇可包含4个盘块，在进行盘块分配时，是以簇为单位进行的。在链接文件中的每个元素也是以簇为单位。这样将会成倍地减少查找指定块的时间，而且也可减少指针所占用的存储空间，但却增大了内部碎片，而且这种改进也是非常有限的。

注：考试题目中遇到未指明隐式/显式的“链接分配”，默认指的是隐式链接的链接分配。

2）显式链接

指把用于链接文件各物理块的指针，从每个物理块的块末尾中提取出来，显式地存放在内存的一种链接表中。该表在整个磁盘中仅设置一张，称为文件分配表（FAT，File Allocation Table）。开机时文件分配表放入内存，并常驻内存。

一个磁盘仅设置一张FAT。 开机时，将FAT读入内存，并常驻内存。

优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
缺点：文件分配表的需要占用一定的存储空间。

4. 索引分配

事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个 FAT 调入内存。为此，应将每个文件所对应的盘块号集中地放在一起，在访问到某个文件时，将该文件所对应的盘块号一起调入内存。索引分配方法就是基于这种想法所形成的一种分配方法。

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

若每个磁盘块1KB，一个索引表项4B，则一个磁盘块只能存放 256 个索引项。如果一个文件的大小超过了256块，那么一个磁盘块是装不下文件的整张索引表的，如何解决这个问题？
可以采用以下机制了解决这个问题。

1）链接方案

链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到 i 号索引块，必须先依次读入 0~i-1 号索引块，这就导致磁盘I/O次数过多，查找效率低下。

2）多层索引

多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256 个索引项。
若某文件采用两层索引，则该文件的最大长度可以到
256 * 256 * 1KB = 65,536 KB = 64MB
可根据逻辑块号算出应该查找索引表中的哪个表项。
如：要访问 1026 号逻辑块，则
1026/256 = 4，1026%256 = 2
因此可以先将一级索引表调入内存（第一次），查询 4 号表项，将其对应的二级索引表调入内存（第二次），再查询二级索引表的2号表项即可知道 1026 号逻辑块存放的磁盘块号了。访问目标数据块，需要3次磁盘I/O。（第三次是将对应的数据块调入内存）

若采用三层索引，则文件的最大长度为
256 * 256 * 256 * 1KB = 16GB
类似的，访问目标数据块，需要四次磁盘I/O。

采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要 K + 1 次读磁盘操作。

多级索引的主要优点是：大大加快了对大型文件的查找速度。其主要缺点是在访问一个盘块时，其所需启动磁盘的次数随着索引级数的增加而增多，即使是对于小文件，也是如此。实际情况是，通常总是以中、小文件居多，而大文件是较少的。因此可见，如果在文件系统中仅采用了多级索引组织方式，并不能获得理想的效果。

3）混合索引（常考）

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

优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

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

5. 逻辑结构 Vs 物理结构

1）C语言创建无结构文件

2）C语言创建顺序文件

文件内部各条记录的逻辑结构（链式存储、顺序存储）：由创建文件的用户自己设计的。
文件整体用什么物理结构（连续分配、链接分配或索引分配）：由操作系统决定。

3）索引文件采用索引分配

索引文件：从用户视角（逻辑结构上）来看，整个文件依然是连续存放的。如：前1MB存放索引项，后续部分存放记录。

4.2.2 文件实现——文件存储空间管理

1. 存储空间的划分与初始化

2. 文件存储器空间管理

文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题。

1）空闲表法

空闲表法属于连续分配方式。系统为外存上的所有空闲区建立一张空闲盘块表。

如何分配磁盘块：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

如何回收磁盘块：与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况——①回收区的前后都没有相邻空闲区；②回收区的前后都是空闲区；③回收区前面是空闲区；④回收区后面是空闲区。总之，回收时需要注意表项的合并问题。

2）空闲链表法

1. 空闲盘块链
   操作系统保存着链头、链尾指针。

   如何分配：若某文件申请 K 个盘块，则从链头开始依次摘下 K 个盘块分配，并修改空闲链的链头指针。
   如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

   这种方法的优点是分配和回收一个盘块的过程非常简单，适用于离散分配的物理结构。但在为一个大小超过一个盘块的文件分配盘块时，需要重复多次操作。

2. 空闲盘区链
   操作系统保存着链头、链尾指针。

   如何分配：若某文件申请 K 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
   如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

   离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。

3. 位示图法

如何分配：若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；③将相应位设置为“1”。
如何回收：①根据回收的盘块号计算出对应的字号、位号；②将相应二进制位设为“0”

这种方法的主要优点是从位示图中很容易找到一个或一组相邻接的空闲盘块。由于位示图很小，占用空间少，因而可将它保存在内存中，进而使在每次进行盘区分配时，无需首先将盘区分配表读入内存中，从而节省了许多磁盘的启动操作。连续分配、离散分配都适用。

4. 成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。


其大致思想是：把顺序的n个空闲扇区地址保存在第一个空闲扇区内，其后一个空闲扇区内则保存另一顺序空闲扇区的地址，如此继续，直到所有空闲扇区均予以链接。

4.2.3 文件系统层次结构

用一个例子来辅助记忆文件系统的层次结构：
假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx” 的最后100条记录。

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

4.2.4 补充

1. 文件的物理结构包括连续、链式、索引三种，其中链式结构不能实现随机访问，连续结构不易于扩展。因此随机访问且易于扩展是索引结构的特性。

2. 为支持CD-ROM中视频文件的快速随机播放，播放性能最好的文件数据块组织（要确保最短的查询时间）是连续结构。

3. 在磁盘上，最容易导致存储碎片发生的物理文件结构是顺序存放（连续分配）。顺序文件需要占用连续的磁盘空间，所以会产生难以分配的碎片。

4. 关于目录检索，通常不采用散列法，散列法是通过类似于哈希函数通过关键字进行检索，而哈希函数需要冗余的空间来避免冲突，所以会导致文件目录很大。一般是采用顺序检索法，只要路径名的一个分量未找到，就应停止查找。
   

5. 
   
   

6. 通常用户可以根据需要来确定文件的逻辑结构，而文件的物理结构是由操作系统的设计者根据文件存储器发特性来确定，一旦确定，就操作系统管理。

7. 文件系统为每个文件创建一张索引表，存放文件数据块的磁盘存放位置。打开文件表仅存放已打开文件信息的表，将指明文件的属性从外存复制到内存，在使用该文件时直接返回索引。而位图和空闲盘块链表是磁盘管理方法。

8. 随机存取是索引文件速度快，顺序存取时顺序存取文件速度快。

9. 顺序文件进行检索时，首先从FCB中读出文件的第一个盘块号；而对索引文件进行检索时，应先从FCB中读出文件索引块的开始地址。

10. 索引文件支持变长的文件，同时可以随机访问文件的指定数据块；链接分配不支持随机访问，需要依靠指针依次访问；连续分配的文件长度固定，不支持可变文件长度（连续分配的文件长度虽然也可变，但是需要大量移动数据，代价较大，相比之下不太合适）。

11. ①连续分配方式的优点是可以随机访问（磁盘），访问速度快；缺点是要求有连续的存储空间，容易产生碎片，降低磁盘空间的利用率，并且不利于文件的增长扩充。
    ②链接分配方式的优点是不要求连续的存储空间，能更有效地利用磁盘空间，并且有利于扩充文件；缺点是只适合顺序访问，不适合随机访问；另外，链接指针占用一定的空间，降低了存储效率，可靠性也差。
    ③索引分配方式的优点是既支持顺序访问又支持随机访问，查找效率高，便于文件删除；缺点是索引表会占用一定的存储空间。

4.3 磁盘组织与管理

4.3.1 磁盘的结构

1. 磁盘、磁道、扇区

2. 如何在磁盘中读/写数据

3. 盘面、柱面

4. 磁盘的物理地址

可用（柱面号，盘面号，扇区号）来定位任意一个“磁盘块”。在“文件的物理结构”小节中，我们经常提到文件数据存放在外存中的几号块，这个块号就可以转换成（柱面号，盘面号，扇区号）的地址形式。

可根据该地址读取一个“块”
①根据“柱面号”移动磁臂，让磁头指向指定柱面；
②激活指定盘面对应的磁头；
③磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇
区的读/写。

5. 磁盘的分类

4.3.2 磁盘调度算法

用户访问文件，需要操作系统的服务，文件实际上存储在磁盘中，操作系统接收用户的命令后，经过一系列的检验访问权限和寻址过程后，最终都会到达磁盘，控制磁盘把相应的数据信息读出或修改。当有多个请求同时到达时，操作系统就要决定先为哪个请求服务，这就是磁盘调度算法要解决的问题。

1. 一次磁盘读/写操作需要的时间

1）寻道时间

操作系统的磁盘调度算法会直接影响寻道时间。而磁盘调度算法影响的指标是移动磁头所需时间。

2）延迟时间

3）传输时间

总的平均存取时间 Ta = Ts + 1/2r + b/(rN)。
虽然这里给出了总平均存取时间的公式，但是这个平均值是没有太大实际意义的，因为在实际的磁盘I/O操作中，存取时间与磁盘调度算法密切相关。调度算法直接决定寻道时间，从而决定总的存取时间。

三个时间中，一般来说，寻道时间因为要移动磁臂，所以占用时间最长。

目前常用的磁盘调度算法有以下几种。

2. 先来先服务算法（FCFS）

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

优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去。
缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。

3. 最短寻找时间优先（SSTF）

SSTF 算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。（其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优）

优点：性能较好，平均寻道时间短。
缺点：可能产生“饥饿”现象。

4. 扫描算法（SCAN）

SSTF 算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移 动。这就是扫描算法（SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。

优点：性能较好，平均寻道时间较短，不会产生饥饿现象。
缺点：①只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。
②SCAN算法对于各个位置磁道的响应频率不平均（如：假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等磁头移动很长一段距离；而响应了184号磁道的请求之后，很快又可以再次响应 184 号磁道的请求了）

5. LOOK 调度算法

扫描算法（SCAN）中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。LOOK 调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。（边移动边观察，因此叫 LOOK）

优点：比起 SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。

6. 循环扫描算法（C-SCAN）

SCAN算法对于各个位置磁道的响应频率不平均，而 C-SCAN 算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

优点：比起SCAN 来，对于各个位置磁道的响应频率很平均。
缺点：只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了；并且，磁头返回时其实只需要返回到18号磁道即可，不需要返 回到最边缘的磁道。另外，比起SCAN算法来，平均寻道时间更长。

7. C-LOOK 调度算法

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

优点：比起 C-SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。

若题目中无特别说明， 则SCAN 就是 LOOK， C-SCAN 就是C-LOOK。

4.3.3 减少延迟时间的方法

结论：磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”。

为了减少延迟时间，有以下方法：

1. 交替编号

若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。

2. 扩展：磁盘地址结构的设计

注：这种方法需要移动磁头臂。

注：采用这种方法此不需要移动磁头臂。只需要激活相邻盘面的磁头即可。

读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间。

存储一个文件时，当一个磁道存储不下时，剩下部分时存在同一个盘面的不同磁道好，还是存在同一个柱面上的不同盘面好？
寻道时间对于一次磁盘访问的影响是最大的，若存在同一个盘面的不同磁道，则磁臂势必要移动，这样会大大增加文件的访问时间，而存在同一个柱面上的不同盘面就不需要移动磁道，所以一般情况下存在同一个柱面上的不同盘面更好。

3. 错位命名

在不采用错位命名法的情况下：

在采用错位命名法的情况下：

4.3.4 磁盘的管理

1. 磁盘初始化

2. 引导块

计算机启动时需要运行一个初始化程序（自举程序），它初始化CPU、寄存器、设备控制器和内存等，接着启动操作系统。

当初始化程序放在ROM中时，会存在没办法更新初始化程序的问题。

3. 坏块

对坏块的处理实质上就是用某种机制，使系统不去使用坏块。

4.3.4 补充

1. 磁盘调度的目的是缩短寻道时间。
2. 磁盘上的文件以块为单位读/写。因为文件以块为单位存放于磁盘中，文件的读写也以块为单位。
3. 磁盘调度中，对读/写时间影响最大的是寻道时间，寻道过程为机械运动，时间较长，影响较大。
4. 扇区数据的处理时间主要影响传输时间。延迟时间的大小与磁盘调度算法无关；与文件的物理结构有关，而且取决于磁盘空闲空间的分配程序。
5. 先来先服务算法根据磁盘请求的时间先后进行调度，因而可能随时改变词条方向。而电梯调度、循环扫面算法均限制磁头的方向。

其他章节：
操作系统王道考研复习——第一章（计算机系统概述）
操作系统王道考研复习——第二章(进程管理） 上
操作系统王道考研复习——第二章(进程管理） 下
操作系统王道考研复习——第三章（内存管理/存储器管理）
操作系统王道考研复习——第五章（设备管理）