设备管理（二）

目录

5.3 缓冲技术

• 单缓冲
• 双缓冲
• 多缓冲

5.4 驱动调度技术

• 存储设备的物理结构
• 循环排序
• 优化分布
• 搜查定位
• 提高磁盘I/O速度的方法
• Linux磁盘I/O调度算法

---

缓冲技术

引入缓冲技术的目的：

• 改善中央处理器与外围设备之间速度不配的矛盾，
• 协调逻辑记录大小与物理记录大小不一致，
• 提高CPU和I/O设备的并行性。

缓冲技术实现的基本思想

1. 进程执行写操作输出数据时，向系统申请一个缓冲区，若为顺序写请求，则不断把数据填到缓冲区，直到被装满。此后，进程继续它的计算，系统将缓冲区内容写到I/O设备上。

2. 进程执行操作输入数据时，向系统申请一个缓冲区，系统将一个物理记录的内容读到缓冲区，根据进程要求，把当前需要的逻辑记录从缓冲区中选出并传送给进程。

3. 在输出数据时，只有在系统还来不及腾空缓冲而进程又要写数据时，它才需要等待；

4. 在输入数据时，仅当缓冲区空而进程又要从中读取数据时，它才被迫等待。

5.3.1 单缓冲
对于块设备，单缓冲机制如下工作：

image.png

5.3.2 双缓冲

输入数据时，首先填满缓冲区1,操作系统可从缓冲区1把数据送到用户进程区,用户进程便可对数据进行加工计算;与此同时，输入设备填充缓冲区2。

当缓冲区1空出后，输入设备再次向缓冲区1输入。操作系统又可把缓冲区2的数据传送到用户进程区,用户进程开始加工缓冲2的数据。

传输和处理一块的时间

• 如果C<T
  由于M远小于T，在将磁盘上的一块数据传送到缓冲区其间，计算机已完成将另一个缓冲区中的数据传送到用户区并对这块数据进行计算的工作。一块数据的传输和处理时间为T、即max(C,T)，显然，这种情况下可保证块设备连续工作。

• 如果C>T
  当上一块数据计算完毕后，需把一个缓冲区中的数据传送到用户区，花费时间为M，再对这块数据进行计算，花费时间为C，
  所以，一块数据的传输和处理时间为C+M、即max(C,T)+M，这种情况下进程不必要等待I/O。

  
  image.png

5.3.3 多缓冲

操作系统从内存区域中分配一组缓冲区组成循环缓冲，每个缓冲区的大小等于物理记录的大小。多缓冲的缓冲区是系统的公共资源，可供各个进程共享，并由系统统一分配和管理。
缓冲区可用途分为:

• 输入缓冲区
• 处理缓冲区

• 输出缓冲区。

  
  image.png

5.3.4 缓冲区高速缓存

操作系统建立页高速缓存。每当应用进程打开、关闭或撤销文件时，激活高速缓存管理程序管理文件的数据块。其实现思想如下。

1. 当请求从指定文件读写数据时，给定设备号和磁盘块号，快速查询所需数据块是否在页高速缓存中，如果在，是在哪个缓冲区并获得其内容。可设计散列表来快速访问缓冲区，散列数组的每个元素指向一个缓冲区链表，把具有相同散列值的磁盘块链接在一起。
2. 高速缓存中的每个缓冲区链表都有一个缓冲控制块，包含如下信息：逻辑设备号、磁盘块号、高速缓存虚拟地址、数据所属文件的文件描述符、数据在文件内的位移、缓冲区链接指针、空闲缓冲区指针、活动计数 、状态字等。
3. 若数据块不在高速缓存中，就从磁盘读取数据，并将其缓存，系统要把尽可能多的数据保存在缓冲区高速缓存。向磁盘写入数据也暂存于数据缓冲区高速缓存中，供回写磁盘前再次使用。内核需判定数据是否需要回写，或是否很快就要被回写，采用延迟写减少I／O 操作。
4. 当文件关闭或撤销时，需要解决缓冲区释放和重用问题，可采用一定策略 （如LRU） 把单独的缓冲区链接在一起，于是，最不可能被再次访问的缓冲区将被最先释放重用。
5. 提供一组高速缓存操作，为文件驱动程序实现读写文件数据。这些操作通常有：写缓存、延迟写缓存、读缓存、预读缓存等。

---

5.4 驱动调度技术

驱动调度能减少为若干个I/O请求服务所需的总时间，提高系统效率、除了I/O请求的优化排序外，信息在辅助存储器上的排列方式，存储空间分配方法都能影响存取访问速度。

5.4.1 存储设备的物理结构

顺序存取存储设备是严格依赖信息的物理位置进行定位和读写的存储设备 ，具有存储容量大、稳定可靠、卷可装卸和便于保存等优点 。

直接存取存储设备

磁盘是一种直接(随机)存取存储设备。每个物理记录有确定的位置和唯一的地址，存取任何一个物理块所需的时间几乎不依赖于此信息的位置。
访问磁盘记录参数：柱面号、磁头号、块号

image.png

5.4.2 循环排序

考虑磁道保存4个记录的旋转型设备，假定收到四个I/O请求：
请求次序 记录号
（1） 读记录4
（2） 读记录3
（3） 读记录2
（4） 读记录1

image.png

多种I/O请求排序方法

方法1：按照I/O请求次序读记录4、3、2、1，平均用1/2周定位，再加上1/4周读出记录，总处理时间等于3周，即60毫秒。
方法2：如果次序为读记录1、2、3、4。总处理时间等于1.5周，即30毫秒。
方法3：如果知道当前读位置是记录3，则采用次序为读记录4、1、2、3。总处理时间等于１周，即20毫秒。

5.4.3 优化分布
考虑10个逻辑记录A，B……，J被存于旋转型设备上，每道存放10个记录，安排如下：

image.png

处理10个记录的总时间 :

10毫秒(移动到记录A的平均时间)+ 2毫秒(读记录A)+4毫秒(处理记录A)+9×[16毫秒(访问下一记录) +2毫秒(读记录)+4毫秒(处理记录)] ＝214毫秒

按照下面方式对信息优化分布：

image.png

处理10个记录的总时间为：
10毫秒(移动到记录A的平均时间)+10×[2毫秒（读记录）×4毫秒（处理记录）]
=70毫秒

5.4.4 交替地址

每个记录重复记录在设备的多个区域，读相同的数据，有几个交替地址，也称为多重副本或折迭。
成功与否取决于下列因素：数据记录总是读出使用，不需修改写入；数据记录占用的存储空间总量不太大；数据使用极为频繁。

5.4.5 搜查定位

移臂调度有若干策略
(1)“先来先服务” 算法
(2)“最短查找时间优先”算法
(3)“扫描”算法
(4)“分步扫描”算法
(5)“电梯调度”算法
(6)“循环扫描”算法
举例：假如磁盘机共有200个柱面，编号0至199，考虑依次到达下列柱面访问请求序列：
150，30，190，20，100，55，90
同时假磁头当前处于50号柱面位置，且正在向柱面号大的方向移动。

• “先来先服务”算法
  磁盘臂是随机移动的，不考虑各 I／ O 请求间的相对次序和移动臂当前所处位置，进程等待 I／O 请求时间会很长，寻道性能较差。
  移动臂移动柱面总=710。
  image.png
• “最短查找时间优先”算法
  考虑 I／O 请求之间的区别，总是先执行查找时间最短的请求，与FIFO 算法相比有较好寻道性能。

移动臂移动柱面总=210。

image.png

• “扫描”算法
  磁盘臂每次沿一个方向移动，扫过所有柱面，遇到最近的I/O请求便进行处理，直到最后一个柱面后，再向相反方向移动回来。
  移动臂移动柱面总数=328
  

  image.png

• “分布扫描”算法
  进程重复请求访问同一柱面会垄断设备，造成“磁臂粘性”，导致其他柱面访问请求长时间得不到服务，采用“分步扫描”算法可以避免这类问题。具体做法是：将 I／O 请求分为长度为N的子队列，按FIFO算法依次处理每个子队列，而每个子队列采用扫描算法，处理完一个后再服务下一个子队列，以避免出现磁臂粘住现象。这种调度算法能保证每个I/O请求的等待时间不致太长，当 N 值很大时，接近于“扫描”算法性能；当N＝１时，接近于 FIFO算法性能。

• “电梯调度”算法
  “电梯调度”算法 （elevator algorithm）又称LOCK算法，是如扫描算法的一种改进，无访问请求时，移动臂停止不动，有访问请求时，移动臂按电梯规律移动。
  移动臂移动柱面总数=310。
  

  image.png

• “循环扫描”算法
  为适应有大量柱面均匀分布的存取请求进入系统而设计的扫描方式。移动臂总是从０柱面至最大号柱面顺序扫描，然后，直接返回０柱面重复进行，归途中不再提供服务，构成一个循环，缩短处理新来请求的最大延迟。
  移动臂移动柱面总数=378。
  

  image.png

5.4.5 提高磁盘I/O速度的方法

• 提前读
• 延迟写
• 虚拟盘
  Linux提供两种读盘和三种写盘方式：正常读-把磁盘块信息块读入内存缓冲区；提前读-读磁盘当前块时，下一磁盘块也读入内存缓冲区；正常写-把内存缓冲区中的信息写到磁盘块，且写进程应等待写操作完成；
  异步写-写进程无需等待写盘结束就可返回工作；
  延迟写-仅在缓冲区首部设置延迟写标志，然后，释放此缓冲区，并把该缓冲区链入空闲缓冲区链表的尾部，当其他进程申请到该缓冲区时，才真正把缓冲区信息写回磁盘块。

---