ch缓冲技术驱动调技术设备分配虚拟设备实用实用教案

1、缓冲技术缓冲技术(2)(2)缓冲技术实现缓冲技术实现(shxin)(shxin)基基本思想本思想 进程执行写操作输出数据时，向系统申请一个缓冲区，若为顺序写请求，则不断把数据填到缓冲区，直到被装满。此后，进程继续它的计算，系统将缓冲区内容写到I/O设备上。 进程执行操作输入(shr)数据时，向系统申请一个缓冲区，系统将一个物理记录的内容读到缓冲区，根据进程要求，把当前需要的逻辑记录从缓冲区中选出并传送给进程。 在输出数据时，只有在系统还来不及腾空缓冲而进程又要写数据时，它才需要等待； 在输入(shr)数据时，仅当缓冲区空而进程又要从中读取数据时，它才被迫等待。 第1页/共48页第一页，共49页

2、。5.4.1 5.4.1 单缓冲单缓冲(hunchng)(hunchng) 对于块设备,单缓冲机制如下工作： 数据处理过程 数据处理时间(shjin)约为maxC，T+M， 进程 系统 设备 TMC第2页/共48页第二页，共49页。5.4.2 5.4.2 双缓冲双缓冲(hunchng)(1)(hunchng)(1) 输入数据时，首先(shuxin)填满缓冲区1,操作系统可从缓冲区1把数据送到用户进程区,用户进程便可对数据进行加工计算;与此同时，输入设备填充缓冲区2 当缓冲区1空出后，输入设备再次向缓冲区1输入。操作系统又可把缓冲区2的数据传送到用户进程区,用户进程开始加工缓冲2的数据。 第3页

3、/共48页第三页，共49页。双缓冲双缓冲(hunchng)(2)(hunchng)(2) 传输和处理一块的时间(1)如果CT，当上一块数据计算完毕后，需把一个缓冲区中的数据传送到用户区，花费时间为M，再对这块数据进行(jnxng)计算，花费时间为C，所以，一块数据的传输和处理时间为C+M、即max(C,T)+M，这种情况下进程不必要等待I/O。第5页/共48页第五页，共49页。双缓冲双缓冲(hunchng)(4)(hunchng)(4) 进程 系统 设备 (1)CT，MT, MT max(C,T)+M=C+M，保证(bozhng)进程不等I/O。CMT第6页/共48页第六页，共49页。5.4.

4、3 5.4.3 多缓冲多缓冲(hunchng)(1)(hunchng)(1) 操作系统从主存区域(qy)中分配一组缓冲区组成循环缓冲，每个缓冲区的大小等于物理记录的大小。多缓冲的缓冲区是系统的公共资源，可供各个进程共享，并由系统统一分配和管理。 缓冲区可用途分为：输入缓冲区，处理缓冲区和输出缓冲区。 第7页/共48页第七页，共49页。5.5 5.5 驱动驱动(q dn)(q dn)调度技调度技术术(1)(1)5.5.1 存储设备的物理(wl)结构 5.5.2 循环排序 5.5.3 优化分布5.5.4 搜查定位 5.5.5 独立磁盘冗余阵列 5.5.6 提高磁盘I/O速度的一些方法 第8页/共4

5、8页第八页，共49页。 驱动调度驱动调度(diod)(diod)技术技术(2)(2) 驱动调度和驱动调度算法。 驱动调度能减少(jinsho)为若干个I/O请求服务所需的总时间，提高系统效率、除了I/O请求的优化排序外，信息在辅助存储器上的排列方式，存储空间分配方法都能影响存取访问速度。第9页/共48页第九页，共49页。5.5.1 5.5.1 存储设备的物理存储设备的物理(wl)(wl)结构结构(1)(1) 顺序存取存储设备是严格依赖信息的物理位置进行定位和读写的存储设备 具有存储容量(cn ch rn lin)大、稳定可靠、卷可装卸和便于保存等优点 始点块1间隙块2间隙块3间隙块i间隙块i+

6、1末点 磁头(正走,反走,正读,反读,正写,反写,倒带)第10页/共48页第十页，共49页。存储设备的物理存储设备的物理(wl)(wl)结结构构(2)(2)直接存取存储设备直接存取存储设备 磁盘是一种直接(随机)存取存储设备。每个物理记录有确定的位置和唯一的地址，存取任何一个物理块所需的时间几乎不依赖于此信息的位置。 访问磁盘记录参数(cnsh)：柱面号、磁头号、块号第11页/共48页第十一页，共49页。5.5.25.5.2循环循环(xnhun)(xnhun)排序排序(1)(1) 考虑磁道保存4个记录的旋转(xunzhun)型设备，假定收到四个I/O请求。 请求次序 记录号 （1） 读记录4

7、（2） 读记录3 （3） 读记录2 （4） 读记录11234第12页/共48页第十二页，共49页。循环排序循环排序(pi x)(2)(pi x)(2)多种多种I/OI/O请求排序请求排序(pi x)(pi x)方法方法 方法1：按照I/O请求次序读记录4、3、2、1，平均用1/2周定位，再加上1/4周读出记录，总处理(chl)时间等于3周，即60毫秒。 方法2：如果次序为读记录1、2、3、4。总处理(chl)时间等于1.5周，即30毫秒。 方法3：如果知道当前读位置是记录3，则采用次序为读记录4、1、2、3。总处理(chl)时间等于周，即20毫秒。第13页/共48页第十三页，共49页。5.5.

8、3 5.5.3 优化分布优化分布(fnb)(1)(fnb)(1) 考虑10个逻辑记录A，B，J被存于旋转型设备上，每道存放10个记录，安排如下： 物理块 逻辑纪录 1-10 A-J (A B C D E .) 处理10个记录的总时间 10毫秒(移动到记录A的平均(pngjn)时间)+ 2毫秒(读记录A)+4毫秒(处理记录A)+916毫秒(访问下一记录) +2毫秒(读记录)+4毫秒(处理记录) 214毫秒 第14页/共48页第十四页，共49页。优化分布优化分布(2)(2)按照下面方式按照下面方式(fngsh)(fngsh)对对信息优化分布信息优化分布物理(wl)块 逻辑纪录1 A2 H3 E4

9、B5 I6 F7 C8 J9 G10 D第15页/共48页第十五页，共49页。优化分布优化分布(3)(3)处理处理(chl)10(chl)10个记录的个记录的总时间为总时间为 10毫秒(移动到记录(jl)A的平均时间)+102毫秒（读记录(jl)）4毫秒（处理记录(jl)） =70毫秒第16页/共48页第十六页，共49页。5.5.4 5.5.4 交替交替(jiot)(jiot)地址地址 每个记录重复记录在设备的多个区域(qy)，读相同的数据，有几个交替地址，也称为多重副本或折迭。 成功与否取决于下列因素：数据记录总是读出使用，不需修改写入；数据记录占用的存储空间总量不太大；数据使用极为频繁。第

10、17页/共48页第十七页，共49页。5.5.5 5.5.5 搜查搜查(such)(such)定位定位(1)(1)移臂调度(diod)有若干策略 (1)“电梯调度(diod)”算法 (2)“最短查找时间优先”算法 (3)“扫描”算法 (4)“分步扫描”算法 (5)“单向扫描”算法 第18页/共48页第十八页，共49页。搜查搜查(such)(such)定位定位(2) (2) “电梯调度电梯调度”算法算法 电梯调度算法有等待请求?结束请求与当前 柱面相同?处理有最近块号的请求启动C CC C是向里或向外移?是否否向外向里有比当前柱面小的请求?改变移动方向A A有比当前柱面大的请求?改变移动方向否否处

11、理大于当前柱面号请求中柱面号最小的请求处理小于当前柱面号请求中的柱面号最大的请求移动磁头到指定柱面，登记当前位置启动C CB BB BA A第19页/共48页第十九页，共49页。搜查定位搜查定位(dngwi)(4) (dngwi)(4) “最短查找时间优先最短查找时间优先”算法算法 本算法考虑了各个请求之间的本算法考虑了各个请求之间的区别，总是先执行查找时间最区别，总是先执行查找时间最短的那个磁盘请求，从而，较短的那个磁盘请求，从而，较“先来先服务先来先服务(fw)”(fw)”算法算法有较好的寻道性能。有较好的寻道性能。 第20页/共48页第二十页，共49页。搜查定位搜查定位(dngwi)(5

12、) (dngwi)(5) “扫描扫描”算法算法 磁盘臂每次沿一个方向移动，磁盘臂每次沿一个方向移动，扫过所有柱面，遇到扫过所有柱面，遇到(y do)(y do)最近的最近的I/OI/O请求便进行处理，直请求便进行处理，直到最后一个柱面后，再向相反到最后一个柱面后，再向相反方向移动回来。方向移动回来。 第21页/共48页第二十一页，共49页。搜查搜查(such)(such)定位定位(6) (6) “分步扫描分步扫描 ” ”算法算法 将将I/OI/O请求分成组，每组不超过请求分成组，每组不超过(chogu)N(chogu)N个请求，每次选一个请求，每次选一个组进行扫描，处理完一组后再个组进行扫描，

13、处理完一组后再选下一组。选下一组。 第22页/共48页第二十二页，共49页。搜查定位搜查定位(7) (7) “循环扫描循环扫描(somio)”(somio)”算法算法 移动臂总从移动臂总从0 0号柱面至最大号柱号柱面至最大号柱面顺序扫描，然后，直接返回面顺序扫描，然后，直接返回0 0号柱面重复进行，归途中不再服号柱面重复进行，归途中不再服务务(fw)(fw)，构成了一个循环。，构成了一个循环。 第23页/共48页第二十三页，共49页。5.5.6 5.5.6 独立独立(dl)(dl)磁盘冗余阵列磁盘冗余阵列(1)(1) 独立磁盘冗余(rn y)阵列是利用一台磁盘阵列控制器统一管理和控制一组磁盘驱

14、动器,组成一个速度快 、可靠性高、性能价格比好的大容量磁盘系统。 RAID填补CPU速度快与磁盘设备速度慢之间的间隙,其策略是:第24页/共48页第二十四页，共49页。独立磁盘冗余阵列独立磁盘冗余阵列(zhn (zhn li)(2) li)(2) RAIDRAID共同特性共同特性 RAID是一组物理磁盘驱动器，可被操作系统看作是单一逻辑磁盘驱动器; 数据被分布存储(cn ch)在阵列横跨的物理驱动器上; 冗余磁盘的作用是保存奇偶校验信息，当磁盘出现失误时它能确保数据的恢复。 第25页/共48页第二十五页，共49页。 独立磁盘冗余(rn y)阵列(3) Strip0Strip4Strip8Str

15、ip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10RAID Level 0(1)第26页/共48页第二十六页，共49页。 Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10Data mapping for a RAID Level0 ArrayStrip0Strip1Strip

16、2Strip3Strip4Strip5Strip6Strip7Strip8. . . .ArrayManagementsoftware独立(dl)磁盘冗余阵列(4) RAID level 0(2)第27页/共48页第二十七页，共49页。 RAID Level 1 (Mirrored)Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Strip14Strip10Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3

17、Strip7Strip15Strip11Strip2Strip6Strip14Strip10独立磁盘冗余(rn y)阵列(5) RAID level 1第28页/共48页第二十八页，共49页。 b0b1b2b3f0(b)f1(b)f2(b)RAID Level 2 (Redundancy through Hamming Code)独立磁盘冗余(rn y)阵列(6) RAID level 2第29页/共48页第二十九页，共49页。 b0b1b2b3P(b) RAID Level 3 (Bit interleaved Parity)独立磁盘(c pn)冗余阵列(7) RAID level 3第30

18、页/共48页第三十页，共49页。 block0block4block8block12block1block5block9block13block3block7block15block11block2block6block14block10P(0-3)P(4-7)90P(8-11)P(12-15)RAID Level 4 (Block level Parity)独立(dl)磁盘冗余阵列(8) RAID level 4第31页/共48页第三十一页，共49页。 独立磁盘(c pn)冗余阵列(9) RAID level 5block0block4block8block12block1block5blo

19、ck9P(12-15)block3P(4-7)block14block10block2block6block13P(8-11)P(0-3)block7Block11Block15block0block4block8block12RAID Level 5 (Block level Distributed parity)第32页/共48页第三十二页，共49页。5.5.65.5.6提高磁盘提高磁盘I/OI/O速度速度(sd)(sd)的方法的方法 提前读 延迟写 虚拟盘 UNIX/Linux提供两种读盘和三种写盘方式： 正常读-把磁盘块信息块读入主存缓冲区； 提前读-读磁盘当前块时，下一磁盘块也读入主

20、存缓冲区； 正常写-把主存缓冲区中的信息写到磁盘块，且写进程应等待写操作完成； 异步写-写进程无需等待写盘结束就可返回工作； 延 迟 写 - 仅 在 缓 冲 区 首 部 设 置 延 迟 写 标 志(biozh)，然后，释放此缓冲区，并把该缓冲区链入空闲缓冲区链表的尾部，当其他进程申请到该缓冲区时，才真正把缓冲区信息写回磁盘块。第33页/共48页第三十三页，共49页。5.6 5.6 设备设备(shbi)(shbi)分配分配 5.6.1 设备独立性5.6.2 设备分配(fnpi)和设备分配(fnpi)数据结构 第34页/共48页第三十四页，共49页。5.6.1 5.6.1 设备设备(shbi)(s

21、hbi)独立性独立性 通常用户不指定特定的设备，而指定逻辑设备，使得用户作业和物理设备独立开来，再通过其它途径建立逻辑设备和物理设备之间的对应关系，称这种特性为“设备独立性”。 设备独立性带来的好处 用户与物理的外围设备无关(wgun)，系统增减或变更外围设备时程序不必修改；易于对付输入输出设备的故障。第35页/共48页第三十五页，共49页。5.6.2 5.6.2 设备设备(shbi)(shbi)分配分配(1)(1) 从设备的特性来看，可以把设备分成(fn chn)独占设备、共享设备和虚拟设备三类： 相应的管理和分配外围设备的技术可分成(fn chn)：独占方式、共享方式和虚拟方式 。 常用的

22、I/O设备分配算法 先请求先服务，优先级高者先服务等。此外，在多进程请求I/O设备分配时，应防止因循环等待对方所占用的设备而产生死锁，应预先进行性检查。第36页/共48页第三十六页，共49页。设备设备(shbi)(shbi)分配分配(2)(2)I/OI/O设备设备(shbi)(shbi)分配的实现分配的实现(1)(1) 设备分配的数据结构：设备类表和设备表。 系统中拥有一张设备类表，每类设备对应于表中一栏，包括内容有：设备类、总台数、空闲台数和设备表起始地址等。 每一类设备都有各自的设备表，用来登记这类设备中每一台设备的状态，包含(bohn)的内容有：物理设备名、逻辑设备名、占有设备的进程号、

23、已分配/未分配、好/坏等。第37页/共48页第三十七页，共49页。设备分配设备分配(fnpi)(3)(fnpi)(3)I/OI/O设备分配设备分配(fnpi)(fnpi)的实的实现现(2)(2) 采用通道结构的系统中，设备分配的数据结构设置：系统设备表、通道控制表、控制器控制表和设备控制表。 系统建立一张系统设备表，记录配置在系统中的所有物理设备的情况。 每个通道、控制器、设备各设置一张表，记录各自的地址(标识符)、状态(zhungti)(忙/闲)、等待获得此部件的进程队列指针、及一次分配后相互勾链的指针，以备分配和执行I/O时使用。第38页/共48页第三十八页，共49页。5.7 5.7 虚拟

24、虚拟(xn)(xn)设备设备5.7.1 问题(wnt)的提出 5.7.2 SPOOLING的设计和实现 5.7.3 SPOOLING应用例子 第39页/共48页第三十九页，共49页。5.7.15.7.1问题问题(wnt)(wnt)的提出的提出 静态分配方式是不利于提高系统效率 采用脱机外围设备操作（SPOOLING）联机同时(tngsh)外围设备操作(又称作假脱机操作) 第40页/共48页第四十页，共49页。5.7.2 5.7.2 斯普林系统斯普林系统(xtng)(xtng)的设计和实现的设计和实现(1)(1) “井”是用作缓冲的存储区域，采用井的技术能调节(tioji)供求之间的矛盾，消除人

25、工干预带来的损失。 “预输入程序” “缓输出程序” “井管理程序”第41页/共48页第四十一页，共49页。 预输入程序作业1信息作业n信息输入井作业1结果作业n结果输出井缓输出程序井管理程序运行作业输入设备输出设备作业调度程序斯普林系统(xtng)的设计和实现(2) SPOOLING组成和结构 第42页/共48页第四十二页，共49页。斯普林系统斯普林系统(xtng)(xtng)的设的设计和实现计和实现(3)(3)输入井中作业状态输入井中作业状态 输入状态：作业信息正在从输入设备上预输入； 收容收态：作业预输入结束，但未被选中执行(zhxng)； 执 行 ( z h x n g ) 状 态 ： 正 在 执 行(zhxng)，可读数据也可以写数据； 完成状态：作业已经撤离，结果等待输出。第43页/共48页第四十三页，共49页。斯普林系统的设计和实现斯普林系统的设计和实现(shxin)(4)(shxin)(4)SPOOLINGSPOOLING数据结构数据结构 作业表 登记进入系统的所有作业的作业名、状态、预输入表位置等信息。预输入表 每个用户作业有一张用来登记该作业的各个文件的情况，包括设备类、信息长度(chngd)及存放位置等。缓输出表 每个用户作业