ednow

0%

王道-操作系统-ch4-文件管理

发表于 更新于
本文字数： 29k 阅读时长 ≈ 26 分钟

王道

文件管理

【考纲内容】

(一）文件系统基础

  1. 文件的概念
  2. 文件的逻辑结构: $\color{red}{\text{文件元数据}}$ 和索引节点（inode）
  3. 文件的操作（建立，删除，打开，关闭，读，写）
  4. 文件的保护
  5. 文件的逻辑结构
  6. 文件的物理结构

(二）目录

  1. 目录的基本概念
  2. 树形目录
  3. $\color{red}{\text{目录的操作}}$
  4. 硬链接和软链接

(二）文件系统

  1. $\color{red}{\text{文件系统的全局结构}}$ (layout)（文件系统在外存中的结构，文件系统在内存中的结构）
  2. 外存空闲空间管理办法
  3. $\color{red}{\text{虚拟文件系统}}$
  4. $\color{red}{\text{文件系统挂载}}$ (mounting)
  • 概念——定义、属性、基本操作、打开与关闭
  • 文件逻辑结构
    • 无结果文件（流式文件）
    • 有结构文件(记录式文件)
      • 顺序文件
      • 索引文件
      • 索引顺序文件
  • 目录结构
    • 文件控制块（FCB）、索引结点
    • 单级目录结构、两级目录结构、树形目录结构、图形目录结构
  • 文件共享
    • 基于索引结点（硬链接)
    • 利用符号链实现(软链接)
  • 文件保护————访问类型、访问控制
  • 实现
    • 层次结构
    • 目录实现————线性列表、哈希表
    • 文件分配
      • 连续分配
      • 链接分配
      • 索引分配————索引链接、多层索引、混合索引
    • 文件存储空间管理
      • 空闲表法
      • 空闲链表法
      • 位示图法成组链接法
  • 磁盘
    • 访问时间——寻道时间、延迟时间、传输时间
    • 调度算法
      • 先来先服务（FCFS)————公平
      • 最短寻找时间优先(SSTF)————“饥饿”现象
      • 扫描算法(SCAN)
      • 循环扫描(C-SCAN)
    • 磁盘的管理————初始化、引导块、坏块

【复习提示】

本章内容较为具体，要注意对概念的理解。重点掌握文件系统的结构及其实现、磁盘的相关知识点等。要掌握文件系统的文件控制块、物理分配方法、索引结构，以及磁盘特性和结构、磁盘调度算法，能分析磁盘相关的性能等。这些都是综合题易考查的内容。

文件系统基础

在学习本节时，请读者思考以下问题:

1）什么是文件?什么是文件系统?

2）文件系统要完成哪些功能?

本节内容较为抽象，对于初学者，推荐配合相关教材的相关章节进行学习。学习过程中要注意区分文件的逻辑结构和物理结构，不要把二者混为一谈。在读者的学习过程中，可尝试以上面的两个问题为线索，构建整个文件系统的概念，先思考有什么方法可以实现文件的共享和保护，再将自己的方法与书上的方法相比较。

在前面的学习中，曾经提醒过读者不要忽略对基本概念的理解。操作系统这门课程在统考中算是比较容易得分的一门课程，从历年的情况来看，大部分同学对进程管理、内存管理有较好的掌握，但对于文件管理及下一章的IO管理，往往理解不太深入，记忆不太牢固，在考试中，即使面对一些关于本章内容的基本问题也容易失分，这十分可惜。主要原因还是对概念的理解不够全面和透彻，希望各位读者能够关注这个问题。

文件的概念

文件的定义

文件(File）是操作系统中的一个重要概念。文件是以计算机硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档、图片、程序等。在系统运行时，计算机以进程为基本单位进行资源的调度和分配;而在用户进行的输入、输出中，则以文件为基本单位。大多数应用程序的输入都是通过文件来实现的，其输出也都保存在文件中，以便信息的长期存储及将来的访问。当用户将文件用于应用程序的输入、输出时，还希望可以访问文件、修改文件和保存文件等，实现对文件的维护管理，这就需要系统提供一个文件管理系统，操作系统中的 $\color{green}{\text{文件系统}}$ (File System)就是用于实现用户的这些管理要求的。

要清晰地理解文件的概念，就要了解文件究竟由哪些东西组成。

首先，文件中肯定包括一块存储空间，更准确地说，是存储空间中的数据;其次，由于操作系统要管理成千上万的数据，因此必定需要对这些数据进行划分，然后贴上“标签”，以便于分类和索引，所以文件必定包含分类和索引的信息;最后，不同的用户拥有对数据的不同访问权限，因此文件中一定包含一些关于访问权限的信息。

再举生活中的一个直观例子来类比文件，相信读者了解这个例子后会更深入地了解文件。这个例子就是图书馆中的书，可以认为，计算机中的一个文件相当于图书馆中的一本书，操作系统管理文件，相当于图书管理员管理图书馆中的书。

首先，一本书的主体一定是书中的内容，相当于文件中的数据;其次，不同类别的书需要放在不同的书库，然后加上编号，再把编号登记在图书管理系统中，方便读者查阅，相当于文件的分类和查找;最后，有些已经绝版或价格比较高的外文书籍，只能借给VIP会员或权限比较高的其他读者，而有些普通的书籍可供任何人借阅，这就是文件中的访问权限。

所举的例子与实际操作系统中的情形并不绝对等价，读者应能找出类比中的不严谨之处，但对于某些关键的属性，图书馆管理图书和操作系统管理文件的思想却有相一致的地方，因此通过这种类比可使初学者快速认识陌生的概念。

从用户的角度看，文件系统是操作系统的重要部分之一。用户关心的是如何命名、分类和查找文件，如何保证文件数据的安全性及对文件可以进行哪些操作等。而对其中的细节，如文件如何存储在辅存上、如何管理文件辅存区域等关心甚少。

文件系统提供了与二级存储相关的资源的抽象，让用户能在不了解文件的各种属性、文件存储介质的特征及文件在存储介质上的具体位置等情况下，方便快捷地使用文件。

用户通过文件系统建立文件，提供应用程序的输入、输出，对资源进行管理。首先了解文件的结构，我们通过自底向上的方式来定义。

1）数据项。数据项是文件系统中最低级的数据组织形式，可分为以下两种类型:

  • 基本数据项。用于描述一个对象的某种属性的一个值，如姓名、日期或证件号等，是数据中可命名的最小逻辑数据单位，即原子数据。
  • 组合数据项。由多个基本数据项组成。

2）记录。记录是一组相关的数据项的集合，用于描述一个对象在某方面的属性，如一名考生的报名记录包括考生姓名、出生日期、报考学校代号、身份证号等一系列域。

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

虽然上面给出了结构化的表还，但头协上NJ大#制代码，其基太访问单元可以是字节、行或程序和数据组织成文件。文件可以定效丁、于出m中允许可控制的进程间共享访问，能够被组记录。文件可以长期存储于硬盘或其他二级存储器中，允许可控制的进程间共享访问,能够被组织成复杂的结构。

文件的属性

文件具有一定的属性，系统不同，属性也会有所不同，但通常都包括如下属性。

1） $\color{green}{\text{名称}}$ 。文件名称唯一，以容易读取的形式保存。

2） $\color{green}{\text{标识符}}$ 。标识文件系统内文件的唯一标签，通常为数字，是对人不可读的一种内部名称。

3） $\color{green}{\text{类型}}$ 。被支持不同类型的文件系统所使用。

4） $\color{green}{\text{位置}}$ 。指向设备和设备上文件的指针。

5） $\color{green}{\text{大小}}$ 。文件当前大小（用字节、字或块表示)，也可包含文件允许的最大值。

6） $\color{green}{\text{保护}}$ 。对文件进行保护的访问控制信息。

7） $\color{green}{\text{时间、日期和用户标识}}$ 。文件创建、上次修改和上次访问的相关信息，用于保护和跟踪文件的使用。

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

文件的基本操作

文件属于抽象数据类型。为了恰当地定义文件，需要考虑有关文件的操作。操作系统提供系统调用，它对文件进行创建、写、读、重定位、删除和截断等操作。

1） $\color{green}{\text{创建文件}}$ 。创建文件有两个必要步骤:一是在文件系统中为文件找到空间;二是在目录中为新文件创建条目，该条目记录文件名称、在文件系统中的位置及其他可能的信息。

2） $\color{green}{\text{写文件}}$ 。为了写文件，执行一个系统调用，指明文件名称和要写入文件的内容。对于给定文件名称，系统搜索目录以查找文件位置。系统必须为该文件维护一个写位置的指针。每当发生写操作时，便更新写指针。

3） $\color{green}{\text{读文件}}$ 。为了读文件，执行一个系统调用，指明文件名称和要读入文件块的内存位置。同样，需要搜索目录以找到相关目录项，系统维护一个读位置的指针。每当发生读操作时，更新读指针。一个进程通常只对一个文件读或写，因此当前操作位置可作为每个进程当前文件位置的指针。由于读和写操作都使用同一指针，因此节省了空间，也降低了系统复杂度。

4） $\color{green}{\text{文件重定位}}$ (文件寻址)。按某条件搜索目录，将当前文件位置设为给定值，并且不会读、写文件。

5） $\color{green}{\text{删除文件}}$ 。先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。

6） $\color{green}{\text{截断文件}}$ 。允许文件所有属性不变，并删除文件内容，即将其长度设为0并释放其空间。这6个基本操作可以组合起来执行其他文件操作。例如，一个文件的复制，可以创建新文件、从旧文件读出并写入新文件。

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

文件的打开与关闭

因为许多文件操作都涉及为给定文件搜索相关目录条目，因此许多系统要求在首次使用文件时，使用系统调用open将指明文件的 $\color{green}{\text{属性}}$ (包括该文件在外存上的物理位置)从外存 $\color{green}{\text{复制}}$ 到内存打开文件表的一个表目中，并将该表目的编号（也称索引）返回给用户。操作系统维护一个包含所有打开文件信息的表(打开文件表，open-file table)。当用户需要一个文件操作时，可通过该表的一个索引指定文件，因此省略了搜索环节。当文件不再使用时，进程可以关闭它，操作系统从打开文件表中删除这一条目。

大部分操作系统要求在文件使用之前就被显式地打开。操作 open 会根据文件名搜索目录，并将目录条目复制到打开文件表。若调用open 的请求（创建、只读、读写、添加等）得到允许，则进程就可打开文件，而 open通常返回一个指向打开文件表中的一个条目的指针。通过使用该指针（而非文件名）进行所有IO操作，以简化步骤并节省资源。

注意，在open调用完成后，操作系统对该文件的任何操作都不再需要文件名，而只需要open调用返回的指针。

整个系统表包含进程相关信息，如文件在磁盘的位置、访问日期和大小。一个进程打开一个文件，系统打开文件表就会为打开的文件增加相应的条目。当另一个进程执行open时，只不过是在其进程打开表中增加一个条目，并指向整个系统表的相应条目。通常，系统打开文件表的每个文件时，还用一个文件打开计数器（Open Count)，以记录多少进程打开了该文件。每个关闭操作close使count递减，当打开计数器为0时，表示该文件不再被使用，系统将回收分配给该文件的内存空间等资源。若文件被修改过，则将文件写回外存，并将系统打开文件表中的相应条目删除，最后释放文件的文件控制块（File Control Block，FCB)。

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

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

文件的逻辑结构

文件的逻辑结构是从用户观点出发看到的文件的组织形式。文件的物理结构(又称文件的存储结构，见4.2.1节）是从实现观点出发看到的文件在外存上的存储组织形式。文件的逻辑结构与存储介质特性无关，但文件的物理结构与存储介质的特性有很大关系。文件的逻辑结构实际上是指在文件的内部，数据逻辑上是如何组织起来的。

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

无结构文件（流式文件)

无结构文件是最简单的文件组织形式。无结构文件将数据按顺序组织成记录并积累、保存，它是有序相关信息项的集合，以字节(Byte）为单位。由于无结构文件没有结构，因而对记录的访问只能通过穷举搜索的方式，因此这种文件形式对大多数应用不适用。但字符流的无结构文件管理简单，用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于采用字符流的无结构方式，如源程序文件、目标代码文件等。

有结构文件（记录式文件)

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

1）顺序文件。文件中的记录一个接一个地顺序排列，记录通常是定长的，可以顺序存储或以链表形式存储，在访问时需要顺序搜索文件。顺序文件有以下两种结构:第一种是串结构，记录之间的顺序与关键字无关。通常的办法是由时间决定，即按存入时间的先后排列，最先存入的记录作为第1条记录，其次存入的为第2条记录，以此类推。第二种是顺序结构，指文件中的所有记录按关键字顺序排列。

在对记录进行批量操作，即每次要读或写一大批记录时，顺序文件的效率是所有逻辑文件中最高的;此外，也只有顺序文件才能存储在磁带上，并能有效地工作，但顺序文件对查找、修改、增加或删除单条记录的操作比较困难。

2）索引文件。索引文件示意图如图4.1所示。对于定长记录文件，要查找第i条记录,可直接根据下式计算得到第i条记录相对于第1条记录的地址:

然而，对于可变长记录的文件，要查找第i条记录，必须顺序地查找前 $i$ –1条记录，从而获得相应记录的长度L，进而按下式计算出第 $i$ 条记录的首址:

注意:假定每条记录前用一个字节指明该记录的长度。

变长记录文件只能顺序查找，系统开销较大。为此，可以建立一张索引表以加快检索速度，索引表本身是定长记录的顺序文件。在记录很多或访问要求高的文件中，需要引入索引以提供有效的访问。实际中，通过索引可以成百上千倍地提高访问速度。

图4.1索引文件示意图找不到图片(Image not found)

3）索引顺序文件。索引顺序文件是顺序和索引两种组织形式的结合。索引顺序文件将顺序文件中的所有记录分为若干组，为顺序文件建立一张索引表，在索引表中为每组中的第一条记录建立一个索引项，其中含有该记录的关键字值和指向该记录的指针。

如图4.2所示，主文件名包含姓名和其他数据项。姓名为关键字，索引表中为每组的第一条记录（不是每条记录）的关键字值，用指针指向主文件中该记录的起始位置。索引表只包含关键字和指针两个数据项，所有姓名关键字递增排列。主文件中记录分组排列，同一个组中的关键字可以无序，但组与组之间的关键字必须有序。查找一条记录时，首先通过索引表找到其所在的组，然后在该组中使用顺序查找，就能很快地找到记录。

图4.2索引顺序文件示意图找不到图片(Image not found)

对于含有N条记录的顺序文件，查找某关键字值的记录时，平均需要查找N/2次。在索引顺序文件中，假设N条记录分为 $\sqrt{N}$ 组，索引表中有$\sqrt{N}$个表项，每组有$\sqrt{N}$条记录,在查找某关键字值的记录时，先顺序查找索引表，需要查找√N/2次，然后在主文件中对应的组中顺序查找，也需要查找$\sqrt{N}$/2次，因此共需查找$\sqrt{N}$ /2+$\sqrt{N}$ /2=$\sqrt{N}$ 次。显然，索引顺序文件提高了查找效率，若记录数很多，则可采用两级或多级索引。

索引文件和索引顺序文件都提高了存取的速度，但因为配置索引表而增加了存储空间。

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

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

复习了数据结构的读者读到这里时，会有这样的感觉:有结构文件逻辑上的组织，是为在文件中查找数据服务的（顺序查找、索引查找、索引顺序查找、哈希查找)。

目录结构

与文件管理系统和文件集合相关联的是文件目录，它包含有关文件的信息如属性、位置和所有权等，这些信息主要由操作系统进行管理。首先我们来看目录管理的基本要求:从用户的角度看，目录在用户(应用程序）所需要的文件名和文件之间提供一种映射，所以目录管理要实现“按名存取”;目录存取的效率直接影响到系统的性能，所以要提高对目录的检索速度;在共享系统中，目录还需要提供用于控制访问文件的信息。此外，文件允许重名也是用户的合理和必然要求,目录管理通过树形结构来解决和实现。

前面介绍了文件内部的逻辑结构，下面介绍多个文件之间在逻辑上是如何组织的，这实际上是文件“外部”的逻辑结构的问题。

文件控制块和索引结点

与进程管理一样，为实现目录管理，操作系统中引入了文件控制块的数据结构。

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

FCB主要包含以下信息:

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

2）索引结点。在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项（查找文件名与目录项中文件名匹配）时，才需要从该目录项中读出该文件的物理地址。也就是说，在检索目录时，文件的其他描述信息不会用到，也不需要调入内存。因此，有的系统（如UNIX，见表4.1）采用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称i结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。

表4.1UNIX的文件目录结构找不到图片(Image not found)

一个FCB的大小是64B，盘块大小是1KB，因此在每个盘块中可以存放16个FCB(注意，FCB必须连续存放)。而在 UNIX系统中，一个目录项仅占16B，其中14B是文件名，2B是i结点指针。在1KB的盘块中可存放64个目录项。这样，就可使查找文件时的平均启动磁盘次数减少到原来的1/4，大大节省了系统开销。

存放在磁盘上的索引结点称为磁盘索引结点，UNIX中的每个文件都有一个唯一的磁盘索引结点，主要包括以下几个方面:

  • $\color{green}{\text{文件主标识符}}$ ，拥有该文件的个人或小组的标识符。
  • $\color{green}{\text{文件类型}}$ ，包括普通文件、目录文件或特别文件。文件存取权限，各类用户对该文件的存取权限。
  • $\color{green}{\text{文件物理地址}}$ ，每个索引结点中含有13个地址项，即 iaddr(O)一iaddr(12)，它们以直接或间接方式给出数据文件所在盘块的编号。
  • $\color{green}{\text{文件长度}}$ ，以字节为单位。
  • $\color{green}{\text{文件链接计数}}$ ，在本文件系统中所有指向该文件的文件名的指针计数。
  • $\color{green}{\text{文件存取时间}}$ ，本文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间。

文件被打开时，磁盘索引结点复制到内存的索引结点中，以便于使用。在内存索引结点中又增加了以下内容:

  • 索引结点编号，用于标识内存索引结点。
  • 状态，指示i结点是否上锁或被修改。
  • 访问计数，每当有一进程要访问此i结点时，计数加1，访问结束减1。
  • 逻辑设备号，文件所属文件系统的逻辑设备号。
  • 链接指针，设置分别指向空闲链表和散列队列的指针。

FCB或索引结点相当于图书馆中图书的索书号，我们可以在图书馆网站上找到图书的索书号，然后根据索书号找到想要的书本。

目录结构

在理解一个文件系统的需求前，我们首先考虑在目录这个层次上所需要执行的操作，这有助于后面文件系统的整体理解。

  • 搜索。当用户使用一个文件时，需要搜索目录，以找到该文件的对应目录项。
  • 创建文件。当创建一个新文件时，需要在目录中增加-个目录项。
  • 删除文件。当删除一个文件时，需要在目录中删除相应的目录项。
  • 显示目录。用户可以请求显示目录的内容，如显示该用户目录中的所有文件及属性。
  • 修改目录。某些文件属性保存在目录中，因而这些属性的变化需要改变相应的目录项。操作时，考虑以下几种目录结构:

操作时，考虑以下几种目录结构:

1）$\color{green}{\text{单级目录结构}}$ 。在整个文件系统中只建立一张目录表，每个文件占一个目录项，如图4.3所示。

图4.3单级目录结构找不到图片(Image not found)

当访问一个文件时，先按文件名在该目录中查找到相应的FCB，经合法性检查后执行相应的操作。当建立一个新文件时，必须先检索所有目录项以确保没有“重名”的情况，然后在该目录中增设一项，把FCB 的全部信息保存在该项中。当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后清除该目录项。

单级目录结构实现了“按名存取”，但是存在查找速度慢、文件不允许重名、不便于文件共享等缺点，而且对于多用户的操作系统显然是不适用的。

2）两级目录结构。单级目录很容易造成文件名称的混淆，因此可以考虑采用两级方案,将文件目录分成主文件目录(Master File Directory，MFD）和用户文件目录（User FileDirectory, UFD)两级，如图4.4所示。

主文件目录项记录用户名及相应用户文件目录所在的存储位置。用户文件目录项记录该用户文件的FCB 信息。当某用户欲对其文件进行访问时，只需搜索该用户对应的UFD，这既解决了不同用户文件的“重名”问题，又在一定程度上保证了文件的安全。

两级目录结构可以解决多用户之间的文件重名问题，文件系统可以在目录上实现访问限制。但是两级目录结构缺乏灵活性，不能对文件分类。

图4.4两级目录结构找不到图片(Image not found)

3）多级目录结构（树形目录结构)。将两级目录结构的层次关系加以推广，就形成了多级目录结构，即树形目录结构，如图4.5所示。

用户要访问某个文件时，用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。从根目录出发的路径称为绝对路径。当层次较多时，每次从根目录查询会浪费时间，于是加入了当前目录(又称工作目录)，进程对各文件的访问都是相对于当前目录进行的。当用户要访问某个文件时，使用相对路径标识文件，相对路径由从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。

图4.5树形目录结构找不到图片(Image not found)

图4.5是Linux 操作系统的目录结构,”/dev/hda”就是一个绝对路径。若当前目录为“/bin”,则“./1s”就是一个相对路径，其中符号“.”表示当前工作目录。

通常，每个用户都有各自的“当前目录”，登录后自动进入该用户的“当前目录”。操作系统提供一条专门的系统调用，供用户随时改变“当前目录”。例如，在 UNIX系统中，”/etc/passwd”文件就包含有用户登录时默认的“当前目录”，可用cd命令改变“当前目录”。

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，在树形目录中查找一个文件时，需要按路径名逐级访问中间结点，这就增加了磁盘访问次数，无疑将影响查询速度。

4）无环图目录结构。树形目录结构能便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上增加了一些指向同一结点的有向边，使整个目录成为一个有向无环图。引入无环图目录结构是为了实现文件共享，如图4.6所示。

图4.6无环图目录结构找不到图片(Image not found)

当某用户要求删除一个共享结点时，若系统只是简单地将它删除，则当另一共享用户需要访问时，会因无法找到这个文件而发生错误。为此，可为每个共享结点设置一个共享计数器，每当图中增加对该结点的共享链时，计数器加1;每当某用户提出删除该结点时,计数器减1。仅当共享计数器为0时，才真正删除该结点，否则仅删除请求用户的共享链。共享文件（或目录）不同于文件拷贝(副本)。若有两个文件拷贝，则每个程序员看到的是拷贝而不是原件;然而，若一个文件被修改，则另一个程序员的拷贝不会改变。对于共享文件，只存在一个真正的文件，任何改变都会为其他用户所见。

无环图目录结构方便地实现了文件的共享，但使得系统的管理变得更加复杂。

文件共享

文件共享使多个用户(进程）共享同一个文件，系统中只需保留该文件的一个副本。若系统不能提供共享功能，则每个需要该文件的用户都要有各自的副本，会造成对存储空间的极大浪费。随着计算机技术的发展，文件共享的范围已由单机系统发展到多机系统，进而通过网络扩展到全球。这些文件的分享是通过分布式文件系统、远程文件系统、分布式信息系统实现的。这些系统允许多个客户通过C/S模型共享网络中的服务器文件。

现代常用的两种文件共享方法如下。

基于索引结点的共享方式（硬链接)

在树形结构的目录中，当有两个或多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个或多个用户的目录中，才能方便地找到该文件，如图4.7所示。

图4.7基于索引结点的共享方式找不到图片(Image not found)

在这种共享方式中，诸如文件的物理地址及其他的文件属性等信息，不再放在目录项中，而放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。在索引结点中还应有一个链接计数count，用于表示链接到本索引结点（即文件)上的用户目录项的数目。当count = 2时，表示有两个用户目录项链接到本文件上，或者说有两个用户共享此文件。

用户A创建一个新文件时，它便是该文件的所有者，此时将count置为1。用户B要共享此文件时，在用户B的目录中增加一个目录项，并设置一个指针指向该文件的索引结点。此时，文件主仍然是用户A，count=2。用户A不再需要此文件，不能将文件直接删除。因为若删除了该文件，则必然也删除了该文件的索引结点，这样便会使用户B的指针悬空，而用户B可能正在此文件上执行写操作，此时用户B会无法访问到文件。因此用户A不能删除此文件，只是将该文件的count减1，然后删除自己目录中的相应目录项。用户B仍可以使用该文件。当count =0时，表示没有用户使用该文件，系统将负责删除该文件。如图4.8给出了用户B链接到文件上的前、后情况。

图4.8文件共享中的链接计数找不到图片(Image not found)
利用符号链实现文件共享（软链接)

为使用户B能共享用户A的一个文件F，可以由系统创建一个LINK类型的新文件也取名为F，并将文件F写入用户B的目录中，以实现用户B的目录与文件F的链接。在新文件中只包含被链接文件F的路径名。这样的链接方法被称为符号链接。

新文件中的路径名只被视为符号链，当用户B要访问被链接的文件F且正要读LINK类新文件时，操作系统根据新文件中的路径名去读该文件，从而实现用户B对文件F的共享。

在利用符号链方式实现文件共享时，只有文件的拥有者才拥有指向其索引结点的指针而共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也就不会发生在文件主删除一个共享文件后留下一个悬空指针的情况。当文件的拥有者把一个共享文件删除后，其他用户通过符号链去访问它时，会出现访问失败，于是将符号链删除，此时不会产生任何影响。当然，利用符号链实现文件共享仍然存在问题。例如，一个文件采用符号链方式共享，当文件拥有者将其删除，而在共享的其他用户使用其符号链接访问该文件之前，又有人在同一路径下创建了另一个具有同样名称的文件，则该符号链将仍然有效，但访问的文件已经改变，从而导致错误。

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

符号链方式有一个很大的优点，即网络共享只需提供该文件所在机器的网络地址及该机器中的文件路径。

上述两种链接方式都存在一个共同的问题，即每个共享文件都有几个文件名。换言之，每增加一条链接，就增加一个文件名。这实质上是每个用户都使用自己的路径名去访问共享文件。当我们试图去遍历整个文件系统时，将会多次遍历到该共享文件。

硬链接和软链接都是文件系统中的静态共享方法，在文件系统中还存在着另外的共享需求，即两个进程同时对同一个文件进行操作，这样的共享称为 $\color{green}{\text{动态共享}}$ 。

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

文件保护

为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。为此，必须在文件系统中建立相应的文件保护机制。

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

访问类型

对文件的保护可从限制对文件的访问类型中出发。可加以控制的访问类型主要有以下几种。

  • 读。从文件中读。
  • 写。向文件中写。
  • 执行。将文件装入内存并执行。
  • 添加。将新信息添加到文件结尾部分。
  • 删除。删除文件，释放空间。
  • 列表清单。列出文件名和文件属性。

此外还可以对文件的重命名、复制、编辑等加以控制。这些高层的功能可以通过系统程序调用低层系统调用来实现。保护可以只在低层提供。例如，复制文件可利用一系列的读请求来完成,这样，具有读访问权限的用户同时也就具有了复制和打印权限。

访问控制

解决访问控制最常用的方法是根据用户身份进行控制。而实现基于身份访问的最为普通的方法是，为每个文件和目录增加一个 $\color{green}{\text{访问控制列表}}$ (Access-Control List，ACL)，以规定每个用户名及其所允许的访问类型。

这种方法的优点是可以使用复杂的访问方法，缺点是长度无法预计并且可能导致复杂的空间管理，使用精简的访问列表可以解决这个问题。

精简的访问列表采用拥有者、组和其他三种用户类型。

1）拥有者。创建文件的用户。

2）组。一组需要共享文件且具有类似访问的用户。

3）其他。系统内的所有其他用户。这样，只需用三个域即可列出访问表中这三类用户的访问权限。文件拥有者在创建文件时，说明创建者用户名及所在的组名，系统在创建文件时也将文件主的名字、所属组名列在该文件的FCB中。用户访问该文件时，按照拥有者所拥有的权限访问文件，若用户和拥有者在同一个用户组，则按照同组权限访问，否则只能按其他用户权限访问。UNIX操作系统即采用此种方法。

口令和密码是另外两种访问控制方法。

口令指用户在建立一个文件时提供一个口令，系统为其建立FCB 时附上相应口令，同时告诉允许共享该文件的其他用户。用户请求访问时必须提供相应的口令。这种方法时间和空间的开销不多，缺点是口令直接存在系统内部，不够安全。

密码指用户对文件进行加密，文件被访问时需要使用密钥。这种方法保密性强，节省了存储空间，不过编码和译码要花费一定的时间。

口令和密码都是防止用户文件被他人存取或窃取，并没有控制用户对文件的访问类型。注意两个问题:

1）现代操作系统常用的文件保护方法是，将访问控制列表与用户、组和其他成员访问控制方案一起组合使用。

2）对于多级目录结构而言，不仅需要保护单个文件，而且需要保护子目录内的文件，即需要提供目录保护机制。目录操作与文件操作并不相同，因此需要不同的保护机制。

本节小结

本节开头提出的问题的参考答案如下。

1）什么是文件?什么是文件系统?

文件是以计算机硬盘为载体的存储在计算机上的信息集合，它的形式多样，可以是文本文档、图片、程序等。操作系统中负责管理和存储文件信息的软件机构称为文件管理系统，简称文件系统。文件系统由三部分组成:与文件管理有关的软件、被管理文件及实施文件管理所需的数据结构。

2）文件系统要完成哪些功能?

对于用户而言，文件系统最主要的功能是实现对文件的基本操作，让用户可以按名存储和查找文件，组织成合适的结构，并应当具有基本的文件共享和文件保护功能。对于操作系统本身而言，文件系统还需要管理与磁盘的信息交换，完成文件逻辑结构和物理结构上的变换，组织文件在磁盘上的存放，采取好的文件排放顺序和磁盘调度方法以提升整个系统的性能。

学习到这里时，读者应会有这样的一种体会:现代操作系统的管理思想中，到处能够见到面向对象程序设计的影子。本节我们学习的一个新概念————文件，实质上就是一个抽象数据类型，也就是一种 $\color{red}{\text{数据结构}}$ ，若读者在复习操作系统之前已复习完数据结构，则遇到一种新的数据结构时，一定会有这样的意识:要认识它的逻辑结构、物理结构，以及对这种数据结构的操作。本节我们已经学完文件的 $\color{green}{\text{逻辑结构}}$ ，下一节将介绍文件的实现，也就是文件的 $\color{green}{\text{物理结构}}$ 。操作系统对文件的操作不是本课程关心的问题，我们不去研究。

文件系统实现

在学习本节时，请读者思考以下问题:

1）在目录中查找某个文件可以使用什么方法?

2）文件的逻辑结构和物理结构有何区别?单个文件的逻辑结构和物理结构之间是否存在某些制约关系?上节介绍了目录和文件的逻辑结构,本节将介绍文件物理结构和目录的实现。建议读者阅读之前先回顾上节的内容，并自己思考相应功能的实现方法，在学习过程中和本节的方法进行对比，这样能更好地理解本节的内容。

图4.9文件系统层次结构找不到图片(Image not found)

文件系统层次结构

现代操作系统有多种文件系统类型（如FAT32，NTFS,ext2，ext3，ext4等)，因此文件系统的层次结构也不尽相同。图4.9是一种合理的层次结构。

图4.9文件系统层次结构找不到图片(Image not found)
用户调用接口

文件系统为用户提供与文件及目录有关的调用，如新建、打开、读写、关闭、删除文件，建立、删除目录等。此层由若干程序模块组成，每个模块对应一条系统调用，用户发出系统调用时，控制即转入相应的模块。

文件目录系统

文件目录系统的主要功能是管理文件目录，其任务有管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织存储设备上的文件目录结构、调用下一级存取控制模块。

存取控制验证模块

实现文件保护主要由该级软件完成，它把用户的访问要求与FCB中指示的访问控制权限进行比较，以确认访问的合法性。

逻辑文件系统与文件信息缓冲区

逻辑文件系统与文件信息缓冲区的主要功能是，根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号。

物理文件系统

物理文件系统的主要功能是把逻辑记录所在的相对块号转换成实际的物理地址。

辅助分配模块

分配模块的主要功能是管理辅存空间，即负责分配辅存空闲空间和回收辅存空间。

设备管理程序模块

设备管理程序模块的主要功能是分配设备、分配设备读写用缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等。

对于文件管理系统的层次结构我们不能忽略，因为它是重要考点之一，当然也不需要死记硬背，我们可以通过用户请求访问某个文件时发生的一系列事情来辅助记忆文件系统的层次结构。

例如，用户要查看文件F中的内容，对操作系统发出命令（操作系统有面向用户的接口),于是就经过了第О级的用户调用接口。

操作系统得到命令后，需要查找目录以查找文件F的索引信息，可能是FCB，也可能是索引结点，经过了第1级文件目录系统。

通过目录找到文件FCB后，需要查看文件FCB上的信息，看看那个用户有没有访问该文件的权限，于是经过了存取控制验证模块。

用户通过验证后，就真正开始寻址。经历第3章的学习后，我们有这样的意识:操作系统的寻址往往要先得到逻辑地址，再得到物理地址，于是在开始寻址时，操作系统经过逻辑文件系统与文件信息缓冲区，得到了相应文件的内容的逻辑地址。

把 $\color{green}{\text{逻辑地址}}$ 转换为 $\color{green}{\text{物理地址}}$ ，是在 $\color{green}{\text{物理文件系统}}$ 中完成的。

至此为止，寻址就已完成。寻址完成后，我们关心的是找到的这块空间应该如何管理，若要释放这块空间，则任务就交给辅助分配模块，若要把这块空间分配给设备用于输入/输出，则把任务交给设备管理程序模块。

目录实现

在读文件前，必须先打开文件。打开文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。目录实现的基本方法有线性列表和哈希表两种，要注意目录的实现就是为了查找，因此线性列表实现对应线性查找，哈希表的实现对应散列查找。

线性列表

最简单的目录实现方法是使用存储文件名和数据块指针的线性表。创建新文件时，必须首先搜索目录表以确定没有同名的文件存在，然后在目录表后增加一个目录项。删除文件则根据给定的文件名搜索目录表，接着释放分配给它的空间。重用目录项有许多方法:可以将目录项标记为不再使用，或将它加到空闲目录项表上，还可以将目录表中的最后一个目录项复制到空闲位置，并降低目录表长度。采用链表结构可以减少删除文件的时间，其优点在于实现简单，不过由于线性表的特殊性，比较费时。

哈希表

哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。这种方法的优点是查找非常迅速，插入和删除也较简单，不过需要一些预备措施来避免冲突。最大的困难是哈希表长度固定以及哈希函数对表长的依赖性。

目录查询是通过在磁盘上反复搜索完成的，需要不断地进行I/O操作，开销较大。所以如前所述，为了减少I/O操作，把当前使用的文件目录复制到内存，以后要使用该文件时只需在内存中操作，因此降低了磁盘操作次数，提高了系统速度。

文件实现—文件分配方式

前面说过，文件实际上是一种抽象数据类型，我们要研究它的逻辑结构、物理结构以及关于它的一系列操作（不是统考关注的内容)。文件的实现就是研究文件的物理结构，即文件数据在物理存储设备上是如何分布和组织的。同一个问题有两个方面的回答:一是文件的分配方式，讲的是对磁盘非空闲块的管理;二是文件存储空间管理，讲的是对磁盘空闲块的管理。

文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种:连续分配、链接分配和索引分配。有的系统（如RDOS操作系统）对三种方法都支持，但更普遍的是一个系统只支持一种方法。对于本节的内容，读者要注意与文件的逻辑结构区分，从历年的经验来看，这是很多读者容易搞混的地方（读者复习完数据结构后，应该了解 $\color{green}{\text{线性表}}$ 、 $\color{green}{\text{顺序表}}$ 和 $\color{green}{\text{链表之间}}$ 的关系，类比到这里就不易混淆)。

连续分配

连续分配方法要求每个文件在磁盘上占有一组连续的块，如图4.10所示。磁盘地址定义了磁盘上的一个线性排序。这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。

图4.10连续分配找不到图片(Image not found)

文件的连续分配可以用第一块的磁盘地址和连续块的数量来定义。若文件长 $n$ 块并从位置 $b$ 开始，则该文件将占有块b,b+ 1,b+2,…,b+n-1。一个文件的目录条目包括开始块的地址和该文件所分配区域的长度。

连续分配支持顺序访问和直接访问。其优点是实现简单、存取速度快。缺点是文件长度不宜动态增加，因为一个文件末尾后的盘块可能已分配给其他文件，一旦需要增加，就需要大量移动盘块。此外，反复增删文件后会产生外部碎片（与内存管理分配方式中的碎片相似)，且很难确定一个文件需要的空间大小，因而只适用于 $\color{green}{\text{长度固定}}$ 的文件。

链接分配

链接分配采取离散分配的方式，消除了外部碎片，因此显著提高了磁盘空间的利用率;又因为根据文件的当前需求为其分配必需的盘块，当文件动态增长时，可以动态地再为它分配盘块，因此无须事先知道文件的大小。此外，对文件的增、删、改也非常方便。链接分配又可以分为隐式链接和显式链接两种形式。

隐式链接如图4.11所示。每个文件对应一个磁盘块的链表;磁盘块分布在磁盘的任何地方，除最后一个盘块外，每个盘块都有指向下一个盘块的指针，这些指针对用户是透明的。目录包括文件第一块的指针和最后一块的指针。

图4.11隐式链接分配找不到图片(Image not found)

创建新文件时，目录中增加一个新条目。每个目录项都有一个指向文件首块的指针。该指针初始化为NULL 以表示空文件，大小字段为0。写文件会通过空闲空间管理系统找到空闲块，将该块链接到文件的尾部，以便写入。读文件则通过块到块的指针顺序读块。

$\color{green}{\text{隐式链接}}$ 分配的缺点是无法直接访问盘块，只能通过指针顺序访问文件，且盘块指针会消耗一定的存储空间。隐式链接分配的稳定性也是一个问题，系统在运行过程中由于软件或硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失。

$\color{green}{\text{显式链接}}$ 是指把用于链接文件各物理块的指针，从每个物理块的块末尾中提取出来，显式地存放在内存的一张链接表中。该表在整个磁盘中仅设置一张，称为文件分配表(File AllocationTable，FAT)。每个表项中存放对应块的下一块链接指针，即下一个盘块号。文件的第一个盘块号记录在目录中，后续的盘块可通过查FAT找到。例如，某磁盘共有100个磁盘块，存放了两个文件:文件“aa”占三个盘块，依次是2→8→5;文件“bbb”占两个盘块，依次是7→1。其余盘块都是空闲盘块，则该磁盘的FAT表如图4.12所示。

图4.12文件分配表找不到图片(Image not found)

不难看出，FAT的表项与全部磁盘块一一对应，并且可以用一个特殊的数字-1表示文件的最后一块，用-2表示这个磁盘块是空闲的（当然也可指定为-3,-4)。因此，文件分配表（FAT）不仅记录了文件各块之间的先后链接关系，同时还标记了空闲的磁盘块，操作系统也可以通过FAT对文件存储空间进行管理。当某进程请求操作系统分配一个磁盘块时，操作系统只需从FAT中找到-2的表项,并将对应的磁盘块分配给进程即可。

FAT表在系统启动时就会被读入内存，因此查找FAT的过程是在内存中进行的，因此不仅显著地提高了检索速度，而且明显减少了访问磁盘的次数。

索引分配

链接分配解决了连续分配的外部碎片和文件大小管理的问题。但是，链接分配不能有效支持直接访问(FAT 除外)。索引分配解决了这个问题，它把每个文件的所有的盘块号都集中放在一起构成索引块（表)，如图4.13所示。

图4.13 索引分配找不到图片(Image not found)

每个文件都有其 $\color{green}{\text{索引块}}$ ，这是一个磁盘块地址的数组。索引块的第i个条目指向文件的第i个块。目录条目包括索引块的地址。要读第 i块，通过索引块的第 i个条目的指针来查找和读入所需的块。

创建文件时，索引块的所有指针都设为空。首次写入第i块时，先从空闲空间中取得一个块，再将其地址写到索引块的第i个条目。索引分配支持直接访问，且没有外部碎片问题。其缺点是由于索引块的分配，增加了系统存储空间的开销。索引块的大小是一个重要的问题，每个文件必须有一个索引块，因此索引块应尽可能小，但索引块太小就无法支持大文件。可以采用以下机制来处理这个问题。

  • 链接方案。一个索引块通常为一个磁盘块，因此它本身能直接读写。为了处理大文件，可以将多个索引块链接起来。
  • 多层索引。多层索引使第一层索引块指向第二层的索引块，第二层索引块再指向这种方法根据最大文件大小的要求，可以继续到第三层或第四层。例如，4096B 的块，能在索引块中存入1024个4B的指针。两层索引允许1048576个数据块，即允许最大文件为4GB。
  • 混合索引。将多种索引分配方式相结合的分配方式。例如，系统既采用直接地址单级索引分配方式或两级索引分配方式（混合索引是本章最综合的高频考点，可先学习本章疑难点4，然后回来接着学习)。

表4.2是三种分配方式的比较。

表4.2文件三种分配方式的比较找不到图片(Image not found)

此外，访问文件需要两次访问外存——首先要读取索引块的内容，然后访问具体的磁盘块，因而降低了文件的存取速度。为了解决这一-问题，通常将文件的索引块读入内存的缓冲区中，以加快文件的访问速度。

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

(1）文件存储器空间的划分与初始化

一般来说，一个文件存储在一个文件卷中。文件卷可以是物理盘的一部分，也可以是整个物理盘，支持超大型文件的文件卷也可由多个物理盘组成，如图4.14所示。

在一个文件卷中，文件数据信息的空间(文件区）和存放文件控制信息FCB的空间(目录区)是分离的。由于存在很多种类的文件表示和存放格式，所以现代操作系统中一般都有很多不同的文件管理模块，通过它们可以访问不同格式的逻辑卷中的文件。逻辑卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区,建立空闲空间管理表格及存放逻辑卷信息的 $\color{green}{\text{超级块}}$ 。

图4.14逻辑卷与物理盘的关系找不到图片(Image not found)

(2）文件存储器空间管理

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

空闲表法

空闲表法属于连续分配方式，它与内存的动态分配方式类似，为每个文件分配一块连续的存储空间。系统为外存上的所有空闲区建立一张空闲盘块表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，如表4.3所示。

空闲盘区的分配与内存的动态分配类似，同样采用首次适应算法、循环首次适应算法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲盘块表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户，同时修改空闲盘块表。

系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。

表4.3空闲盘块表找不到图片(Image not found)
空闲链表法

将所有空闲盘区拉成一条空闲链,根据构成链所用的基本元素不同,可把链表分成两种形式:空闲盘块链和空闲盘区链。

空闲盘块链将磁盘上的所有空闲空间以盘块为单位拉成—条链。当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。这种方法的优点是分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时可能要重复多次操作。

空闲盘区链将磁盘上的所有空闲盘区（每个盘区可包含若干盘块）拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数）的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区合并。

位示图法

位示图利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。当其值为“0”时，表示对应的盘块空闲;当其值为“1”时，表示对应的盘块已分配。位示图法示意如图4.15所示。

图4.15位示图法示意图找不到图片(Image not found)

盘块的分配:

${\textstyle\unicode{x2460}}$ 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位。

②将找到的一个或一组二进制位，转换成与之对应的盘块号。若找到的其值为“0O”的二进制位位于位示图的第 $i$ 行、第 $j$ 列,则其相应的盘块号应按下式计算( $n$ 代表每行的位数):

③修改位示图，令map[ i,j ]= 1。盘块的回收:

①将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为

②修改位示图，令map[ i,j ]=0。

成组链接法

空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太大。在UNIX系统中采用的是成组链接法，这种方法结合了空闲表和空闲链表两种方法，克服了表太大的缺点。其大致思想是:把顺序的n个空闲扇区地址保存在第一个空闲扇区内，其后一个空闲扇区内则保存另一顺序空闲扇区的地址，如此继续，直至所有空闲扇区均予以链接。系统只需要保存一个指向第一个空闲扇区的指针。假设磁盘最初全为空闲扇区，其成组链接如图4.16所示。通过这种方式可以迅速找到大批空闲块地址。

图4.16成组链接法示意图找不到图片(Image not found)

表示文件存储器空闲空间的“位向量”表或第一个成组链块，以及卷中的目录区、文件区划分信息都需要存放在辅存储器中，一般放在卷头位置，在UNIX系统中称为超级块。在对卷中的文件进行操作前，超级块需要预先读入系统空闲的主存，并且经常保持主存超级块与辅存卷中超级块的一致性。

注意:本书如无特别提示，所使用的位示图法中行和列都从1开始编号。特别注意，若题目中指明从0开始编号，则上述计算方法要进行相应调整。

本节小结

本节开头提出的问题的参考答案如下。

在目录中查找某个文件可以使用什么方法?

可以采用线性列表法或哈希表法。线性列表把文件名组织成一个线性表，查找时依次与线性表中的每个表项进行比较。若把文件名按序排列，则使用折半查找法可以降低平均的查找时间，但建立新文件时会增加维护线性表的开销。哈希表用文件名通过哈希函数得到一个指向文件的指针，这种方法非常迅速，但要注意避免冲突。

文件的逻辑结构和物理结构有何区别?单个文件的逻辑结构和物理结构之间是否存在着某些制约关系?

文件的逻辑结构是用户可见的结构，即用户使用文件的结构。文件的物理结构是文件在存储器上的组织结构，它表示一个文件在辅存上安置、链接、编目的方法。它和文件的存取方法以及辅存设备的特性等都有着密切的联系。单个文件的逻辑结构和物理结构之间虽无明显的制约或关联关系，但是如果物理结构选择不慎，也很难体现出逻辑结构的特点，比如一个逻辑结构是顺序结构，而物理结构是隐式链接结构的文件，即使理论上可以很快找出某条记录的地址，而实际找时仍然需要在磁盘上一块一块地找。

磁盘组织与管理

在学习本节时，请读者思考以下问题:

1）在磁盘上进行一次读写操作需要哪几部分时间?其中哪部分时间最长?

2）存储一个文件时，当一个磁道存储不下时，剩下部分是存在同一个盘面的不同磁道好，还是存在同一个柱面上的不同盘面好?

本节主要介绍文件系统管理磁盘的方式，由于内容较少且属于实现部分，不需要问题来引导学习，因此本节不给出问题。学习本节时，要重点掌握计算一次磁盘操作的时间，以及对于给定访盘的磁道序列，按照特定算法求出磁头通过的总磁道数及平均寻道数。

磁盘的结构

磁盘（Disk）是由表面涂有磁性物质的金属或塑料构成的圆形盘片，通过一个称为磁头的导体线圈从磁盘存取数据。在读/写操作期间，磁头固定，磁盘在下面高速旋转。如图4.17所示，磁盘盘面上的数据存储在一组同心圆中，称为 $\color{green}{\text{磁道}}$ 。每个磁道与磁头一样宽，一个盘面有上千个磁道。磁道又划分为几百个扇区，每个扇区固定存储大小(通常为512B)，一个 $\color{green}{\text{扇区}}$ 称为一个 $\color{green}{\text{盘块}}$ 。相邻磁道及相邻扇区间通过一定的间隙分隔开，以避免精度错误。注意，由于扇区按固定圆心角度划分，所以密度从最外道向里道增加，磁盘的存储能力受限于最内道的最大记录密度。

磁盘安装在一个磁盘驱动器中，它由磁头臂、用于旋转磁盘的主轴和用于数据输入/输出的电子设备组成。如图4.18所示，多个盘片垂直堆叠，组成 $\color{green}{\text{磁盘组}}$ ，每个盘面对应一个磁头，所有磁头固定在一起，与磁盘中心的距离相同且一起移动。所有盘片上相对位置相同的磁道组成柱面。按照这种物理结构组织，扇区就是磁盘可寻址的最小存储单位，磁盘地址用“柱面号·盘面号·扇区号(或块号)”表示。

图4.17磁盘盘片 图4.18 磁盘驱动器找不到图片(Image not found)

磁盘按不同的方式可分为若干类型:磁头相对于盘片的径向方向固定的，称为固定头磁盘，每个磁道一个磁头;磁头可移动的，称为活动头磁盘，磁头臂可来回伸缩定位磁道;磁盘永久固定在磁盘驱动器内的，称为固定盘磁盘;可移动和替换的，称为可换盘磁盘。

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

磁盘调度算法

一次磁盘读写操作的时间由寻找（寻道)时间、旋转延迟时间和传输时间决定。

1）寻找时间 $T_s$ ,。活动头磁盘在读写信息前，将磁头移动到指定磁道所需要的时间。这个时间除跨越 $n$ 条磁道的时间外，还包括启动磁臂的时间 $s$ ，即

式中，m是与磁盘驱动器速度有关的常数，约为0.2ms，磁臂的启动时间约为2ms。

2）旋转延迟时间 $T_s$ 。磁头 $\color{green}{\text{定位}}$ 到某一磁道的扇区所需要的时间，设磁盘的旋转速度为 $r$ ,则

对于硬盘，典型的旋转速度为5400转/分，相当于一周11.1ms，则 $T_r$ 为5.55ms;对于软盘，其旋转速度为300～600转/分，则 $T_r$ 为50～100ms。

3）传输时间 $T_t$ 。从磁盘读出或向磁盘写入数据所经历的时间，这个时间取决于每次所读/写的字节数 $b$ 和磁盘的旋转速度:

式中， $r$ 为磁盘每秒的转数， $N$ 为一个磁道上的字节数。

在磁盘存取时间的计算中，寻道时间与磁盘调度算法相关，下面将会介绍分析几种算法;而延迟时间和传输时间都与磁盘旋转速度相关，且为 $\color{green}{\text{线性相关}}$ ，所以在硬件上，转速是磁盘性能的一个非常重要的参数。

总平均存取时间 $T_a$ 可以表示为

虽然这里给出了总平均存取时间的公式，但是这个平均值是没有太大实际意义的，因为在实际的磁盘IO操作中，存取时间与磁盘调度算法密切相关。调度算法直接决定寻找时间从而决定总的存取时间。

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

先来先服务（First Come First Served，FCFS)算法

FCFS算法根据进程请求访问磁盘的先后顺序进行调度，这是一种最简单的调度算法，如图4.19所示。该算法的优点是具有公平性。若只有少量进程需要访问，且大部分请求都是访问簇聚的文件扇区，则有望达到较好的性能;若有大量进程竞争使用磁盘，则这种算法在性能上往往接近于随机调度。所以，实际磁盘调度中会考虑一些更为复杂的调度算法。

图4.19 FCFS磁盘调度算法找不到图片(Image not found)

例如，磁盘请求队列中的请求顺序分别为55,58,39,18,90,160,150,38,184，磁头的初始位置是磁道100,采用FCFS算法时磁头的运动过程如图4.19所示。磁头共移动了(45＋3+19+21+72＋70＋10+112+146)= 498个磁道，平均寻找长度=498/9=55.3。

最短寻找时间优先( Shortest Seek Time First, SSTF)算法

SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以便使每次的寻找时间最短。当然，总是选择最小寻找时间并不能保证平均寻找时间最小，但能提供比 FCFS算法更好的性能。这种算法会产生“饥饿”现象。如图4.20所示，若某时刻磁头正在18号磁道，而在18号磁道附近频繁地增加新的请求，则SSTF 算法使得磁头长时间在18号磁道附近工作，将使184号磁道的访问被无限期地延迟，即被“饿死”。

4.20 SSTF磁盘调度算法找不到图片(Image not found)

例如，磁盘请求队列中的请求顺序分别为55,58,39,18,90,160,150,38,184，磁头初始位置是磁道100，采用SSTF算法时磁头的运动过程如图4.20所示。磁头共移动了10+32+3+16+1＋ 20+132+10＋24= 248个磁道，平均寻找长度=248/9 = 27.5。

扫描（SCAN)算法（又称电梯调度算法)
  • scan求移动的磁道数的快速方法：找到「 $\color{green}{\text{枢纽}}$ 」，两边减去枢纽

SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象，实际上就是在最短寻找时间优先算法的基础上规定了磁头运动的方向，如图4.21所示。由于磁头移动规律与电梯运行相似，因此又称电梯调度算法。SCAN算法对最近扫描过的区域不公平，因此它在访问局部性方面不如 FCFS 算法和SSTF算法好。

图4.21SCAN磁盘调度算法找不到图片(Image not found)

例如，磁盘请求队列中的请求顺序分别为55,58, 39,18,90,160,150,38,184，磁头初始位置是磁道100。采用SCAN算法时，不但要知道磁头的当前位置，而且要知道磁头的移动方向，假设磁头沿磁道号增大的顺序移动，则磁头的运动过程如图4.21所示。移动磁道的顺序为100,150,160,184,200,90,58,55,39,38,18。磁头共移动了(50+10+24+16+110＋32+3+16+1+20)=282个磁道，平均寻道长度=282/9= 31.33。

循环扫描( Circular SCAN, C-SCAN）算法

在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求。由于SCAN算法偏向于处理那些接近最里或最外的磁道的访问请求，所以使用改进型的C-SCAN 算法来避免这个问题，如图4.22所示。

采用SCAN算法和C-SCAN 算法时，磁头总是严格地遵循从盘面的一端到另一端，显然，在实际使用时还可以改进，即磁头移动只需要到达最远端的一个请求即可返回,不需要到达磁盘端点。这种形式的SCAN算法和C-SCAN算法称为LOOK调度（见图4.23-1)和C-LOOK(见图4.23-2)调度，因为它们在朝一个给定方向移动前会查看是否有请求。

4.22 C-SCAN磁盘调度算法找不到图片(Image not found)
4.23-1 LOOK磁盘调度算法找不到图片(Image not found)

注意,若无特别说明,也可以默认SCAN算法和C-SCAN算法为LOOK和C-LOOK调度(请读者认真领悟，并通过结合后面的习题进一步加深对以上相关算法的理解)。

4.23-2C-LOOK磁盘调度算法找不到图片(Image not found)

例如，磁盘请求队列中的请求顺序为55,58,39,18,90,160,150,38,184，磁头初始位置是磁道100。采用C-SCAN算法时，假设磁头沿磁道号增大的顺序移动，则磁头的运动过程如图4.23所示。移动磁道的顺序为100,150,160,184,200,0,18,38,39,55,58,90。磁头共移动50＋10＋24＋16+200+ 18＋20+1+16＋3+32=390个磁道，平均寻道长度=390/9= 43.33。

不太熟悉操作系统整体框架的读者经常混淆磁盘调度算法中的循环扫描算法和页面调度算法中的CLOCK算法，请读者注意区分。

对比以上几种磁盘调度算法，FCFS 算法太过简单， $\color{green}{\text{性能较差}}$ ，仅在请求队列长度接近于1时才较为理想;SSTF 算法较为通用和自然;SCAN算法和C-SCAN算法在磁盘 $\color{green}{\text{负载较大}}$ 时比较占优势。它们之间的比较见表4.4。

表4.4磁盘调度算法比较找不到图片(Image not found)

除减少寻找时间外，减少延迟时间也是提高磁盘传输效率的重要因素。可以对盘面扇区进行交替编号，对磁盘片组中的不同盘面错位命名。假设每个盘面有8个扇区，磁盘片组共8个盘面,则可以采用如图4.24所示的编号。

磁盘是连续自转设备，磁头读/写一个物理块后，需要经过短暂的处理时间才能开始读/马下一块。假设逻辑记录数据连续存放在磁盘空间中，若在盘面上按扇区交替编号连续存放,则连续读/写多条记录时能减少磁头的延迟时间;同柱面不同盘面的扇区若能错位编号，连续读/写相邻两个盘面的逻辑记录时也能减少磁头延迟时间。

图4.24 磁盘片组扇区编号找不到图片(Image not found)

以图4.24为例，在随机扇区访问情况下，定位磁道中的一个扇区平均需要转过4个扇区，这时，延迟时间是传输时间的4倍，这是一种非常低效的存取方式。理想化的情况是不需要定位而直接连续读取扇区，没有延迟时间，这样磁盘数据存取效率可以成倍提高。但由于读取扇区的顺序是不可预测的，所以延迟时间不可避免。图4.24中的编号方式是读取连续编号扇区时的一种方法。

磁盘寻块时间分为三个部分，即寻道时间、延迟时间和传输时间，寻道时间和延迟时间属于“找”的时间，凡是“找”的时间都可以通过一定的方法削减，但传输时间是磁盘本身性质所决定的，不能通过一定的措施减少。

磁盘的管理

磁盘初始化

一个新的磁盘只是一个含有磁性记录材料的空白盘。在磁盘能存储数据之前，它必须分成扇区以便磁盘控制器能进行读和写操作，这个过程称为 $\color{green}{\text{低级格式化}}$ （物理分区)。低级格式化为磁盘的每个扇区采用特别的数据结构。每个扇区的数据结构通常由 $\color{green}{\text{头}}$ 、 $\color{green}{\text{数据区域}}$ (通常为512B大小）和 $\color{green}{\text{尾部}}$ 组成。头部和尾部包含了一些磁盘控制器所使用的信息。

为了使用磁盘存储文件，操作系统还需要将自己的数据结构记录在磁盘上:第一步将磁盘分为由一个或多个柱面组成的 $\color{green}{\text{分区}}$ （即我们熟悉的C盘、D盘等形式的分区);第二步对物理分区进行 $\color{green}{\text{逻辑格式化}}$ （创建文件系统)，操作系统将初始的文件系统数据结构存储到磁盘上,这些数据结构包括空闲和已分配的空间及一个初始为空的目录。

引导块

计算机启动时需要运行一个初始化程序（ $\color{green}{\text{自举程序}}$ )，它初始化CPU、寄存器、设备控制器和内存等，接着启动操作系统。为此，该自举程序应找到磁盘上的操作系统内核，装入内存，并转到起始地址，从而开始操作系统的运行。

自举程序通常保存在ROM 中，为了避免改变自举代码而需要改变ROM硬件的问题，因此只在ROM中保留很小的自举装入程序，将完整功能的自举程序保存在磁盘的启动块上，启动块位于磁盘的固定位。拥有启动分区的磁盘称为启动磁盘或系统磁盘。

坏块

由于磁盘有移动部件且容错能力弱，因此容易导致一个或多个扇区损坏。部分磁盘甚至从出厂时就有坏扇区。根据所使用的磁盘和控制器，对这些块有多种处理方式。

对于简单磁盘，如电子集成驱动器(IDE)，坏扇区可手工处理，如 MS-DOS的Format 命令执行逻辑格式化时便会扫描磁盘以检查坏扇区。坏扇区在FAT表上会标明，因此程序不会使用。

对于复杂的磁盘，如小型计算机系统接口(SCSI)，其控制器维护一个磁盘坏块链表该链表在出厂前进行低级格式化时就已初始化，并在磁盘的整个使用过程中不断更新。低级格式化将一些块保留作为备用，对操作系统透明。控制器可用备用块来逻辑地替代坏块，这种方案称为 $\color{green}{\text{扇区备用}}$ 。

对坏块的处理实质上就是用某种机制，使系统不去使用坏块。坏块属于硬件故障，操作系统是不能修复坏块的。

本节小结

本节开头提出的问题的参考答案如下。

在磁盘上进行一次读写操作需要哪几部分时间?其中哪部分时间最长?

在磁盘上进行一次读写操作花费的时间由寻道时间、延迟时间和传输时间决定。其中寻道时间是将磁头移动到指定磁道所需要的时间，延迟时间是磁头定位到某一磁道的扇区（块号）所需要的时间，传输时间是从磁盘读出或向磁盘写入数据所经历的时间。一般来说， $\color{green}{\text{寻道时间}}$ 因为要移动磁臂，所以占用时间最长。

存储一个文件时，当一个磁道存储不下时，剩下部分是存在同一个盘面的不同磁道好，还是存在同一个柱面上的不同盘面好?

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

本章疑难点

磁盘结构

引导控制块（Boot Control Block)包括系统从该分区引导操作系统所需要的信息。若磁盘没有操作系统，则这块的内容为空。它通常为分区的第一块。UFS称为引导块(Boot Block);NTFS称为分区引导扇区(Partition Boot Sector)。

分区控制块(Partition Control Block)包括分区详细信息，如分区的块数、块的大小、空闲块的数量和指针、空闲FCB 的数量和指针等。UFS称为超级块(Super Block)，而NTFS称为主控文件表(Master File Table)。

内存结构

内存分区表包含所有安装分区的信息。

内存目录结构用来保存近来访问过的目录信息。对安装分区的目录，可以包括一个指向分区表的指针。

系统范围的打开文件表，包括每个打开文件的FCB复制和其他信息。

单个进程的打开文件表，包括一个指向系统范围内已打开文件表中合适条目和其他信息的指针。

文件系统实现概述

为了创建一个文件，应用程序调用逻辑文件系统。逻辑文件系统知道目录结构形式，它将为文件分配一个新的 FCB，把相应目录读入内存，用新的文件名更新该目录和FCB，并将结果写回磁盘。图4.25显示了一个典型的FCB。

图4.25典型的FCB找不到图片(Image not found)

一旦文件被创建,它就能用于IO,不过首先要打开文件。调用open将文件名传给文件系统，文件系统根据给定文件名搜索目录结构。部分目录结构通常缓存在内存中以加快目录操作。找到文件后，其FCB复制到系统范围的打开文件表。该表不但存储FCB，而且存储打开该文件的进程数量的条目。

然后，单个进程的打开文件表中会增加一个条目，并通过指针将系统范围的打开文件表的条目与其他域(文件当前位置的指针和文件打开模式等)相连。调用open返回的是一个指向单个进程的打开文件表中合适条目的指针，所以文件操作都是通过该指针进行的。

文件名不必是打开文件表的一部分，因为一旦完成对FCB在磁盘上的定位，系统就不再使用文件名。对于访问打开文件表的索引，UNIX称之为文件描述符(File Descriptor)，而Windows2000称之为文件句柄(Fiie Handle)。因此，只要文件未被关闭，所有文件操作就通过打开文件表来进行。

当一个进程关闭文件时，就会删除单个进程打开文件表中的一个相应条目，即目录项，系统范围内打开文件表的打开数也会递减。当打开文件的所有用户都关闭了一个文件时，更新的文件信息会复制到磁盘的目录结构中，系统范围的打开文件表的条目也将删除。

在实际中，系统调用open 时会首先搜索系统范围的打开文件表，以确定某文件是否已被其他进程所使用。如果是，就在单个进程的打开文件表中创建一项，并指向现有系统范围的打开文件表的相应条目。该算法在文件已打开时，能节省大量开销。

混合索引分配的实现

混合索引分配已在UNIX系统中采用。在UNIX System V的索引结点中，共设置了13个地址项，即 iaddr(0)~iaddr(12)，如图4.26所示。在BSD UNIX 的索引结点中，共设置了13个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。

(1）直接地址

为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(O)一iaddr(9)来存放直接地址。换言之，这里每项中所存放的是该文件数据所在盘块的盘块号。假如每个盘块的大小为4KB，当文件不大于40KB时，便可直接从索引结点中读出该文件的全部盘块号。

(2)一次间接地址

对于大、中型文件，只采用直接地址并不现实。可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1024个盘块号，因而允许文件长达 4MB。

(3）多次间接地址

当文件长度大于4MB＋40KB(一次间接地址与10个直接地址项)时，系统还须采用二次间接地址分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时在二次间接地址块中记入所有一次间接地址块的盘号。在采用二次间接地址方式时，文件的最大长度可达4GB。同理，地址项iaddr(12)作为三次间接地址，其允许的文件最大长度可达4TB。

4.26UNIX系统的inode结构示意图找不到图片(Image not found)

最后，我们对本章内容再进行一次宏观上的把握。贯穿本章内容的有两条主线:第一条主线是介绍一种新的抽象数据类型、文件，从逻辑结构和物理结构两个方面进行;第二条主线是操作系统是如何管理“文件”这种数据结构的，介绍了多文件的逻辑结构的组织，即目录，还介绍了如何处理用户对文件的服务请求，即磁盘管理。但宏观认识是远远不够的，从宏观上把握知识的目的是从微观上更加准确地掌控细微知识点，在考试中得到好成绩。读者要通过反复做题、对答案，不断加深自己对知识点的认知程度。