文件系统基础

文件的概念

文件的定义

文件是以计算机硬盘为载体的存储在计算机上的信息集合，可以是文本文档、图片、程序等

在用户进行的输入、输出中，以文件为基本单位；大多数应用程序从文件输入，也输出到文件，以实现信息长期存储

操作系统中的文件系统 File System 用于实现用户或应用程序对文件进行创建、访问、修改等

文件包括：一块存储空间用于存储数据、分类和索引的信息、访问权限的信息

文件系统提供了与二级存储（除内存外可以访问数据的存储器）相关的资源的抽象，让用户可以方便快捷地使用文件

文件的结构（自底向上）如下：

1. 数据项：数据项是文件系统中最低级的数据组织形式，分为:
   • 基本数据项：描述一个对象的某种属性的一个值，是数据中可命名的最小逻辑数据单位，即原子数据
   • 组合数据项：由多个基本数据项组成
2. 记录：一组相关的数据项的集合，用于描述一个对象在某方面的属性
3. 文件：文件是指由创建者所定义的一组相关信息的集合，逻辑上可分为：
   • 有结构文件：由一组相似的记录组成，又称记录式文件，如 Excel 表
   • 无结构文件：二进制文件或字符文件，又称流式文件

在操作系统中，通常将程序和数据组织成文件；文件基本访问单元可以是字节、行或记录

文件可以长期存储于硬盘或其他二级存储器中，允许可控制的进程间共享访问，能够被组织成复杂的结构

额外：逻辑地址：逻辑上磁盘的块号，因为一块可能等于多个扇区；物理地址：柱面号·盘面号·扇区号

文件的属性

文件通常包括如下属性：

1. 名称：文件名称唯一，以容易读取的形式保存
2. 标识符：标识文件系统内文件的唯一标签，通常为数字，是对人不可读的一种内部名称
3. 类型：被支持不同类型的文件系统所使用，如 .txt 类型
4. 位置：指向设备和设备上文件的指针
5. 大小：文件当前大小，也可包含文件允许的最大值
6. 保护：对文件进行保护的访问控制信息
7. 时间：日期和用户标识

所有文件的信息都保存在目录结构中，而目录结构保存在外存上，需要时才调入内存

文件的基本操作

文件属于抽象数据类型，下面是有关文件的操作，通过系统调用使用：

1. 创建文件，两个必要步骤：

   • 在文件系统中为文件找到空间
   • 在目录中为新文件创建条目

2. 写文件：

   对于给定文件名称，系统搜索目录以查找文件位置

   系统维护一个写位置的指针，每当发生写操作时，写入并更新写指针

3. 读文件：

   对于给定文件名称，系统搜索目录以查找文件位置

   系统维护一个读位置的指针，每当发生读操作时，读出并更新读指针

   一个进程通常对一个文件只进行读或写，因此只维护文件位置指针，由读写共用

4. 文件重定位，文件寻址：按某条件搜索目录，修改目录项将当前文件位置设为给定值

5. 删除文件：先从目录中找到要删除文件的目录项，然后回收该文件所占用的存储空间

6. 截断文件：允许文件所有属性不变，仅删除文件内容

基本操作可以组合起来执行其他文件操作，如复制 = 创建 + 读 + 写

文件的打开与关闭

操作系统在处理 open 系统调用时，主要做了：

1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户的操作权限
2. 若有权限，则将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户（文件描述符）

注意：在打开文件以后，对文件的操作不需要文件名，而使用打开文件表的编号来指明要操作的文件

整个系统有一个打开文件表，记录 FCB 和其他信息；每个进程有一个打开文件表，记录系统打开表的索引和其他信息

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

• 文件指针：当前文件内的位置的指针，对打开文件的某个进程来说是唯一的
• 文件打开计数：在系统打开表中，以记录多少进程打开了该文件，打开时加一，关闭时减一，为零时才回收资源
• 文件磁盘位置：该信息保存在系统打开表项中，以免为每个操作都从磁盘中读取
• 访问权限：每个进程打开文件都需要有一个访问模式，以便操作系统能够允许或拒绝之后的 I/O 请求

注意：打开已经被打开的文件时，为对应进程的打开表增加条目，系统打开表的对应条目的文件打开计数加一

文件的逻辑结构

文件的逻辑结构：从用户观点出发看到的文件的组织形式

文件的物理结构：从实现观点出发看到的文件在外存上的存储组织形式

思考：文件逻辑结构：文件是怎么样的；文件物理结构：文件是怎样存储的

注意：这里的文件结逻辑构是文件的内部逻辑结构，外部逻辑结构是目录结构

无结构文件（流式文件）

无结构文件是最简单的文件组织形式，它将数据按顺序组织成记录，是有序相关信息项的集合，以字节 Byte 为单位

由于无结构文件没有结构，因而对记录的访问只能通过穷举搜索的方式，因此这种文件形式对大多数应用不适用

但字符流的无结构文件管理简单，用户可以方便地对其进行操作

所以，那些对基本信息单位操作不多的文件较适于采用字符流的无结构方式，如源程序文件、目标代码文件等

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

顺序文件

文件中的记录一个接一个地顺序排列，记录通常是定长的，可以顺序存储或链表形式存储

顺序文件有以下两种结构：

1. 串结构：记录之间的顺序与关键字无关，通常由时间决定

2. 顺序结构：指文件中的所有记录按关键字顺序排列

   只有顺序结构，顺序存储且记录定长时可随机存储

在对记录进行批量操作，即每次要读或写一大批记录时，顺序文件的效率是所有逻辑文件中最高的

只有顺序文件才能存储在磁带上，并能有效地工作，但顺序文件对增加或删除单条记录的操作比较困难

索引文件

索引文件由索引表和逻辑文件组成，索引表指出逻辑文件在整个文件中的相对位置，是逻辑地址

顺序文件的变长记录只能顺序查找系统开销较大，故建立一张索引表以加快检索速度，索引表本身是定长记录的顺序文件

在记录很多或访问要求高的文件中，需要引入索引以提供有效的访问，这样即使变长记录也能随机访问以提高速度

索引顺序文件

索引顺序文件是顺序和索引两种组织形式的结合，索引顺序文件将顺序文件中的所有记录分为若干组

为顺序文件建立一张索引表，在索引表中为每组中的第一条记录建立一个索引项，包含记录的关键字值和指向该记录的指针

主文件中记录分组排列，同一个组中的关键字可以无序，但组与组之间的关键字必须有序

查找一条记录时，首先通过索引表找到其所在的组，然后在该组中使用顺序查找，就能很快地找到记录

在索引顺序文件中，N 条记录分为 $\sqrt{N}$ 组，每组有 $\sqrt{N}$ 条记录，则平均查找查找次数为 ${\displaystyle \frac{\sqrt{N}}{2}}+{\displaystyle \frac{\sqrt{N}}{2}}=\sqrt{N}$

索引顺序文件提高了查找效率，若记录数很多，则可采用两级或多级索引

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

直接文件或散列文件

给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址

这种映射结构不同于顺序文件或索引文件，没有顺序的特性

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

思考：有结构文件逻辑上的组织，是为在文件中查找数据服务的

目录结构

文件目录把文件管理系统和文件集合相关联，它包含有关文件的信息，这些信息主要由操作系统进行管理

首先我们来看目录管理的基本要求：

1. 从用户的角度看，目录管理要实现按名存取
2. 目录存取的效率直接影响到系统的性能，所以要提高对目录的检索速度
3. 在共享系统中，目录还需要提供用于控制访问文件的信息

目录结构即多个文件之间在逻辑上是如何组织的，这实际上是文件“外部”的逻辑结构的问题

文件控制块和索引结点

文件控制块

文件控制块 FCB 是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”

FCB 的有序集合称为文件目录，一个 FCB 就是一个文件目录项

创建一个新文件，系统将分配一个 FCB 并存放在文件目录中，成为目录项

FCB 主要包含以下信息：

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

索引结点

在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项时，才需要从该目录项中读出该文件的物理地址

因此，有的系统采用文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称 i 结点

在文件目录中的每个目录项仅由文件名和指向该文件所对应的 i 结点的指针构成（把 FCB 分割为两部分）

使用索引结点后，目录项的大小缩小很多，一个盘块可以装更多的目录项，从而减少平均启动磁盘次数

存放在磁盘上的索引结点称为磁盘索引结点，UNIX 中的每个文件都有一个唯一的磁盘索引结点

磁盘索引节点主要包括以下内容：

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

文件被打开时，磁盘索引结点复制到内存的索引结点中，以便于使用

内存索引结点中又增加了以下内容：

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

目录结构

在目录这个层次上所需要执行的操作：

• 搜索：搜索目录，找到该文件的对应目录项
• 创建文件：创建文件时，在目录中增加目录项
• 删除文件：删除文件时，在目录中删除目录项
• 显示目录：显示目录的内容，如目录的属性及所有文件
• 修改目录：文件的一些属性放在目录中，修改这些属性时必须修改目录

单级目录结构

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

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

实现了按名存取，但是存在查找速度慢、文件不允许重名、不便于文件共享等缺点，而且不适合多用户的操作系统

两级目录结构

单级目录很容易造成文件名称的混淆，因此将文件目录分成主文件目录和用户文件目录两级

主文件目录项记录用户名及相应用户文件目录所在的存储位置，用户文件目录项记录该用户文件的 FCB 信息

当用户访问其文件时，在自己的目录中搜索，这用户间不会重名，且一定程度上保证了文件的安全

优点：解决多用户之间的文件重名问题，文件系统可以在目录上实现访问限制；缺点：缺乏灵活性，不能对文件分类

多级目录结构

将两级目录结构的层次关系加以推广，就形成了多级目录结构，即树形目录结构

访问文件：用文件的路径名标识文件，文件路径名是个字符串，目录名与数据文件名用分隔符 / 链接而成

绝对路径：从根目录出发的路径，当层次较多时，每次从根目录查询会浪费时间

相对路径：进程对各文件的访问都是相对于当前目录进行（工作目录）的，一般使用 ./ 表示当前目录

每个用户都有各自的当前目录，登录后自动进入该用户的当前目录，用户可以使用系统调用随时改变当前目录

优点：很方便地对文件进行分类，层次结构清晰，有效地进行文件的管理和保护

缺点：查找一个文件时，需要按路径名逐级访问中间结点，增加了磁盘访问次数，影响查询速度

无环图目录结构

在树形目录结构的基础上增加了一些指向同一结点的有向边，使整个目录成为一个有向无环图，以便实现文件共享

如下图，使用这种结构就很方便的实现 dict 和 spell 目录共享 count 文件和 p 目录

删除一个共享结点时，若只是简单地将它删除，则另一个用户访问时会发生错误

所以给每个共享结点设置一个共享计数器：

• 每当图中增加对该结点的共享链时，计数器加 1
• 每当某用户提出删除该结点时，计数器减 1
• 仅当共享计数器为 0 时，才删除该结点，否则仅删除请求用户的共享链

优点：方便地实现了文件的共享；缺点：使系统的管理变得更加复杂

文件共享

文件共享使多个用户或进程共享同一个文件，系统中只需保留该文件的一个副本

随着计算机技术的发展，文件共享的范围已由单机系统发展到多机系统，进而通过网络扩展到全球

基于索引结点的共享方式

也称硬链接，有两个或多个用户要共享一个子目录或文件时，将共享文件或子目录链接到两个或多个用户的目录中

在这种共享方式中，在文件目录中只设置文件名及指向相应索引结点的指针，文件信息放在索引结点中

在索引结点中还应有一个链接计数 count，用于表示链接到本索引结点上的用户目录项的数目

1. A 创建一个文件，是该文件的所有者，将 count 置为 1
2. B 共享此文件，在 B 的目录中增加一个目录项，并设置一个指针指向该文件的索引结点，count = 2
3. A 删除此文件时，将该文件的 count 减 1，仅删除自己目录中的相应目录项，B 仍可以使用该文件
4. B 也删除 count = 0 时，系统将负责删除该文件；过程如下图

利用符号链实现文件共享

也称软链接，B 共享文件时在 B 的目录中创建一个 LINK 类型的文件，内部放被共享文件的路径，这称为符号链接

新文件中的路径名只被视为符号链，当用户访问 LINK 文件时，操作系统根据 LINK 文件中的路径名去读该文件

只有文件的拥有者才拥有指向其索引结点的指针，其他用户只有该文件的路径名

当文件的拥有者把共享文件删除后，通过符号链去访问它时，会出现访问失败，于是将符号链删除

当文件拥有者将文件删除后，在未删除 LINK 文件前，有人在同一路径下创建了同样名称的文件，则该符号链将仍然有效

其他用户读共享文件时，需要根据文件路径名逐个地查找目录，使得访问文件的开销变大并增加了启动磁盘的频率，而且符号链的索引结点也要耗费一定的磁盘空间

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

---

两种链接方式共同问题：每个共享文件都有几个文件名，当我们试图去遍历整个文件系统时，将会多次遍历到该共享文件

硬链接和软链接都是文件系统中的静态共享方法；两个进程同时对同一个文件进行操作，这样的共享称为动态共享

硬链接：多个指针指向一个索引结点，只要还有一个指针指向索引结点，索引结点就不能删除（速度更快）

软链接：把到达共享文件的路径记录下来，当要访问文件时，根据路径寻找文件

文件保护

为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取

文件保护通过口令保护、加密保护和访问控制等方式实现

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

访问类型

对文件的保护可从限制对文件的访问类型中出发：

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

此外还可以对文件的重命名、复制、编辑等加以控制，这些功能可以由上面的功能完成，故保护可以只在低层提供

如具有读访问权限的用户同时也就具有了复制和打印权限

访问控制

访问控制

根据用户身份进行控制，为每个文件和目录增加一个访问控制列表 ACL，以规定每个用户名及其所允许的访问类型

优点：可以使用复杂的访问方法；缺点：长度无法预计并且可能导致复杂的空间管理

精简的访问列表可以解决这个问题，它采用拥有者、组和其他三种用户类型：

1. 拥有者：创建文件的用户
2. 组：与创建文件在同一个用户组的用户
3. 其他：系统内的所有其他用户

只需用三个域即可列出访问表中这三类用户的访问权限：

1. 文件拥有者在创建文件时，说明创建者用户名及所在的组名，系统会列在文件的 FCB 中
2. 用户访问该文件时，查看其访问权限：
   • 若是拥有者，按拥有者权限
   • 若用户和拥有者在同一个用户组，则按照同组权限
   • 否则按其他用户权限

选择题：用户访问优先级，指多个用户访问同一个文件谁先访问，但文件不是谁先访问谁就能访问的

口令和密码

• 口令：用户在创建文件时提供一个口令，放在 FCB 上，告诉共享此文件的其他用户，访问时必须提供相应的口令

  优点：时间和空间的开销不多；缺点：口令直接存在系统内部，不够安全

• 密码：用户对文件进行加密，文件被访问时需要使用密钥

  优点：保密性强，节省了存储空间；缺点：编码和译码要花费一定的时间

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

注意两个问题：

1. 现代 OS 常用方法：将访问控制列表与用户、组和其他成员访问控制方案一起组合使用
2. 目录结构而言，需要保护单个文件和子目录，故需要提供目录和文件保护机制

文件系统实现

文件系统层次结构

现代操作系统有多种文件系统类型如 FAT32，NTF 等，因此文件系统的层次结构也不尽相同

1. 用户调用接口：

   文件系统提供与文件及目录有关的调用，如新建、打开、读写、关闭、删除文件，建立、删除目录等

   此层由若干程序模块组成，每个模块对应一条系统调用，用户发出系统调用时，转入相应的模块

2. 文件目录系统：

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

3. 存取控制验证模块：

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

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

   主要功能是，根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号

   文件信息缓冲区用于缓冲如索引文件的索引表之类的信息

5. 物理文件系统：

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

6. 辅助分配模块：

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

7. 设备管理程序模块：

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

例子：用户要使用文件 F ：

1. 调用 OS 的系统调用，这是第 0 级
2. 系统调用内部查找 F 的 FCB，这是第 1 级
3. 在 FCB 上检查用户权限，这是第 2 级
4. 通过验证后，把记录索引转换为逻辑地址，这是第 3 级
5. 把逻辑地址转换成物理地址，这是第 4 级
6. 若要释放空间，则把任务就交给辅助分配模块
7. 若要输入/输出，则把任务交给设备管理程序模块

目录实现

目录实现的基本方法有线性列表和哈希表两种，线性列表实现对应线性查找，哈希表的实现对应散列查找

思考：目录的实现是指目录项在目录中逻辑上是如何存放的，相应的查找方法是什么，物理存放还是通过文件分配方式

线性列表

线性列表优点在于实现简单，不过由于线性表的特殊性，比较费时，最简单的目录表项是存储文件名 + 数据块指针

可以采用顺序表和链表：

• 顺序表：查找文件快速，但插入和删除文件比较费时间
• 链表：减少删除文件的时间，但查找文件时只能顺序查找

重用（删除）目录项有许多方法：

• 将目录项标记为不再使用
• 将它加到空闲目录项表上
• 将目录表中的最后一个目录项复制到空闲位置，并降低目录表长度

哈希表

根据文件名得到一个值，并返回一个指向线性列表中元素的指针

优点：查找非常迅速，插入和删除也较简单；缺点：需要一些预备措施来避免冲突

最大的困难是哈希表长度固定以及哈希函数对表长的依赖性

---

目录查询是通过在磁盘上反复搜索完成的，需要不断地进行 I/O 操作，开销较大

所以把当前使用的文件目录复制到内存，以降低了磁盘操作次数，提高了系统速度

文件实现：文件分配方式

文件实现就是研究文件数据在物理存储设备上是如何分布和组织的

文件的分配方式，是对磁盘非空闲块的管理，指如何为文件分配磁盘块

常用的分配方法有三种：连续分配、链接分配和索引分配；通常一个文件系统只支持一种方法，但也有三种都支持的

思考：因为文件分配是按块（簇）分配，不足两个块的内容也会占两个块（是块的整数倍），会有内部碎片

连续分配

连续分配方法要求每个文件在磁盘上占有一组连续的块，这种方法作业访问磁盘时需要的寻道数和寻道时间最小

文件的连续分配的一个文件的目录条目包括开始块的地址和该文件所分配区域的长度

连续分配支持顺序访问和直接访问，其优点是实现简单、存取速度快；缺点是文件长度不宜动态增加

反复增删文件后会产生外部碎片，且很难确定一个文件需要的空间大小，因而只适用于长度固定的文件

链接分配

链接分配采取离散分配的方式，消除了外部碎片，显著提高了磁盘空间的利用率

可以动态地为文件分配盘块，无须事先知道文件的大小，对文件的增、删、改也非常方便

隐式链接

文件的磁盘块分散，除最后一个盘块外，每个盘块有指向下一个盘块的指针，目录条目 = 首块地址 + 尾块地址或块数

文件刚创建时，首块的指针为 NULL，大小字段为 0，写文件会把空闲块链接到文件的尾部

缺点是无法直接访问盘块，只能通过指针顺序访问文件，且盘块指针会消耗一定的存储空间

稳定性也是一个问题：系统在运行过程中由于软件或硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失

显式链接

把下一块指针从每个物理块的块末尾中提取出来，显式地存放在内存的一张链接表中，称为文件分配表 FAT

FAT 在整个磁盘中仅设置一张，每个表项中存放对应块的下一块链接指针

文件的第一个盘块号记录在目录条目中，后续的盘块可通过查 FAT 找到

可以用一个特殊的数字 -1 表示文件的最后一块，用 -2 表示这个磁盘块是空闲的，如下图

FAT 记录了文件各块之间的先后链接关系和空闲的磁盘块，OS 可以通过 FAT 对文件存储空间进行管理

当某进程请求操作系统分配一个磁盘块时，操作系统从 FAT 中找到空闲块分配给进程

FAT 表在系统启动时就会被读入内存，因此查找 FAT 的过程是在内存中进行的，提高了检索速度，减少了访问磁盘的次数，但同时也需要消耗一定的内存资源

索引分配

索引分配在链接分配的基础上解决了直接访问，它把每个文件的所有的盘块号都集中放在一起构成索引块（表）

每个文件都有其索引块，索引块的第 i 个条目指向文件的第 i 个块，目录条目包括索引块的地址

创建文件时，索引块的所有指针都设为空，首次写入第 i 块时，OS 分配空闲块并将其地址写到索引块的第 i 个条目

优点：索引分配支持直接访问，且没有外部碎片问题；缺点：由于索引块的分配，增加了系统存储空间的开销

索引块大小难以确定，可以采用以下机制来处理索引块大小问题：

• 链接方案：当索引块大小超过一个磁盘块时，按磁盘块拆开并链接起来

• 多层索引：第一层索引块指向第二层的索引块，第二层索引块再指向文件块，可扩展更多层

• 混合索引：将多种索引分配方式相结合的分配方式，如索引表包含 3 个直接索引 1 个单极索引 1 个二级索引

  这样既可以在文件小时索引表小，又在文件大时索引表仍然可以索引

通常将文件的索引块读入内存的缓冲区中，以加快文件的访问速度

三种分配方式的比较

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

1. 文件存储器空间的划分与初始化：

   一个文件存储在一个文件卷中，文件卷可以是物理盘的一部分，也可以是整个物理盘，也可由多个物理盘组成

   

   在一个文件卷中，文件数据信息的空间（文件区）和存放文件控制信息 FCB 的空间（目录区）是分离的

   逻辑卷在提供文件服务前，必须由对应的文件程序进行初始化，如划分好目录区和文件区等

2. 文件存储器空间管理：

   文件存储设备分成许多大小相同的物理块，并以块为单位交换信息

   文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题

空闲表法

空闲表法属于连续分配方式，与内存的动态分配方式类似，用于分配一块连续的存储空间

系统为外存上的所有空闲区建立一张空闲盘块表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区第一个盘块号、该区的空闲盘块数等信息，再将所有空闲区按其起始盘块号递增的次序排列

空闲盘区的分配与内存的动态分配类似，同样采用首次适应算法、循环首次适应算法等

系统在对用户所释放的存储空间进行回收时，当回收的区与原来的空闲区相邻时，需要进行合并

空闲链表法

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

• 空闲盘块链：将磁盘上的所有空闲空间以盘块为单位拉成一条链

  分配存储空间时：系统从链首开始，依次摘下适当数目的空闲盘块分配给用户

  释放存储空间时：系统将回收的盘块依次插入空闲盘块链的末尾

  优点：分配和回收一个盘块的过程非常简单；缺点：为一个文件分配盘块时可能要重复多次操作

• 空闲盘区链：将磁盘上的所有空闲盘区（每个盘区可包含若干盘块）拉成一条链

  在每个盘区上含有用于指示下一个空闲盘区的指针和本盘区的大小信息

  分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法

  在回收盘区时，同样也要将回收区与相邻接的空闲盘区合并

位示图法

利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上的每个盘块都有一个二进制位与之对应

当其值为 0 时，表示对应的盘块空闲；当其值为 1 时，表示对应的盘块已分配

盘块的分配：

1. 顺序扫描位示图，从中找出一个或一组其值为 0 的二进制位
2. 转换成与之对应的盘块号，如位于位示图的第 i 行、第 j 列，每行有 n 位，则盘块号为：b = n(i - 1) + j
3. 修改位示图，令 map[i, j] = 1

盘块的回收：

1. 将回收盘块的盘块号转换成位示图中的行号和列号，转换公式为 i = (b - 1) DIV n + 1，j = (b - 1) MOD n + 1
2. 修改位示图，令 map[i, j] = 0

特别注意：上面公式是从 1 开始编号，若题目中指明从 0 开始编号，则上述计算方法要进行相应调整

成组链接法

空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太大

在 UNIX 系统中采用的是成组链接法，这种方法结合了空闲表和空闲链表两种方法，克服了表太大的缺点

其大致思想是：

• 把顺序的 n 个空闲扇区地址保存在第一个空闲扇区内
• n 个空闲扇区中的某一个，一般是第一个或最后一个，再保存顺序的 n 个空闲扇区的地址
• 如此继续，直至所有空闲扇区均予以链接
• 系统只需要保存一个指向第一个空闲扇区的指针

通过这种方式可以迅速找到大批空闲块地址

分区控制块一般放在卷头位置，保存了文件系统的全局信息，如分区的块数、块的大小、空闲块的数量和指针、空闲 FCB 的数量和指针、卷中的目录区和文件区划分信息等；UNIX 的 UFS 中称为超级块，NTFS 中称为主控文件表

在对卷中的文件进行操作前，超级块需要预先读入系统空闲的主存，并且经常保持主存超级块与辅存卷中超级块的一致性

磁盘组织与管理

磁盘的结构

磁盘是由表面涂有磁性物质的圆形盘片，通过磁头从磁盘存取数据，在读/写操作期间，磁头固定，磁盘在下面高速旋转

一个盘面有多个磁道（与磁头同宽），一个磁道有多个扇区（大小固定），一个扇区称为一个盘块

相邻磁道及相邻扇区间通过一定的间隙分隔开，以避免精度错误

注意：扇区的存储密度从最外道向里道增加，磁盘的存储能力受限于最内道的最大记录密度

磁盘安装在一个磁盘驱动器中，它由磁头臂、用于旋转磁盘的主轴、用于数据输入/输出的电子设备组成

多个盘片垂直堆叠，组成磁盘组，每个盘面对应一个磁头，所有磁头固定在一起，与磁盘中心的距离相同且一起移动

所有盘片上相同位置的磁道组成柱面，扇区是磁盘可寻址的最小存储单位，磁盘地址：柱面号·盘面号·扇区号

磁盘按不同的方式可分为若干类型：

• 每个磁道一个磁头，磁头不需要移动，称为固定头磁盘
• 磁头需要移动寻找磁道，称为活动头磁盘
• 磁盘永久固定在磁盘驱动器内的，称为固定盘磁盘
• 磁盘可移动和替换的，称为可换盘磁盘

注意：一般柱面、盘面、扇区、簇都是从 0 编号，一般柱面有多少个磁道就是有多少个盘面

磁盘操作时间

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

1. 寻找时间 $T_S$：活动头磁盘在读写信息前，将磁头移动到指定磁道所需要的时间

   这个时间包括跨越 n 条磁道的时间，和启动磁臂的时间 s，即 $T_s=m\times n+s$

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

2. 旋转延迟时间 $T_r$：磁头定位到某一磁道的扇区所需要的时间

   设磁盘的旋转速度为 r，则 $T_r={\displaystyle \frac{1}{2r}}$，平均时间所以要除以 2

3. 传输时间 $T_t$：从磁盘读出或向磁盘写入数据所经历的时间

   取决于每次所读/写的字节数 b 和磁盘的旋转速度，$T_t={\displaystyle \frac{b}{rN}}$

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

寻道时间与磁盘调度算法相关（OS 只能优化寻道时间）；旋转延迟时间和传输时间都与磁盘旋转速度线性相关

总平均存取时间 $T_a$ 可以表示为 $T_a=T_s+{\displaystyle \frac{1}{2r}}+{\displaystyle \frac{b}{rN}}$，在实际的中调度算法直接决定寻找时间，从而决定总的存取时间

磁盘调度算法

用户访问文件时，操作系统经过一系列的检验访问权限和寻址过程后，控制磁盘把相应的数据信息读出或修改

当有多个请求同时到达时，操作系统就要决定先为哪个请求服务，这就是磁盘调度算法要解决的问题

先来先服务 FCFS 算法

FCFS 算法根据进程请求访问磁盘的先后顺序进行调度，这是一种最简单的调度算法

优点：具有公平性，若只有少量进程需要访问，且大部分访问的磁道比较集中，则有望达到较好的性能

缺点：大量进程竞争使用磁盘时，则这种算法在性能上往往接近于随机调度（性能很差，一般不用）

例子：磁盘请求队列中的请求顺序分别为 55, 58, 39, 18, 90, 160, 150, 38, 184，磁头的初始位置是磁道 100

采用 FCFS 算法时磁头共移动了 (45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146) = 498 个磁道，平均寻找长度 = 498 / 9 = 55.3

最短寻找时间优先 SSTF 算法

SSTF 选择与当前磁头所在磁道距离最近的磁道，以便使每次的寻找时间最短，但不能保证平均寻找时间最小

能提供比 FCFS 算法更好的性能，但这种算法会产生饥饿现象，即一直处理近的请求而忽略远的请求

使用 FCFS 的参数：采用 SSTF 算法时磁头共移动了 248 个磁道，平均寻找长度 = 248 / 9 = 27.5

扫描 SCAN 算法

SCAN 在磁头当前移动方向上选择与当前磁道距离最近的请求，由于磁头移动与电梯相似，又称电梯调度算法

SCAN 算法对最近扫描过的区域不公平，因此它在访问局部性方面不如 FCFS 算法和 SSTF 算法好

采用 SCAN 算法时，要知道磁头的当前位置和磁头的移动方向，但解决了 SSTF 的饥饿现象，且性能比 FCFS 快

使用 FCFS 的参数：磁头朝磁道号增大的方向移动，采用 SCAN 磁头共移动了282 个磁道，平均寻道长度 = 282 / 9 = 31.33

循环扫描 C-SCAN 算法

在 SCAN 的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求

使用改进型的 C-SCAN 算法来避免偏向于处理那些接近最里或最外的磁道的访问请求（避免不公平）

使用 FCFS 的参数：磁头沿磁道号增大的顺序移动，采用 C-SCAN 磁头共移动 390 个磁道，平均寻道长度 = 390 / 9 = 43.33

LOOK 调度算法

LOOK 调度：在 SCAN 的基础上磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点

C-LOOK 调度：和 LOOK 差不多，但它是在 C-SCAN 的基础上实现的

LOOK 和 C-LOOK 通过在移动前会查看此方向是否有请求实现的

注意，若无特别说明，也可以默认 SCAN 算法和 C-SCAN 算法为 LOOK 和 C-LOOK 调度

磁盘调度算法比较

• FCFS 算法太过简单，性能较差，仅在请求队列长度接近于 1 时才较为理想
• SSTF 算法较为通用和自然
• SCAN 算法和 C-SCAN 算法在磁盘负载较大时比较占优势

减少延迟时间

对盘面扇区进行交替编号，不同盘面错位命名，假设每个盘面有 8 个扇区，磁盘片组共 8 个盘面，可如此编号：

磁盘是连续自转设备，磁头读/写一个物理块后，需要经过短暂的处理时间才能开始读/写下一块

这种编号的好处是，读完了 0 号扇区后，处理数据时磁头刚好在 4 号扇区，处理完了后就转到了 1 号扇区

若编号连续，读完 0 号后，转到 1 号扇区头部时在处理数据，处理完后就错过了，需要再转一圈

不同盘面的扇区错位类似；这种编号只会减少连续读时的延迟时间，不能减少随机读的时间

磁盘寻块时间分为寻道时间、延迟时间、传输时间

• 寻道时间和延迟时间这种找的时间都可以通过一定的方法削减
• 传输时间是磁盘本身性质所决定的，不能通过一定的措施减少

注意：题目中盘面扇区交替编号和处理时间没有出现，当这节内容是空气就好了，也可以当作现代的磁盘没这种毛病

额外：间隔因子，交错因子：硬盘磁道上相邻的两个逻辑扇区之间的物理扇区的数量

磁盘的管理

磁盘初始化

一个新的磁盘只是一个含有磁性记录材料的空白盘

低级格式化，物理分区：在磁盘能存储数据之前，厂家必须划分扇区以便磁盘控制器能进行读和写操作：

• 低级格式化为磁盘的每个扇区采用特别的数据结构：通常由头部、数据区域和尾部组成
• 头部和尾部包含了一些磁盘控制器所使用的信息，如扇区校验码；数据区用于存放文件数据

为了使用磁盘存储文件，操作系统还需要将自己的数据结构记录在磁盘上：

1. 将磁盘分为由一个或多个柱面组成的分区，即我们熟悉的 C 盘、D 盘等形式的分区
2. 对物理分区进行逻辑格式化，创建文件系统：操作系统将初始的文件系统数据结构存储到磁盘上，这些数据结构包括空闲和已分配的空间及一个初始为空的目录

引导块

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

自举程序需要找到磁盘上的操作系统内核，装入内存，并转到起始地址，从而开始操作系统的运行

在 ROM 中保留很小的自举装入程序，将完整功能的自举程序保存在磁盘的启动块上，启动块（引导控制块）位于磁盘的固定位置；若磁盘没有操作系统，则这块的内容为空，通常为分区的第一块，UFS 中称为引导块，NTFS 中称为分区引导扇区

拥有启动分区的磁盘称为启动磁盘或系统磁盘

坏块

由于磁盘有移动部件且容错能力弱，因此容易导致一个或多个扇区损坏，部分磁盘甚至从出厂时就有坏扇区

根据所使用的磁盘和控制器，对这些块有以下处理方式：

1. 对于简单磁盘：如电子集成驱动器 IDE，坏扇区可由 OS 处理

   如 MS-DOS 的 Format 命令执行逻辑格式化时便会扫描磁盘以检查坏扇区

   坏扇区在 FAT 表上会标明，因此程序不会使用

2. 对于复杂的磁盘：如小型计算机系统接口 SCSI，则由其控制器处理

   其控制器维护一个磁盘坏块链表，在低级格式化时就已初始化，并在磁盘的整个使用过程中不断更新

   低级格式化将一些块保留作为备用，对操作系统透明，控制器可用备用块来逻辑地替代坏块，这种方案称为扇区备用

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

---

📝 个人补充与原笔记精华

NOTE

索引结点的优势：将文件名与文件描述信息（元数据）分开。目录项仅包含文件名和指向索引结点的指针。这大大减小了目录项大小，使得一个磁盘块能存放更多目录项，从而显著减少检索文件时的磁盘 I/O 次数。

IMPORTANT

FAT 的特点：FAT（文件分配表）记录了磁盘块的链接关系。一个磁盘仅有一张 FAT，开机时读入内存并 常驻内存。这使得显式链接不仅支持随机访问，且地址转换不需要访问磁盘，效率极高。