408操作系统知识点——第五章 IO管理

注：内容参考王道2024考研复习指导

I/O管理概述

I/O设备的基本概念

“I/O”就是“输入/输出”（Input/Output）。

I/O设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。

I/O设备的分类

按使用特性分类

1. 人机交互类外部设备，数据传输速度慢
2. 存储设备数据，传输速度快
3. 网络通信设备数据传输，速度介于上述二者之间

按传输速率分类

1. 低速设备
2. 中速设备
3. 高速设备

按信息交换的单位分类

1. 块设备，传输速率较高，可寻址，即对它可随机地读/写任一块
2. 字符设备，传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式

按设备的共享属性分类

1. 独占设备。同一时刻只能由一个进程占用的设备。一旦将这类设备分配给某进程，便由该进程独占，直至用完释放。低速设备一般是独占设备，如打印机。
2. 共享设备，同一时间段内允许多个进程同时访问的设备。对于共享设备，可同时分配给多个进程，通过分时的方式共享使用。典型的共享设备是磁盘。
3. 虚拟设备，通过SPOOLing技术将独占设备改造为共享设备，将一个物理设备变为多个逻辑设备，从而可将设备同时分配给多个进程。

I/O控制器

机械部件

I/O设备的机械部件主要用来执行具体I/O操作。

如我们看得见摸得着的鼠标/键盘的按钮；显示器的LED屏；移动硬盘的磁臂、磁盘盘面。

I/O设备的电子部件通常是一块插入主板扩充槽的印刷电路板。

电子部件

CPU无法直接控制I/O设备的机械部件，因此I/O设备还要有一个电子部件作为CPU和I/O设备机械部件之间的“中介”，用于实现CPU对设备的控制。

这个电子部件就是I/O控制器，又称设备控制器（I/O接口）。CPU可控制I/O控制器，又由I/O控制器来控制设备的机械部件。

功能如下：

1. 接受和识别CPU发出的命令

如CPU发来的read/write命令，I/O控制器中会有相应的控制寄存器来存放命令和参数。

2. 向CPU报告设备的状态

I/O控制器中会有相应的状态寄存器，用于记录I/O设备的当前状态。如：1表示空闲，0表示忙碌

3. 数据交换

I/O控制器中会设置相应的数据寄存器。输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备。

输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据。

4. 地址识别

类似于内存的地址，为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的“地址”。I/O控制器通过CPU提供的“地
址”来判断CPU要读/写的是哪个寄存器。

I/O控制器的组成

1. 设备控制器与CPU的接口

用于实现CPU与设备控制器之间的通信。该接口有三类信号线：数据线、地址线和控制线。

数据线传送的是读/写数据、控制信息和状态信息；地址线传送的是要访问I/O接口中的寄存器编号；控制线传送的是读/写等控制信号。

2. 设备控制器与设备的接口。

一个设备控制器可以连接一个或多个设备，因此控制器中有一个或多个设备接口。每个接口都可传输数据、控制和状态三种类型的信号。

3. I/O逻辑

用于实现对设备的控制。它通过一组控制线与CPU交互，对从CPU收到的I/O命令进行译码。

CPU启动设备时，将启动命令发送给控制器，同时通过地址线将地址发送给控制器，由控制器的I/O逻辑对地址进行译码，并对所选设备进行控制。

注2：数据寄存器、控制寄存器、状态寄存器可能有多个（如：每个控制/状态寄存器对应一个具体的设备），且这些寄存器都要有相应的地址，才能方便CPU操作。

I/O编址

内存映射I/O：控制器中的寄存器与内存地址统一编址。

优点：简化了指令。可以采用对内存进行操作的指令来对控制器进行操作。

寄存器独立编制：控制器中的寄存器使用单独的地址

缺点：需要设置专门的指令来实现对控制器的操作，不仅要指明寄存器的地址，还要指明控制器的编号。

I/O控制方式

程序直接控制方式

1. CPU干预的频率

很频繁，I/O操作开始之前、完成之后需要CPU介入，并且在等待I/O完成的过程中CPU需要不断地轮询检查。

2. 数据传送的单位

每次读/写一个字。

4. 数据的流向

读操作（数据输入）：I/O设备->CPU（中的寄存器）->内存；写操作（数据输出）：内存->CPU->I/O设备

每个字的读/写都需要CPU的帮助。

5.主要缺点和主要优点

优点：实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可（因此才称为“程序直接控制方式”）。

缺点：CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于“忙等”状态，CPU利用率低。

具体的读/写流程如下：

中断驱动方式

引入中断机制。

由于I/O设备速度很慢，因此在CPU发出读/写命令后，可将等待I/O的进程阻塞，先切换到别的进程执行。当I/O完成后，控制器会向CPU发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。

处理中断的过程中，CPU从I/O控制器读一个字的数据传送到CPU寄存器，再写入主存。接着，CPU恢复等待I/O的进程（或其他进程）的运行环境，然后继续执行。

注1： CPU会在每个指令周期的末尾检查中断；

注2：中断处理过程中需要保存、恢复进程的运行环境，这个过程是需要一定时间开销的。可见，如果中断发生的频率太高，也会降低系统性能。

1. CPU干预的频率

每次I/O操作开始之前、完成之后需要CPU介入。等待I/O完成的过程中CPU可以切换到别的进程执行。

3. 数据传送的单位

每次读/写一个字。

4. 数据的流向

读操作（数据输入）：I/O设备->CPU->内存；写操作（数据输出）：内存->CPU->I/O设备

5. 主要缺点和主要优点

优点：与“程序直接控制方式”相比，在“中断驱动方式”中，I/O控制器会通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。CPU和I/O设备可并行工作，CPU利用率得到明显提升。

缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。

DMA方式

DMA方式（Direct Memory Access，直接存储器存取。主要用于块设备的I/O控制）有这样几个改进：

1. 数据的传送单位是“块”。不再是一个字、一个字的传送。
2. 数据的流向是从设备直接放入内存，或者从内存直接到设备。
3. 仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。

DMA控制器结构

DR（Data Register，数据寄存器）：暂存从设备到内存，或从内存到设备的数据。

MAR（Memory Address Register，内存地址寄存器）：在输入时，MAR表示数据应放到内存中的什么位置；输出时MAR表示要输出的数据放在内存中的什么位置。

DC（Data Counter，数据计数器）：表示剩余要读/写的字节数。

CR（Command Register，命令/状态寄存器）：用于存放CPU发来的I/O命令，或设备的状态信息。

具体读/写流程如下：

1. CPU干预的频率

仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。

2. 数据传送的单位

每次读/写一个或多个块（注意：每次读写的只能是连续的多个块，且这些块读入内存后在内存中也必须是连续的）。

3. 数据的流向（不再需要经过CPU）

读操作（数据输入）：I/O设备->内存；写操作（数据输出）：内存->/O设备

4. 主要缺点和主要优点

优点：数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。

缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成。

通道控制方式

通道：一种硬件。通道可以识别并执行一系列通道指令。

1. CPU干预的频率

极低，通道会根据CPU的指示执行相应的通道程序，只有完成一组数据块的读/写后才需要发出中断信号，请求CPU干预。

2. 数据传送的单位

每次读/写一组数据块。

3. 数据的流向（在通道的控制下进行）

读操作（数据输入）：I/O设备->内存；写操作（数据输出）：内存->I/O设备

4. 主要缺点和主要优点

缺点：实现复杂，需要专门的通道硬件支持。

优点：CPU、通道、I/O设备可并行工作，资源利用率很高。

具体流程如下：

总结

I/O软件层次结构

注：直接涉及到硬件具体细节、且与中断无关的操作肯定是在设备驱动程序层（硬件、无中断）完成的；没有涉及硬件的、对各种设备都需要进行的管理工作都是在设备独立性软件层（无硬件、管理）完成的。

用户层软件

用户层软件实现了与用户交互的接口，用户可直接使用该层提供的、与I/O操作相关的库函数对设备进行操作。

用户层软件将用户的请求翻译成格式化的I/O请求，并通过“系统调用”请求操作系统内核的服务。

设备独立性软件

设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现。

为实现设备独立性而引入了逻辑设备和物理设备这两个概念。在应用程序中，使用逻辑设备名来请求使用某类设备：而在系统实际执行时，必须将逻辑设备名映射成物理设备名。

主要实现如下功能：

1. 执行所有设备的公有操作，包括：对设备的分配与回收；将逻辑设备名映射为物理设备名：对设备进行保护，禁止用户直接访问设备；缓冲管理；差错控制；提供独立于设备的大小统一的逻辑块，屏蔽设备之间信息交换单位大小和传输速率的差异。
2. 向用户层（或文件层）提供统一接口。无论何种设备，它们向用户所提供的接口应是相同的。例如，对各种设备的读/写操作，在应用程序中都统一使用read/write命令等。

设备独立性软件需要通过“逻辑设备表（LUT，Logical Unit Table）”来确定逻辑设备对应的物理设备，并找到该设备对应的设备驱动程序。

操作系统系统可以采用两种方式管理逻辑设备表（LUT）：

1. 整个系统只设置一张LUT，这就意味着所有用户不能使用相同的逻辑设备名，因此这种方式只适用于单用户操作系统。
2. 为每个用户设置一张LUT，各个用户使用的逻辑设备名可以重复，适用于多用户操作系统。系统会在用户登录时为其建立一个用户管理进程，而LUT就存放在用户管理进程的PCB中。

设备驱动程序

I/O设备被当做一种特殊的文件。

不同类型的I/O设备需要有不同的驱动程序处理（不同的I/O设备有不同的硬件特性），每类设备配置一个设备驱动程序。

注：驱动程序一般会以一个独立进程的方式存在。

设备驱动程序需要向设备寄存器中写入命令，以控制设备操作和数据的传输方式。

中断处理程序

当I/O任务完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。

中断处理程序的处理流程如下：

应用程序I/O接口

I/O应用程序接口

字符设备接口

get/put系统调用：向字符设备读/写一个字符。

块设备接口

read/write系统调用：向块设备的读写指针位置读/写多个字符；

seek系统调用：修改读写指针位置。

网络设备接口

又称“网络套接字(socket）接口。

socket系统调用：创建一个网络套接字，需指明网络协议(TCP?UDP?）；

bind：将套接字绑定到某个本地“端口；

connect：将套接字连接到远程地址；

read/write：从套接字读/写数据。

阻塞I/O与非阻塞I/O

阻塞I/O：应用程序发出I/O系统调用，进程需转为阻塞态等待。

eg：字符设备接口——从键盘读一个字符get

非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待。

eg：块设备接口——往磁盘写数据write

设备驱动程序接口

设备驱动程序是I/O系统的上层与设备控制器之间的通信程序，其主要任务是接收上层应用发来的抽象I/O请求，如read或write命令，将它们转换为具体要求后发送给设备控制器，进而使其启动设备去执行任务：反之，它也将设备控制器发来的信号传送给上层应用。

设备驱动程序的功能：

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

设备驱动程序的特点：

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

操作系统规定好设备驱动程序的接口标准，各厂商必须按要求开发设备驱动程序。不同的操作系统，对设备驱动程序接口的标准各不相同。设备厂商必须根据操作系统的接口要求，开发相应的设备驱动程序，设备才能被使用。

设备独立性软件

I/O核心子系统

需要重点理解和掌握的功能是：I/O调度、设备保护、假脱机技术/（SPOOLing技术）、设备分配与回收、缓冲区管理（即缓冲与高速缓存）。

SPOOLing技术

假脱机技术需要请求“磁盘设备”的设备独立性软件的服务（软件的方式模拟脱机技术），因此一般来说假脱机技术是在用户层软件实现的。

同时，要实现SPOOLing技术，必须要有多道程序技术的支持。

SPOOLing技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。

SPOOLing系统的组成如下：

1. 在磁盘上开辟出两个存储区域”输入井“和”输出井“。

输入井，模拟脱机输入时的磁带，用于收容I/O设备输入的数据。

输出井，模拟脱机输出时的磁带，用于收容用户进程输出的数据。

2. 输入进程和输入缓冲区

输入进程，模拟脱机输入时的外围控制机。在输入进程的控制下，“输入缓冲区”用于暂存从输入设备输入的数据，之后再转存到输入井中。

3. 输出进程和输出缓冲区

输出进程，模拟脱机输出时的外围控制机。在输出进程的控制下，“输出缓冲区”用于暂存从输出井送来的数据，之后再传送到输出设备上。

注：输入缓冲区和输出缓冲区是在内存中的缓冲区。

共享打印机原理分析

独占式设备，只允许各个进程串行使用的设备。一段时间内只能满足一个进程的请求。

共享设备，允许多个进程“同时”使用的设备（宏观上同时使用，微观上可能是交替使用）。可以同时满足多个进程的使用请求。

打印机是种“独占式设备”（即，若进程1正在使用打印机，则进程2请求使用打印机时必然阻塞等待），但是可以用SPOOLing技术改造成“共享设备”。

当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做下面几件事：

1. 在磁盘输出井中为进程申请一个空闲缓冲区（在磁盘上的），并将要打印的数据送入其中。
2. 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（说明用户待打印数据存放位置等信息），再将该表挂到假脱机文件队列上。
3. 当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务。

虽然系统中只有一个台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于分配了一个逻辑设备），使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享。

设备的分配与回收

考虑因素

设备的属性

设备的固有属性可分为三种：独占设备、共享设备、虚拟设备。

独占设备，一个时段只能分配给一个进程（如打印机）。

共享设备，可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用。

虚拟设备，采用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用（如采用SPOOLing技术实现的共享打印机）。

设备的分配算法

对于设备分配通常采用FCFS算法和最高优先级优先算法。

设备分配中的安全性

从进程运行的安全性上考虑，设备分配有两种方式：

1. 安全分配方式

为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒。（eg：考虑进程请求打印机打印输出的例子）。

一个时段内每个进程只能使用一个设备。

优点：破坏了“请求和保持”条件，不会死锁。

缺点：对于一个进程来说，CPU和I/O设备只能串行工作。

2. 不安全分配方式

进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。

一个进程可以同时使用多个设备。

优点：进程的计算任务和I/O任务可以并行处理，使进程迅速推进。

缺点：有可能发生死锁（需要涉及死锁避免、死锁的检测和解除）。

静态分配和动态分配

静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源。破坏了“请求和保持”条件，不会发生死锁。

动态分配：进程运行过程中动态申请设备资源。

分配管理中的数据结构

一个通道可控制多个设备控制器，每个设备控制器可控制多个设备。

在设备分配管理中有如下数据结构：

1. 设备控制表（DCT），系统为每个设备配置一张DCT，用于记录设备情况。

2. 控制器控制表（COCT），每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理。

3. 通道控制表（CHCT），每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理。

4. 系统设备表（SDT）：记录了系统中全部设备的情况，每个设备对应一个表目。

分配步骤

1. 分配设备。根据进程请求的物理设备名查找SDT（注：物理设备名是进程请求分配设备时提供的参数）。根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程。
2. 分配控制器。根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
3. 分配通道。根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。

注1：只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送。

注2：可以建立逻辑设备名与物理设备名的映射机制（即，逻辑设备表），用户编程时只需提供逻辑设备名。

高速缓存与缓冲区

磁盘高速缓存

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

例如，正在运行进程的数据既存储在磁盘上，又存储在物理内存上，也被复制到CPU的二级和一级高速缓存中。不过，磁盘高速缓存技术不同于通常意义下的介于CPU与内存之间的小容量高速存储器，而是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。因此，磁盘高速缓存逻辑上属于磁盘，物理上则是驻留在内存中的盘块。

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

缓冲区

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。

使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如快表）。

一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区。

缓冲区的主要作用是：

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

单缓冲

注：当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。

若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）。

计算：每处理一块数据平均需要多久？

采用单缓冲策略，处理一块数据平均耗时Max(C, T)+M

双缓冲

采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区。

计算：每处理一块数据平均需要多久？假设初始状态为：工作区空，其中一个缓冲区满，另一个缓冲区空。

采用双缓冲策略，处理一个数据块的平均耗时为Max (T, C+M)

循环缓冲

将多个大小相等的缓冲区链接成一个循环队列。

图例中橙色表示已充满数据的缓冲区，绿色表示空缓冲区。

in指针，指向下一个可以冲入数据的空缓冲区；out指针，指向下一个可以取出数据的满缓冲区。

缓冲池

缓冲池由系统中共用的缓冲区组成。

这些缓冲区按使用状况可以分为：空缓冲队列、装满输入数据的缓冲队列（输入队列）、装满输出数据的缓冲队列（输出队列）。

根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：

1. 收容输入数据的工作缓冲区（hin，空缓冲队列队首）
2. 提取输入数据的工作缓冲区（sin，输入队列队首）
3. 收容输出数据的工作缓冲区（hout，空缓冲队列队首）
4. 提取输出数据的工作缓冲区（sout，输出队列队首）。

磁盘和固态硬盘

磁盘的结构

磁盘、磁道和扇区

磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。

磁盘的盘面被划分成一个个磁道，一个圈就是一个磁道。

一个磁道又被划分成一个个扇区，每个扇区就是一个磁盘块，各个扇区存放的数据量相同（所以每个磁道的位密度都不同）。

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

读写数据

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

可根据磁盘的物理地址读取一个“块”，步骤如下：

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

盘面、柱面

磁盘的物理地址

可用**（柱面号，盘面号，扇区号）**来定位任意一个“磁盘块”。块号就可以转换成（柱面号，盘面号，扇区号）的地址形式。

磁盘的分类

活动头磁盘，磁头可以移动。磁臂可以来回伸缩来带动磁头定位磁道。

固定头磁盘，磁头不可移动。这种磁盘中每个磁道有一个磁头。

可换盘磁盘，盘片可以更换。

固定盘磁盘，盘片不可更换。

磁盘调度算法

一次读/写磁盘需要的时间

寻找时间（寻道时间）$T_s$，在读/写数据前，将磁头移动到指定磁道所花的时间。

• 启动磁头臂，耗时$s$
• 移动磁头，匀速移动，跨越一个磁道耗时为$m$，跨越$n$条磁道

则有，寻道时间$T_s=s+m\ast n$。

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

传输时间$T_t$，从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为$r$，此次读/写的字节数为$b$，每个磁道上的字节数为$N$。

则有，传输时间$T_t=\frac{1}{r}\ast \frac{b}{N}=\frac{b}{rN}$。

总平均存取时间为：$T_a=T_s+\frac{1}{2r}+\frac{b}{rN}$。

延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间，但是操作系统的磁盘调度算法会直接影响寻道时间。

先来先服务算法（FCFS）

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

优点：公平，如果请求访问的磁道比较集中，算法性能较好。

缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。

最短寻找时间优先（SSTF）

SSTF算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。

优点：性能较好，平均寻道时间短。

缺点：可能产生“饥饿”现象。原因是磁头可能会在一个小区域内来回来去地移动。

扫描算法（SCAN）

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

SSTF算法会产生饥饿的原因在于磁头可能在一个小区域内来回移动，为了防止这个问题，规定：只有磁头移动到最外侧磁道的时候才能往内有移动，移动到最内侧磁道的时候才能往外移动。

这就是扫描算法（SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。

优点：性能较好，平均寻道时间较短，不会产生饥饿现象。

缺点：

• 只有到达最边上的磁道时才能改变磁头移动方向，可能会产生多余的移动。
• SCAN算法对于各个位置磁道的响应频率不平均。

LOOK调度算法

扫描算法（SCAN）中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。

LOOK调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。

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

循环扫描算法（C-SCAN）

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

SCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。

规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

优点：比起SCAN来，对于各个位置磁道的响应频率很平均。

缺点：只有到达最边上的磁道时才能改变磁头移动方向，并且，磁头返回时也不一定要返回到最边缘的磁道。

另外，比起SCAN算法来，平均寻道时间更长。

C-LOOK调度算法

C-SCAN算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。

C-LOOK算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

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

减少延迟时间的方法

交替编号

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

原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区。

错位命名

让相邻盘面的扇区编号错位。

由于采用错位命名法，因此读取完磁盘块（000, 00, 111）之后，还有一段时间处理，当（000, 01, 000）第一次划过1号盘面的磁头下方时，就可以直接读取数据。从而减少了延迟时间。

原理与交替编号相同。

磁盘地址结构的设计

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

若物理地址结构是（盘面号，柱面号，扇区号），且需要连续读取物理地址（00, 000, 000）~（00, 001, 111）的扇区：

• （00, 000, 000）~（00, 000, 111 ）转两圈可读完
• 之后再读取物理地址相邻的区域，即（00, 001, 000）~（00, 001, 111 ），需要启动磁头臂，将磁头移动到下一个磁道

若物理地址结构是（柱面号，盘面号，扇区号），且需要连续读取物理地址（000, 00, 000）~（000, 01, 111）的扇区：

• （000, 00, 000）~（000, 00, 111 ）由盘面0的磁头读入数据
• 之后再读取物理地址相邻的区域，即（000, 01, 000）~（000, 01, 111 ），由于柱面号/磁道号相同，只是盘面号不同，因此不需要移动磁头臂。只需要激活相邻盘面的磁头即可

磁盘的管理

磁盘初始化

一个新的磁盘只是一个磁性记录材料的空白盘。在磁盘可以存储数据之前，必须将它分成扇区，以便磁盘控制器能够进行读/写操作，这个过程称为低级格式化（或称物理格式化）。

每个扇区通常由头部、数据区域（256或512字节大小）和尾部组成。头部和尾部包含了一些磁盘控制器的使用信息，其中利用磁道号、磁头号和扇区号来标志一个扇区，利用CRC字段对扇区进行校验。

分区

在可以使用磁盘存储文件之前，还要完成两个步骤。

第一步是，将磁盘分区（我们熟悉的C盘、D盘等形式的分区），每个分区由一个或多个柱面组成，每个分区的起始扇区和大小都记录在磁盘主引导记录的分区表中。

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

因扇区的单位太小，为了提高效率，操作系统将多个相邻的扇区组合在一起，形成一簇（在Linux中称为块）。为了更高效地管理磁盘，一簇只能存放一个文件的内容，文件所占用的空间只能是簇的整数倍；如果文件大小小于一簇（甚至是0字节），也要占用一簇的空间。

引导块

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

自举程序通常存放在ROM中，为了避免改变自举代码而需要改变ROM硬件的问题，通常只在ROM中保留很小的自举装入程序，而将完整功能的引导程序保存在磁盘的启动块上，启动块位于磁盘的固定位置。

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

引导ROM中的代码指示磁盘控制器将引导块读入内存，然后开始执行，它可以从非固定的磁盘位置加载整个操作系统，并且开始运行操作系统。

以Windows为例来分析引导过程：

1. Windows允许将磁盘分为多个分区，有一个分区为引导分区，它包含操作系统和设备驱动程序。
2. Windows系统将引导代码存储在磁盘的第0号扇区，它称为主引导记录（MBR）。
3. 引导首先运行ROM中的代码，这个代码指示系统从MBR中读取引导代码。
4. 除了包含引导代码，MBR还包含一个磁盘分区表和一个标志（以指示从哪个分区引导系统）。
5. 当系统找到引导分区时，读取分区的第一个扇区，称为引导扇区，并继续余下的引导过程，包括加载各种系统服务。

坏块

坏了、无法正常使用的扇区就是“坏块”。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它。

对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在FAT表上标明。（在这种方式中，坏块对操作系统不透明）

对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。

固态硬盘SSD

注：与计组第三章 存储系统中的内容相同。