5.1.1 $I/O$ 设备的概念与分类

一、基本概念

$I/O$ 设备即输入/输出（$Input/Output$）设备，是负责实现计算机与外部环境之间数据输入、输出交互的外部设备。

分类

1. 按使用特性分类

• 人机交互类外部设备：用于实现人与计算机的交互，数据传输速度慢。 典型设备：鼠标、键盘、打印机等。
• 存储设备：用于持久化存储数据，数据传输速度快。 典型设备：磁盘、移动硬盘、光盘等。
• 网络通信设备：用于跨主机的网络数据通信，数据传输速度介于人机交互设备与存储设备之间。 典型设备：调制解调器、路由器等。

2. 按传输速率分类

• 低速设备：传输速率为每秒几个到几百字节。 典型设备：鼠标、键盘。
• 中速设备：传输速率为每秒数千至上万个字节。 典型设备：激光打印机。
• 高速设备：传输速率为每秒数千字节至千兆字节级别。 典型设备：磁盘。

3. 按信息交换的单位分类（核心考点）

• 块设备
  • 数据传输的基本单位是“块”；
  • 传输速率高，支持寻址，可随机读写任意一块；
  • 典型设备：磁盘。
• 字符设备
  • 数据传输的基本单位是字符；
  • 传输速率慢，不可寻址，输入输出通常采用中断驱动方式；
  • 典型设备：鼠标、键盘。

5.1.2 $I/O$ 控制器

$I/O$ 设备的组成

$I/O$设备分为两大部分：

1. 机械部件：执行具体的$I/O$操作。
   例：鼠标、键盘的按钮；显示器$LED$屏；移动硬盘磁臂、磁盘盘面。
2. 电子部件：一般是插入主板扩展槽的印刷电路板，也就是**$I/O$控制器（设备控制器）**。

   $CPU$无法直接控制$I/O$设备的机械部件，$I/O$控制器作为$CPU$与设备机械部件之间的中介；$CPU$控制$I/O$控制器，再由$I/O$控制器控制设备机械部件。

$I/O$ 控制器的主要功能

1. 接受和识别$CPU$发出的命令：依靠控制寄存器，存放命令与参数，如$read、write$命令。
2. 向$CPU$报告设备的状态：依靠状态寄存器，记录设备当前状态，如 $1$ 代表空闲， $0$ 代表忙碌。
3. 数据交换：依靠数据寄存器，暂存输入/输出数据。
   • 输出：暂存$CPU$下发的数据，再传给设备。
   • 输入：暂存设备发来的数据，等待$CPU$读取。
4. 地址识别：由$I/O$逻辑实现，识别$CPU$指定的寄存器地址，判断操作目标。

$I/O$ 控制器的组成

1. $CPU$与控制器的接口：完成$CPU$和控制器之间通信。$CPU$通过控制线发命令；地址线指定操作设备；数据线读写数据。
2. $I/O$逻辑：接收、识别$CPU$命令（地址译码），向设备下发控制命令。
3. 控制器与设备的接口：完成控制器与$I/O$设备机械部件之间的通信，传输数据、状态、控制信号。

值得注意的小细节：
① 一个$I/O$控制器可能会对应多个设备；
② 数据寄存器、控制寄存器、状态寄存器可能有多个（每个控制/状态寄存器对应一个具体的设备），且这些寄存器都要有相应的地址，才能方便$CPU$操作。

$I/O$ 控制器寄存器的两种编址方式

1. 内存映射$I/O$
   • 控制器内寄存器与内存统一编址，占用一部分内存地址空间。
   • 优点：可以直接使用内存操作指令访问控制器，指令集简单。
2. 寄存器独立编址
   • 控制器寄存器使用独立的$I/O$专用地址，和内存地址空间相互独立。
   • 缺点：必须设置专门的$I/O$指令操作控制器，指令需要同时指明寄存器地址与控制器编号。

两种编址对比

5.1.3 I/O控制方式

1. 程序直接控制方式（轮询方式）

1. 一次读/写流程
   $CPU$发出$I/O$命令后需要不断轮询设备状态。
2. $CPU$干预频率
   极高，$I/O$操作前后都需要$CPU$介入；等待$I/O$完成的全过程$CPU$持续循环轮询。
3. 数据传送单位
   每次读/写 $1$ 个字。
4. 数据流向

• 读操作：$I/O$设备 $\rightarrow$ $CPU$ $\rightarrow$ 内存
• 写操作：内存 $\rightarrow$ $CPU$ $\rightarrow$ $I/O$设备
  每一个字的传输都需要$CPU$参与。

5. 优缺点

• 优点：实现简单，只需在读写指令后增加循环检查代码。
• 缺点：$CPU$与$I/O$设备只能串行工作；$CPU$持续轮询，处于忙等状态，$CPU$利用率很低。

2. 中断驱动方式

1. 一次读/写流程
   $CPU$发出$I/O$命令后可执行其他任务；$I/O$完成后，设备控制器向$CPU$发送中断信号。
   $CPU$在每条指令周期末尾检查中断；中断触发时保存进程上下文，执行中断处理程序，完成数据传输，之后恢复进程继续运行。
2. $CPU$干预频率
   高，每次一个字的$I/O$完成后都需要$CPU$介入处理中断。
3. 数据传送单位
   每次读/写 $1$ 个字。
4. 数据流向

• 读操作：$I/O$设备 $\rightarrow$ $CPU$ $\rightarrow$ 内存
• 写操作：内存 $\rightarrow$ $CPU$ $\rightarrow$ $I/O$设备

5. 优缺点

• 优点：$CPU$无需持续轮询，$CPU$与$I/O$设备可并行工作，$CPU$利用率显著提升。
• 缺点：每个字传输都要经过$CPU$；频繁中断会带来上下文切换开销，消耗$CPU$时间。

  注意：中断处理需要保存、恢复进程运行环境，存在时间开销；中断频率过高会降低系统性能。

3. $DMA$方式（直接存储器存取）

$DMA$主要用于块设备的$I/O$控制

1. 一次读/写流程
   $CPU$发出$I/O$命令后可执行其他任务；$DMA$控制器自主完成整块数据传输；一组数据块传输全部完成后，$DMA$控制器向$CPU$发送中断信号。
2. $CPU$干预频率
   中等，仅在一组数据块传输的开始、结束时需要$CPU$干预。
3. 数据传送单位
   每次读/写一个或多个连续块；内存中存放的数据块地址也必须连续。
4. 数据流向

• 读操作：$I/O$设备 $\rightarrow$ 内存
• 写操作：内存 $\rightarrow$ $I/O$设备
  数据不经过$CPU$。

5. $DMA$控制器内部寄存器

• $DR$（数据寄存器）：暂存设备与内存之间传输的数据。
• $MAR$（内存地址寄存器）：存放内存读写目标地址。
• $DC$（数据计数器）：记录剩余待传输字节数。
• $CR$（命令/状态寄存器）：存放$CPU$下发$I/O$命令，记录设备状态。

6. 优缺点

• 优点：以块为单位传输，$CPU$介入次数大幅减少；数据直接在设备与内存之间传输，传输效率高；$CPU$与$I/O$并行性强。
• 缺点：一条$I/O$指令只能处理连续的数据块；读写离散的多个块时，$CPU$需要多次下发$I/O$指令、多次中断处理。

4. 通道控制方式

通道：专用硬件，可理解为弱鸡版的$CPU$，能够识别并执行通道指令；通道程序存放在主机内存，通道与$CPU$共享内存。

1. 一次读/写流程
   ① $CPU$向通道下发$I/O$指令，指明通道程序内存位置与目标$I/O$设备，之后$CPU$切换执行其他进程。
   ② 通道读取内存中的通道程序，自主控制$I/O$设备完成一组块的数据读写。
   ③ 通道程序执行完毕，通道向$CPU$发送中断信号，$CPU$处理中断。
2. $CPU$干预频率
   低，仅在一组块全部传输完成后才需要$CPU$干预。
3. 数据传送单位
   一组块。
4. 数据流向

• 读操作：$I/O$设备 $\rightarrow$ 内存
• 写操作：内存 $\rightarrow$ $I/O$设备

5. 优缺点

• 优点：$CPU$、通道、$I/O$设备三者可以并行工作，系统资源利用率很高。
• 缺点：硬件实现复杂，需要专门的通道硬件支持。

四种$I/O$控制方式汇总对比表

5.1.4 $I/O$ 软件层次结构

$I/O$软件分为四层，自上而下依次为：用户层软件、设备独立性软件、设备驱动程序、中断处理程序。

注：设备独立性软件、设备驱动程序、中断处理程序属于操作系统内核部分。

1. 用户层软件

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

• 作用：将用户请求翻译成格式化的$I/O$请求，并通过系统调用请求操作系统内核服务。
• 示例：printf (“hello, world!”);，会被翻译为等价的write系统调用，同时填充对应参数。
• 补充：系统调用格式严格、使用繁琐，因此在用户层封装库函数接口（Windows $API$），方便用户使用。

2. 设备独立性软件（设备无关性软件）

与设备硬件特性无关的功能，几乎都在本层实现。 主要功能：

1. 向上层提供统一的调用接口（$read / write$系统调用）
2. 设备的保护：将设备视作特殊文件，控制不同用户对设备的访问权限，原理类似文件保护。
3. 差错处理
4. 设备的分配与回收
5. 数据缓冲区管理
6. 建立逻辑设备名到物理设备名的映射关系，根据设备类型选择调用对应驱动程序。
   逻辑设备表（$LUT$）两种管理方式：
7. 整个系统仅设置一张$LUT$：所有用户不能使用相同逻辑设备名，适合单用户操作系统。
8. 为每个用户设置一张$LUT$：不同用户逻辑设备名可重复，适合多用户操作系统；用户登录时建立用户管理进程，$LUT$存放在该进程的$PCB$中。

3. 设备驱动程序

负责对硬件设备的具体控制，将上层的read/write等命令，转化为特定设备能够识别的硬件操作。

• 工作内容：设置设备寄存器、检查设备状态。
• 特点：不同$I/O$设备硬件特性不同，硬件细节由设备厂商掌握，厂商提供对应驱动程序；驱动程序一般以独立进程的方式存在。
• 逻辑设备表记录：逻辑设备名、物理设备名、驱动程序入口地址。

4. 中断处理程序

当$I/O$任务完成时，$I/O$控制器发送中断信号，系统根据中断信号类型找到并执行对应的中断处理程序，会直接和硬件打交道。 执行流程：

1. 从控制器读出设备状态
2. 判断$I/O$是否正常结束
   • 若否：根据异常原因做对应处理
   • 若是：从设备读入一个字的数据，经由$CPU$放到内存缓冲区中

注意

$I/O$请求从上到下传递，$I/O$应答（中断信号）自下而上返回。

• 设备驱动程序：直接涉及硬件具体细节、与中断无关的操作，在这一层完成。
• 设备独立性软件：不涉及硬件、所有设备通用的管理工作，在这一层完成。

5.1.5 输入输出应用程序接口和驱动程序接口

输入/输出管理整体框架

输入输出管理分为两大模块：

1. 输入/输出应用程序接口
2. 设备驱动程序接口
   输入输出应用程序接口包含三类接口：字符设备接口、块设备接口、网络设备接口，同时包含阻塞/非阻塞 $I/O$ 相关概念。

输入/输出应用程序接口

操作系统在用户层提供统一的接口，向上层应用提供读写设备的系统调用，分为三类：

1. 字符设备接口

• 系统调用：$get / put$
• 功能：向字符设备读、写一个字符
• 设备特点：不可寻址，每次读写 $1$ 个字符
• 例子：键盘、打印机

2. 块设备接口

• 系统调用：$read / write，seek$
• $ read/write$：向块设备读写指针位置读/写多个字符
• $ seek$：修改读写指针位置
• 设备特点：可寻址，每次读/写 $1$ 个块
• 例子：磁盘

3. 网络设备接口（网络套接字socket接口）

• $ socket$：创建网络套接字，指明网络协议（ $TCP$ / $UDP$ ）
• $ bind$：套接字绑定到本地端口
• $ connect$：套接字连接到远程地址
• $ read / write$：从套接字读、写数据
• 设备例子：网络控制器（网卡）

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

1. 阻塞 $I/O$ 应用程序发出 $I/O$ 系统调用，进程转为阻塞态等待。 例子：字符设备接口，键盘读取字符（$scanf、get$）。
2. 非阻塞 $I/O$ 应用程序发出 $I/O$ 系统调用，调用可快速返回，进程不需要阻塞等待。 例子：块设备接口，向磁盘写数据（$write$ ）。

设备驱动程序接口

操作系统规定统一标准的设备驱动程序接口，硬件厂商按照该接口标准开发设备驱动。

$I/O$软件层次（自上而下）

1. 用户层 $I/O$ 软件
2. 设备独立软件
3. 设备驱动程序接口
4. 驱动程序
5. 中断处理程序
6. $I/O$ 设备（硬件）

• 不同厂商（如罗技、雷蛇）的硬件，各自实现驱动程序，对外遵循统一接口（例如read( $p1$ , $p2$ , $p3$ )）。
• 设备独立软件通过标准接口调用不同硬件的驱动，实现设备无关性。

网络设备接口工作流程（$socket$通信）

1. 主机 $1$ 进程 $P1$，用户空间调用 $write$ ，将数据写入内核空间$socket$缓冲区。
2. 内核中设备无关软件调用网卡驱动，将数据交给网络控制器（网卡），通过 $TCP/IP$ 协议发送。
3. 主机 $2$ 网卡收到数据包，触发中断，中断处理程序唤醒网卡驱动。
4. 数据存入主机 $2$ 内核$socket$缓冲区，进程 $P3$ 调用$read$，将数据读到用户空间。

核心：依靠端口号，区分数据要交付给主机上哪一个进程。

5.2.1 I/O核心子系统

I/O软件层次

$I/O$软件自上而下分为四层：

1. 用户层软件
2. 设备独立性软件
3. 设备驱动程序
4. 中断处理程序

   硬件不属于$I/O$软件。 $I/O$核心子系统 = 设备独立性软件 + 设备驱动程序 + 中断处理程序，属于操作系统内核部分。
   $I/O$核心子系统需要实现的功能：

• 设备独立性软件：$I/O$调度、设备保护、设备分配与回收、缓冲区管理（缓冲与高速缓存管理）
• 用户层软件：假脱机技术（$SPOOLing$技术）

I/O调度

$I/O$调度：采用调度算法，确定处理各个 $I/O$ 请求的先后顺序。

1. 磁盘调度算法：先来先服务、最短寻道优先、 $SCAN$ 、 $C-SCAN$ 、 $LOOK$ 、 $C-LOOK$ 。多个磁盘 $I/O$ 请求到达时，使用算法确定请求处理顺序。
2. 其他设备（打印机等）调度算法：先来先服务、优先级算法、短作业优先等。

设备保护

1. 基本思想：设备看作特殊文件，不同用户拥有不同访问权限（只读、读写等）。
2. UNIX系统实现：每个设备对应一个 $FCB$；用户请求访问设备时，系统查询 $FCB$ 记录，校验用户访问权限，以此实现设备保护。

   实现逻辑和文件保护机制一致。

I/O核心子系统功能

• $I/O$调度
• 设备保护
• 假脱机技术（ $SPOOLing$ 技术）
• 设备分配与回收
• 缓冲区管理（缓冲与高速缓存）

  注意：

  • 用户层软件：假脱机技术 $SPOOLing$
  • 设备独立性软件： $I/O$ 调度、设备保护、设备分配回收、缓冲区管理

5.2.2 假脱机技术

脱机技术（前身）

批处理阶段引入脱机输入/输出技术，依靠外围控制机与磁带实现。

• 原理：在外围控制机控制下，慢速设备的数据先存入高速磁带，主机直接从磁带读写数据。
• 名称由来：脱机指脱离主机控制执行输入输出。
• 作用：缓解设备与 $CPU$ 的速度矛盾，实现预输入、缓输出。

假脱机技术（$SPOOLing$技术）

假脱机技术，又称 $SPOOLing$ 技术，使用软件方式模拟脱机技术。

1. $SPOOLing$系统组成

1. 输入井、输出井：位于磁盘，模拟脱机技术中的磁带。输入井收容输入设备的数据；输出井收容用户进程输出的数据。
2. 输入进程、输出进程：模拟脱机技术中的外围控制机。
3. 输入缓冲区、输出缓冲区：位于内存，作为输入、输出数据的中转站。
   • 输入缓冲区：输入进程控制，暂存输入设备数据，再转存到输入井。
   • 输出缓冲区：输出进程控制，暂存输出井送来的数据，再传送至输出设备。

2. 共享打印机原理（经典例子）

打印机属于独占设备， $SPOOLing$ 技术可将其虚拟为共享设备。

1. 多个用户进程发起打印请求，系统不会直接分配物理打印机。
2. 假脱机管理进程执行两步操作：
   （1）在磁盘输出井中分配存储空间，将待打印数据存入。
   （2）填写打印请求表，挂入假脱机文件队列（打印任务队列）。
3. 打印机空闲时，输出进程从队列头部取出打印请求，把输出井的数据送入内存输出缓冲区，再送到物理打印机完成打印。

   系统只有一台物理打印机，但每个进程在输出井分配到一块存储区，相当于分配逻辑设备，进程感觉自己独占一台打印机。
   $SPOOLing$技术可以把一台物理设备虚拟成逻辑上的多台设备，将独占式设备改造成共享设备。

5.2.3 设备的分配与回收

设备按固有属性分类

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

1. 独占设备：一个时段只能分配给一个进程（如打印机）
2. 共享设备：可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用。
3. 虚拟设备：采用 $SPOOLing$ 技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用（如采用 $SPOOLing$ 技术实现的共享打印机）

设备分配考虑因素

1. 设备固有属性：独占设备、共享设备、虚拟设备（ $SPOOLing$ ）
2. 分配算法：先来先服务、优先级高者优先、短任务优先等
3. 安全性：安全分配方式、不安全分配方式

静态分配与动态分配

• 静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源。
• 动态分配：进程运行过程中动态申请设备资源。

  静态分配破坏了“请求和保持”条件，因此不会发生死锁。

设备分配管理中的数据结构

1. 系统设备表（ $SDT$ ）

记录了系统中全部设备的情况，每个设备对应一个表目。 表目字段：

• 设备类型
• 设备标识符（物理设备名）
• $DCT$（设备控制表）
• 驱动程序入口

2. 设备控制表（ $DCT$ ）

系统为每个设备配置一张 $DCT$，用于记录设备情况。 字段：

• 设备类型
• 设备标识符（物理设备名，唯一）
• 设备状态：忙碌/空闲/故障
• 指向控制器表的指针
• 重复执行次数或时间：重复多次 $I/O$ 仍失败，判定 $I/O$ 失败
• 设备队列的队首指针：指向等待该设备的进程 $PCB$ 队列

  注：系统会根据阻塞原因不同，将进程 $PCB$ 挂到不同的阻塞队列中。

3. 控制器控制表（ $COCT$ ）

每个设备控制器对应一张 $COCT$，操作系统根据 $COCT$ 管理控制器。 字段：

• 控制器标识符：控制器唯一 $ID$
• 控制器状态：忙碌/空闲/故障
• 指向通道表的指针
• 控制器队列的队首指针
• 控制器队列的队尾指针：指向等待该控制器的进程 $PCB$ 队列

4. 通道控制表（ $CHCT$ ）

每个通道对应一张 $CHCT$，操作系统根据 $CHCT$ 管理通道。 字段：

• 通道标识符：通道唯一 $ID$
• 通道状态：忙碌/空闲/故障
• 与通道连接的控制器表首址：找到该通道管理的所有 $COCT$
• 通道队列的队首指针
• 通道队列的队尾指针：指向等待该通道的进程 $PCB$ 队列

  补充：一个通道控制多个控制器，一个控制器控制多个设备。

设备分配步骤（原始方案：使用物理设备名）

1. 根据进程请求的物理设备名查找 $SDT$
2. 根据 $SDT$ 找到 $DCT$，若设备忙碌，则将进程 $PCB$ 挂到设备等待队列；不忙碌则分配设备。
3. 根据 $DCT$ 找到 $COCT$，若控制器忙碌，则将进程 $PCB$ 挂到控制器等待队列；不忙碌则分配控制器。
4. 根据 $COCT$ 找到 $CHCT$，若通道忙碌，则将进程 $PCB$ 挂到通道等待队列；不忙碌则分配通道。

   注：只有设备、控制器、通道三者都分配成功，本次设备分配才算成功，之后启动 $I/O$ 设备进行数据传送。
   原始方案缺点

5. 用户编程必须使用物理设备名，底层细节不透明，编程不便。
6. 更换物理设备后，程序无法运行。
7. 请求的物理设备忙碌时，即使系统存在同类型空闲设备，进程仍必须阻塞等待。
   改进思路：建立逻辑设备名与物理设备名的映射机制，用户编程仅提供逻辑设备名。

改进后的设备分配步骤（使用逻辑设备名）

逻辑设备表（ $LUT$ ）建立逻辑设备名与物理设备名之间的映射关系。

1. 根据进程请求的逻辑设备名查找 $SDT$（逻辑设备名本质是设备类型）
2. 查找 $SDT$，找到指定类型的空闲设备分配给进程，操作系统在 $LUT$ 中新增表项。
3. 根据 $DCT$ 找到 $COCT$，控制器忙碌则将进程 $PCB$ 挂入控制器等待队列；空闲则分配控制器。
4. 根据 $COCT$ 找到 $CHCT$，通道忙碌则将进程 $PCB$ 挂入通道等待队列；空闲则分配通道。

   $LUT$ 工作机制： 进程第一次使用设备，使用逻辑设备名发起请求；操作系统查找 $SDT$，分配空闲设备，在 $LUT$ 添加表项。后续再次用同一逻辑设备名请求设备，操作系统直接查询 $LUT$，获取对应的物理设备名与驱动程序入口地址。
   逻辑设备表的设置方案

5. 整个系统只有一张 $LUT$：各用户逻辑设备名不允许重复，适用于单用户操作系统。
6. 每个用户一张 $LUT$：不同用户的逻辑设备名可重复，适用于多用户操作系统。

设备分配的安全性

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

1. 安全分配方式 为进程分配一个设备后就将进程阻塞，本次 $I/O$ 完成后才唤醒进程。

• 特点：一个时段内每个进程只能使用一个设备。
• 优点：破坏了请求和保持条件，不会发生死锁。
• 缺点：同一个进程的 $CPU$ 和 $I/O$ 设备只能串行工作。

2. 不安全分配方式 进程发出 $I/O$ 请求后，系统分配设备，进程可继续执行，还可以发起新的 $I/O$ 请求；仅当某个 $I/O$ 请求无法满足时，进程才阻塞。

• 特点：一个进程可以同时使用多个设备。
• 优点：进程计算任务与 $I/O$ 任务可并行处理，推进速度更快。
• 缺点：有可能发生死锁，需要配套死锁避免、死锁检测与解除机制。

设备回收

进程结束后，操作系统回收设备、控制器、通道资源，修改 $DCT$、 $COCT$、 $CHCT$、 $LUT$ 等数据结构，唤醒等待该资源的其他进程。

5.2.4 缓冲区管理

缓冲区的概念

一般利用内存作为缓冲区。 缓冲区作用

• 缓解 $CPU$ 与设备的速度矛盾
• 减少对 $CPU$ 的中断频率
• 解决数据粒度不匹配的问题
• 提高 $CPU$ 与 $I/O$ 设备之间的并行性

单缓冲

操作系统在主存中为进程分配一个缓冲区，若无特殊说明，一个缓冲区大小等于一个块。

规则：缓冲区非空时，不能冲入新数据，只能传出数据；缓冲区为空时，才可以冲入数据，且必须充满后才能传出。 数据流向：设备—( $T$ )—缓冲区—( $M$ )—工作区—( $C$ )—处理 初始状态：工作区满，缓冲区空
处理一块数据平均耗时：$$Max(C, T)+M$$
通信场景：两台机器配置单缓冲区，任一时刻只能单向传输数据。A机数据先放入缓冲区，缓冲区满才发送；B机缓冲区取完数据后，才能向A机回传数据。

双缓冲

操作系统在主存中为进程分配两个缓冲区，若无特殊说明，单个缓冲区大小等于一个块。

初始状态：工作区空，一个缓冲区满，另一个缓冲区空
处理一块数据平均耗时：$$Max(T, C+M)$$
通信场景：两台机器配置双缓冲区，同一时刻可以实现双向数据传输。

循环缓冲区

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

• $in$ 指针：指向下一个可以冲入数据的空缓冲区
• $out$ 指针：指向下一个可以取出数据的满缓冲区

  图示说明：橙色代表已满数据缓冲区，绿色代表空缓冲区。

缓冲池

缓冲池由系统共用的缓冲区组成，缓冲区按使用状态分为三个队列：

1. 空缓冲队列
2. 输入队列：装满输入数据的缓冲区
3. 输出队列：装满输出数据的缓冲区
   根据缓冲区功能，设置四种工作缓冲区：

• $hin$：用于收容输入数据的工作缓冲区
• $sin$：用于提取输入数据的工作缓冲区
• $hout$：用于收容输出数据的工作缓冲区
• $sout$：用于提取输出数据的工作缓冲区

工作流程简述

1. 输入进程请求输入数据
2. 计算进程提取输入数据
3. 计算进程将准备好的数据冲入缓冲区
4. 输出进程请求输出数据

输出逻辑：从输出队列取出一块满输出数据的缓冲区，作为 $sout$；缓冲区数据读空后，重新挂入空缓冲队列。

5.3.1磁盘的结构

磁盘、磁道、扇区的概念

• 磁盘由表面涂有磁性物质的圆形盘片组成。
• 每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区。
• 盘的盘面被划分成一个个磁道，一个“圈”就是一个磁道；一个磁道又被划分成一个个扇区，每个扇区就是一个磁盘块，各个扇区存放的数据量相同。
• 最内侧磁道上的扇区面积最小，因此数据密度最大。

如何在磁盘中读/写数据

磁头移动到目标位置，盘片旋转，对应扇区划过磁道才能完成读/写。

盘面、柱面的概念

• 磁盘有多个盘片“摞”起来，每个盘片有两个盘面。
• 所有盘面中相对位置相同的磁道组成柱面。
• 每个盘面对应一个磁头；所有的磁头都是连在同一个磁臂上的，因此所有磁头只能“共进退”。

磁盘的物理地址

物理地址格式：$$(\text{柱面号},\ \text{盘面号},\ \text{扇区号})$$

• 可用$$(\text{柱面号},\ \text{盘面号},\ \text{扇区号})$$来定位任意一个“磁盘块”。文件物理结构小节提到的块号，可以转换为该地址形式。
• 读/写指定块的步骤：
  1. 根据柱面号移动磁臂，让磁头指向指定柱面；
  2. 激活指定盘面对应的磁头；
  3. 磁盘旋转，指定扇区从磁头下方划过，完成扇区读/写。

磁盘的分类

1. 根据磁头是否可移动
   • 固定头磁盘：磁头不可移动，每个磁道有一个磁头。
   • 移动头磁盘（活动头磁盘）：磁头可以移动，磁臂伸缩带动磁头定位磁道；每个盘面只有一个磁头。
2. 根据盘片是否可更换
   • 固定盘磁盘：盘片不可更换。
   • 可换盘磁盘：盘片可以更换。

5.3.3 磁盘调度算法

一次磁盘读/写操作的时间组成

磁盘调度算法只会影响寻找时间（寻道时间）。

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

• 启动磁头臂耗时 $s$；
• 磁头匀速移动，每跨越一个磁道耗时 $m$，跨越 $n$ 条磁道。 $$T_s = s + m \times n$$
  寻道时间：启动磁臂，移动磁头所花的时间

2. 延迟时间 $T_R$ 旋转磁盘，使磁头定位到目标扇区所需要的时间。 磁盘转速 $r$（单位：转/秒），平均延迟时间： $$T_R = \frac{1}{2r}$$
3. 传输时间 $T_t$ 读/写数据花费的时间。 设转速 $r$，读写字节数 $b$，每个磁道字节数 $N$： $$T_t = \frac{1}{r} \times \frac{b}{N} = \frac{b}{rN}$$
4. 总平均存取时间 $T_a$ $$T_a = T_s + \frac{1}{2r} + \frac{b}{rN}$$

   说明：延迟时间、传输时间由磁盘硬件转速决定，操作系统无法优化；磁盘调度算法只能优化寻道时间。

磁盘调度算法

例题统一条件：磁道范围 $0 \sim 200$，磁头初始位置 $100$，磁头初始向磁道号增大方向移动；访问请求： $55、58、39、18、90、160、150、38、184$ ，共 $9$ 个请求。

1. 先来先服务（$FCFS$）

• 思想：按访问请求到达的先后顺序依次处理。
• 例题计算： 磁头移动总磁道数 $45+3+19+21+72+70+10+112+146 = 498$ 平均寻道长度 $$498/9 = 55.3$$
• 优点：公平；请求磁道集中时性能尚可。
• 缺点：请求分散时，寻道时间很长，性能差。

2. 最短寻找时间优先（$SSTF$）

• 思想：每次优先响应距离当前磁头最近的磁道请求，贪心思想，局部最优，不能保证总寻道时间最短。
• 例题计算： 总移动磁道数 $(100-18)+(184-18)=248$ 平均寻道长度 $$248/9 = 27.5$$
• 优点：性能较好，平均寻道时间短。
• 缺点：可能产生饥饿现象。

3. 扫描算法（$SCAN$，电梯算法）

• 思想：只有磁头移动到磁盘最边缘磁道时，才可以改变磁头移动方向。
• 例题计算： 总移动磁道数 $(200-100)+(200-18)=282$ 平均寻道长度 $$282/9 = 31.3$$
• 优点：性能较好，平均寻道时间较短，不会产生饥饿。
• 缺点： ① 必须走到磁盘最边缘才换向，存在多余移动； ② 对各个位置磁道的响应频率不均匀。

4. 循环扫描算法（$C-SCAN$）

• 思想：磁头只在朝某一个方向移动时处理请求；到达磁盘最边缘后，直接快速返回磁盘起始端，返回途中不响应任何请求。
• 例题计算： 总移动磁道数 $(200-100)+(200-0)+(90-0)=390$ 平均寻道长度 $$390/9 = 43.3$$
• 优点：相比 $SCAN$，各磁道的响应频率更平均。
• 缺点：必须走到最边缘磁道才能换向；返回需要走到磁盘起始端，平均寻道时间更长。

5. $LOOK$ 算法（低频考点，$SCAN$改进）

• 思想：边移动边观察，只要磁头前进方向上没有未处理请求，就立刻改变磁头方向，不需要走到磁盘最边缘。
• 例题计算： 总移动磁道数 $(184-100)+(184-18)=250$ 平均寻道长度 $$250/9 = 27.5$$
• 优点：相比 $SCAN$，消除到磁盘边缘的多余移动，缩短寻道时间。

6. $C-LOOK$ 算法（低频考点，$C-SCAN$改进）

• 思想：磁头单向处理请求；前进方向无请求时，直接返回到最靠近边缘且存在访问请求的磁道，返回途中不处理请求，不需要回到磁盘最边缘。
• 例题计算： 总移动磁道数 $(184-100)+(184-18)+(90-18)=322$ 平均寻道长度 $$322/9 = 35.8$$
• 优点：相比 $C-SCAN$，减少走到磁盘边界的多余移动，进一步缩短寻道时间。

  做题备注：若无特别说明，则 $SCAN$ 等价 $LOOK$，$C-SCAN$ 等价 $C-LOOK$

三、算法对比小结

5.3.4 减少磁盘延迟的方法

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

1. 寻找时间（寻道时间）：启动磁臂( $2$、$3$ )移动磁头所花的时间
2. 延迟时间：将目标扇区转到磁头下面所花的时间
3. 传输时间：读/写数据花费的时间

   举例：连续读取 $2(2、3)3(2、3)4$ 号扇区 磁头读取一个扇区内容后，需要一小段时间处理，而盘片不停旋转。若 $2(2、3)3$ 号扇区物理相邻，读完 $2$ 号扇区后，来不及立刻读取 $3$ 号扇区，只能等待盘片旋转一圈，$3$ 号扇区再次划过磁头，才能继续读取。 结论：磁头读入一个扇区数据后需要小段时间处理；若逻辑相邻扇区物理上也相邻，读取连续逻辑扇区会产生较长的延迟时间。

交替编号

• 具体做法：让编号相邻的扇区在物理上不相邻
• 原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区
• 核心作用：逻辑上相邻的扇区在物理上设置间隔，减小读取连续逻辑扇区的延迟时间。

错位命名

• 具体做法：让相邻盘面的扇区编号“错位”
• 原理：与交替编号原理相同，错位命名法可降低延迟时间
• 示例：读取磁盘块$( (000,00,111) )$之后，存在数据处理时间；由于盘面同轴同步旋转，错位命名后，$( (000,01,000) )$第一次划过 $1$ 号盘面磁头下方时，就可以直接读取数据，减少延迟。

  若不采用错位命名：读取完$( (000,00,111) )$，处理数据的过程中盘片持续转动，$( (000,01,000) )$划过磁头时无法读取，需要等待盘片旋转一整圈。

磁盘地址结构的设计

思考：磁盘物理地址使用$( (柱面号，盘面号，扇区号) )$，而不是$( (盘面号，柱面号，扇区号) )$

• 原因：读取地址连续的磁盘块时，采用$( (柱面号，盘面号，扇区号) )$的地址结构，可以减少磁头移动消耗的时间。
• 原理：同一柱面下，多个盘面共用同一磁臂，切换盘面不需要移动磁头；如果优先改变盘面号，连续块会分布在不同柱面，频繁触发寻道，开销更大。

5.3.5 固态硬盘

原理

基于闪存技术 $Flash Memory$，属于电可擦除 $ROM$ ，即 $EEPROM$。

组成

1. 闪存翻译层：负责翻译逻辑块号，找到对应页（$Page$）。
2. 存储介质：多个闪存芯片（$Flash Chip$）
   • 每个芯片包含多个块（$block$）
   • 每个块包含多 个页（$page$）
   • 页大小：比如$$512\text{B} \sim 4\text{KB}$$

读写性能特性

• 以页（$page$）为单位读/写，相当于磁盘的扇区。
• 以块（$block$）为单位擦除；擦干净的块，其中的每页都可以写一次，读无限制。
• 支持随机访问，系统给定一个逻辑地址，闪存翻译层可通过电路迅速定位到对应的物理地址。
• 读快、写慢。要写的页如果有数据，则不能写入，需要将块内其他页全部复制到一个新的（擦除过的）块中，再写入新的页。

与机械硬盘相比的特点

• $SSD$读写速度快，随机访问性能高，用电电路控制访问位置；机械硬盘通过移动磁臂旋转磁盘控制访问位置，存在寻道时间和旋转延迟。
• $SSD$安静无噪音、耐摔抗震、能耗低、造价更贵。
• $SSD$的一个块被擦除次数过多（重复写同一个块）可能会坏掉，而机械硬盘的扇区不会因为写的次数太多而坏掉。

磨损均衡技术

核心思想：将“擦除”平均分布在各个块上，以提升使用寿命。

1. 动态磨损均衡：写入数据时，优先选择累计擦除次数少的新闪存块。
2. 静态磨损均衡：$SSD$监测并自动进行数据分配、迁移，让老旧的闪存块承担以读为主的储存任务，让较新的闪存块承担更多的写任务。