操作系统(11) I/O管理和磁盘调度_操作系统磁盘调度scan改进型

1. I/O设备

1.1 I/O设备简介

• I/O设备(外部设备)：与用户交互的打印机和终端等；数据 存储与通信的磁盘、USB设备、控制器、网络设备等。
• 各种设备的数据传输率 、传输单位、数据编码方式、可能 的错误和处理等有很大差异
• 每个设备通过各自的设备控制器与总线、CPU、内存相连

1.2 I/O功能的组织-四种技术

• 程序控制I/O:CPU忙等I/O结束,串行工作
• 中断驱动I/O:各种设备通用，中断次数多，CPU负担重
• 直接存储器访问DMA:速度快，数据量大，在完成一个数据块的I/O之后，向CPU发出一次中断，中断次数少。适合于磁盘、网络接口等I/O
• 通道Channel:比DMA效率更高，通道具有自己的指令系统和专用的I/O处理器，专门完成I/O操作
  • CPU发出I/O指令，I/O过程由通道程序控制
  • 通道程序中包含多条通道指令,每条通道指令完成一个连续内存区的I/O。通道在完成多个数据块的I/O之后，才向CPU一次中断

1.3 中断驱动I/O

• 中断驱动I/O:设备每I/O完一批字(这个一批的数量由设备控制器的数据缓冲区长度来决定)后，以中断请求方式通知CPU，再由CPU把这些字送入内存，然后设备再I/O下一批字
• 中断可以使I/O设备之间、I/O设备与CPU之间并行操作。但中断种类和次数太多时，CPU的负担重。
  

1.4 直接存储器访问DMA(Direct Memory Access)

• 直接存储器访问DMA:在内存和设备间直接进行块传送，仅在传送开始和结束时才需要CPU的干预，整块数据的传送是在DMA控制器的控制下完成的
• 通过窃取总线周期:在争用总线的时候，DMA控制器的优先级比CPU要高。
  
• DMA工作原理和过程:
  • CPU向DMA控制器发出I/O数据块的指令:
    • <读/写操作、源/目的地址、传送字(节)数>
  • 发出数据传送请求的进程阻塞，CPU调度其他进程
  • 由DMA控制器完成设备的一个连续数据块与一个连续内存区之间的直接传送(不断地抢占总线，挪用CPU工作周期，将缓冲中的数据写入内存单元，或从内存单元读出到写缓冲)，传送字节数递减至0
  • 一个数据块I/O结束后，DMA向CPU发出中断请求
  • 发出数据传送请求的进程就被唤醒
• I/O效率高，DMA传送时，CPU执行效率略降低

课后习题1.8： CPU以每秒100万次的速度取指令。一个 DMA模块从外设向内存传送字符(字节)，传送速度为 9600 bps。由于DMA活动，CPU的速度将减慢多少？
答:首先CPU以每秒10^6次的频率取指令,也就是一微秒访问一次内存,传送速度为9600 bit per second,也就是1200 Byte per second(1200Bps),那么其就会在第(1/1200) = 833微秒的时刻占用一次总线,则CPU减慢约(1/833)=0.12% (注:这是因为原本如果没有DMA存在的话，这第833us的时刻依然是给CPU用的，但是现在是给DMA抢占了，就因此而变慢了)

对磁盘可采用DMA I/O控制方式，对打印机、键盘等大多数设备可以采用什么I/O控制方式？
中断驱动的I/O方式

1.5 操作系统设计问题

• 设计目标
  • 效率:I/O设备的性能经常成为系统性能的瓶颈
    • 解决:多道程序设计,不同I/O设备并行工作
    • 特别需要提高效率和速度的设备是磁盘
  • 通用性:以统一的方式处理所有设备
    • 设备驱动程序向OS隐藏了设备的细节和差异
    • I/O系统调用向应用程序隐藏了不同设备的差异，各种设备和文件都用open(),read(),close(),write()等api进行操作

1.6 Buffer

• 缓存(Buffer):在设备间或设备与程序间传输时， 用来保存数据的内存区域或设备专用缓冲
  • 内存公用缓冲池由OS划分、分配、回收、管理
  • 设备的专用缓冲由设备控制器管理。
• 单缓冲(不实用)
  
  数据送到工作区之后，开始下一次缓冲输入。
  其问题在于，当缓冲区非空的时候，就不IO，当缓冲区是空的时候才IO，当读取速度和写入速度几乎一致的时候，可以说是串行执行的。
• 双缓冲(不实用)
  
  当生产者和消费者速度基本匹配时， 两个缓冲交替使用。
• 循环缓冲－生产者/消费者的有界缓冲
  
• 实际上，以上介绍的三种缓冲模型都是不实用的，现代OS采取的缓冲模型为:内存的公用缓冲池，在内存中事先设置一个缓冲池，包含有一批buffer，任何进程需要用时申请、分配、用完后释放、回收。
• 缓冲的作用
  • 缓和CPU与I/O设备间速度不匹配矛盾，提高并行性
  • 协调设备数据大小的差异(如逻辑记录与磁盘块大小不一致的问题)
  • 减少对CPU的中断频率，放宽响应时间限制
    • 从远程终端来的数据仅用一位缓冲来接收，若通信速率为9600bps，则中断CPU的频率=9600Hz，即约 100μs中断一次，且CPU必须在100μs内响应，否则可能导致数据丢失
    • 若设置一个8位的缓冲，则中断频率降为原来的1/8， 但响应时间仍只有100μs。
    • 若再增设一8位的缓冲，则响应时间放宽到900μs。
      

2. 磁盘调度

2.1 磁盘简介

• 性能:磁盘访问速度(ms)要远远慢于CPU和内存速度(ns)
• 磁盘的物理结构
  
  可以使得磁盘移动次数减少的原因是，当扫描同一柱面，不同磁道，这些磁道上的信息可以被同步扫描，有时候只需要扫描半圈，四分一圈，…就能够获取一个完整的文件信息，当分布在同一个磁道上的时候，可能需要扫描完整整一圈
• 扇区地址
  • 驱动器号
  • 柱面号
  • 磁头号（盘面号）
  • 扇区号
• 磁盘调度
  • 扇区是最小寻址单位和存取单位(但不是分配单位)
  • 分配磁盘空间以盘块(簇) 为单位,1盘块 = 2^n扇区
  • 一磁道内扇区数可能固定或不固定，但数据传输率 （kb/s）应保持恒定。
    

2.2 磁盘性能参数

磁盘访问时间包括如下三部分：Ta=Ts+Tr+Tt

• 寻道时间 Ts = 启动磁盘时间+横跨n条磁道时间
  • 目前，典型的磁盘平均寻道时间Ts小于10ms。
• 旋转延迟时间 Tr = 将待访问扇区转到磁头下的时间
  • 若15000转/分钟，则每转 4ms，Tr平均约2ms。
  • 计算一转要多久:60/15000=0.004=4ms
• 传输时间
  • $$Tt=\frac{读写字节数b}{旋转速度r\ast 每磁道字节数N}$$
  • 若每磁道 500扇区，则每扇区需 0.008ms。
• 其中，寻道时间对磁盘访问时间影响最大

2.3 磁盘调度策略

• 磁盘调度:调整多个磁盘访问请求的服务顺序， 以降低平均磁盘服务时间
• 磁盘调度算法减少的是磁头移动距离(寻道时间)
• 4种磁盘调度算法：
  • 先进先出(FIFO, First-In-First-Out)
  • 最短服务时间优先算法(SSTF, Shortest Service Time First)
  • SCAN扫描算法
  • C-SCAN 循环扫描算法

2.4 FIFO

• 先进先出(FIFO)：按请求的接收顺序服务

例：磁头现位于100# 磁道。收到9个磁盘访问请求， 请求顺序为 55, 58, 39, 18, 90, 160, 150, 38, 184

磁头共移动498条磁道，平均寻道长度=498/9=55.3

• 后进先出(LIFO)：先处理最新提出的请求。 事务处理时，读取文件具有局部性，LIFO可减少 磁臂移动，提高吞吐量。但先提出的请求会饥饿。

2.5 SSTF

• 最短服务时间优先算法(SSTF)：也称最短寻道时间优先算法。优先选择距当前磁头位置最近的访问请求进行服务。

例：磁头现位于100# 磁道。请求顺序为 184, 55, 58, 39, 18, 90, 160, 150, 38

磁头共移动248条磁道，平均寻道长度=27.5

2.6 SCAN

• SCAN扫描算法：也称电梯算法。选择位于磁头移动方向前方且距磁头位置最近的访问请求进行服务。 当前方没有访问请求时，立即改变磁头移动方向 (LOOK)；或继续扫描到磁盘边界后再转向(SCAN)。

例：磁头现位于100# 磁道。请求顺序为 184, 55, 58, 39, 18, 90, 160, 150, 38

• 电梯LOOK被普遍采用。是对SCAN的改进。 SCAN偏爱靠近磁盘边界处的请求，对最近横跨过的区域不公平

2.7 C-SCAN

• C-SCAN 循环扫描算法：磁头从磁盘一端移到另 一端，随着移动而不断处理请求。当磁头移到另一端时，马上返回磁盘起始，返回时不处理请求。
  
  注:这里根据书本上的描述应该是说扫描到这个方向上的最后一个请求就转向，磁头就转向到另一个方向上的第一个请求，然后继续扫描。

1、以下算法中，可能出现饥饿现象的是 。(B)
A.电梯调度 B. 最短服务时间优先 C. 循环扫描算法 D. 先来先服务
2、下列算法中，用于磁盘调度的是 。 ©
A. RR B. LRU C. SSTF D. 优先级
3、对于可随机访问的Flash半导体存储器，例如 U盘和固态硬盘，可以采用什么调度策略来处理 I/O请求？
Flash半导体存储器的物理结构不需要考虑寻道时间 和旋转延迟，故采用先来先服务策略更高效

3. RAID-独立磁盘冗余阵列(Redundant Array of Independent Disk)

3.1 RAID简介

• RAID用多个小容量磁盘代替单个大容量磁盘。 优势是：增加数据容量，多个磁盘并行I/O可提高 速度，设置冗余磁盘可提高可靠性

  • RAID是一组磁盘阵列，但OS视作为一个整体
  • 数据以"条带化" 方式存储在磁盘阵列中
  • 除数据盘，另有冗余磁盘保存（奇偶）校验信息，作为校验盘，在某个磁盘失效时用于恢复数据

• RAID级别:0~6,常用的RAID有0、1、5、6

3.2 三个关键技术

• RAID中的磁盘条带化
  • 将N个(一组)磁盘看作为一个存储部件。将每个数据盘块分为几个子块(条带strip)
• RAID中的并行访问
  • 读时,N个磁盘并行地读写各个子块。磁盘数据传输率提高了N-1倍
    
    也就是将原本的读写时间切分给了N个磁盘，这N个磁盘里面，有一个磁盘等价于原本的磁盘读写，其他N-1个磁盘是新增进来的，因此说速率是提高了N-1倍
• RAID中的块交叉检验技术
  • 在磁盘条带化的基础上，在每组磁盘中设置一个校验盘，该盘上任一位的内容为组中其余所有数据盘同一位的校验(如奇偶校验)
  • 在写组中任一数据盘中的任一块的时候，都要计算新的校验并写入校验盘的相同块
  • 当一个数据盘出故障时，可以根据其余数据盘和校验盘的内容，计算并恢复故障盘内容
    

3.3 RAID级别0~1

• RAID0:无冗余的并行访问,只实现条带化和并行访问。 容量大，快，不容错， 不可靠
  
  RAID1:可并行访问的镜像磁盘(复制每个磁盘)。 容量大，快，可靠，但磁盘数太多
  
  RAID2:位汉明校验。条带单位是字节或字
  
  RAID3:位交错奇偶校验。条带单位是字节或字。
  
  RAID4:块奇偶校验。校验盘负担重。
  
  RAID5:块分布奇偶校验。校验块分散到各磁盘
  
  RAID6:P+Q 双重冗余。允许两个磁盘错误
  

课后习题11.12：有一个RAID磁盘阵列，包含4个磁盘， 每个磁盘200GB。当RAID级别分别为0、1、3、4、5、 6时，该磁盘阵列的有效存储容量是多少？

4. 虚拟设备和假脱机SPOOLing技术

4.1 为什么需要实现虚拟设备

• 独占设备的静态分配方式不利于提高系统效率
• 虚拟设备：将一台独占设备经SPOOLing技术改造成虚拟的共享设备，供多个进程使用。
• 利用磁盘进行“假脱机SPOOLing操作”，实现：
  • 预输入：作业运行前预先将数据输入到磁盘的“输 入井”中，运行时直接取用；
  • 缓输出：作业的运行结果先保存到磁盘的“输出井” 中，稍后成批输出到输出设备
• 用户请求打印时，SPOOLing系统将数据送到磁盘的输出 （system32\spool目录）上，排入请求打印队列中。待 打印机空闲时，按先入先出顺序打印。

1、SPOOLing技术的主要目的是 (D)。
A.提高CPU和和设备交换数据的速度
B. 减轻用户编程负担
C. 提供主存、辅存接口
D. 提高独占设备的利用率
2、采用SPOOLing技术时，用户的打印数据首先 被送到(A)
A. 磁盘固定区域 B. 内存固定区域 C. 终端 D. 打印机

5. 磁盘高速缓存－内存缓冲池

• 磁盘高速缓存：在内存公用缓冲池中，为磁盘扇区(块) 分配一个缓冲，包含磁盘中某些扇区(块)的副本
• 当要求访问某一特定扇区(块)时，先查找其是否已在 磁盘高速缓存中。若在(命中)则直接访问，若不在则 从磁盘读到内存的一个缓冲buffer中

6.UNIX SVR4操作系统的I/O

• UNIX的缓冲池例子：缓冲区高速缓存buffer cache。 UNIX在内存建立数据缓冲区(缓冲池，称为块高速缓 存)，用于保存最近使用过的磁盘数据块
• 所有缓冲被组织在两种双向链接循环队列中
  • 散列队列：按设备号和块号，将缓冲buffer散列
  • 空闲链表：保存缓冲buffer最近将被再次分配的次序
• 当进程请求从指定文件读写数据时，根据给定的设备 号和盘块号，从散列队列中快速查询该块是否已在缓 冲buffer中。若在则立即获得其内容；
• 如果不在buffer中，则从磁盘上读数据，并分配一个 空闲buffer保存其内容，并链入相应散列队列。
• 当进程关闭文件时，可采用策略(如LRU)把这些空闲 buffer链在空闲链表中。于是，最不可能被再次访问 的buffer（位于空闲链首）将被最先分配
• 空闲链表中的数据被延迟写磁盘，需再次分配该空闲 块时才写回磁盘，或定期调用sync将空闲块成批写回 磁盘。（采用“延迟写”“成批写”来减少I/O开销）

7. Linux操作系统的I/O

• Linux2.4采用电梯调度算法。Linux 2.6增加以下两种算法：
• 时限调度算法：
  • 有3个队列：电梯排序队列、读FIFO队列、写FIFO队列。 读（写）请求被同时放入电梯队列和读（写）FIFO队列。 处理完后从两个队列中同时移出。
  • 读请求时限0.5s，写请求时限5s。
  • 平常按电梯算法调度。但当FIFO队列首请求已超过时限时， 就按该队列处理请求。防止“饥饿”。
• 预期调度算法：可显著缩短有大量磁盘请求时的I/O时间
  • 处理一个读请求后，延迟若干毫秒再进行下次调度。目的是希 望在延迟时段内，会发生和刚才的读请求邻近的读请求