ch5-5.4缓冲技术5.5驱动调度技术5.6设备分配5.7虚拟设备1

1、 减少对CPU的中断频率， 放宽对CPU中断响应时间的限制。 缓冲区有不同的类型：1.单缓冲2.双缓冲3.循环缓冲：空缓冲区、装满数据的缓冲区4.缓冲池：空缓冲区、装满输入数据的缓冲区、装满输出数据的缓冲区单缓冲工作区处理(C)缓冲区传送(M)输入(T)I/O设备(a)T1M1C1T2M2C2T3M3C3T4t(b)用户进程2. 双缓冲双缓冲(Double Buffer) 工作区用户进程缓冲区1缓冲区2I/O 设备T1(缓冲1)M1C1M2C2M3C3T2(缓冲2)T3(缓冲3)M4C4T4(缓冲4)(a)(b)图 5-12 双缓冲工作示意图 1. 循环缓冲的组成循环缓冲的组成 图 5-14

2、循环缓冲 RGGGRG165423NextiNextgRGGGRC165423NextiNextgcurrent 对于磁盘,同时会有若干个输入输出请求来到并等待处理,系统必须采用一种调度策略,能按最佳次序执行要求访问的各个请求,这就叫驱动调度,使用的算法叫驱动调度算法 驱动调度能减少为若干个I/O请求服务所需的总时间，提高系统效率、除了I/O请求的优化排序外，信息在辅助存储器上的排列方式，存储空间分配方法都能影响存取访问速度.始点块1间隙块2间隙块3间隙块i间隙块i+1末点 磁头(正走,反走,正读,反读,正写,反写,倒带)盘片盘片磁道磁道轴轴磁头磁头移动臂移动臂柱面柱面1. 数据的组织和格式数

3、据的组织和格式 Gap102031292293Field GapField GapGap FieldGap FieldGap17741515201774151520IDDataIDDataGap1292293Field GapField1774151520IDDataSectorPhysical Sector 0Physical Sector 1Physical Sector 29BytesSynchByteTrack#Head#Sector#Bytes 1211CRC3SynchByteDataCRC15122600 Bytes/SectorGap图 5-22 磁盘的格式化 2. 磁盘的类型

4、磁盘的类型 1) 固定头磁盘 这种磁盘在每条磁道上都有一读/写磁头，所有的磁头都被装在一刚性磁臂中。通过这些磁头可访问所有各磁道，并进行并行读/写，有效地提高了磁盘的I/O速度。 这种结构的磁盘主要用于大容量磁盘上。 2) 移动头磁盘 每一个盘面仅配有一个磁头，也被装入磁臂中。为能访问该盘面上的所有磁道，该磁头必须能移动以进行寻道。可见，移动磁头仅能以串行方式读/写，致使其I/O速度较慢；但由于其结构简单， 故仍广泛应用于中小型磁盘设备中。 3. 磁盘访问时间磁盘访问时间 1) 寻道时间Ts 这是指把磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时

5、间之和， 即Ts=mn+s其中，m是一常数，与磁盘驱动器的速度有关，对一般磁盘， m=0.2；对高速磁盘，m0.1,磁臂的启动时间约为2 ms。 这样，对一般的温盘， 其寻道时间将随寻道距离的增加而增大， 大体上是530 ms。 2) 旋转延迟时间T 这是指定扇区移动到磁头下面所经历的时间。对于硬盘，典型的旋转速度大多为5400 r/min，每转需时11.1 ms，平均旋转延迟时间T为5.55 ms；对于软盘，其旋转速度为300 r/min或600 r/min，这样，平均T为50100 ms。 3) 传输时间Tt 这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。 Tt的大小与每次所读/写的

6、字节数b和旋转速度有关： rNbTt其中，r为磁盘每秒钟的转数；N为一条磁道上的字节数， 当一次读/写的字节数相当于半条磁道上的字节数时，Tt与T相同， 因此， 可将访问时间Ta表示为： rNbrTTsa21考虑磁道保存4个记录的旋转型设备，假定收到四个I/O请求（旋转一周耗时20ms）。 请求次序 记录号 （1） 读记录4 （2） 读记录3 （3） 读记录2 （4） 读记录1方法1：按照I/O请求次序读记录4、3、2、1，平均用1/2周定位，再加上1/4周读出记录，总处理时间等于1/2+1/4+3*3/4=3周，即60毫秒。定位并读出记录4需要1/2+1/4毫秒,读出记录4后,磁盘已经旋转到

7、记录1,再旋转2/4周,到达记录3,再旋转1/4周,读出记录3.同理,读出记录3后,磁盘旋转到记录4,再旋转3/4周,读出记录2.读出记录1也需要3/4周时间.1234 方法2：如果次序为读记录1、2、3、4。总处理时间等于1/2+1/4+3*1/4=1.5周，即30毫秒。定位并读出记录1需要1/2+1/4周时间,读出记录1后,磁盘已经旋转到纪录2,定位并读出纪录2的时间是1/4周,定位并读出纪录3和记录4的时间也都是1/4周.1234方法3：如果知道当前读位置是记录3，则采用次序为读记录4、1、2、3。总处理时间等于周，即20毫秒。如果知道当前读位置是记录3,则不必花费平均1/2周去寻找某个

8、记录.因为当前的读位置是记录3,所以只需旋转1/4周即可读出记录4,然后再旋转1/4周即可读出记录1,旋转一周可读出4个记录.信息在存储空间的排列方式会影响存取等待时间。考虑10个逻辑记录A，B，J被存于旋转型设备上，每道存放10个记录，安排如下： 物理块 逻辑纪录 1-10 A-J假定旋转速度为20ms/周,处理程序读出每个记录后花4ms进行处理.则读出记录A需要旋转20/10=2ms,即旋转一个扇区,处理完记录A之后磁盘又旋转了B、C两个扇区(因为处理每个记录需4ms时间),将转到记录D的开始.所以为了读出B,必须再转一周.从D开始旋转到B开始共有8个扇区,需耗时16ms.处理10个记录的

9、总时间 ：10毫秒(移动到记录A的平均时间)+ 2毫秒(读记录A)+4毫秒(处理记录A)+916毫秒(访问下一记录) +2毫秒(读记录)+4毫秒(处理记录) 214毫秒ABCDEFGHIJ按照下面方式对信息优化分布AHEBIFCJGD则读出记录A并处理结束后,恰巧转至记录B的位置,立即就可读出并处理.除了记录A需要1/2周(10ms)旋转寻道时间外,其它9个记录没有旋转寻道时间.10个记录都需要2ms的读出一个扇区的时间和4ms的处理时间.处理10个记录的总时间 ：10毫秒(移动到记录A的平均时间)+102毫秒（读记录）+4毫秒（处理记录）= 70毫秒本算法不会导致某一个进程的请求长期得不到满

10、足，产生饥饿电梯调度算法有等待请求?结束请求与当前 柱面相同?处理有最近块号的请求启动C CC C是向里或向外移?是否否向外向里有比当前柱面小的请求?改变移动方向A A有比当前柱面大的请求?改变移动方向否否处理大于当前柱面号请求中柱面号最小的请求CB处理小于当前柱面号请求中的柱面号最大的请求移动磁头到指定柱面，登记当前位置启动C CB BB BA A举例：假定磁头正从100号磁道开始，向磁道号增加方向移动，这时9个进程先后提出访问以下磁道：55、58、39、18、90、160、150、38、184，则按电梯调度算法进行调度的过程如下：183839555890100150160184电梯算法存在

11、一种现象：当磁头刚从里向外越过某个磁道时，恰好又有一个进程请求访问该磁道时.，必须等待，磁头移到最外层然后再返回来处理了其他磁道后才能处理它，导致该进程的请求被长时间延迟最短寻道时间优先最短寻道时间优先SSTF(Shortest Seek Time First) 图 5-24 SSTF调度算法 SCAN算法 图 5-25 SCAN调度算法示例N很大时性能接近电梯算法N很小时蜕化为FCFS算法4. 循环扫描循环扫描(CSCAN)算法算法 图 5-26 CSCAN调度算法示例Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip

12、3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10RAID Level 0(2)Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10Data mapping for a RAID Level0 ArrayStrip0Strip1Strip2Strip3Strip4Strip5Strip6Strip7Strip8.ArrayManagementsoftware独

13、立磁盘冗余阵列(5) RAID level 0(3) RAID level 0(3)Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10具有最好的读写性能和最低的成本磁盘的利用率是100%安全性最低不存储校验信息Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Strip14Strip10RA

14、ID Level 1 (Mirrored)Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Strip14Strip10独立磁盘冗余阵列(7) RAID level 1(2)RAID level 1(2)b0b1b2b3f0(b)f1(b)f2(b)RAID Level 2 (Redundancy through Hamming Code)独立磁盘冗余阵列(9) RAID level 2(2)RAID level 2(2) b0b1b2b3P(b) RAID Level

15、 3 (Bit interleaved Parity)独立磁盘冗余阵列(11) RAID level 3(2) RAID level 3(2)block0block4block8block12block1block5block9block13block3block7block15block11block2block6block14block10P(0-3)P(4-7)90P(8-11)P(12-15)RAID Level 4 (Block level Parity)独立磁盘冗余阵列(13) RAID level 4(2)block0block4block8block12block1block5

16、block9P(12-15)block3P(4-7)block14block10block2block6block13P(8-11)P(0-3)block7Block11Block15block0block4block8block12RAID Level 5 (Block level Distributed parity)5.4.4 独占设备的分配程序独占设备的分配程序 1. 基本的设备分配程序基本的设备分配程序 1) 分配设备 2) 分配控制器 3) 分配通道 处理器内存I/O设备I/O设备I/O设备I/O设备I/O设备通道控制器通道控制器控制器控制器2. 设备分配程序的改进设备分配程序的改进 1) 增加设备的独立性 2) 考虑多通路情况 模拟脱机输出时的外围控制机，将用户要求输出的数据，先从内存送到输出井，待输出设备空闲时，再将输出井中的数据送到输出设备上。预输入程序作业1信息作业n信息输入井作业1结果作业n结果输出井缓输出程序井管理程序运行作业输入设备输出设备作业调度程序斯普林系统的设计和实现(2) SPOOLING组成和结构 SPOOLing技术可以将本属于独占设备的打印机改造成为可供多个用户使用的共享设备。其原理如下：当用户进程请求打印输出时， SPOOLing同意为它打印输