OSIDP-I/O管理和磁盘调度-11

I/O设备

I/O设备分类：人可读、机器可读和远程通信三类。

I/O设备之间的差别：

1.数据传送速率

2.应用领域

3.控制的复杂性

4.传送单位

5.数据表示形式

6.错误条件

I/O功能的组织

I/O的三种技术

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

2.中断驱动I/O：处理器代表一个进程给I/O模块发送I/O命令，若该命令是非阻塞的，则发送命令的进程继续执行；若是阻塞的，则 OS 将该进程阻塞，执行另外的进程。

3.直接存储器访问(DMA)：处理器向DMA模块发I/O命令，DMA模块控制内存和I/O模块之间的数据交换。当I/O操作执行完成后，DMA模块向处理器发信号告知执行完成。

I/O功能的发展

1.处理器直接控制I/O设备，处理器需要知道I/O设备的细节。

2.I/O模块出现，处理器通过程序控制I/O，不需要知道I/O设备细节。

3.处理器通过中断方式控制I/O。

4.DMA模块出现，处理器通过DMA模块控制I/O，仅在I/O传输的整个过程中的前后两个时间点处理器才和DMA模块交互。

5.I/O模块有自己的处理器，专门的指令集。CPU指导I/O处理器交互。

6.I/O模块有自己的局部存储器，I/O传输过程中CPU参与度更低。

DMA的执行过程：
1.CPU向DMA通过两者之间的读写控制线发送请求读操作或者写操作信号。
2.相关的I/O设备地址通过数据线传送。
3.从内存读数据或者向内存写数据的起始地址通过数据线传送，DMA将该地址存入地址寄存器中。
4.读或者写的的数据通过数据线传送，保存在其数据寄存器中；读或者写的数据的多少（读或者写数据的以字为单位的数目）保存在其数据计数寄存器中。
5.传送完毕，DMA模块向CPU发送中断信号告知已完成数据传送任务。

DMA在计算机系统中的可能架构：

OS 设计问题

目标：效率和通用性。

I/O操作一般是计算机系统的瓶颈。

通用性分两点：1.处理器看待I/O设备的方式；2.OS 管理I/O设备和I/O操作的方式。

I/O的逻辑结构如下

逻辑I/O：将设备当作一个进程可以使用的资源，允许使用通用的读写命令操控。

设备I/O：发出请求的指令和传输的设备在此转换成适当的I/O指令序列等。

调度和控制：实际和硬件打交道的层，处理中断，执行实际操作。

通信架构：比如网络传输的实际四层架构(TCP/IP)就属于这一层。

目录管理：用标识符表示文件，同时可以使用简单的命令操控文件。

文件系统：处理文件的逻辑结构和用户的操作。

物理组织：文件的逻辑结构到物理结构的转换。

I/O 缓冲

单进程死锁：当一个进程发出一个I/O请求后，被挂起等待结果，在开始I/O操作之前被换出，该进程阻塞，等待I/O事件的发生。此时I/O操作也被阻塞，等待该进程被换入。

原文：

If a process issues an I/O command, is suspended awaiting the result, and then is swapped out prior to the beginning of the operation, the process is blocked

waiting on the I/O event, and the I/O operation is blocked waiting for the process to be swapped in.

解决办法：发出I/O请求前，参与I/O操作的内存中用户进程空间被锁定。

I/O设备

面向块：信息保存在固定大小的块中，传输以块为单位。

面向流：以字节流的方式传输数据。

缓冲：输入（I/O设备到内存的数据传送）请求发出前开始执行输入传送，在输出请求发出一段时间后开始执行输出传送的技术。

单缓冲：OS 在内存的系统区域分配一个区域，称为缓冲区。当输入时，数据先传输到该缓冲区，再从缓冲区传输到用户进程的内存区域中。输出时反过来。

双缓冲：和单缓冲相比，有两个缓冲区，可以在一个进程向缓冲区中传送数据时，OS正在填充（清空）另一个缓冲区。这种方式也称缓冲交换。

循环缓冲：和双缓冲类似，使用的缓冲区大于2个。类似于有限缓冲区的生产者消费者模型。

缓冲作用：平滑I/O需求的峰值，提高 OS 效率和单个进程性能。

磁盘调度

性能参数

寻道时间：磁头定位到磁盘需要的时间。

旋转延迟：磁头到达扇区开始位置需要的时间。

存取时间：寻道时间+旋转延迟。达到读或者写位置需要的时间。

\(传输时间=\frac{传送的字节数}{一个磁道中的字节数 \times 旋转速度}\)

磁盘调度策略：

1.FIFO：最简单，公平。适用于大部分请求访问的文件处于簇聚扇区。

2.优先级：较短的作业优先级较高，长作业优先级较低。不会优化磁盘的利用率。

3.后进先出(LIFO)：提高吞吐量，缩短队列长度。

4.最短服务时间优先：选择使磁头从当前位置移动距离最短的磁盘I/O请求。

5.SCAN(电梯算法)：磁头从一个方向移动，处理完遇到的请求（该方向上没有待处理的请求了）或者到达该方向的边界时，反转，继续按此方式移动。

6.C-SCAN(循环SCAN)：磁头扫描固定在一个方向上。

7.N步SCAN：将磁盘请求队列分成长度为N的子队列，每次使用SCAN处理一个队列，此时新的请求加入其他队列中。

8.FSCAN：扫描开始时，所有请求处于一个队列中。当处理过程中，新请求到来，则加入另一个空队列中，直到队列处理完成。

RAID

RAID(redundant array of independent disks, RAID)称为独立磁盘冗余阵列。分为0-6共7个级别。三个特性：
1.RAID是一组物理磁盘驱动器，逻辑上视为一个。
2.数据分布在物理驱动器阵列中。
3.使用冗余磁盘保存奇偶校验信息，保证一个磁盘失效时，数据具有可恢复性。

RAID0

数据被视为保存在一个逻辑磁盘上，磁盘被划分为多个条带，一个条带可以为一个物理块、扇区或者其他某种单位。

优点：若一个I/O请求由多个逻辑上连续的条带组成，则请求可并行，减少传输时间。

RAID1

RAID1通过临时复制所有数据实现冗余。

优点：读请求可由包含被请求数据的任何一个磁盘提供服务；写请求需要对两个条带进行更新，可并行完成；从失效中恢复简单。

缺点：成本高。

RAID2

使用的条带很小，只有1个字节或者字。对每个数据磁盘中相应位计算机一个错误校正码（通常是汉明码），计算得到的码保存在多个奇偶校验磁盘对应的位中。

缺点：成本高。

优点：在可能发生许多磁盘错误的环境中是一种有效的选择。

RAID3

只需要一个冗余磁盘，为所有数据磁盘同一位置的位的集合计算一个简单的奇偶校验位。

优点：数据传送率高。

RAID4

数据条带较大。对每个数据磁盘中相应的条带计算一个逐位奇偶校验，保存在奇偶校验磁盘的相应条带中。

优点：适合需要I/O请求速度较高的进程。

缺点：不适合需要较高数据传输率的进程；写操作包含奇偶校验磁盘，该磁盘可能成为瓶颈。

RAID5

将奇偶校验条带分布到所有磁盘中，按照循环分配方式。

优点：避免单个奇偶校验磁盘存在的瓶颈问题。

RAID6

需要的磁盘数为N+2，N为数据磁盘。使用两个不同的数据校验算法：异或计算和独立数据校验算法。

优点：提高极高的数据可用性。

缺点：严重的写性能损失。

磁盘高速缓存

磁盘高速缓存是内存中为磁盘扇区设置的一个缓冲区，包含磁盘中某些扇区的副本。

命中时，两种方式：第一种，将缓冲区扇区复制到用户进程空间内存区域；第二种，将指向缓冲区的特定扇区的指针传给特定进程。

置换策略

1.最近最少使用(LRU)：置换在高速缓存中未被访问的时间最长的块。

2.最长不常使用页面置换算法(least frequently used, LFU)：置换缓冲区中访问次数最少的块。

3.基于频率的置换算法：将缓冲区逻辑上视为栈，将栈的区域按照离栈顶的距离划分成三部分。离栈顶最近为新区，其次为中间区，最远为老区。新块进入缓冲区时进入栈顶，访问计数为1。新区中的块被访问，计数不变，其他区访问计数随之增加。同时，被置换的块只能在老区选择，置换时选择访问计数最小的块。

巴特西