操作系统教程：缓冲技术、驱动调度技术、设备分配、虚拟设备

5.4缓冲技术

5.4.1单缓冲5.4.2双缓冲5.4.3多缓冲5.4缓冲技术(1)

引入缓冲技术的目的

•改善中央处理器与外围设备之间速度不配的矛盾，

•协调逻辑记录大小与物理记录大小不一致，

•提高CPU和I/O设备的并行性。缓冲技术(2)

缓冲技术实现基本思想(1)进程执行写操作输出数据时，向系统申请一个缓冲区，若为顺序写请求，则不断把数据填到缓冲区，直到被装满。此后，进程继续它的计算，系统将缓冲区内容写到I/O设备上。进程执行操作输入数据时，向系统申请一个缓冲区，系统将一个物理记录的内容读到缓冲区，根据进程要求，把当前需要的逻辑记录从缓冲区中选出并传送给进程。缓冲技术(3)

缓冲技术实现基本思想(2)在输出数据时，只有在系统还来不及腾空缓冲而进程又要写数据时，它才需要等待；在输入数据时，仅当缓冲区空而进程又要从中读取数据时，它才被迫等待。

5.4.1单缓冲

对于块设备,单缓冲机制如下工作：数据处理过程数据处理时间约为max[C，T]+M，对于字符设备,单缓冲机制如下工作：数据处理过程5.4.2双缓冲(1)

输入数据时，首先填满缓冲区1,操作系统可从缓冲区1把数据送到用户进程区,用户进程便可对数据进行加工计算;与此同时，输入设备填充缓冲区2当缓冲区1空出后，输入设备再次向缓冲区1输入。操作系统又可把缓冲区2的数据传送到用户进程区,用户进程开始加工缓冲2的数据。双缓冲(2)

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

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

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

UnixI/O字符缓存队列

5.5驱动调度技术(1)

5.5.1存储设备的物理结构5.5.2循环排序5.5.3优化分布5.5.4交替地址5.5.5搜查定位5.5.6独立磁盘冗余阵列5.5.7提高磁盘I/O速度的一些方法

驱动调度技术(2)

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

顺序存取存储设备是严格依赖信息的物理位置进行定位和读写的存储设备具有存储容量大、稳定可靠、卷可装卸和便于保存等优点■始点块1间隙块2间隙块3间隙块i间隙块i+1■末点…

……

…磁头(正走,反走,正读,反读,正写,反写,倒带)存储设备的物理结构(2)

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

访问磁盘记录参数：柱面号、磁头号、块号查找时间：磁盘根据柱面号控制臂作机械横向移动，带动读写磁头到达指定柱面。搜索延迟：从磁头号可确定数据所在的盘面，等待被访问信息块旋转到读写头下，按块号进行存取。磁盘机实现些操作的通道命令是：查找、搜索、转移和读写。5.5.2循环排序(1)

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

（2）读记录3

（3）读记录2

（4）读记录1循环排序(2)

多种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.5.3优化分布(1)

信息在存储空间的排列方式会影响存取等待时间。考虑10个逻辑记录A，B……，J被存于旋转型设备上，每道存放10个记录，安排如下：物理块逻辑纪录

1-10A-J优化分布(2)

处理10个记录的总时间

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

＝214毫秒优化分布(2)

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

物理块逻辑纪录1A2

H3E4B5I6F7C8J9G10D优化分布(3)

处理10个记录的总时间为

10毫秒(移动到记录A的平均时间)+10×[2毫秒（读记录）×4毫秒（处理记录）]=70毫秒5.5.4交替地址

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

移臂调度有若干策略

(1)“电梯调度”算法

(2)“最短查找时间优先”算法

(3)“扫描”算法

(4)“分步扫描”算法

(5)“单向扫描”算法

搜查定位(2)

“电梯调度”算法(1)

选择沿臂的移动方向最近的柱面，如果同一柱面上有多个请求，还需进行旋转优化。如果这个方向没有访问请求时，就改变臂的移动方向，并使移动频率极小化，处理所迂到的最近的I/O请求，非常类似于电梯的调度规则。

搜查定位(3)

“电梯调度”算法(2)

电梯调度算法有等待请求?结束请求与当前柱面相同?处理有最近块号的请求启动CC是向里或向外移?是否否向外向里有比当前柱面小的请求?改变移动方向A有比当前柱面大的请求?改变移动方向否否处理大于当前柱面号请求中柱面号最小的请求B处理小于当前柱面号请求中的柱面号最大的请求移动磁头到指定柱面，登记当前位置启动CBBA搜查定位(4)

“最短查找时间优先”算法

本算法考虑了各个请求之间的区别，总是先执行查找时间最短的那个磁盘请求，从而，较“先来先服务”算法有较好的寻道性能。

搜查定位(5)

“扫描”算法

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

搜查定位(6)

“分步扫描”算法

将I/O请求分成组，每组不超过N个请求，每次选一个组进行扫描，处理完一组后再选下一组。搜查定位(7)

“循环扫描”算法

移动臂总从0号柱面至最大号柱面顺序扫描，然后，直接返回0号柱面重复进行，归途中不再服务，构成了一个循环。

搜查定位(8)

算法比较(1)

•

(1)(2)两种算法，单位时间内处理的I/O请求多即吞吐量大，但请求的等待时间较长。•“扫描”算法适宜于磁盘负载重的系统，它不分具体情况扫过所有柱面造成性能不够好。•“分步扫描”算法使得I/O请求等待时间之间的差距最小，吞吐量适中。搜查定位(9)

算法比较(2)

•“电梯调度”算法杜绝饥饿，性能适中。•“循环扫描”算法适应不断有大批量柱面均匀分布的I/O请求，且磁道上存放记录数量较大的情况。5.5.6独立磁盘冗余阵列(1)

独立磁盘冗余阵列是利用一台磁盘阵列控制器统一管理和控制一组磁盘驱动器,组成一个速度快、可靠性高、性能价格比好的大容量磁盘系统。RAID填补了CPU速度快与磁盘设备速度慢之间的间隙,其策略是:独立磁盘冗余阵列(2)

RAID共同特性

①RAID是一组物理磁盘驱动器，可被操作系统看作是单一逻辑磁盘驱动器;②数据被分布存储在阵列横跨的物理驱动器上;③冗余磁盘的作用是保存奇偶校验信息，当磁盘出现失误时它能确保数据的恢复。独立磁盘冗余阵列(3)

RAIDlevel0(1)数据划成条块被分布存储在横跨阵列中的所有磁盘上逻辑上连续的数据条块，在物理上可被依次存储在横向相邻的磁盘驱动器上通过阵列管理软件进行逻辑地址空间到物理地址空间的映射优点和缺点

独立磁盘冗余阵列(4)

Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10RAIDLevel0(2)

Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10DatamappingforaRAIDLevel0ArrayStrip0Strip1Strip2Strip3Strip4Strip5Strip6Strip7Strip8...ArrayManagementsoftware独立磁盘冗余阵列(5)RAIDlevel0(3)

独立磁盘冗余阵列(6)

RAIDlevel1(1)

双份数据，每个盘都有一个包含相同数据的镜像盘。

①读请求能通过包含相同请求数据中的任何一个磁盘提供服务，其中的一个所化查找和搜索时间最少;②写操作时，要求改写对应的两个数据子块，可采用并行操作，写操作的性能由并行操作中较慢的一个决定;③一个驱动器出现故障，数据可以从镜像盘获得。

Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Strip14Strip10RAIDLevel1(Mirrored)Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Strip14Strip10独立磁盘冗余阵列(7)

RAIDlevel1(2)

独立磁盘冗余阵列(8)

RAIDlevel2(1)

采用并行存取技术，驱动器的移动臂同步工作，每个磁盘的磁头都在相同位置。纠错码按照横跨的每个数据盘的相应位计算，并存储在多只奇偶校验盘的相应位的位置。奇偶校验磁盘的数量与数据盘的多少成比例。执行单个读操作时的操作：执行单个写请求时的操作：

b0b1b2b3f0(b)f1(b)f2(b)RAIDLevel2(RedundancythroughHammingCode)独立磁盘冗余阵列(9)

RAIDlevel2(2)

独立磁盘冗余阵列(10)

RAIDlevel3(1)

RAID3仅使用一只冗余盘，出现故障时，使用奇偶校验盘的信息校验，数据可用剩下的磁盘的信息重新构造，若X0到X3存放数据，X4为奇偶盘，对于第i位的奇偶校验位可如下计算:

X4(i)=X3(i)⊕X2(i)⊕X1(i)⊕X0(i)

假定驱动器X1出故障，如果把X4(i)，X1(i)加到上面等式两边，得到

X1(i)=X4(i)⊕X3(i)⊕X2(i)⊕X0(i)

b0b1b2b3P(b)RAIDLevel3(BitinterleavedParity)独立磁盘冗余阵列(11)

RAIDlevel3(2)

独立磁盘冗余阵列(12)

RAIDlevel4(1)

RAID4和RAID5使用独立存取技术，在一个独立存取的磁盘阵列中，每个驱动器都可以独立地工作，所以，独立的I/O请求可以被并行地得到满足。因此独立存取阵列适合于有频繁I/O请求的应用。

block0block4block8block12block1block5block9block13block3block7block15block11block2block6block14block10P(0-3)P(4-7)90P(8-11)P(12-15)RAIDLevel4(BlocklevelParity)独立磁盘冗余阵列(13)

RAIDlevel4(2)

独立磁盘冗余阵列(14)

RAIDlevel4(3)

每当执行一个小数据量写操作时，阵列管理软件不旦要修改用户数据，而且也要修改对应的奇偶校验位。

独立磁盘冗余阵列(15)

RAIDlevel4(4)考虑驱动器阵列，X0到X3存储数据，X4是奇偶校验磁盘。假如执行一个涉及磁盘X1上数据的写操作。开始对每个二进位i，有下列关系式:

X4(i)=X3(i)⊕X2(i)⊕X1(i)⊕X0(i)

在数据修改之后，对于改变了的二进位用’符号来指出，得到:

独立磁盘冗余阵列(16)

RAIDlevel4(5)X4’(i)=X3(i)⊕X2(i)⊕X1’(i)⊕X0(i)=X3(i)⊕X2(i)⊕X1’(i)⊕X0(i)⊕X1(i)⊕X1(i)=X4(i)⊕X1(i)⊕X1’(i)

为计算新的奇偶校验位，必须读出老的用户数据子块和老的奇偶校验码，每个数据写操作包含了两次读操作和两次写操作。独立磁盘冗余阵列(17)

RAIDlevel5(1)

RAID5的奇偶校验码是分布横跨轮转存放在所有的磁盘上，设有n个磁盘的阵列，则开头的n个奇偶校验码螺旋式地位于n个磁盘上，能避免RAID4发生的奇偶校验盘瓶颈口问题。

独立磁盘冗余阵列(18)

RAIDlevel5(2)block0block4block8block12block1block5block9P(12-15)block3P(4-7)block14block10block2block6block13P(8-11)P(0-3)block7Block11Block15block0block4block8block12RAIDLevel5(BlocklevelDistributedparity)独立磁盘冗余阵列(19)

RAIDlevel6和RAIDlevel7

增强型RAID。RAID6中设置了专用快速的异步校验磁盘，具有独立的数据访问通路，比低级RAID性能更好，但价格昂贵。RAID7对RAID6作了改进，该阵列中的所有磁盘都有较高传输速率，性能优异，但价格也很高。5.5.7提高磁盘I/O速度的方法

提前读。延迟写。虚拟盘。5.6设备分配

5.6.1设备独立性5.6.2设备分配

5.6.1设备独立性(1)

通常用户不指定特定的设备，而指定逻辑设备，使得用户作业和物理设备独立开来，再通过其它途径建立逻辑设备和物理设备之间的对应关系，称这种特性为“设备独立性”。设备独立性(2)

设备独立性带来的好处用户与物理的外围设备无关，系统增减或变更外围设备时程序不必修改；易于对付输入输出设备的故障。5.6.2设备分配(1)

从设备的特性来看，可以把设备分成独占设备、共享设备和虚拟设备三类：相应的管理和分配外围设备的技术可分成：独占方式、共享方式和虚拟方式。设备分配(2)

常用的I/O设备分配算法先请求先服务，优先级高者先服务等。此外，在多进程请求I/O设备分配时，应防止因循环等待对方所占用的设备而产生死锁，应预先进行性检查。设备分配(3)

I/O设备分配的实现(1)设备分配的数据结构：设备类表和设备表。系统中拥有一张设备类表，每类设备对应于表中一栏，包括内容有：设备类、总台数、空闲台数和设备表起始地址等。每一类设备都有各自的设备表，用来登记这类设备中每一台设备的状态，包含的内容有：物理设备名、逻辑设备名、占有设备的进程号、已分配/未分配、好/坏等。设备分配(4)

I/O设备分配的实现(2)采用通道结构的系统中，设备分配的数据结构设置：系统设备表、通道控制表、控制器控制表和设备控制表。系统建立一张系统设备表，记录配置在系统中的所有物理设备的情况。每个通道、控制器、设备各设置一张表，记录各自的地址(标识符)、状态(忙/闲)、等待获得此部件的进程队列指针、及一次分配后相互勾链的指针，