操作系统：I/O子系统

I/O特点

常见的I/O系统有三类：

• 字符设备

这些设备的访问特征是以字节为单位顺序访问，例如键盘、鼠标、串口等。这些设备的I/O命令是get(),put()。设备通常被封装为文件，提供API接口。

• 块设备

块设备以基本数据块为单位传输数据，例如磁盘、软盘、网络硬盘等。

• 网络设备

由于网络通信比较复杂(前面的文章提到过，网络架构有7层)，网络设备的交互比较复杂，通常是以格式化的报文交换形式进行，I/O命令通常为send(),receive()。常见的网络设备有以太网、无线、蓝牙等。

从I/O通信是否阻塞可以将I/O分为阻塞I/O,非阻塞I/O,异步I/O。以异步I/O为例，信息传递过程为

用户I/O请求 --> 设备驱动 --> 硬件控制数据传输 --> 设备驱动 --> 用户

这是一个即时过程，内核立即返回给用户而不等待数据传输完成，而是使用指针标记好用户缓冲区。当数据传输完成时，

硬件控制数据传送 --> 中断处理 --> 设备驱动 --> 用户

I/O结构

从硬件上看，北桥通常有内存、内置显卡，南桥通常有PCI总线，USB等。CPU通过特殊的指令来控制I/O硬件，访问方式主要是通过特殊的I/O指令或者内存映射I/O(设备的寄存器/存储被映射到内存物理地址空间)。

I/O结构分为一下几层：

不同的设备 --> 不同的设备控制器 --> 不同的软件驱动 --> 操作系统的I/O子系统 --> 内核

一个常见的I/O请求周期如下图所示:

I/O数据传输

I/O数据传输方式主要分为4种：

• 程序控制I/O(PIO)

通过CPU的in/out或者load/store传输所有的数据。因为数据传输直接由CPU负责，因此实现PIO编程容易，硬件简单，但是数据量越大，消耗CPU时间越多，常常用于低速的字符设备，诸如鼠标等。

• 直接内存访问(DMA)

控制器直接与内存互相传输数据，因此设备传输不影响CPU。这种方式适合大量数据传输，诸如块设备。

• 轮询

I/O设备在特定的状态寄存器中存放位置信息和错误信息，操作系统定期检查这些变量。由于检查时间有间隔与不确定性，这导致数据传输具有不确定性，并且处理突发情况的能力较弱。

• 设备中断

CPU在I/O之前设置参数, I/O设备在处理数据传输完成之后，触发CPU中断请求。这种方式可以很好处理不可预测事件，但是需要CPU参与。

实际应用中，通常是这些方式的混合。例如高速宽带网络对于第一个传入的数据包采用设备中断方式，后面的数据包则采用轮询。

磁盘调度

磁盘I/O传输事件决定于下面的耗时：

• 等待设备可用
• 等待通道可用
• 寻道时间
• 旋转延时
• 数据传输

通常最耗时间的部分是寻道。通过优化磁盘访问请求顺序，可以大大缩短寻道时间。磁盘优化的前提是同时有多个在同一磁盘上的I/O请求。

• FIFO算法

这种算法按先到先处理的方式依次为每个I/O请求寻道。这种方式公平性好但是寻道接近随机访问，性能比较差。

• 最短服务时间优先(SSTF)

在访问一个请求后，访问与这个请求最近的磁道。这种方式可以缩短整体的寻道时间，但是每次需要计算磁道距离。

• 扫描算法

为了克服SSTF的缺陷，扫描算法的磁臂在一个方向上移动，访问所有未完成的请求，直到磁臂到达改变方向上最后的位置。类似的算法还有循环扫描算法。

• N步扫描算法

如果大量的I/O请求都集中在某一磁道区域，扫描算法可能导致磁臂一直停留在这个区域，导致其它部分的I/O请求得不到处理。这种现象叫做磁头粘着(arm stickiness)。一个解决方案是将磁盘队列分成每个长度为N的子队列，对于每个队列使用扫描算法，按顺序处理每个队列。

• 双队列扫描

另一种方法是制作两个队列：新队列与旧队列。将新的I/O请求放置到新队列，处理完旧队列后再处理新队列。

磁盘缓存

缓存是为了数据传输双方数据不匹配时，引入数据匹配中间层。缓存与分层是计算机科学家解决复杂问题的两大利器。

磁盘缓存是将磁盘数据放在内存中，这个恰好与虚拟内存相反。但是由于磁盘的访问频率远远小于内存，因此磁盘缓存算法要比虚拟内存算法复杂。

单缓存

单缓存只是用一个缓存区，由于对于缓存区，读写不能同时进行，因此可能导致一个延时。

双缓存

为了解决这个问题，可以采用双缓存方式，让读写可以同时进行：

磁盘缓存置换算法(Frequency-based Replacement)
置换算法的思想是对于密集的引用不计数。

栈顶 | 新区域 | 中间区域 | 旧区域 | 栈底

在新区域中，引用计数不变。而在中间区域与旧区域中，引用计数每次增加1。当有新的访问时，将数据放入栈顶，同时选择旧区域中引用计数最小的出栈。