一、文件系统

1. 文件的概念

（1）文件的概念与文件系统

文件是操作系统中的重要概念，是存储在计算机硬盘上的信息集合，如文本文档、图片、程序等。在系统运行时，资源调度和分配以进程为基本单位，而用户的输入、输出则以文件为基本单位。

大多数应用程序通过文件实现输入，输出也保存在文件中，以便长期存储和访问。用户希望能够访问、修改和保存文件，这需要系统提供一个文件管理系统。操作系统中的文件系统（File System） 就是为实现这些管理需求而设计的。

文件系统通过将程序和数据组织为一系列文件来实现管理功能。文件是由文件名和若干相关元素组成的集合，元素通常是记录，而记录是一组有意义的数据项的集合。

文件内部的逻辑结构

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

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

   • 基本数据项：用于描述一个对象的某种属性的一个字符集（值），是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为字段。例如，用于描述一个学生的基本数据项有：学号、姓名、年龄、所在班级等。
   • 组合数据项：由若干个基本数据项组成，简称组项。例如工资是个组项，它可由基本工资、工龄工资和奖励工资等基本项所组成。

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

3. 文件：文件是指由创建者所定义的一组相关信息的集合，逻辑上可分为有结构文件和无结构文件两种。在有结构文件中，文件由若干个相关记录组成，又称记录式文件；而无结构文件则被视为一个字符流，比如一个进制文件或字符文件，又称流式文件。

文件外部的逻辑结构（多个文件之间在逻辑结构）：

1. 文件：文件系统中包含各种类型的文件，它们是文件管理的直接对象。
2. 目录：目录用于方便用户存取和检索文件，每个目录项包含文件名、文件属性说明及文件的物理地址（或指针）。目录的组织和管理对于用户使用便捷性和文件存取速度至关重要。
3. 磁盘（磁带）存储空间：文件和目录占用存储空间，有效管理这部分空间不仅提高外存利用率，还能提升文件存取速度。
   

（2）文件的属性

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

• 名称：文件名称唯一，以容易读取的形式保存。由文件名和扩展名构成，其中扩展名用于指示文件的类型。
• 标识符：标识文件系统内文件的唯一标签，通常为数字，是对人不可读的一种内部名称。
• 类型：被支持不同类型的文件系统所使用。
• 位置：指向设备和设备上文件的指针。
• 大小：文件当前大小(用字节、字或块表示)，也可包含文件允许的最大值。
• 保护：对文件进行保护的访问控制信息。
• 时间、日期和用户标识：文件创建、上次修改和上次访问的相关信息，用于保护和跟踪文件的使用。

（3）文件类型

1. 按性质和用途分类

   • 系统文件：由系统软件构成，通常只允许用户调用，不允许读或修改。有些系统文件不对用户开放。
   • 用户文件：由用户的源代码、目标文件、可执行文件或数据构成，用户将这些文件委托给系统保管。
   • 库文件：由标准子例程及常用例程构成，允许用户调用但不允许修改。

2. 按文件中数据的形式分类

   • 源文件：由源程序和数据构成，通常由终端或输入设备输入，通常用ASCII码或汉字表示。
   • 目标文件：由编译后的目标代码构成，尚未经过链接程序链接，后缀名为“.obj”。
   • 可执行文件：编译后的目标代码经过链接程序链接后形成，后缀名为“.exe”。

3. 按存取控制属性分类

   • 只执行文件：只允许核准的用户调用执行，不允许读和写。
   • 只读文件：只允许文件主及核准用户读，不允许写。
   • 读写文件：允许文件主和核准用户读或写。

4. 按组织形式和处理方式分类

   • 普通文件：由ASCII码或二进制码组成的字符文件，包括源程序文件、数据文件、操作系统代码文件、实用程序等。
   • 目录文件：由文件目录组成，用于检索和操作其下属文件的信息，与普通文件类似。
   • 特殊文件：特指系统中的各类IO设备，系统将所有IO设备视为文件，并按文件方式提供给用户使用。对这些文件的操作由设备驱动程序完成。

（4）文件操作

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

1. 创建文件：首先在文件系统中为文件找到空间，然后在目录中创建条目，记录文件名称、位置及其他信息。
2. 删除文件：从目录中找到要删除的文件项，使之成为空项，并回收文件所占用的存储空间。
3. 写文件：通过系统调用指定文件名称和要写入的内容，系统搜索目录找到文件位置，并维护写位置的指针。每次写操作时，更新写指针。
4. 读文件：通过系统调用指定文件名称和要读入的内存位置，系统搜索目录找到文件位置，并维护读位置的指针。每次读操作时，更新读指针。由于读写操作使用同一指针，节省了空间并降低了系统复杂度。
5. 文件重定位：按条件搜索目录，将当前文件位置设为给定值，不进行读写操作。
6. 截断文件：保持文件属性不变，删除文件内容，将其长度设为0并释放空间。

这些基本操作可以组合执行其他文件操作。例如，文件复制可以通过创建新文件并从旧文件读出写入新文件来实现。

当用户对一个文件实施多次读/写操作时，每次都需从检索目录开始。为了避免重复检索，大多数操作系统引入了“打开”（open）文件系统调用。用户第一次请求对某文件进行操作时，先用open系统调用将文件打开，即将文件属性从外存拷贝到内存的打开文件表中，并返回表目的编号（索引号）给用户。此后，用户可以通过该连接直接获取文件信息，避免再次检索目录，从而节省检索开销并提高操作速度。如果用户不再需要对该文件操作，可以用“关闭”（close）系统调用关闭文件，断开连接，操作系统会将该文件从打开文件表中删除。

2. 文件的逻辑结构

文件的逻辑结构是从用户角度看到的文件组织形式。按逻辑结构，文件可分为无结构文件和有结构文件两种：

1. 无结构文件（流式文件）：这是最简单的文件组织形式，内部数据由一系列二进制流或字符流组成，将数据按顺序组织成记录并保存。它是有序相关信息项的集合，以字节（Byte）为单位。

2. 有结构文件（记录式文件）：由一组相似的记录组成，每条记录由若干数据项构成，通常有一个数据项作为关键字。根据记录长度是否相等，可分为定长记录和可变长记录两种。

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

• 顺序文件：记录按逻辑顺序排列，记录可为定长或可变长。在物理上，记录可顺序存储或链式存储。
  

• 索引文件：为可变长记录文件建立索引表，每个记录设置一个表项，以加速记录检索速度。
  

• 索引顺序文件：结合顺序和索引两种组织形式，将顺序文件中的记录分为若干组，为每组的第一条记录建立索引项，索引项包含该记录的关键字值和指向该记录的指针。
  

3. 文件目录

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

（1）文件控制块与索引节点

• 文件控制块（FCB）：是存储控制文件所需的各类信息的一种一种数据结构，从而达成按名存取的功能。众多 FCB 有序排列形成文件目录，其中单个 FCB 即为一个目录项（Directory Entry）。当创建新文件时，系统会分配一个 FCB 并将其置入文件目录，使之成为目录项。FCB 主要涵盖以下信息：

  • 基本信息：包括文件名、文件物理位置等。
  • 存取控制信息：如文件的存取权限等内容。
  • 使用信息：像文件的建立时间、修改时间等。

• 索引节点（Index Node，inode）：用于记录文件的描述信息（元信息），诸如 inode 编号、文件大小、访问权限、创建时间、修改时间以及数据在磁盘中的位置等等。索引节点是文件的唯一标识，二者一一对应，且均存储于硬盘之中，所以索引节点也会占用一定的磁盘空间。

（2）目录结构

1. 单级目录结构：整个系统中只建立一张目录表，每个文件占一个目录项。单级目录实现了按名存取，但是不允许文件重名。
   当访问一个文件时，先按文件名在该目录中查找到相应的FCB，经合法性检查后执行相应的操作。

2. 两级目录结构：单级目录很容易造成文件名称的混淆，因此可以考虑采用两级方案。将目录分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User Flie Directory）。主文件目录项记录用户名及相应用户文件目录所在的存储位置，用户文件目录项记录该用户文件的 FCB 信息。
   当某用户欲对其文件进行访问时，只需搜索该用户对应的UFD。
   

3. 多级目录结构（树形目录结构）：将两级目录结构的层次关系加以推广，就形成了多级目录结构，即树形目录结构。
   用户要访问某个文件时，用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。从根目录出发的路径称为绝对路径。当层次较多时，每次从根目录查询会浪费时间，于是加入了当前目录，进程对各文件的访问都是相对于当前目录进行的。当用户要访问某个文件时，使用相对路径标识文件，相对路径由从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。
   

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

4. 文件物理结构（文件的存储）

在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件块。文件系统的基本操作单位是数据块。

文件的数据是要存储在硬盘上面的，数据在磁盘上的存放方式，就像程序在内存中存放的方式那样，有以下两种：

• 连续分配方式
• 非连续空间存放方式
  • 链表方式
  • 索引方式

（1）连续空间存放方式

连续空间存放方式要求文件存储在磁盘的连续物理空间中。这种模式下，文件数据紧密相连，读写效率高，因为一次磁盘寻道即可读取整个文件。

使用连续存放方式的前提是必须先知道文件大小，以便文件系统在磁盘上找到一块连续空间进行分配。因此，文件头需要指定起始块位置和长度，以表示文件在磁盘上连续存放。

• 优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快
• 缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片

（2）非连续空间存放方式

非连续空间存放方式又可以分为链表方式和索引方式。

1. 链表分配方式

链表方式采取离散分配的方式，可以为文件分配离散的磁盘块。链表方式可以消除磁盘碎片，大大提高磁盘空间的利用率，同时文件的长度可以动态扩展。根据实现的方式的不同，分为隐式链接和显式链接两种。

隐式链表：

文件头记录了文件存放的起始块号和结束块号，并且每个数据块里面留出一个指针空间，用来存放下一个数据块的位置。这样一个数据块连着一个数据块，从链头开始就可以顺着指针找到所有的数据块，所以存放的方式可以是不连续的。

• 优点：很方便文件拓展，不会有碎片问题，外存利用率高。
• 缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

显式链接：

把用于链接文件各数据块的指针显式地存放在内存的一张链接表中，即文件分配表（File Allocation Table，FAT） 。文件分配表在整个磁盘仅设置一张，每个表项中存放链接指针，指向下一个数据块号。

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

2. 索引分配方式

索引分配方式允许文件分散存储在不同的磁盘块中。系统为每个文件建立一张索引表，记录文件各个逻辑块与物理块之间的映射关系。索引表存放的磁盘块称为索引块，而文件数据存放的磁盘块称为数据块。

• 优点：支持随机访问，易于实现文件的拓展；
• 缺点：索引表需占用一定的存储空间。访问数据块前需要先读入索引块。若采用链接方案，查找索引块时可能需要很多次读磁盘操作。

解决索引表项过多的方法：

1. 链接方案：如果索引表过大，单个索引块无法容纳所有项，可以将多个索引块链接起来存放。
   

2. 多层索引：建立多层索引，类似于多级页表。第一层索引块指向第二层索引块，根据文件大小需求，还可以建立第三层、第四层索引块。
   

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

5. 文件存储空间管理

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

• 存储空间的初始化：将各个文件卷划分为目录区、文件区。目录区主要存放文件目录信息（FCB）、
  于磁盘存储空间管理的信息；文件区用于存放文件数据。

• 存储空间的划分：将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）。有的系统支持超大型文件，可支持由多个物理磁盘组成一个文件卷。

（2）存储空间管理机制

为了确认当需要保存一个数据块时应该放在硬盘的哪个位置，需要引入管理机制来高效地管理磁盘的空闲空间。

1. 空闲表法

空闲表法就是为所有空闲空间建立一张表，表内容包括空闲区的第一个块号和该空闲区的块个数，这个方式是连续分配的。

• 分配空间：系统依次扫描空闲表里的内容，直到找到一个合适的空闲区域为止。
• 回收空间：顺序扫描空闲表，寻找一个空闲表条目并将释放空间的第一个物理块号及它占用的块数填到这个条目中。

2. 空闲链表法

使用链表的方式来管理空闲空间，每一个空闲块里有一个指针指向下一个空闲块，这样也能很方便的找到空闲块并管理起来。操作系统保存着链头、链尾指针。

空闲链表法可以分为空闲盘块链和空闲盘区链。其中空闲盘块链以盘块为单位组成一条空闲链，以盘区为单位组成一条空闲链。

空闲盘块链：

• 分配空间：从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。
• 回收空间：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

空闲盘区链：

• 分配空间：从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。
• 回收空间：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

3. 位示图法

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

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

6. 文件共享

文件共享：操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件。

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

在 Linux 中可以通过硬链接（Hard Link） 和软链接（Symbolic Link） 的方式来实现文件共享，它们都是比较特殊的文件，但是实现方式也是不相同的。

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

硬链接是指多个目录项中的索引节点指向同一个文件，即指向同一个 inode。然而，由于每个文件系统都有各自的 inode 数据结构和列表，inode 是无法跨越文件系统的，因此硬链接不可用于跨文件系统。由于多个目录项都指向同一个 inode，只有当删除了文件的所有硬链接及源文件时，系统才会彻底删除该文件。

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

软链接则相当于重新创建一个文件，该文件有独立的 inode，但其内容是另一个文件的路径。因此，访问软链接时，实际上是访问到另一个文件。软链接可以跨文件系统，甚至在目标文件被删除后，链接文件仍然存在，只是指向的文件无法找到而已。

7. 文件保护

（1）口令保护

为文件设置一个口令（如：123456），用户请求访问该文件时必须提供口令。

口令一般存放在文件对应的 FCB 或索引结点中。用户访问文件前需要先输入口令，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件。

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

（2）加密保护

使用某个密码对文件进行加密，在访问文件时需要提供正确的密码才能对文件进行正确的解密。

举例：
一个最简单的加密算法：异或加密。假设用于加密和解密的密码为 “01001”。

• 优点：保密性强，不需要在系统中存储密码。
• 缺点：编码和译码（加密和解密）要花费一定时间。

（3）访问控制

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

有的计算机可能会有很多个用户，因此访问控制列表可能会很大，可以用精简的访问列表解决这个问题。
精简的访问列表：以组为单位，标记各组用户可以对文件执行哪些操作。

二、磁盘组织与管理

1. 磁盘的结构

要想读懂磁盘调度算法，首先要了解磁盘（机械硬盘）的结构。

硬盘由多个**盘片（platter）**组成。盘片的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。

**磁道（track）**是磁盘表面上的一个圆形轨迹，通常呈同心圆环状排列‌。

一个磁道又被划分成一个个扇区（sector），每个扇区就是一个“磁盘块”。各个扇区存放的数据量相同（如1KB）

最内侧磁道上的扇区面积最小，因此数据密度最大。

一个盘片可能会有两个盘面。

每个盘面对应一个磁头（head），所有的磁头都是连在同一个磁臂上的，因此所有磁头只能共进退。

所有盘面中相对位置相同的磁道组成柱面（cylinder）。

读写数据时，需要把磁头移动到想要读/写的扇区所在的磁道。磁盘会转起来，让目标扇区从磁头下面划过，才能完成对扇区的读/写操作。

可用（柱面号，盘面号，扇区号）来定位任意一个磁盘块。

可根据该地址读取一个块

1. 根据“柱面号”移动磁臂，让磁头指向指定柱面；
2. 激活指定盘面对应的磁头；
3. 磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读/写

磁盘的分类：

1. 磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道。
   

2. 磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头。
   

2. 磁盘调度算法

（1）一次磁盘读写操作需要的时间

1. 寻找时间（寻道时间）T_S ：在读写数据前，将磁头移动到指定磁道所花的时间。

   • 启动磁头臂需要的时间。假设耗时为 s；
   • 移动磁头需要的时间。假设磁头匀速移动，每跨越一个磁道耗时为 m，总共需要跨越 n 条磁道。则：寻道时间 $T_S=s+m\ast n$

2. 延迟时间T_R ：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为 r （单位：转/秒，或 转/分），则平均所需的延迟时间$T_R=\frac{1}{2}\times \frac{1}{r}=\frac{1}{2r}$

3. 传输时间T_t：从磁盘读出或向磁盘写入数据所经历的时间.假设磁盘转速为 r，此次读/写的字节数为 b，每个磁道上的字节数为 N。则：传输时间 $T_t=\frac{1}{r}\times \frac{b}{N}=\frac{b}{rN}$

总的平均存取时间 $T_a=T_S+\frac{1}{2r}+\frac{b}{rN}$

（2）磁盘调度算法

1. 先来先服务算法（First-Come，First-Served，FCFS）：根据进程请求访问磁盘的先后顺序进行调度。
   优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去
   缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。
   举例：假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。
   
   磁头总共移动了 45+3+19+21+72+70+10+112+146 = 498 个磁道。响应一个请求平均需要移动 498 / 9 = 55.3 个磁道（平均寻找长度）。
2. 最短寻道时间优先算法（Shortest Seek First，SSF）：优先处理与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。
   优点：性能较好，平均寻道时间短。
   缺点：可能产生“饥饿”现象。
   举例：假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。
   
   磁头总共移动了 (100-18) + (184-18) = 248 个磁道。响应一个请求平均需要移动 248 / 9 = 27.5 个磁道（平均寻找长度）。
3. 扫描算法（Scan）：又称电梯算法。磁头在一个方向上移动，访问所有未完成的请求，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。
   优点：性能较好，平均寻道时间较短，不会产生饥饿现象。
   缺点：只有到达最边上的磁道时才能改变磁头移动方向；对于各个位置磁道的响应频率不平均。
   举例：假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。
   
   磁头总共移动了 (200-100) + (200-18) = 282 个磁道。响应一个请求平均需要移动 282/9 = 31.3 个磁道（平均寻找长度）。
4. 循环扫描算法（Circular Scan, CSCAN）：在扫描算法（Scan）基础上做出改进，只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求，也就是复位磁头。
   优点：比起SCAN 来，对于各个位置磁道的响应频率很平均。
   缺点：只有到达最边上的磁道时才能改变磁头移动方向。
   举例：假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。
   
   磁头总共移动了 (200-100) + (200-0) + (90-0)= 390 个磁道。响应一个请求平均需要移动 390/9 = 43.3 个磁道（平均寻找长度）。
5. LOOK算法：在扫描算法（Scan）基础上做出改进，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。
   优点：比起 SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进
   一步缩短。
   举例：假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。
   
   磁头总共移动了 (184-100) + (184-18) = 250 个磁道。响应一个请求平均需要移动 250/9 = 27.5 个磁道（平均寻找长度）。
6. C-LOOK 算法：综合循环扫描算法（Circular Scan, CSCAN）与LOOK算法，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。
   优点：比起 C-SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间
   进一步缩短
   举例：假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。
   磁头总共移动了 (184-100) + (184-18) + (90-18)= 322 个磁道。响应一个请求平均需要移动 322/9 = 35.8 个磁道（平均寻找长度）。