《现代操作系统》读书笔记（五）——输入/输出

5.1 I/O硬件原理

5.1.1 I/O设备

I/O设备大致可以分为两类：块设备（block device）和字符设备（character device）。
块设备的基本特征是每个块都能独立于其他块而读写。
字符设备以字符为单位发送或接收一个字符流，而不考虑任何块结构。

5.1.2 设备控制器

I/O设备一般由机械部件和电子部件两部分组成，电子部件称作设备控制器（device controller）或适配器（adapter），机械部件是设备本身。
控制器卡上通常有一个连接器，通向设备本身的电缆可以插入到这个连接器中。控制器与设备之间的接口通常是一个很低层次的接口。
控制器的任务是把串行的位流转换为字节块，并进行必要的错误校正工作。字节块通常首先在控制器内部的一个缓冲区中按位进行组装，然后在对校验和进行校验并证明字节块没有错误后，再将它复制到主存中。

5.1.3 内存映射I/O

每个控制器有几个寄存器用来与CPU进行通信：通过写入这些寄存器，操作系统可以命令设备发送数据、接收数据、开启或关闭，或者执行某些其他操作；通过读取这些寄存器，操作系统可以了解设备的状态，是否准备好接收一个新的命令等。
CPU与设备的控制寄存器和数据缓冲区进行通信的方法：1)每个控制寄存器被分配一个I/O端口（I/O port）号，所有I/O端口形成I/O端口空间（I/O port space），并且受到保护使得普通的用户程序不能对其进行访问；2)将所有控制寄存器映射到内存空间中,每个控制寄存器被分配唯一的一个内存地址，并且不会有内存被分配这一地址，这样的系统称为内存映射I/O（memory-mapped I/O），通常分配给控制寄存器的地址位于地址空间的顶端。
对于内存映射I/O，不需要汇编代码仅用C就可以寻址，不需要特殊的保护机制来阻止用户进程执行I/O操作（只要避免把包含控制寄存器的那部分地址空间放入任何用户的虚拟地址空间之中），而且可以引用内存的每一条指令也可以引用控制寄存器。
对于内存映射I/O，硬件必须针对每个页面具备选择性禁用高速缓存的能力。

5.1.4 直接存储器存取

CPU可以从I/O控制器每次请求一个字节的数据，但是这样做浪费CPU的时间，所以经常用到一种称为直接存储器存取（Direct Memory Access，DMA）的不同方案。
DMA工作流程：

1. CPU通过设置DMA控制器的寄存器对它进行编程，所以DMA控制器知道将什么数据传送到什么地方；
2. DMA控制器还要向磁盘控制器发出一个命令，通知它从磁盘读数据到其内部的缓冲区中，并且对校验和进行检验，DMA控制器通过在总线上发出一个读请求到磁盘控制器而发起DMA传送；
3. 磁盘控制器逐字读取磁盘内部缓冲区中数据并写入内存中；
4. 磁盘控制器在总线上发出一个应答信号到DMA控制器；
5. DMA控制器将中断CPU以便让CPU知道传送现在已经完成了。

许多总线能够以两种模式操作：每次一字模式和块模式。每次一字模式：DMA控制器请求传送一个字并且得到这个字，如果CPU也想使用总线，它必须等待，这一机制称为周期窃取（cycle stealing），因为设备控制器偶尔偷偷溜入并且从CPU偷走一个临时的总线周期，从而轻微地延迟CPU。块模式：DMA控制器通知设备获得总线，发起一连串的传送，然后释放总线，这一操作形式称为突发模式（burst mode）。
飞越模式（fly-by mode）中，DMA控制器通知设备控制器直接将数据传送到主存。
在DMA可以开始之前磁盘首先要将数据读入其内部的缓冲区中的原因：1)磁盘控制器可以在开始传送之前检验校验和；2)总线很忙时，磁盘控制器来不及将数据读入内存中，则先暂存入磁盘内部的缓冲区中。

5.1.5 重温中断

当一个I/O设备完成交给它的工作时，它就产生一个中断，它是通过在分配给它的一条总线信号线上置起信号而产生中断的，该信号被主板上的中断控制器芯片检测到，由中断控制器芯片决定做什么。
为了处理中断，中断控制器在地址线上放置一个数字表明哪个设备需要关注，并且置起一个中断CPU的信号，地址线上的数字被用做指向一个称为中断向量（interrupt vector）的表格的索引，以便读取一个新的程序计数器。
将机器留在一个明确状态的中断称为精确中断（precise interrupt），具有4个特性：

1. PC（程序计数器）保存在一个已知的地方；
2. PC所指向的指令之前的所有指令已经完全执行；
3. PC所指向的指令之后的所有指令都没有执行；
4. PC所指向的指令的执行状态是已知的。

非精确中断称为不精确中断（imprecise interrupt）。

5.2 I/O软件原理

5.2.1 I/O软件的目标

设备独立性（device independence）要求能编写出可以访问任意I/O设备而无需事先指定设备的程序。
与设备独立性密切相关的是统一命名（uniform naming），即一个文件或一个设备的名字应该是一个简单的字符串或一个整数，它不应依赖于设备。I/O软件的其他问题有错误处理（error handling）、同步（synchronous）（即阻塞）和异步（asynchronous）（即中断驱动）、缓冲（buffering）。

5.2.2 程序控制I/O

I/O最简单的形式就是让CPU做全部工作，这一方法称为程序控制I/O（programmed I/O）。
程序控制I/O：先在用户空间的一个缓冲区组装字符串，随后用户进程发出系统调用打开输出设备（若失败则返回错误代码且阻塞至输出设备可用），然后操作系统将字符串缓冲区复制到内核空间中的一个数组中，一旦输出设备可用，则复制一个字符到输出设备，随后查看其是否就绪准备接收另一个字符。
CPU要不断地查询设备以了解它是否就绪准备接收另一个字符，这一行为经常称为轮询（polling）或忙等待（busy waiting）。

5.2.3 中断驱动I/O

中断驱动I/O：输出第一个字符及之前的过程与程序控制I/O相似，当输出设备输出了字符并且准备好接收下一个字符时，它将产生一个中断，这一中断将停止当前进程并且保存其状态，然后，如果没有更多字符要输出，中断处理程序将采取某个操作将用户进程解除阻塞，否则，它将输出下一个字符，应答中断，并且返回到中断之前正在运行的进程，该进程将从其停止的地方继续运行。

5.2.4 使用DMA的I/O

DMA控制器一次给输出设备提供一个字符，而不必打扰CPU，将中断的次数从输出每个字符一次减少到输出每个缓冲区一次。

5.3 I/O软件层次

I/O软件层次自顶向下分别为：用户级I/O软件、与设备无关的操作系统软件、设备驱动程序和中断处理程序，再之下就是硬件。
当一个用户进程试图从一个文件中读一个块时，操作系统被调用以实现这一请求，与设备无关的软件在缓冲区高速缓存中查找有无要读的块，如果需要的块不在其中，则调用设备驱动程序，向硬件发出一个请求，让它从磁盘中获取该块，然后进程被阻塞直到磁盘操作完成，当磁盘操作完成时，硬件产生一个中断，中断处理程序就会运行，它要查明发生了什么事情，也就是说此刻需要关注哪个设备，然后，中断处理程序从设备提取状态信息，唤醒休眠的进程以结束此次I/O请求，并且让用户进程继续运行。

5.3.1 中断处理程序

1. 保存没有被中断硬件保存的所有寄存器（包括PSW）；
2. 为中断服务过程设置上下文，可能包括设置TLB、MMU和页表；
3. 为中断服务过程设置堆栈；
4. 应答中断控制器，如果不存在集中的中断控制器，则再次开放中断；
5. 将寄存器从它们被保存的地方复制到进程表中；
6. 运行中断服务过程，从发出中断的设备控制器的寄存器中提取信息；
7. 选择下一次运行哪个进程，如果中断导致某个被阻塞的高优先级进程变为就绪，则可能选择它现在就运行；
8. 为下一次要运行的进程设置MMU上下文，也许还需要设置某个TLB；
9. 装入新进程的寄存器，包括PSW；
10. 开始运行新进程。

5.3.2 设备驱动程序

每个连接到计算机上的I/O设备都需要某些设备特定的代码来对其进行控制，这样的代码称为设备驱动程序（device driver），它一般由设备的制造商编写并随同设备一起交付，驱动程序代码片段被安装在操作系统内部。
设备驱动程序的若干功能：接收来自其上方与设备无关的软件所发出的抽象的读写请求并且目睹这些请求被执行；对设备进行初始化；对电源需求和日志事件进行管理；检查输入参数搞清其是否有效；检查设备当前是否在使用；控制设备（发出一系列命令）。
命令发出后，在多数情况下，设备驱动程序必须等待，直到控制器为其做某些事情，所以驱动程序将阻塞其自身直到中断到来解除阻塞；在另外一些情况下，操作可以无延迟地完成，所以驱动程序不需要阻塞。
驱动程序必须是重入的（reentrant），这意味着一个正在运行的驱动程序必须预料到在第一次调用完成之前第二次被调用。
驱动程序不允许进行系统调用，但是它们经常需要与内核的其余部分进行交互，对某些内核过程的调用通常是允许的。

5.3.3 与设备无关的I/O软件

功能：

1. 设备驱动程序的统一接口
   驱动程序通常包含一张表格，这张表格具有针对一组驱动程序必须支持的函数指向驱动程序自身的指针，当驱动程序装载时操作系统记录下这张函数指针表的地址，所以当操作系统需要调用一个函数时，它可以通过这张表格发出间接调用，这张函数指针表定义了驱动程序与操作系统其余部分之间的接口，给定类型的所有设备都必须服从这一要求。
2. 缓冲
   用户空间、内核空间和网络控制器中都该设置缓存。可以在内核空间中设置双缓冲（double buffering）：当一个缓冲区正在被复制到用户空间的时候，另一个缓冲区正在收集新的输入。另一种形式的缓冲是循环缓冲区（circular buffer）：它由一个内存区域和两个指针组成，一个指针指向下一个空闲的字，新的数据可以放到此处，另一个指针指向缓冲区中数据的第一个字，该字尚未被取走。
3. 错误报告
   一种类型的I/O错误是编程错误，另一种类型的错误是实际的I/O错误。
4. 分配与释放专用设备
   用一个队列存放因试图得到不可用的设备而被阻塞的进程。
5. 与设备无关的块大小
   隐藏不同设备的物理数据块大小的差异，向高层软件提供大小统一的逻辑数据块。

5.3.4 用户空间的I/O软件

大部分I/O软件都在操作系统内部，但是仍然有一小部分在用户空间，包括与用户进程连接在一起的库，甚至完全运行于内核之外的程序，系统调用通常由库过程实现。
另一种用户层I/O软件的类别是假脱机（spooling）系统，是多道程序设计系统中处理独占I/O设备的一种方法。这种用户层I/O的方法是创建一个特殊进程，称为守护进程（daemon），以及一个特殊目录，称为假脱机目录（spooling directory）。一个进程要输出一个文件时，首先生成要输出的整个文件，并且将其放在假脱机目录下，由守护进程输出该目录下的文件，该进程是允许使用输出设备特殊文件的唯一进程，通过保护特殊文件来防止用户直接使用，可以解决某些进程不必要地长期空占输出设备的问题。

5.4 盘

5.4.1 盘的硬件

1. 磁盘：
   磁盘被组织成柱面，每一个柱面包含若干磁道，磁道数与垂直堆叠的磁头个数相同，磁道又被分成若干扇区，软盘上大约每条磁道有8~32个扇区，磁盘上每条磁道上扇区的数目可以多达几百个，磁头数大约是1~16个。老式的磁盘只有少量的电子设备，它们只是传送简单的串行位流。在这些磁盘上，控制器做了大部分的工作。在其他磁盘如IDE（Integrated Drive Electronics，即集成驱动电子设备）和SATA（Serial ATA，串行ATA）盘上，磁盘驱动器本身包含一个微控制器，该微控制器承担了大量的工作并且允许实际的控制器发出一组高级命令，控制器经常做磁道高速缓存、坏块重映射以及更多的工作。对磁盘驱动程序有重要意义的一个设备特性是：控制器是否可以同时控制两个或多个驱动器进行寻道，这就是重叠寻道（overlapped seek）。为了隐藏每个磁道有多少扇区的细节，大多数现代磁盘都有一个虚拟几何规格呈现给操作系统。所有现代磁盘都支持一种称为逻辑块寻址（logical block addressing，LBA）的系统，在这样的系统中，磁盘扇区从0开始连续编号，而不管磁盘的几何规格。
2. RAID：
   RAID（Redundant Array of Inexpensive Disk，即廉价磁盘冗余阵列）背后的基本思想是将一个装满了磁盘的盒子安装到计算机（通常是一个大型服务器）上，用RAID控制器替换磁盘控制器卡，将数据复制到整个RAID上，然后继续常规的操作，将数据分布在多个驱动器上称为划分条带（striping）。
3. CD-ROM：
   CD-ROM（Compact Disc Read-Only Memory，即只读光盘）是一种在电脑上使用的光碟。这种光碟只能写入数据一次，信息将永久保存在光碟上，使用时通过光碟驱动器读出信息。
4. 可刻录CD：
   CD-R（CD-Recordable，即可刻录CD）是一种一次写入、永久读的标准。
5. 可重写CD：
   CD-RW（CD-Rewritable，即可重写CD）指一种可重复刻录的光盘，其原理是利用激光束加热的方式来改变材质的结构，利用“相位改变”的原理来刻录数据。
6. DVD：
   DVD（Digital Video Disk，即数字视盘）分别采用MPEG—2技术和AC—3标准对视频和音频信号进行压缩编码。

5.4.2 磁盘格式化

在磁盘能够使用之前，每个盘片必须经受由软件完成的低级格式化（low-level format），该格式包含一系列同心的磁道，每个磁道包含若干数目的扇区，扇区间存在短的间隙。在低级格式化后，要对磁盘进行分区。
在准备一块磁盘以便于使用的最后一步是对每一个分区分别执行一次高级格式化（high-level format），这一操作要设置一个引导块、空闲存储管理（空闲列表或位图）、根目录和一个空文件系统，还要将一个代码设置在分区表项中，以表明在分区中使用的是哪个文件系统。
当电源打开时，BIOS最先运行，它读入主引导记录并跳转到主引导记录，然后这一引导程序进行检查以了解哪个分区是活动的，引导扇区包括一个小的程序，它一般会装入一个较大的引导程序装载器，该引导程序装载器将搜索文件系统以找到操作系统内核，该程序被装入内存并执行。

5.4.3 磁盘臂调度算法

读或者写一个磁盘块需要的时间：1)寻道时间，2)旋转延迟，3)实际数据传输时间。
如果磁盘驱动程序每次接收一个请求并按照接收顺序完成请求，即先来先服务（First-Come, First-Served，FCFS），则很难优化寻道时间。
另一种方法是下一次总是处理与磁头距离最近的请求以使寻道时间最小化，这个算法即最短寻道优先（Shortest Seek First，SSF），但是获得最小响应时间的目标和公平性之间存在冲突。
还有一种算法是电梯算法（elevator algorithm），先往同一方向寻道，随后往反向寻道。

5.4.4 错误处理

对于坏块存在两种一般的处理方法：在控制器中对它们进行处理或者在操作系统中对它们进行处理。

5.4.5 稳定存储器

当一个写命令发给一个磁盘子系统时，磁盘要么正确地写数据，要么什么也不做，让现有的数据完整无缺地留下，这样的系统称为稳定存储器（stable storage），并且是在软件中实现的。稳定存储器使用一对完全相同的磁盘，对应的块一同工作以形成一个无差错的块，当不存在错误时，在两个驱动器上对应的块是相同的，读取任意一个都可以得到相同的结果，为达到这一目的，定义了三种操作：1)稳定写（stable write），2)稳定读（stable read），3)崩溃恢复（crash recovery）。
非易失性（nonvolatile RAM）是一个特殊的CMOS存储器，由锂电池供电。

5.5 时钟

时钟（clock）又称为定时器（timer），负责维护时间，并且防止一个进程垄断CPU。

5.5.1 时钟硬件

现在常用的一种类型的时钟由三个部件构成：晶体振荡器、计数器和存储寄存器。

5.5.2 时钟软件

时钟驱动程序的任务：1)维护日时间，2)防止进程超时运行，3)对CPU的使用情况记账，4)处理用户进程提出的alarm系统调用，5)为系统本身的各个部分提供监视定时器，6)完成概要剖析、监视和统计信息收集。

5.5.3 软定时器

一般管理I/O有两种方法：中断和轮询。软定时器（soft timer）避免了中断，无论何时当内核因某种原因在运行时，在它返回到用户态之前，它都要检查实时时钟以了解软定时器是否到期，如果这个定时器已经到期，则执行被调度的事件，而无需切换到内核态，因为系统已经在内核态，在完成工作之后，软定时器被复位以便再次闹响，要做的全部工作是将当前时钟复制给定时器并且将超时间隔加上。

5.6 用户界面：键盘、鼠标和监视器

5.6.1 输入软件

1. 键盘软件
   I/O端口中的数字是键编号，称为扫描码（scan code），而不是ASCII码，跟踪每个键的状态（按下或弹起）是驱动程序的任务。键盘驱动程序处理方式分为：原始模式（raw mode）或非规范模式（uncanonical mode）——面向字符处理、加工模式（cooked mode）或规范模式（canonical mode）——面向行处理。虽然键盘和监视器在逻辑上是两个独立的设备，但是很多用户习惯于看到他们刚刚键入的字符出现在屏幕上，这个过程叫回显（echoing）。
2. 鼠标软件
   鼠标发送到计算机的消息为：坐标和按钮及其状态。

5.6.2 输出软件

1. 文本窗口
   大多数输出驱动程序支持一系列命令来移动光标，在光标处插入或者删除字符或行，这些命令常常被称为转义序列（escape sequence）。
2. X窗口系统
   X窗口系统是一种用于UNIX系统的标准图形化用户界面、一种可以在远程连接之上很好工作的C/S的设计。
3. 图形用户界面
   图形用户界面是指采用图形方式显示的计算机操作用户界面。
4. 位图
   位图图像亦称为点阵图像或栅格图像，是由称作像素的单个点组成的。
5. 字体

5.7 瘦客户机

主流计算范式一直在中心化计算和分散化计算之间震荡。大部分用户想要高性能的交互式计算，但是实在不想管理一台计算机，于是分时系统使用的瘦客户机出现了，它比一台普通计算机有更加安全可靠的使用环境、更低的功耗和更高的安全性。

5.8 电源管理

两种减少能量消耗的方法：

1. 当计算机的某些部件不用的时候由操作系统关闭它们，因为关闭的设备使用的能量很少或者不使用能量；
2. 应用程序使用较少的能量，这样为了延长电池时间可能会降低用户体验的质量。

5.8.1 硬件问题

将CPU、内存以及I/O设备设计成具有多种状态：工作、睡眠、休眠和关闭。

5.8.2 操作系统问题

1. 显示器：定期关闭屏幕；
2. 硬盘：一个停止的磁盘是休眠而不是睡眠，重启会消耗相当多的时间与能量，设定一个特征时间来决定是否停转，或者在RAM中拥有一个大容量磁盘高速缓存，或者操作系统通过发送信息或信号保持磁盘的状态通知给正在运行的程序；
3. CPU：平常睡眠，当中断发生时醒来，或者降低电压，慢速运行比快速运行具有更高的能量效率；
4. 内存：刷新然后关闭高速缓存（睡眠），或者将主存的内容写到磁盘上然后关闭主存本身（休眠）；
5. 无线通信：由用户或者周期性关闭无线电设备；
6. 热量管理：加装风扇将内部热空气吹出机箱；
7. 电池管理：使用智能电池；
8. 驱动程序接口：操作系统可以对电源进行管理。

5.8.3 应用程序问题

使应用程序尽可能少地消耗能量。

5.9 有关输入/输出的研究

5.10 小结

实现I/O的三种方式：程序控制I/O、中断驱动的I/O和DMA。
I/O的4个层次（自底向上）：中断服务程序、设备驱动程序、与设备无关的I/O软件和运行在用户空间的I/O库与假脱机程序。
时钟可以用于跟踪实际时间、限制进程可以运行多长时间、处理监视定时器以及进行记账。

博文补充（转）：
《Linux内核设计与实现》读书笔记（七）- 中断处理
《Linux内核设计与实现》读书笔记（八）- 中断下半部的处理
《Linux内核设计与实现》读书笔记（十一）- 定时器和时间管理
《Linux内核设计与实现》读书笔记（十四）- 块I/O层
《Linux内核设计与实现》读书笔记（十七）- 设备与模块
Linux的五种I/O模型
Linux下I/O多路复用的三种机制Select，Poll，Epoll