I/O 管理

概述

I/O设备

I/O外设大致分为三类

人可读：比如显示器，键盘，鼠标
机器可读：比如磁盘驱动器、USB密钥、传感器、控制器和执行器。
通信：比如数字线路驱动器和调制解调器

这些设备可能的主要差别在数据传输速率，控制复杂度，传输单位，数据表示，错误条件等等各有不同；

或者分成两类

面向块：信息保存在块中，块的大小通常是固定的，传送过程中一次传送一个块，比如磁盘，USB智能卡等
面向流：以字节流的方式输入/输出数据，比如终端，打印机，网卡，鼠标等

由于设备具有差异性，设备被设计为不直接和CPU通信，而是与设备控制器通信，在I/O设备应该包含和设备控制器的接口；

I/O设备发给控制器的信号有三种：

数据信号：双向，有缓存。
控制信号：控制器发给设备；要求其完成相关操作。

状态信号：设备发给控制器，后者“显示”。

设备控制器

Device Controller的组成

设备控制器与CPU的接口：数据线，地址线，控制线
设备控制器与I/O设备的接口：每个接口包含数据、命令、状态三类信号的交换
I/O逻辑：接受I/O命令并译码

Device Controller的基本功能：

接受和识别命令：应该有相应的寄存器存放命令；
数据交换：实现CPU与设备控制器，设备控制器和I/O设备之间的数据交换；
标识和报告设备的状态：通过状态寄存器记录
地址识别
数据缓冲
差错控制

I/O控制方式

常见的I/O控制包含四种技术：程序控制I/O、中断驱动控制I/O，直接存储器访问(DMA)，包括I/O通道控制

程序控制I/O

程序控制I/O(Programmed I/O)典型的方式是轮询(Polling);

处理器代表一个进程给I/O模块发送一个I/O命令, 该进程进入忙等待，直到操作完成才能继续执行。

CPU需要花费代价不断查询I/O状态，CPU花费极大

流程图如下所示

中断控制I/O

中断：一个进程占有处理器运行时，由于自身或外界的原因（出现了某事件）使运行被打断。让操作系统处理所出现的事件，处理完中断事件之后，再让被打断的进程继续运行；

外部中断事件：比如计算机故障中断，输入输出中断
内部中断：比如由地址越界，除数为0等造成的程序性中断事件，系统调用中断(访管中断)；

中断源：引起中断的事件；

中断处理程序：对出现的事件进行处理的程序；以下是一个可能的流程图

中断响应：处理器每执行完一条指令后，硬件的中断装置立即检查有无中断事件发生，若有中断事件发生，则暂停现行进程的执行，而让操作系统的中断处理程序占用处理器；

首先检查是否有中断事件发生，并确定中断的原因。
若有中断事件发生，则保护好被中断进程的断点以及其他一些信息(上下文)，以便进程在适当时候能继续执行。
根据中断原因找到中断处理程序并启动中断处理程序工作。

中断寄存器：如果有外部中断事件出现，而外部中断源又各不相同，需要用寄存器记录原因。例如以下8259A寄存器图示

中断向量表：在微机中将中断源统一编号，不同的中断源有不同的中断类型编号；每一个中断类型号对应一个中断处理程序。 中断向量表中存放各个中断处理程序的入口地址。在计算机系统初始化时，根据设备处理程序在内存中的位置，由引导程序完成中断向量表的建立。

中断优先级：中断优先级是按中断事件的重要性和紧迫程度来确定的。中断装置是按预定的顺序响应同时出现的中断事件，这个顺序可以由编程实现。下图是一个可能系统实现

中断控制I/O: 处理器代表进程向I/O模块发送I/O命令

该指令是非阻塞的：处理器继续执行该指令的后续命令
该指令是阻塞的：处理器下个指令来自操作系统，将当前进程阻塞并调度其他进程(当前进程发生了中断);

直接内存访问控制

直接内存访问(Direct Memory Access, DMA)用于实现控制内存和I/O模块之间的数据交换。

处理器向DMA发送请求
整个数据块传送结束后请求中断

设计目的：进一步减少CPU对I/O的干预；

特点：

数据传输的基本单位是数据块，即CPU与I/O设备之间，每次传送至少是一个数据块；
所传送的数据是从设备直接送入内存的，或者从内存送到设备输出；
仅在传送一个或多个数据块的开始和结束时，才需CPU 干预，整块数据的传送是在通道控制器的控制下完成的；

组成：

主机和DMA控制器接口
DMA控制器和块设备接口
I/O控制逻辑

实现：在DMA控制器中设置四类寄存器，即命令/状态寄存器(CR), 内存地址寄存器(MAR), 数据寄存器(DR),数据计数器(DC);

一个典型的DMA框图如下：

DMA工作流程如下：DMA可以模拟处理器，实际上也能像处理器一样获得系统总线的控制权

I/O通道

I/O 通道方式(I/O channel) 是DMA 方式的发展，实际上属于DMA的一种；

它可进一步减少 CPU 的干预，即把对一个数据块的读(或写)为单位的干预减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。
可实现CPU、通道和I/O 设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

通道：一种特殊的执行I/O指令的处理机，与CPU共享内存，可以有自己的总线。

字节多路通道：这是一种按字节交叉方式工作的通道。每一个子通道连接一台I／O设备，并控制该设备的I／O操作。这些子通道按时间片轮转方式共享主通道。只要字节多路通道扫描每个子通道的速率足够快，而连接到子通道上的设备的速率不是太高时，便不致丢失信息，适用于低、中速设备。
数组选择通道：数组选择通道可以连接多台高速设备，但是只有一个分配型子通道，一段时间内只能执行一道通道程序。某台设备占用该通道后，即使无数据传送，通道被闲置，也不允许其他设备使用该通道，直至设备传送完毕释放该通道。缺点是利用率低。
数组多路通道：数组多路通道将数组选择通道传输速率高和字节多路通道能使各子通道分时并行操作的优点相结合。数组多路通道含有多个非分配型子通道，既具有很高的数据传输速率，又有较高的通道利用率。广泛应用于连接多台高、中速外围设备，数据传送方式按数组方式进行。

通道程序：通道是通过执行通道程序，并与设备控制器共同实现对I/O设备的控制的。通道程序是由一系列通道指令（或称为通道命令）所构成的

通道的设计可以解脱CPU对I/O的组织管理，更好地处理终端命令；CPU只需发送I/O命令给通道，通道通过调用内存中的相应通道程序完成任务。

在I/O通道设计中，可能存在瓶颈问题：

原因：通道不足
解决的最有效办法不是增加通道，而是增加设备到主机间的通路

设别的硬件层次

I/O子系统分类

用户层I/O软件：实现与用户交互的接口，用户可直接调用在用户层提供的、与I/O操作有关的库函数，对设备进行操作；
设备独立性软件：用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护，以及设备分配与释放等，同时也为设备管理和数据传送提供必要的存储空间。
设备驱动程序：硬件相关，具体实现OS对设备发出的操作指令，驱动I/O设备工作。每一类设备有一个设备驱动程序。比如我们插入U盘时，系统会弹出安装驱动，安装完成后，这个驱动程序不会消失，而是运行在后台进程。无论你用的是正版金士顿还是盗版，用的是东芝还是闪迪，驱动程序都是一类，系统中驱动U盘的都是相同的驱动程序。
中断服务程序
硬件：这里的硬件也需要单独说明，是因为这里是指代I/O设备，有不同之处。分为两个部分：机械部件和电子部件。

设备管理软件

设计目标

与具体设备无关
统一命名
对错误的处理
缓冲技术
设备的分配和释放
I/O 控制方式

软件层次结构

要使设备按用户的要求工作，必须对与设备接口的通道和控制器等进行程序编制，通过程序实现对设备的控制。
为了方便用户使用还必须给出调用接口或命令接口。
为了更有效的利用设备还必须研究管理技术和算法。

设备驱动程序

功能

接收由设备独立性软件发来的命令和参数，并将命令中的抽象要求转换为具体要求。
检查用户I/O 请求的合法性。
发出I/O 命令。
及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进行处理。根据用户的I/O 请求，自动地构成通道程序。

处理过程：

对指定的设备进行初始化：在执行输入或输出之前完成必要的准备工作
将抽象要求转换为具体要求：用户及上层软件对设备控制器的具体情况毫无了解，因而只能向它们发出抽象的要求，但又无法传送给设备控制器。因此，就需要能将这些抽象要求转换为具体要求。在OS中只有设备驱动程序才同时了解抽象要求和设备控制器中的寄存器情况；也只有它才知道数据和参数应分别送到哪个寄存器。例如，将抽象要求中的盘块号转换为磁盘的盘面、磁道号及扇区。这一转换工作只能由设备驱动程序来完成。
检查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，设备I/O，调度和控制，实现用户进程和硬件的交互；

设计缓冲区是操作系统提高I/O效率的机制；

设计缓冲区的主要原因：

缓和CPU与I／O设备间速度不匹配的矛盾。
减少对CPU的中断频率，放宽对CPU中断响应时间的限制。
提高CPU和I／O设备之间的并行性。

单缓冲

在单缓冲情况下，每当用户进程发出一I/O请求时，操作系统便在主存中为之分配一缓冲区。

假设输入时间为，计算时间为,数据传送时间(数据从缓冲区复制到用户内存)为,输入和计算并行，系统对于每一块的处理时间为；

双缓冲

在设备输入时,先将数据送入第一缓冲区，装满后便转向第二缓冲区。此时操作系统可以从第一缓冲区中移出数据，并送入用户进程。

在双缓冲时，如果假设缓冲区的数据传送到用户区时间远小于输入时间或计算时间，系统处理一块数据的最大时间可粗略地认为。如果，可使磁盘数据连续输入；如果，可使CPU不必等待数据输入。

假设一个两台机器的通信场景，单缓冲无法实现双方同时向对方发送数据，若为每个机器设置发送缓冲区和接受缓冲区，就能实现双向的数据传输；

循环缓冲

循环缓冲可以解决输入输出速度差异很大的问题，遵循生产者-消费者模型实现对资源的互斥共享；

组成：

多个缓冲区：每个缓冲区的大小相同；
多个指针：指示计算进程下一个可用缓冲区G 的指针Nextg, 指示输入进程下次可用的空缓冲区R 的指针Nexti, 指示计算进程正在使用的缓冲区C 的指针Current。

缓冲池

缓冲池是各种系统的流行技术，在池中设置了多个可供若干个进程共享的缓冲区。

组成：

空缓冲队列emq:由空缓冲区所链成的队列。
输入队列inq:由装满输入数据的缓冲区所链成的队列。
输出队列outq:由装满输出数据的缓冲区所链成的队列。
四种工作缓冲区：收容输入数据，提取输入数据，收容输出数据，提取输出数据

设备分配及算法

表结构

在进行设备分配时，通常都需要借助于一些表格的帮助。在表格中记录了相应设备或控制器的状态及对设备或控制器进行控制所需的信息。

设备控制表DCT: 系统为每一个设备都配置了一张设备控制表，用于记录本设备的情况;
控制器控制表COCT
通道控制表 CHCT
系统设备表SDT

设计原则

设备的固有属性：共享+虚拟+独享

设备分配时应考虑的因素：设备的固有属性、分配算法、安全性、独立性

同步是安全的分配方式：当进程发出一个I/O后，即blocked，直到其I/O完成，打破了请求并保持条件，缺点是CPU、I/O串行工作，进程进展缓慢

异步是不安全的分配方式，进程执行效率高，但是要进行安全性检查；

分配算法：FIFO，优先权

SPOOLing技术

假脱机操作(Simultaneaus Periphernal Operating On-Line, SPOOLing)技术：是用于将 I/O 设备进行虚拟化的技术。在主机的直接控制下，实现脱机输入、输出功能。此时的外围操作与CPU对数据的处理同时进行.可以实现将一台物理I/O设备虚拟为多台逻辑I/O设备，同样允许多个用户共享一台物理I/O设备；

SPOOLing技术是实现Linux中’一切皆文件’和虚拟设备的基础,欺骗进程使进程认为自己都拥有设备资源；

组成：

输入井和输出井：在磁盘上开辟的2个大存储空间，模拟输入和输出设备；
输入缓冲区和输出缓冲区：内存中，输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井。输出缓冲区用于暂存从输出井送来的数据，以后再传送给输出设备。
输出进程SPi：模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井，当 CPU 需要输入数据时，直接从输入井读入内存。
输出进程SPo：模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井，待输出设备空闲，再将输出井的数据经过输出缓冲区送到输出设备上。

比如共享打印机场景中，利用SPOOLing技术可以将打印机改造成多个用户共享的设备，比如某一打印word的进程，调用了统一的接口，然后进入内核。内核例程负责将 word 想要打印的内容做成一个打印申请表，将这个申请表放入打印输出队列中（这个队列在输出井中）。然后由输出进程从打印队列中取打印申请表，根据表格内容将用户数据从磁盘中取出放入内存输出缓冲区，然后再输出到 I/O 设备中。输出进程会不断的查看打印输出队列，直到队列为空，则输出进程被阻塞。

特点：

提高了I／O的速度：缓和了CPU与低速I／O设备之间速度不匹配的矛盾
将独占设备改造为共享设备
实现了虚拟设备功能 SPOOLing系统实现了将独占设备变换为若干台对应的逻辑设备的功能

I/O设备调用

磁盘

原理

磁盘(disk) 的组成

包括一或多个物理盘片，每个磁盘片分一个或两个存储面(Cylinder)
每个磁头(Head)负责读写一条磁道，一般每条磁道又被逻辑上划分成8个扇区(Sector)
扇区是磁盘存储数据的最小单位，一般用逻辑块号(LBN)标识,每次读写至少一个扇区的数据；
块(block)是文件系统逻辑上的一段存储空间，通常具有整数个扇区；

下图是一个柱面和一面盘面的组成

块号=柱面号×柱面扇区数+磁头号×盘面扇区数+盘扇号;

柱面扇区数=盘面数×盘面扇区数；

柱面号=块号/柱面扇区数;

磁头号=块号MOD柱面扇区数 / 盘面扇区数;

扇区号=块号MOD柱面扇区数MOD盘面扇区数;

类型：读写前磁头必须位于磁道的开始处

固定头磁盘：每个磁道上有一个磁头，快。
移动头磁盘：每个盘面仅有一个磁头，慢。

磁盘性能参数

寻道时间Ts：磁头定位到磁道的时间，记磁盘启动时间为S，磁道数为n，则满足Ts=O(n)+S;

旋转延迟Tr：指定扇区旋转到磁头下的时间，若转速为r，则均值Tr=r/2；

存取时间：达到读写正确位置的时间，Ts+Tr;

传输时间Tt：磁头定位完成后，数据传输所用时间，读写字节数为b，每道上的字节数为N，Tt=b/rN;

访问时间：Ta=Ts+Tr+Tt,对于特定磁盘，只有集中存放数据，集中读写才能提高传输效率;

磁盘的I/O很慢，往往成为瓶颈，有如下方式提高磁盘I/O速度

提前读/延迟写：访问频率高的磁盘块放在替换队列的尾部，减少回写次数。
优化物理块分布：减少磁头移动距离，如簇分配就是将一个簇分为多个连续块
虚拟盘(RAM): 由用户控制；

磁盘高速缓存

磁盘高速缓存(disk cache)：形式上是磁盘，物理上是驻留在内存的盘块，大小可固定也可以设计为可变；

数据交付：磁盘高速缓存中的数据传送给请求者进程，先查缓存、后查磁盘并更新缓存，一般可分为数据交付和指针交付；
置换算法：应考虑局部性原理，访问频率，可预见性，数据一致性等原则，如最近最久未使用LRU，最近未使用NRU，最少未使用LFU等
周期性写回磁盘：比如以windows为例的ms-dos操作系统采用写穿透方式；

磁盘调度

为减小寻道时间，对于磁盘的请求队列来说，I/O请求可能来自多个进程，若随机从队列中选择项目，性能很差；

可设计如下算法：以请求序列为为190，97， 90，45，150，32，162， 108，112，80，磁盘共200个柱面，磁头现在在98号柱面上为例

先来先服务FCFS：根据进程请求访问磁盘的先后次序进行调度

公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况，但是平均寻道时间可能较长；
最短服务时间优先SSTF：总是从等待访问者中挑选寻找时间最短的那个请求先执行，而不管访问者到来的先后次序，可能由磁臂黏着现象；
电梯调度扫描SCAN

总是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近 的那个柱面的访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。
循环扫描CSACAN

该算法不考虑等待访问者的先后次序，总是从0号柱面开始向里扫描，按照各访问者所要访问的柱面位置的次序去选择访问者。移动臂到达最后一个柱面后，立即带动读写磁头快速返回到0号柱面。
N步扫描NStepSCAN

将磁盘请求队列分成若干个长度为N 的子队列，磁盘调度将按FCFS 算法依次处理这些子队列。而每处理一个队列时又是按SCAN 算法，对一个队列处理完后，再处理其他队列。
FSCAN

FSCAN 只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O 的进程形成的队列，由磁盘调度按SCAN 算法进行处理。在扫描期间，将新出现的所有请求磁盘I/O 的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理

设备管理接口

操作系统为设备管理定义两种接口:

驱动程序接口：介于驱动程序与操作系统内核之间的接口驱动程序模块及优化的管理模块接口，这些模块构成操作系统中的输入和输出内核,实现了对设备操作和控制，提高了对设备的利用率；
设备管理器：应用编程接口（API），即提供了一组函数，这组函数是用于为进程服务,实现用户输入输出意图；
- I/O设备的操作通过一组固定的入口点进行，这组入口点是指向每个设备驱动程序提供的一些子程序。服务于I/O请求的子程序，又称为I/O系统调用。
- 在不同的系统给出的调用的形式不一样
- 设备管理器包含有打开函数和关闭函数：打开函数能分配设备和初始化设备，以便做好对该设备使用的准备工作。关闭函数用于释放设备，则应由描述子反映出该设备不能被使用的状态。设备管理器提供读设备函数和写设备函数。

磁盘冗余阵列

它是利用一台磁盘阵列控制器，来统一管理和控制一组(几台到几十台)磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统。

并行交叉存取（条化存取）

系统将每一盘块中的数据分为若干个子盘块数据，再把每一个子盘块的数据分别存储到各个不同磁盘中的相同位置上；
当要将一个盘块的数据传送到内存时，采取并行传输方式，将各个盘块中的子盘块数据同时向内存中传输，从而使传输时间大大减少。

RAID0级：

无冗余，无校验，分布式存储，低可靠性，低价格
仅提供了并行交叉存取，它虽能有效地提高磁盘I/O 速度，但并无冗余校验功能，致使磁盘系统的可靠性不好。只要阵列中有一个磁盘损坏，便会造成不可弥补的数据丢失

RAID1级：

分布存放，镜像冗余，不校验
读性能比 RAID 0好 (选择寻道时间小的磁盘访问)，写性能比 RAID 0差，存储开销大，可靠性高

RAID2级：

采用海明码进行校验，每两块数据盘就有一块校验盘(海明校验码)：当数据损坏时通过校验码可恢复损坏磁盘上的数字，每次只能传输2路数据，因数据盘就两块。
可进行并存并取。

RAID 3 级

并行传输
存在奇偶校验盘来完成数据校验功能；
常用于科学计算和图像处理

RAID4级：

使用了独立访问技术，在独立访问阵列中，每个磁盘独立的运转，因此不同的I/O请求可以并行的得到满足

RAID 5 级：

这是一种具有独立传送功能的磁盘阵列。每个驱动器都各有自己独立的数据通路，独立进行读/写，且无专门的校验盘。
用来进行纠错的校验信息，是以螺旋(Spiral)方式散布在所有数据盘上。
RAID 5 级常用于 I/O 较频繁的事务处理中。

RAID 6 级和RAID 7 级。在 RAID 6 级的阵列中，设置了一个专用的、可快速访问的异步校验盘。该盘具有独立的数据访问通路，具有比RAID 3 级及RAID 5 级更好的性能，但其性能改进得很有限，且价格昂贵。RAID 7 级是对RAID 6 级的改进，在该阵列中的所有磁盘，都具有较高的传输速率和优异的性能。