基于王道计算机考研 操作系统。

笔记目录

第一章-计算机系统概述
第二章-进程与线程
第三章-内存管理
第四章-文件系统
第五章-输入/输出管理

第五章 输入/输出（I/O）管理

5.1 I/O管理概述

5.1.1 I/O设备

设备的分类

I/O设备从不同角度可分为不同的类型。

按信息交换的单位分类：

1. 块设备。信息交换以块为单位，如磁盘、磁带等。磁盘设备的基本特征是传输速率较高、可寻址，即对它可随机地读/写任意一块。
2. 字符设备。信息交换以字符为单位，如交互式终端机、打印机等。基本特征是传输速率低，不可寻址，并且时常采用中断I/O方式。

按设备的传输速率分类：

1. 低速设备。每秒几字节到几百字节，比如鼠标、键盘。
2. 中速设备。每秒几千字节到几万字节，比如激光打印机。
3. 高速设备。每秒数百千字节到千兆字节，比如磁盘机，光盘及。

按使用特性分类：

1. 存储设备。
2. 输入/输出设备。又可分为输入设备、输出设备、交互式设备。

按共享属性分类：

1. 独占设备。低速设备一般是独占设备，比如打印机。
2. 共享设备。同一时间段内允许多个进程同时访问的设备。
3. 虚拟设备。通过SPOOLing技术将独占设备改造成共享设备。

I/O接口

I/O接口（设备控制器）是CPU与设备之间的接口，实现设备和计算机的数据交换，它接受发自CPU的命令，控制设备工作，主要由三部分组成：

1. 设备控制器与CPU的接口。有三类信号线：数据线、地址线和控制线。
2. 设备控制器和设备的接口。一个设备控制器可以链接一个或多个设备，控制器中有多个设备接口。每个设备都可以传输数据、控制和状态三种信号。
3. I/O逻辑。实现对设备的控制。

设备控制器的主要功能：

1. 接受和识别命令；
2. 数据交换；
3. 标识和报告设备的状态；
4. 地址识别；
5. 数据缓冲；
6. 差错控制。

I/O接口的类型

1. 按数据传送方式，分为并行接口和串行接口，接口要完成数据格式的转换。
2. 按主机访问I/O设备的控制方式，分为程序查询接口、中断接口和DMA接口。
3. 按功能选择的灵活性分为可编程家口和不可编程接口。

I/O端口

指的是设备控制器可被CPU直接访问的寄存器。

• 数据寄存器；
• 状态寄存器；
• 控制寄存器。

I/O端口想要被访问，就要对端口进行编址，每个端口对应一个端口地址，有统一编址和独立编址。

• 独立编址

为每个端口分配一个I/O端口号，I/O端口地址空间和主存空间是独立的，只有操作系统使用特殊的I/O指令才能访问端口。

优点：I/O端口比主存单元少得多，只需要少量地址线，使得I/O端口译码简单，寻址速度更快，使用专用I/O指令，程序更好理解。

缺点：I/O指令少，只提供简单的传输操作，程序设计的灵活性较差；还需要提供两组独立的存储器和设备读写控制信号，增加了控制的复杂性。

• 统一编址

又称为内存映射I/O，将主存地址分出一部分给I/O编址，根据地址范围分辨是I/O端口还是主存单元。

优点：不需要专门的I/O指令，提高了灵活性，还扩大了编址空间；I/O访问的保护机制可以由虚拟存储管理系统实现，无需专门设置。

缺点：占用了部分主存地址空间，全部地址线都要参加译码，增加了复杂度，降低了寻址速度。

5.1.2 I/O控制方式（详见计算机组成原理）

通道控制方式（大纲删除）

5.1.3 I/O软件层次结构

目前普遍采用层次结构的I/O软件，只要层次间的接口不变，对某一层次的修改不会影响其它层的代码，只有最底层才涉及硬件的具体特性。可以视为具有4个层次的系统结构，各层次及其功能如下：

• 用户层软件

实现用户交互的接口，用户可以直接调用这一层的库函数，对设备进行操作，大部分I/O软件都在内核层，但仍有一部分在用户层，包括与用户程序链接在一起的库函数。用户层I/O软件必须通过一组系统调用来获取操作系统服务。

• 设备独立性软件

用于实现用户程序与设备驱动器的统一接口、设备命名、设备保护以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间。

设备独立性又称设备无关性，指应用程序所用的设备不限于某个具体的物理设备。为实现设备独立性，引入了逻辑设备和物理设备两个概念。在应用程序中，使用逻辑设备名来请求使用某设备；在系统实际执行时，必须将逻辑设备映射成物理设备名。

可以用逻辑设备表(LUT)管理逻辑设备名-物理设备名-驱动程序入口地址的关系，整个系统设置一张（不可重名）或每个用户设置一张（存在用户管理系统的PCB）。

使用逻辑设备名的好处是：

1. 增加设备分配的灵活性；
2. 易于实现I/O重定向，用于I/O操作的设备可以更换，而不必改变应用程序。

为了实现设备独立性，必须实现再在驱动程序上设置一层设备独立性软件。

设备独立性的主要功能：

1. 执行所有设备的公有操作，比如：对设备的分配与回收；对设备进行保护，禁止用户直接访问设备；缓冲管理；差错控制；提供独立于设备的大小统一的逻辑块，屏蔽设备之间信息交换单位大小和传输速率的差异…
2. 向用户层或文件层提供统一接口，无论什么设备，向用户提供的接口应该是相同的。

• 设备驱动程序

与硬件直接相关，负责具体实现系统对设备发出的操作命令，驱动I/O设备工作的驱动程序。

每类设备配备一个设备驱动程序，是I/O进程和设备控制器之间的通信程序，通常以进程的方式存在。设备驱动程序向上层用户程序提供一组标准接口，设备具体的差别被设备驱动程序封装。

• 中断处理程序

用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断的现场后，返回到被中断进程。

5.1.4 应用程序I/O接口

I/O接口的分类

• 字符设备接口

字符设备指的是数据存取与传输以字符为单位的设备，比如键盘、打印机。基本特征是传输速率较低、不可寻址，输入输出通常采用中断驱动方式。

get和put操作。由于不可寻址，只能采用顺序存取方式，建立一个字符缓冲区，用户程序通过get操作从缓冲区获取字符，通过put操作将字符输出到缓冲区。

in-control指令。字符设备类型较多，在接口中提供通用的in-control指令来处理他们。

字符设备都属于独占设备，接口中还要提供打开和关闭操作，实现互斥共享。

• 块设备接口

块设备指的是数据存取与传输以数据块为单位的设备，比如磁盘。基本特征是传输速率较高、可寻址。磁盘的I/O常采用DMA方式。

隐藏了磁盘的二维结构。每个扇区的地址需要用磁道号和扇区号来表示，块设备接口直接将扇区从0到n-1直接编号，变为线性序列。

将抽象命令映射为底层操作。块设备接口支持上层发来的对文件或设备的开、关、读写等抽象命令，该接口将上层命令映射成设备能识别的较低层的具体操作。

内存映射接口通过内存的字节数组来访问磁盘，不提供读写操作。映射文件到内存的系统调用包含文件副本的一个虚拟内存地址。只在需要访问内存映像时才调页。

• 网络设备接口

使计算机能够通过网络与其他计算机通信。

许多操作系统提供的网络I/O接口为网络套接字接口，套接字接口的系统调用使应用程序创建的本地套接字连接到远程应用程序创建的套接字，通过此连接发送和接收数据。

阻塞I/O和非阻塞I/O

阻塞I/O指的是进程调用到I/O操作时就阻塞，完成后唤醒回到就绪队列。大多数操作系统提供的I/O接口都是采用阻塞I/O。

优点：操作简单，实现难度低，适合并发量小的应用开发。

缺点：I/O执行阶段进程会一直阻塞。

非阻塞I/O指的是当进程调用到I/O操作时不阻塞，但是进程需要不断轮询I/O操作是否完成。

优点：进程在等待期间不会阻塞，可以做别的事，适合并发量大的应用开发。

缺点：轮询会占用CPU时间。

5.2 设备独立性软件

5.2.1 设备独立性软件

也称为与设备无关的软件，是I/O系统最高层软件。它的下层是设备驱动程序，界限因操作系统和设备的不同会有所差异。总体而言，设备独立性软件包括执行所有设备共有操作的软件。

5.2.2 高速缓存与缓冲区

磁盘高速缓存（Disk Cache）

操作系统使用磁盘高速缓存来提高磁盘I/O速度，对访问高速缓存要比访问原始磁盘数据更为高效。

磁盘高速缓存不同于通常意义下的介于CPU与内存之间的小容量Cache，而是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块的信息。

磁盘高速缓存逻辑上属于磁盘，物理上是驻留在内存中的盘块。

磁盘高速缓存在内存中分为两种形式：一种是在内存中开辟一个单独的空间作为缓存区，大小固定；另一种是将未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘I/O时共享。

缓冲区（buffer）

引入缓冲区的目的如下：

1. 缓和CPU和I/O设备间速度不匹配的矛盾。
2. 减少对CPU的中断频率，放宽对CPU中断响应时间的限制。
3. 解决基本数据单元大小（数据粒度）不匹配的问题。
4. 提高CPU和I/O设备之间的并行性。

实现方法如下：

1. 采用硬件缓冲区，但是成本比较高，只用于一些关键部位。
2. 利用内存作为缓冲区。

根据系统设置的缓冲区个数，缓冲技术可分为：

• 单缓冲

每当用户进程发出一个I/O请求，就在内存中分配一个缓冲区（大小通常为一个块）。

单缓冲区的T和C是可以并行的。

T>C，CPU处理完一块数据后，必须等待缓冲区装满数据再传送到工作区，平均处理一块的时间为T+M。

T<C，缓冲区装满数据后，必须等待CPU处理完上一块数据，再传送到工作区，平均处理一块的时间为C+M。

总体的平均时间为Max(C,T)+M。

缓冲区是共享资源，使用时必须互斥。

• 双缓冲

为了加快输入输出速度，引入了双缓冲机制，也称缓冲对换。

仍然假设设备输入数据到缓冲区时间为T、数据传送到用户进程和处理的时间为M和C。

在双缓冲区中，C和M是可以和T并行的。

T>C+M时，说明输入的时间比数据传送和处理的时间多，可以连续输入，平均处理一块的时间为T。

T<C+M时，说明设备输入的时间比数据传送和处理的时间少，必须等待数据传送并处理完，平均处理一块的时间为C+M。

平均时间为Max(C+M,T)。

• 循环缓冲

双缓冲区中，如果输入与输出的速度相差甚远，效果不会太理想。引入多缓冲机制，让多个缓冲区组成循环缓冲区。（灰色表示装满的缓冲区，白色表示空缓冲区）

循环缓冲包含多个大小相等的缓冲区，每个缓冲区有一个指针指向下一个缓冲区，最后一个指向第一个。

还需要设置in和out两个指针，in指向第一个可以输入数据的空缓冲区，out指向第一个可以提取数据的满缓冲区。

• 缓冲池

缓冲池包含一个用于管理自身的数据结构和一组操作函数的管理机制，用于管理多个缓冲区，缓冲池可供多个进程共享使用。

缓冲池中的缓冲区按使用状况可以分为：

1. 空缓冲队列，由空缓冲区链接成的队列。
2. 输入队列，装满输入数据的缓冲区链接而成队列。
3. 输出队列，装满输出数据的缓冲区链接成的队列。

还有4种工作缓冲区：

1. 用于收容输入数据的工作缓冲区hin。
2. 用于提取输入数据的工作缓冲区sin。
3. 用于收容输出数据的工作缓冲区hout。
4. 用于提取输出数据的工作缓冲区sout。

缓冲池的缓冲区有4种工作方式：

1. 收容输入。输入进程需要输入数据时，从空缓冲队列摘下一个空缓冲区，作为收容输入工作缓冲区，然后输入完毕挂到输入队列尾。
2. 提取输入。计算进程需要输入数据时，从输入队列摘下一个缓冲区，作为提取输入工作缓冲区，用完挂到空缓冲队列尾。
3. 收容输出。计算进程需要输出数据时，从空缓冲队列摘下一个空缓冲区，作为收容输出工作缓冲区，输出完挂到输出队列尾。
4. 提取输出。输出进程需要输出数据时，从输出队列摘下一个缓冲区，作为提取输出工作缓冲区，然输出完毕挂到空缓冲队列尾。

高速缓存与缓冲区的对比

高速缓存是可以保存数据拷贝的高速缓存器，访问高速缓存比访问原始数据更高效，速度更快。

5.2.3 设备分配与回收

设备分配概述

设备分配指的是根据用户I/O请求分配设备，总原则是充分发挥设备的使用效率，同时避免死锁。

设备分配的数据结构

设备分配的数据结构如下：

• 设备控制表（DCT）

系统为每个设备配置一张DCT，应该有以下字段：

设备类型：设备的类型；设备标识符：物理设备名；设备状态；指向控制器表的指针；重复执行次数或时间：重复执行次数达到规定值仍然不成功，认为此次I/O失败；设备队列的队首指针：指向等待该设备进程队列的队首。

当某个进程释放设备，且无其他进程请求该设备，系统将该设备DCT中的设备状态设为空闲，即可实现设备回收。

• 控制器控制表（COCT）

每个设备控制器都对应一张COCT，操作系统根据COCT的信息对控制器操作和管理。每个控制器由一个通道控制，通过与控制器相连的通道表指针可以找到相应通道的信息。

• 通道控制表（CHCT）

每个通道都对应一张CHCT，操作系统根据CHCT的信息啊对通道进行操作和管理。一个通道可为多个控制器服务，通过与通道连接的控制器表首址可以找到该通道管理的所有控制器。

• 系统设备表（SDT）

整个系统只有一张SDT，记录已连接到系统中的所有物理设备的情况，每个物理设备对应一个表目。

设备分配时应考虑的因素

在多道程序系统中，进程数多于资源数，需要合理的分配因素。

• 设备的固有属性

可分为三种，采取不同的分配策略：

1. 独占设备：进程独占直到完成或释放设备。
2. 共享设备：同时分配给多个进程，需要合理调度先后访问次序。
3. 虚拟设备：属于共享设备，可以同时分配给多个进程使用。

• 设备分配算法

通常只用两种：

1. FCFS算法。
2. 最高优先级优先算法。优先级相同按照FCFS原则排队。

• 设备分配中的安全性

指的是设备分配中应该防止发生进程死锁。

1. 安全分配方式。进程发出I/O请求后阻塞，直到I/O操作完成后才唤醒，这样设备获得设备后便阻塞，阻塞时不保持任何资源。优点是分配安全，缺点是CPU和I/O设备是串行工作的。（破坏请求并保持条件）
2. 不安全分配方式。进程发出I/O请求后继续运行，需要时还会有第二个、第三个。仅当进程请求的设备被另一进程占用才进入阻塞态。优点是一个进程可以同时操控多个设备，缺点是可能造成死锁。（可以通过银行家算法避免）

设备分配的步骤

1. 分配设备。根据请求的物理设备名，查找SDT，从中查出设备的DCT，查询DCT中的设备状态字段。若忙，则将PCB挂到设备等待队列；若不忙，则根据一定策略将设备分配给该进程。
2. 分配控制器。设备分配后，根据DCT找到COCT，查询控制器状态。若忙，将进程PCB挂到控制器等待队列；若不忙，分配控制器给该进程。
3. 分配通道。控制器分配后，根据COCT找到CHCT，查询通道状态。若忙，则将进程PCB挂到通道等待队列；若不忙，将通道分配给该进程。
4. 只有设备、控制器和通道都分配成功，这次的设备分配才算成功，之后可以启动设备进行数据传输。

上例，进程是以物理设备名提出I/O请求的。如果指定设备已经分配给其他进程，则分配失败；或者说设备分配程序不具有设备无关性。

为了获得设备的独立性应该使用逻辑设备名。这样，系统先从SDT找出第一个该类设备的DCT，若忙则查找第二个。只有所有该类设备都忙时，才将进程挂到该类设备的等待队列上；只要有一个可用，就可以进一步分配。

逻辑设备名到物理设备名的映射

需要配置一张逻辑设备表来映射。

逻辑设备表(LUT)每个表项包含：逻辑设备名、物理设备名和设备驱动程序的入口地址。

可采取两种方式设置LUT：

1. 整个系统只设置一张。所有进程的设备分配情况都记录在一张LUT，不能重名，适合单用户系统。
2. 每个用户设置一张。可以重名，适合多用户系统。

5.2.4 SPOOLing技术（假脱机技术）

为了缓和CPU的高速性和I/O设备的低速性之间的矛盾，引入了假脱机技术，可以将独占设备改造成共享设备。

该技术利用专门的外围控制机，将低速I/O设备的数据传到高速磁盘上，或者相反。CPU需要输入时，直接从磁盘上读；CPU需要输出时，直接往磁盘上输出。

引入多道程序技术后，系统便可利用程序模拟脱机输入/输出时的外围控制机，在主机的直接控制下，实现脱机输入/输出。

• 输入井和输出井

在硬盘上开辟出的两个存储区域。输入井模拟脱机输入时的磁盘，收容设备输入数据；输出井模拟脱机输出时的磁盘，收容用户程序的输出数据。一个进程的输入（或输出）数据保存为一个文件，所有进程的输入（或输出）文件链接成一个输入（或输出）队列。

• 输入缓冲区和输出缓冲区

在内存中开辟出的两个缓冲区。输入缓冲区暂存输入设备送来的数据，以后传输到输入井；输出缓冲区暂存输出井送来的数据，以后传送到输出设备。

• 输入进程和输出进程

输入进程模拟脱机输入时的外围控制机，将数据从输入设备送到输入缓冲区，再存到输入井中，CPU需要输入时直接从输入井读；输出进程模拟脱机输出时的外围控制机，将用户要求输入的数据从内存送到输出井，等设备空闲时，将输出井的数据经输出缓冲区到输出设备。

• 井管理程序

用于控制作业与磁盘井之间信息的交换。

打印机是经典的独占设备，利用SPOOLing技术可将他改造为一台多用户共享的打印设备。多个进程发出打印机输出请求，SPOOLing系统同意请求，但不真正立即将打印机分配，而是由假脱机管理进程为每个进程做两项工作：

1. 在磁盘缓冲区为进程申请一个空闲盘块，并将要打印的数据送入暂存。
2. 为用户进程申请一张空白的用户请求表，将用户的要求填入其中，将该表挂到假脱机文件队列上。

系统只是即时将数据输出到缓冲区，用户进程感觉系统已经为它打印。实际上只有打印机空闲且等待队列排到队首才进行，以上过程用户并不可见。

当进程提出打印请求，系统都在输出井中为其分配一个缓冲区，相当于分配一台逻辑设备，实现对打印机的共享。

SPOOLing系统的特点：

1. 提高了I/O速度，将低速I/O设备的操作演变为对磁盘缓冲区中数据的存取操作。缓和了CPU和低速设备之间的速度不匹配问题。
2. 将独占设备改造为共享设备。
3. 实现了虚拟设备功能。

SPOOLing技术是以空间换时间的技术。

5.2.5 设备驱动程序接口

设备驱动程序是I/O系统的上层与设备控制器之间的通信程序，主要任务是接收上层应用发来的抽象请求，比如read和write，将他们转换为具体要求，发给设备控制器；也将设备控制器发送的信号传给上层。

设备驱动程序有以下功能：

1. 接收由上层应用发来的命令与参数，并将抽象请求转换为设备相关的具体要求。
2. 检查用户I/O请求的合法性，了解设备的工作状态，传递与设备操作有关的参数，设置设备的工作方式。
3. 发出I/O命令，若设备空闲，立即启动它；若忙，则将请求者的PCB挂到设备队列等待。
4. 及时响应设备控制器发来的中断请求，根据中断类型调用相应的中断处理程序。

相比普通的应用程序，设备驱动程序有如下差异：

1. 设备驱动程序将抽象的I/O请求转换为具体的操作之后，传送给设备控制器，并将设备控制器中记录的设备状态和I/O操作的完成情况反馈给请求进程。
2. 设备驱动程序中记录的设备状态和I/O控制方式紧密相关，常见的I/O控制方式是中断驱动方式和DMA方式。
3. 设备驱动程序与硬件密切相关，根据不同的设备配置不同的设备驱动程序。
4. 很多设备驱动程序的基本部分固化在ROM中。
5. 设备驱动程序应允许同时多次调用执行。

为了有统一的接口，要求设备驱动程序和操作系统之间有相同或相近的接口；要将抽象的设备名转换为具体的物理设备名以便找到设备驱动程序入口；还要对设备进行保护。

5.3 磁盘和固态硬盘

详见计算机组成原理。

5.3.1 磁盘

磁盘的每个扇区存储固定大小，一个扇区称为一个盘块。磁盘的存储能力受限于最内道的最大记录密度。

现代磁盘不将内外磁道分为相同数目的扇区，而是将盘面分为若干环带，同一环带内的所有磁道具有相同的扇区数，外层环带的磁道拥有更多的扇区。

磁盘安装在磁盘驱动器中，地址用柱面号-盘面号-扇区号表示。

磁头相对于盘片的径向方向固定的称为固定头磁盘，每个磁道有一个磁头。磁头可移动的称为活动头磁盘，磁头臂可以伸缩定位磁道。盘片永久固定在磁盘驱动器的称为固定盘磁盘，盘片可移动和替换的称为可换盘磁盘。

5.2.2 磁盘的管理

磁盘初始化

磁盘在存储数据之前，必须分成扇区，以便磁盘控制器进行读写，称为低级格式化或物理格式化。每个扇区通常由头部、数据区域和尾部组成，头部和尾部包含磁盘控制器的使用信息，其中利用磁道号、磁头号、扇区号标志一个扇区，利用CRC字段对扇区进行校验。

分区

还需要将磁盘分区，每个分区由一个或多个柱面组成，每个分区的起始扇区和大小都记录在磁盘主引导记录的分区表中。

然后对物理分区进行逻辑格式化（也称高级格式化），将初始文件系统数据结构存储到磁盘上，这些数据结构包括空闲空间和已分配空间，以及一个初始为空的目录，建立根目录、对保存空闲磁盘块信息的数据结构进行初始化。

为提高效率，操作系统将多个相邻的扇区组合在一起，形成一簇（Linux称为块）。一簇只能放一个文件的内容，文件的空间只能是簇的整数倍；文件如果比一簇小，也要占用一簇空间。

引导块

计算机启动需要运行初始化程序（也称自举程序），初始化CPU、寄存器、设备控制器和内存等。

自举程序通常存放在ROM中，为了防止代码被改变通常只保留很小的自举装入程序，将完整功能的引导程序保留在启动块上，启动块在磁盘的固定位置。具有启动分区的磁盘称为启动磁盘或系统磁盘。

坏块

磁盘容易出现一个或多个扇区损坏。

对于简单磁盘，如果采用IDE控制器的磁盘，可以手动处理坏块，扫描到的坏块会在FAT表上表明，程序不会使用它们。

对于复杂磁盘，控制器维护磁盘内的坏块列表，这个表在出厂低级格式化时就已初始化，且在使用过程中不断更新。低级格式化将一些块留作备用，操作系统看不到这些块，可以采用备用块逻辑上替代坏块，称为扇区备用。

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

5.3.3 磁盘调度算法

磁盘的存取时间

一次存取时间由寻到时间、旋转延迟时间和传输时间决定。

• 寻道时间$T_s$。包括跨越n道的时间和启动磁头臂的时间。m是与磁盘驱动器速度有关的常数。
  $$
  T_s=m\times n + s
  $$
• 旋转延迟时间$T_r$。定位到读写扇区需要的时间，设磁盘旋转速度为r。
  $$
  T_r=\frac{1}{2r}
  $$
• 传输时间$T_t$。取决于每次读写的字节数b和旋转速度r，N为一个磁道上的字节数。
  $$
  T_t=\frac{b}{rN}
  $$
  总平均存取时间$T_a$可表示为
  $$
  T_a=T_s+\frac{1}{2r}+\frac{b}{rN}
  $$

其中寻道时间占大头，与磁盘调度算法密切相关；延迟时间和传输时间和磁盘旋转速度线性相关，所以转速是磁盘性能的一个关键参数。

磁盘调度算法

磁盘调度的主要目标是减少磁盘的平均寻道时间。

• 先来先服务（FCFS）算法

根据进程访问磁盘的先后顺序进行调度，具有公平性，如果大部分请求都是访问簇聚的扇区则有较好的性能；如果大量进程竞争使用磁盘，性能接近随机调度。

• 最短寻道时间优先（SSTF）算法

每次选择最近的磁道，使每次寻道时间最短，不能保证平均寻道时间最小，但是性能比FCFS更好。会产生饥饿现象。

• 扫描（SCAN）算法

为了防止SSTF的饥饿，在SSTF的基础上规定磁头必须移动到一边才能向另一边移动，又称为电梯调度算法，SCAN算法对最近扫描过的区域不公平，局部性原理不如FCFS和SSTF好。

• 循环扫描（C-SCAN）算法

因为SCAN算法偏向处理接近内外磁道的访问请求，因此在SCAN算法的基础上规定磁头单向移动来提供服务，返回时直接快速移动到起始端，而不服务任何请求。

还可以继续改进SCAN和C-SCAN，即磁头只需移动到最远端的一个请求即可返回，不需要到达磁盘端点。称为LOOK调度和C-LOOK调度。

减少延迟时间的方法

由于读入一个扇区后有短暂的处理时间，可以对一个盘面进行交替编号，让逻辑上相邻的块物理上保持一定的间隔，读入多个连续块能减少延迟时间。

由于所有盘面同步转动，逻辑块在相同柱面上也是按盘面号连续存放的，因此可以对不同的盘面进行错位命名，读入相邻两个盘面的连续块也能减少延迟时间。

提高磁盘I/O速度的方法

文件的访问速度是衡量文件系统性能的最重要因素。可以从三方面优化：

1. 改进文件目录结构以及检索目录的方法，减少目录查询时间。
2. 选取好的文件存储结构，提高对文件的访问速度。
3. 提高磁盘I/O速度。

改善I/O性能的方法有：

1. 采用磁盘高速缓存。
2. 调整磁盘请求顺序。
3. 提前读。读磁盘当前块时，将下一磁盘块也读入内存缓冲区。
4. 延迟写。仅在缓冲区首部设置延迟写标志，释放此缓冲区并链入空闲缓冲区链尾，当其他进程申请到此缓冲区时，才将缓冲信息写入磁盘块。
5. 优化物理块的分布。尽可能将一个文件的盘块安排在一个磁道或相邻磁道上减少寻道时间。同时可以将盘块组成簇，按簇分配文件，也能减少磁头平均移动距离。
6. 虚拟盘。利用内存空间仿真磁盘，通常存临时文件。
7. 采用磁盘阵列RAID。可以并行交叉存取，可以大幅提高磁盘I/O速度。

5.3.4 固态硬盘

固态硬盘的特性

SSD是基于闪存技术的存储器，与U盘无本质差别，只是容量更大、存取性能更好。

一个SSD由一个或多个闪存芯片和闪存翻译层组成。闪存芯片替代磁盘驱动器，闪存翻译层将逻辑块读写请求翻译成对底层物理设备的读写控制信号，闪存翻译层扮演了磁盘控制器的角色。

一个闪存由B块组成，每块P页（通常为512B-4KB），每块32-128页，块的大小为16KB-512KB，数据以页为单位读写。只有在一页所属的块整个被擦除后，才能重写这一页。一旦一个块被擦除，块中的每页就都可以直接再写一遍。

随机写很慢，因为擦除块很慢，其次如果想写一个有数据的页P，所有有数据的页都得复制到新块中，然后才能对P写操作。

SSD有很多优点，由半导体存储器构成，没有移动的部件，随机访问比机械盘快很多，没有噪声和振动，能耗低、抗震性好、安全性高。

磨损均衡

闪存的擦写寿命是有限的，因此引入磨损均衡，分为两种：

1. 动态磨损均衡。写入数据自动选择较新的闪存块。
2. 静态磨损均衡。SSD自动检测并进行数据分配，老的闪存块无需承担写数据的任务，同时腾出较新的闪存块的空间，平常的读写操作在较新的闪存块进行。