操作系统第八章设备与IO管理

《操作系统第八章设备与IO管理》由会员分享，可在线阅读，更多相关《操作系统第八章设备与IO管理（98页珍藏版）》请在装配图网上搜索。

1、第八章第八章 设备与设备与I/O管理管理n设备及其分类设备及其分类n设备的物理特性设备的物理特性nIO传输方式（查询、中断、通道、传输方式（查询、中断、通道、DMA）n设备分配与去配设备分配与去配n设备驱动设备驱动n设备调度设备调度n缓冲技术缓冲技术n输入输出进程输入输出进程nRAID技术技术n虚拟设备虚拟设备8.1 设备及其分类设备及其分类n用途用途n存储型设备存储型设备n磁盘，磁带，光盘磁盘，磁带，光盘nIO型设备型设备n扫描仪，打印机，扫描仪，打印机，mouse，keyboard，monitor，n网络设备网络设备n网卡，交换机，网卡，交换机，etc.8.1 设备及其分类设备及其分类n管

2、理管理n共享型设备（块型）共享型设备（块型）n多个进程的多个进程的IO操作以块为单位可以交叉操作以块为单位可以交叉n独占型设备（块型）独占型设备（块型）n多个进程的多个进程的IO操作以块为单位不宜交叉操作以块为单位不宜交叉n独占型设备（字符型）独占型设备（字符型）n多个进程的多个进程的IO操作以字符为单位不能交叉操作以字符为单位不能交叉IO设备的物理特性设备的物理特性传输一字节发生一次中断传输一字节发生一次中断存储设备的物理特性存储设备的物理特性磁带的物理特性磁带的物理特性头标头标 信息块信息块 信息块信息块 信息块信息块 .尾标尾标间隙间隙操作：反绕，正向查找，反向查找，读，写，操作：反绕，

3、正向查找，反向查找，读，写，地址：一维地址：一维文件：顺序结构（一个文件占若干连续块）文件：顺序结构（一个文件占若干连续块）8.2 设备的物理特性.磁盘组的物理特性磁盘组的物理特性.盘面盘面0盘面盘面1盘面盘面2盘面盘面m-1扇区扇区1扇区扇区0扇区扇区n-1柱面柱面0柱面柱面l-1.引臂柱面号柱面号i盘面号盘面号j扇区号扇区号k块号块号b（一维地址）（一维地址）（三维地址）（三维地址）编址方法：使相邻块物理上最近编址方法：使相邻块物理上最近例子：例子：l=2;m=3;n=3柱面号：柱面号：0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1盘面号：盘面号：0 0 0 1 1

4、 1 2 2 2 0 0 0 1 1 1 2 2 2扇区号：扇区号：0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2块块 号：号：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17三维地址三维地址一维地址：一维地址：b=i m n+j n+k一维地址一维地址三维地址：三维地址：i=b(m n)j=b mod(m n)n k=b mod(m n)mod n未考虑读写延迟的扇区编号：未考虑读写延迟的扇区编号：扇区扇区0扇区扇区7扇区扇区6扇区扇区5扇区扇区4扇区扇区3扇区扇区2扇区扇区1扇区扇区0扇区扇区7扇区扇区3扇区扇区6扇区扇区2扇区

5、扇区5扇区扇区1扇区扇区4考虑读写延迟的扇区编号考虑读写延迟的扇区编号(单交错单交错)：扇区扇区0扇区扇区5扇区扇区2扇区扇区7扇区扇区4扇区扇区1扇区扇区6扇区扇区3考虑读写延迟的扇区编号考虑读写延迟的扇区编号(双交错双交错)：光盘的物理特性:读取原理:pit/land 螺旋线,22188圈(展开5.6km),内侧转速:530转/分;外侧转速:200转/分(密度均匀,读取速度均匀)DataECCP14个bit构成一个symble42个symble构成一个frame98个frame构成一个sectorSector2352bytes588bits的frame各包含24字节Preamble:16b

6、ytes,前12bytes为:00FFFFFFFFFFFFFFFFFFFF00后随3bytes扇区编号,最后字节为mode2048字节288字节8.3 I/O 传输方式nIO操作演变历史操作演变历史n程序查询方式程序查询方式 (programmed IO)(polling)nCPU and Device can not work in parallel n中断方式中断方式 (interrupt)nCPU and device can work in parallel,too many interrupts for CPUn通道方式通道方式 (channel)nspecial processor

7、 for dealing with io operationsn直接内存方式直接内存方式(DMA)nDMA controller in charge of block io8.3.1 程序控制查询方式程序控制查询方式CPU启动设备启动设备完成完成FT缺点缺点:处理机与设备串行工作处理机与设备串行工作;消耗大量处理机时间消耗大量处理机时间.8.3.2 中断驱动方式中断驱动方式nCPUn计算计算n启动设备启动设备n计算计算nn计算计算n中断处理中断处理n计算计算设备设备:工工作作特点特点:CPU与设备并行工作与设备并行工作 设备多时对设备多时对CPU打扰多打扰多8.3.3 DMA方式 数据传输数据

8、传输CPUDMA控制器控制器内存内存地地 址址计计 数数控控 制制缓冲缓冲磁盘磁盘 中断中断 DMA请求请求总线总线磁盘磁盘控制器控制器 回答回答 DMA编程编程启动启动中断中断状态状态8.3.3 DMA方式.nCPU通过设置通过设置DMA控制器实现控制器实现DMA编程，编程，同时启动磁盘控制器由磁盘读入数据至内部缓同时启动磁盘控制器由磁盘读入数据至内部缓冲区并进行和校验；冲区并进行和校验；nDMA控制器向磁盘控制器发出读请求，并控制器向磁盘控制器发出读请求，并将内存地址放在地址总线上；将内存地址放在地址总线上；n磁盘控制器将字节传到内存指定单元；磁盘控制器将字节传到内存指定单元；n磁盘控制器

9、向磁盘控制器向DMA控制器发送回答；控制器发送回答；nDMA控制器将内部地址寄存器加控制器将内部地址寄存器加1同时将记同时将记数减数减1，重复上述过程，重复上述过程直至计数器为直至计数器为0，此时此时DMA控制器向控制器向CPU发出中断信号发出中断信号.8.3.4 通道方式通道方式n通道通道n负责负责IO操作的处理机操作的处理机n指令系统指令系统n基本操作：控制、读、写、转移、结束基本操作：控制、读、写、转移、结束n指令格式：（操作码，传输量，特征位，地址）指令格式：（操作码，传输量，特征位，地址）n运控部件运控部件nCAW，CCW，CSW，CDWn存储区域（与存储区域（与CPU共用内存共用内

10、存,通道内有缓冲区）通道内有缓冲区）n通道程序，通道程序，IO数据（数据（channel does have its buffers）通道程序执行过程：通道程序执行过程：按按CAW取通道命令取通道命令CCW（CAW）+1 CAW是通道结束命令是通道结束命令执行此命令执行此命令F向向CPU发中断发中断一个通道程序可以控制若干设备进行多次一个通道程序可以控制若干设备进行多次IO传输。传输。T通道类型通道类型n字节多路通道字节多路通道(byte multiplexer channel)n 多个非分配型子通道，连接低速外围设备多个非分配型子通道，连接低速外围设备n数组选择通道数组选择通道(block

11、selector channel)n 一个分配型子通道，连接多台高速设备一个分配型子通道，连接多台高速设备n数组多路通道数组多路通道(block multiplexer channel)n 多个非分配型子通道，连接多台高速设备多个非分配型子通道，连接多台高速设备设备、通道、内存连接设备、通道、内存连接选择通道选择通道磁盘字节多路通道字节多路通道打印机打印机输入机输入机内存储器内存储器处理机处理机磁带数组多路通道数组多路通道8.4 设备的分配与去配设备的分配与去配n独占型设备的分配与去配独占型设备的分配与去配n块型独占块型独占n字符型独占字符型独占n共享型设备的分配与去配共享型设备的分配与去配n

12、块型共享块型共享数据结构数据结构设备控制块设备控制块(UCB)通道控制块通道控制块(CCB)设备标识设备标识设备状态设备状态相连通道相连通道占有设备进程占有设备进程通道标识通道标识通道状态通道状态通道类型通道类型占有通道进程占有通道进程系统设备表系统设备表(SDT)设备类设备类 总数总数 设备等待队列设备等待队列 UCB表指针表指针 lp m Sm UCBUCBUCB 独占型设备的分配与去配独占型设备的分配与去配用户使用独占型设备活动：用户使用独占型设备活动：申请，使用，使用，申请，使用，使用，使用，释放，使用，释放 申请：申请：(1)根据设备类查根据设备类查SDT表表 (2)P(Sm)(3)

13、查查UCB表找一空闲设备并分配表找一空闲设备并分配 使用：使用：(1)分配通道分配通道 (2)IO传输传输 (3)去配通道去配通道 释放：释放：(1)找找SDT表对应入口表对应入口 (2)查查UCB表，去配表，去配 (3)V(Sm)l共享型设备的分配与去配共享型设备的分配与去配用户使用共享型设备活动用户使用共享型设备活动使用，使用，使用，使用，使用，使用特征特征来自文件系统；来自文件系统；每次读（写）一块；每次读（写）一块；通常经过缓冲；通常经过缓冲；排队优化。排队优化。使用使用分配通道；分配通道；IO操作；释放通道操作；释放通道8.5 设备驱动设备驱动n通道程序通道程序nCCW指令序列指令序

14、列n静态编制或动态生成静态编制或动态生成n设备启动设备启动n通道启动通道启动n中断处理中断处理n通道向通道向CPU发的中断发的中断8.5 设备驱动设备驱动设备设备CAWCCWCDWCSWCCW1CCW2CCWi.CCWn数据区数据区.形成通道程序形成通道程序.地址地址CAW.启动通道启动通道.中断处理中断处理.启动启动中断中断内存内存CPU通道通道 8.5 设备驱动设备驱动设备设备CAWCCWCDWCSWCCW1CCW2CCWi.CCWn数据区数据区.形成通道程序形成通道程序.地址地址CAW.启动通道启动通道.中断处理中断处理.启动启动中断中断内存内存CPU通道通道 8.5 设备驱动设备驱动设

15、备设备CAWCCWCDWCSWCCW1CCW2CCWi.CCWn数据区数据区.形成通道程序形成通道程序.地址地址CAW.启动通道启动通道.中断处理中断处理.启动启动中断中断内存内存CPU通道通道 8.5 设备驱动设备驱动设备设备CAWCCWCDWCSWCCW1CCW2CCWi.CCWn数据区数据区.形成通道程序形成通道程序.地址地址CAW.启动通道启动通道.中断处理中断处理.启动启动中断中断内存内存CPU通道通道 8.6 设备调度设备调度n优化服务顺序优化服务顺序n考虑因素考虑因素n公平性公平性n防止饿死防止饿死n高效性高效性n减少磁盘引臂移动量减少磁盘引臂移动量磁盘引臂调度磁盘引臂调度(di

16、sk head scheduling)n先到先服务（先到先服务（FCFS）n请求序列：请求序列：130，42，180，15，108，68，970 15 42 53 68 97 108 130 180 199移动量移动量:(130-53)+(130-42)+(180-42)+(180-15)+(108-15)+(108-68)+(97-68)=630磁盘引臂调度磁盘引臂调度(disk head scheduling)n最短寻找时间优先（最短寻找时间优先（SSTF）n请求序列：请求序列：130，42，180，15，108，68，970 15 42 53 68 97 108 130 180 199移

17、动量移动量:(53-42)+(180-42)+(180-15)=314lSCAN（LOOK）请求序列：请求序列：130，42，180，15，108，68，97SCAN移动量移动量:(53-0)+(180-0)=233LOOK移动量移动量:(53-15)+(180-15)=2030 15 42 53 68 97 108 130 180 199 Look ScanlC-SCAN（C-LOOK）请求序列：请求序列：130，42，180，15，108，68，97特点：所有磁道地位最长等待时间相同特点：所有磁道地位最长等待时间相同问题：问题：diskhead stickiness（磁头粘性）（磁头粘性）

18、0 15 42 53 68 97 108 130 180 199 C-Look C-ScannN-step SCAN（N步扫描）步扫描）n将磁盘请求队列分为若干个长度为将磁盘请求队列分为若干个长度为N的子队列，每的子队列，每个队列内采用个队列内采用SCAN算法算法n例子：磁道由外向内编号例子：磁道由外向内编号0-99,磁头当前位置磁头当前位置20,向向内移动内移动,N=4n12,5,7,30,60,77,13,26,61,80,53,66n2030127513266077806661 53n当当N很大时，接近很大时，接近SCAN算法算法n当当N=1时，蜕化为时，蜕化为FCFS算法算法nFSCA

19、N（Freezing SCAN，冻结扫描，冻结扫描)n将磁盘请求分为两个子队列，将磁盘请求分为两个子队列，n服务队列服务队列n请求队列请求队列n用用SCAN算法扫描服务队列，并为请求服务，服务算法扫描服务队列，并为请求服务，服务期间新到达的请求入请求队列期间新到达的请求入请求队列n扫描完成后交换两个队列的地位扫描完成后交换两个队列的地位8.6.1 磁盘磁盘I/O参数参数n首先分析一下读首先分析一下读/写一个磁盘块需要多少写一个磁盘块需要多少时间。它一般由如下三个因素确定时间。它一般由如下三个因素确定：n寻道时间（寻道时间（seek time）：将磁盘引臂移动）：将磁盘引臂移动到指定柱面所需要的

20、时间；到指定柱面所需要的时间；n旋转延迟（旋转延迟（rotational delay）：指定扇区）：指定扇区旋转到磁头下的时间；旋转到磁头下的时间；n传输时间（传输时间（transfer time）：读）：读/写一个扇写一个扇区的时间区的时间。8.6.1 磁盘磁盘I/O参数参数n寻道时间寻道时间Ts计算公式如下：计算公式如下：nTs=mnsn其中，其中，n为跨越磁道数，为跨越磁道数，m为跨越一个磁道为跨越一个磁道所用时间，所用时间，s为启动时间。为启动时间。n旋转延迟旋转延迟Tr计算公式如下：计算公式如下：nTr=1/(2r)n其中，其中，r为磁盘转速。该公式给出的是平均为磁盘转速。该公式给出

21、的是平均旋转延迟，它是磁盘旋转一周时间的一半，旋转延迟，它是磁盘旋转一周时间的一半，即旋转半周所花费的时间。即旋转半周所花费的时间。8.6.1 磁盘磁盘I/O参数参数n传输时间传输时间Tt计算公式如下：计算公式如下：nTt=b/(rN)n其中，其中，b为读为读/写字节数，写字节数，r为磁盘转速，为磁盘转速，N为一条磁道上的字节数。为一条磁道上的字节数。8.6.1 磁盘磁盘I/O参数参数n因此，可将访问时间因此，可将访问时间Ta表示为：表示为：n访问磁盘通常是以扇区（块）为单位的，访问磁盘通常是以扇区（块）为单位的，令令M为一个磁道上扇区的个数，则一个为一个磁道上扇区的个数，则一个扇区的访问时间

22、为：扇区的访问时间为：rNbrsnmTTTTtrsa21rMrsnmTTTTtrsa121例题例题n例例8-1设有一个只有一个移动磁头的磁盘，磁道由设有一个只有一个移动磁头的磁盘，磁道由外向内编号外向内编号0、1、2、199，磁头移动一个磁道，磁头移动一个磁道所需时间为所需时间为1ms，每个磁道有，每个磁道有100个扇区，磁盘转速个扇区，磁盘转速6000r/m。采用。采用CLOOK引臂调度算法，当前引臂位引臂调度算法，当前引臂位置处于第置处于第100磁道，当前移动方向由外向内，并规定磁道，当前移动方向由外向内，并规定引臂向内扫描时为路经请求服务。对于如下磁道请求引臂向内扫描时为路经请求服务。对

23、于如下磁道请求120、85、70、30，每个请求访问对应磁道上的一，每个请求访问对应磁道上的一个扇区，问：个扇区，问：n(1)给出引臂移动序列，计算引臂移动量和寻道时间，忽略启给出引臂移动序列，计算引臂移动量和寻道时间，忽略启动时间；动时间；n(2)计算平均旋转延迟时间；计算平均旋转延迟时间；n(3)计算传输时间；计算传输时间；n(4)计算所有访问处理时间。计算所有访问处理时间。例题例题n解答：解答：n(1)磁盘引臂移动序列为磁盘引臂移动序列为:100120307085，跨越磁道数：跨越磁道数：20+90+40+15=165。共需寻道时间。共需寻道时间1651ms=165ms.n(2)1次访盘

24、的旋转延迟为：次访盘的旋转延迟为：Tr=1/(2r)=1/(2(6000/m)=1/(2(100/s)=5ms，4次访盘的旋转延迟为次访盘的旋转延迟为45ms=20ms.n(3)1次访盘的传输时间为：次访盘的传输时间为：Tt=1/(rM)=1/(6000/m)100)=1/(100/s)100)=0.1ms，4次访盘的传输时间为次访盘的传输时间为40.1ms=0.4ms.n(4)所有访问处理时间所有访问处理时间=165+20+0.4=185.4(ms)。8.7 缓冲技术n设备设备处理数据到达与离开速度不一致所采用的技术处理数据到达与离开速度不一致所采用的技术。nBuffering vs.Cac

25、hingnbuffering:one data copyncaching:multiple data copy(slow多多,fast少少)n硬缓冲与软缓冲硬缓冲与软缓冲 n硬缓冲区通常设在设备中硬缓冲区通常设在设备中 n软缓冲区通常设在内存系统空间中软缓冲区通常设在内存系统空间中 n私用缓冲与公共缓冲私用缓冲与公共缓冲 n一个缓冲区与一个固定设备相联系，不同设备使用不同的缓冲区一个缓冲区与一个固定设备相联系，不同设备使用不同的缓冲区 n利用率低利用率低 n缓冲区由系统统一管理，按需要动态分派给正在进行缓冲区由系统统一管理，按需要动态分派给正在进行I/O传输的设传输的设备备空缓冲空缓冲空缓冲空

26、缓冲空缓冲空缓冲.head共共n个个Var buf_num:semaphore;(init n)mutex:semaphore;(init 1)1.申请申请 2.释放释放(1)P(buf_num)P(mutex)(2)P(mutex)空缓冲入链尾空缓冲入链尾(3)取链头空缓冲取链头空缓冲 V(mutex)(4)V(mutex)V(buf_num)缓冲池管理缓冲池管理 tail8.7.5 缓冲技术实现：输入设备 进程空间进程空间缓冲缓冲输入设备输入设备缓冲缓冲缓冲缓冲.io链进程方面：进程方面：中断方面：中断方面：IO链空链空设备忙设备忙申请空缓冲申请空缓冲启动设备启动设备等待等待由由io链取一

27、缓冲链取一缓冲信息信息进程空间进程空间释放空缓冲释放空缓冲缓冲入缓冲入io链链有等待进程有等待进程唤醒唤醒传输完毕传输完毕申请空缓冲申请空缓冲启动设备启动设备FTFTFTTF8.7.5 缓冲技术实现：输出设备 进程空间进程空间缓冲缓冲输出设备输出设备缓冲缓冲缓冲缓冲.io链进程方面：进程方面：中断方面：中断方面：申请一空缓冲申请一空缓冲信息信息缓冲缓冲设备忙设备忙启动设备启动设备缓冲入缓冲入io链链传输完传输完TFFT释放空缓冲释放空缓冲io链空链空取一缓冲取一缓冲启动设备启动设备TF8.7.5 输入输出设备：输入输出设备：(磁带、磁盘磁带、磁盘)缓冲区头缓冲区头缓冲区体缓冲区体设备块号设备块

28、号IO标识标识等待进程等待进程块型缓冲区：块型缓冲区：进程空间进程空间缓冲缓冲IO设备设备缓冲缓冲缓冲缓冲.io链链进程方面进程方面(输入输入)：进程方面进程方面(输出输出)：中断方面：中断方面：申请空缓冲申请空缓冲填写头部填写头部设备工作设备工作入入io链尾链尾启动设备启动设备信息信息进程进程释放缓冲释放缓冲申请空缓冲申请空缓冲填写头部填写头部信息信息缓冲缓冲设备工作设备工作启动设备启动设备入入io链链输入输入唤醒唤醒等待等待者者释放释放空缓空缓冲冲io链空链空取一缓冲取一缓冲启动设备启动设备FTFTTFFT等待等待UNIX缓冲缓冲n字符型缓冲字符型缓冲n100个缓冲区，长度个缓冲区，长度8

29、字节字节(6字符字符+2指针指针)n组成公共缓冲池，所有字符型设备公用组成公共缓冲池，所有字符型设备公用n缓冲区或属于缓冲区或属于cfreelist,或属于某字符设备或属于某字符设备(eg.tty,lp)n块型缓冲块型缓冲n50个缓冲区，长度个缓冲区，长度514字节字节n组成公共缓冲池，所有块型设备公用组成公共缓冲池，所有块型设备公用n缓冲区可属于缓冲区可属于bfreelist and/or devtabn预先读入的块预先读入的块(breada)n延迟写出的块延迟写出的块(bdwrite)字符型设备缓冲字符型设备缓冲struct cblock struct cblock*c_next;char

30、 info6;struct cblock*cfreelist;/free c blocks struct clist /associated with a character device int c_cc;/character count int c_cf;/pointer to first block int c_cl;/pointer to last blockstruct buf /actually a buffer header,shared by all mounted disks int b_flags;/BUSY,ASYNC,DELWRI,DONE.struct buf*b_f

31、orw;/headed by devtab struct buf*b_back;struct buf*av_forw;/position on free list struct buf*av_back;int b_dev;int b_wcount;/transfer count char *b_addr;/low order core(buffer)address char *b_xmem;/high order core(buffer)address char *b_blkno /block#on device char b_error;char *b_resid;/word not tra

32、nsferred after error bufNBUF块型设备缓冲（头部）15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0B_READ/B_WRITEB_DONEB_ERRORB_BUSYB_WANTEDB_RELOCB_ASYNCB_DELWRIb_flag:struct devtab /设备设备IO队列队列 char d_active;/busy flag char d_errcnt;/error count struct buf *b_forw;/first buffer for this dev struct buf *b_back;/last buffer

33、 for this dev struct buf *d_actf;/head of IO queue struct buf *d_actl;/tail of IO queuechar buffersNBUF514;/块型缓冲区块型缓冲区struct buf bfreelist;/缓冲区头部的链头缓冲区头部的链头struct devtab char d_active;char d_errcnt;struct buf*b_forw;struct buf*b_back;struct buf*d_actf;struct buf*d_actl;1821bfreelist35658368相关操作：getb

34、lk(dev,blkno)/assign a buffer for the given block bread(dev,blkno)/read a block(if necessary),return buf pointerbreada(dev,blkno,rablkno)/read in first block,like read;but also start io on second block bwrite(bp)/write the buffer,wait for completion,then releasebawrite(bp)/start the io,release buffe

35、r,no wait for completionbdwrite(bp)/release buffer,mark it so that if it is grabbed for another purpose,it will be written out before being given upbrelse(bp)/release the buffer,with no io impliedgetblk(dev,blkno)n参数：参数：dev:设备号，设备号，blkno:设备块号设备块号n返回：缓冲区指针返回：缓冲区指针bpn步骤：步骤：n块在块在b链中，且当前空闲链中，且当前空闲n由由av链

36、摘除，标记链摘除，标记BUSY,返回缓冲块指针返回缓冲块指针n块在块在b链中，但链中，但BUSY(其它进程在用其它进程在用)nsleep(空闲事件发生空闲事件发生)，返回缓冲块指针，返回缓冲块指针n不在不在b的链中，在的链中，在av链上取到延迟写的块链上取到延迟写的块n写出该块，分配下一个缓冲区写出该块，分配下一个缓冲区n不在不在b的链中，的链中，av链已空链已空n等待任意缓冲区变空闲的事件等待任意缓冲区变空闲的事件n不在不在b的链中，在的链中，在av链上得到空缓冲链上得到空缓冲n填写头部，由填写头部，由av链摘除，出旧链摘除，出旧b链，如新链，如新b链，返回缓冲块指针链，返回缓冲块指针bre

37、lse(bp)n参数：参数：bp:缓冲区头指针缓冲区头指针n返回：无返回：无n步骤：步骤：nIf 有等待者有等待者(b_flag&B_WANTED!=0),唤醒唤醒;nElsenbfreelist上有等待者上有等待者,唤醒唤醒nbp入入av链链bread(dev,blkno)n参数：参数：dev:设备号，设备号，blkno:设备块号设备块号n返回：载有信息的缓冲区返回：载有信息的缓冲区bpn步骤：步骤：nbp=getblk(dev,blkno)nif(缓冲区数据有效缓冲区数据有效)nreturn(bp)/在在cache中得到中得到n启动磁盘读启动磁盘读(d_actf/d_actl链链)nsle

38、ep(等待读盘完成事件等待读盘完成事件)n中断中断n唤醒唤醒nreturn(bp)breada(dev,blkno,rablkno)n参数：参数：dev:设备号，设备号，blkno:读块号，读块号，rablkno:预读块号预读块号n返回：返回：blk缓冲块指针缓冲块指针rbpn步骤：步骤：nrbp=getblk(dev,blkno)nif(信息无效信息无效)n启动设备读入启动设备读入(d_actf/d_actl链链)nrabp=getblk(dev,rablkno)nif(B_DONE)/缓冲区从缓冲区从b链得到链得到nbrelse(rabp)/入入av链链nelse /缓冲区从缓冲区从av链

39、得到链得到n启动设备读入启动设备读入(d_actf/d_actl链链)/中断时入中断时入av链链niowait(rbp)nreturn(rbp)bwrite(bp)n参数：参数：bp：缓冲区指针：缓冲区指针n步骤：步骤：n入设备入设备d_act队列队列(若设备不忙启动设备若设备不忙启动设备)nif(!B_ASYNC)nsleep(等待等待IO完成事件完成事件)n中断中断n唤醒唤醒nbrelse(bp),(bp入入av链链)bdwrite(bp)n参数参数:bp:缓冲区指针缓冲区指针n返回返回:无无n步骤：步骤：n标记标记b_flags=|B_DELWRI|B_DONEnbrelse(bp),(

40、bp入入av链链)bawrite(bp)n参数：参数：bp:缓冲区头指针缓冲区头指针n返回：无返回：无n步骤：步骤：nbp-b_flag=|B_ASYNCnbwrite(bp)n中断中断n入入av队列队列8.8 输入输出进程输入输出进程n专门负责专门负责IO传输的进程传输的进程n另外一种另外一种IO模式模式服务模式服务模式nC/S Modeln特点特点n界面清晰界面清晰,方便使用方便使用n两次进程切换两次进程切换,速度问题速度问题8.9 RAID技术nRAID:nRedundant Array of Inexpensive Disksncompared with SLEDs(Single La

41、rge Expensive Disks)nRedundant Array of Independent Disks/独立磁盘冗余阵列独立磁盘冗余阵列nProposed by researchers at UC BerkeleynDavid A.PattersonnBackgroundndisk access speed increases slowly compared with CPUnsolution:multiple parallel componentnObjectivenenhanced performancenhigh reliabilityRAID技术nRAIDnRAID is

42、a set of physical disks viewed by the operating system as a single logical drivenData are distributed across an array of physical drivesnRedundant disk capacity is used to store parity information,which guarantees data recoverability in case of disk failurenHardware RAID vs.Software RAIDnhardware ba

43、sed:special controller nWindows NT,2000,UNIX support software RAIDnSCSI RAID vs.IDE RAIDnperformance:SCSI outperforms IDEnprice:IDE beats SCSI8.9.1 RAID级别nRAID级别级别:行业标准规定的数据在多个磁行业标准规定的数据在多个磁盘上的存放方法。盘上的存放方法。n常见常见RAID级别级别:level0,level5;n RAID分条分条(stripping)数据存储方式数据存储方式n位级分条位级分条(bit-level stripping)n块级

44、分条块级分条(block-level stripping)n RAID衡量指标衡量指标l速速 度度:是否支持多个访问同时进行是否支持多个访问同时进行;l可靠性可靠性:是否能够发现和改正错误是否能够发现和改正错误;l成成 本本:是否有额外的开销和开销的大小是否有额外的开销和开销的大小.How to organize data across multiple disks?Industry standards schemeLevel0(数据分条数据分条)n数据分条以块为单位数据分条以块为单位,连续的数据条循连续的数据条循环存放在多个磁盘上。环存放在多个磁盘上。l 访问速度快；访问速度快；l 经济，空

45、间利用率经济，空间利用率100；l 无容错能力，可靠性差。无容错能力，可靠性差。block0block4block8Disk1block1block5block9Disk2block2block6block10Disk3block3block7block11Disk4控控 制制 器器(4,5)(2,3)读请求读请求写请求写请求Level1(镜像镜像,mirroring):n数据分条以块为单位数据分条以块为单位,采用分布镜像方式存储采用分布镜像方式存储,即完即完全相同的数据重复存放在两个盘上。全相同的数据重复存放在两个盘上。l 访问速度快访问速度快;读一个盘、写两个盘读一个盘、写两个盘;l 可靠

46、性可靠性(恢复性恢复性)高高;l 费用高费用高,是无镜像磁盘数的是无镜像磁盘数的2倍倍,空间利用率空间利用率50。block0block3block6Disk1block1block4block7Disk2block2block5block8Disk3控控 制制 器器(3,4)(8)读请求读请求写请求写请求block0block3block6Disk4block1block4block7Disk5block2block5block8Disk6Level2(位级汉明纠错码校验与恢复位级汉明纠错码校验与恢复):n数据以位数据以位(bit)为单位分条为单位分条,分布存放在多个数据磁盘上分布存放在多个

47、数据磁盘上,汉汉明纠错码存放在纠错磁盘上。明纠错码存放在纠错磁盘上。bit0Disk1bit1Disk2bit2Disk3控控 制制 器器(3,4,5)写请求写请求bit3Disk4bit4Disk5bit5Disk6bit6Disk7Level2(位级汉明纠错码校验与恢复位级汉明纠错码校验与恢复):n纠错能力强纠错能力强,可靠性高可靠性高;n发现发现2个错误个错误,纠正纠正1个错误个错误.n需要较多纠错盘存放汉明纠错码需要较多纠错盘存放汉明纠错码,成本较成本较高高;n不能同时为多个请求服务不能同时为多个请求服务,速度较慢速度较慢:n读操作读操作:所有磁盘同时访问所有磁盘同时访问,数据与错误校

48、验数据与错误校验码被送到磁盘阵列控制器码被送到磁盘阵列控制器;n写操作写操作:必须同时访问所有数据盘和纠错盘。必须同时访问所有数据盘和纠错盘。n数据以位数据以位(bit)为单位分条为单位分条,分布存放在多个数据分布存放在多个数据磁盘上磁盘上;只用一个冗余磁盘存放奇偶校验位。只用一个冗余磁盘存放奇偶校验位。bit0Disk1bit1Disk2bit2Disk3bit3Disk4奇偶校验奇偶校验Disk5l 有一定容错能力有一定容错能力;l 存储代价较低存储代价较低;l 读写需要访问所有盘读写需要访问所有盘,多个读写不能多个读写不能并行。并行。控控 制制 器器(0,1)等待等待(3)写请求写请求写

49、请求写请求Level3(位级单个奇偶校验位级单个奇偶校验)Level4(块级异或校验块级异或校验):n数据分条以块为单位数据分条以块为单位,用异或运算产生校验信息用异或运算产生校验信息,n校验信息保存在单独的磁盘上。校验信息保存在单独的磁盘上。block0block4block8Disk1block1block5block9Disk2block2block6block10Disk3block3block7block11Disk4P0-3P4-7P8-11Disk5控控 制制 器器(5,6)(11)读请求读请求读请求读请求Level 4(Cont.)l 读操作不进行异或校验读操作不进行异或校验,

50、可以并行可以并行;l 写操作要更新异或校验信息写操作要更新异或校验信息,都访问校验盘都访问校验盘,不能并行不能并行;写写操作时校验信息更新操作时校验信息更新:P47=(block4 xor block4)xor p47l 异或校验信息用于磁盘发生故障时数据块的恢复。异或校验信息用于磁盘发生故障时数据块的恢复。例如例如:若若block7所在的所在的Disk4发生故障发生故障,要恢复要恢复block7。block7=p47 XOR(block4 XOR block5 XOR block6)Level5(块级分布式异或校验块级分布式异或校验)n数据分条以块为单位数据分条以块为单位,异或校验信息分散循

51、环保存在各异或校验信息分散循环保存在各磁盘上磁盘上。block0block4block8block12P1619Disk1控控 制制 器器(1)(6)写请求写请求写请求写请求block1block5block9P1215block16Disk2block2block6P811block13block17Disk3block3P4-7block10block14block18Disk4P03block7block11block15block19Disk5Level5(块级分布式异或校验块级分布式异或校验)n校验码计算:np47=block4 XOR block5 XOR block6 XOR b

52、lock7n若若block7发生故障，可通过下式恢复发生故障，可通过下式恢复nblock7=p47 XOR block4 XOR block5 XOR block6Level 5(Cont.)l磁盘数量至少为磁盘数量至少为3个个;l读操作可并行读操作可并行;l不涉及相同数据盘和校验盘的写操作可以并行不涉及相同数据盘和校验盘的写操作可以并行;l对于单盘容量为对于单盘容量为S、数量为、数量为N的磁盘阵列的磁盘阵列,有效存储容量有效存储容量为为:S(N-1)磁盘利用率磁盘利用率为为:(N-1)/Nl任意磁盘发生故障任意磁盘发生故障,均可根据其它均可根据其它N-1个磁盘恢个磁盘恢复复;8.9.1 RA

53、ID级别级别(Cont.)表表8-1 RAID 级别的比较级别的比较Level 分条粒度分条粒度读并发性读并发性写并发性写并发性冗余冗余(容错容错/开销开销)0块支持支持无1块支持不支持镜像2位不支持不支持汉明纠错码奇偶校验与恢复3位不支持不支持单个奇偶校验4块支持不支持块级异或校验5块支持支持块级分布式异或校验8.9.2 Remark on Software RAIDnPros:ncost lessnsimplicitynCons:nperformancenboot volume limitation /导引卷不能是RAIDnlevel support:only 0,1,5 are supp

54、ortednOS compatibility:multiple problemnother software compatibilitynreliabilitynsoftware bugsBenefit from RAIDnIncreased read/write speednImproved data reliabilitynEnlarged storage capacitynmultiple disks viewed as a single volume8.10 虚拟设备虚拟设备n概念概念n利用共享型设备实现的数量较多、速度较快的独占型设利用共享型设备实现的数量较多、速度较快的独占型设备备

55、n引入引入n用户直接使用独占型设备效率低用户直接使用独占型设备效率低n实现实现n输入型虚拟设备输入型虚拟设备n输出型虚拟设备输出型虚拟设备n虚拟设备的例子虚拟设备的例子nSPOOLing输入输入nSPOOLing输出输出l用户使用独占型设备活动：用户使用独占型设备活动：申请，使用，使用，申请，使用，使用，使用，释放，使用，释放l缺点：缺点：速度：速度：CPU与设备速度不匹配与设备速度不匹配设备利用率：占有期间不一定一直使用设备利用率：占有期间不一定一直使用进程独占此设备进程独占此设备l方法：方法：在进程与独占型设备之间增加共享设备缓冲在进程与独占型设备之间增加共享设备缓冲虚拟虚拟设备设备虚拟虚

56、拟设备设备虚拟虚拟设备设备虚拟虚拟设备设备进程进程独占设备独占设备 共享设备共享设备（如磁盘）（如磁盘）间断传输间断传输连续传输连续传输l输入型虚拟设备的实现输入型虚拟设备的实现申请：申请：l分配一虚设备分配一虚设备l分配一实设备分配一实设备l信息由实设备信息由实设备虚设备虚设备l去配该实设备去配该实设备使用：使用：l信息由虚设备信息由虚设备进程空间进程空间释放：释放：l去配虚设备去配虚设备l输出型虚拟设备的实现输出型虚拟设备的实现申请：申请：l分配一虚设备分配一虚设备使用：使用：l信息由进程空间信息由进程空间虚设备虚设备释放：释放：l分配一实设备分配一实设备l信息由虚设备信息由虚设备实设备实

57、设备l去配实设备去配实设备l去配虚设备去配虚设备8.10.3 虚拟设备的例子虚拟设备的例子nSPOOLing输入输入n作业预输入（输入机作业预输入（输入机输入井）输入井）nSPOOLing输出输出n作业缓输出（输出井作业缓输出（输出井输出机）输出机）nSPOOLingnSimultaneous Peripheral Operation On-Linen由由SPOOLing程序控制通道完成程序控制通道完成作业控制块作业控制块(Job Control Block)n作业存在标志，其中保存系统管理作业需要的全部信作业存在标志，其中保存系统管理作业需要的全部信息。息。nJCB内容：内容：n作业标识作业

58、标识n用户标识用户标识n作业状态作业状态n调度参数调度参数n作业位置作业位置n资源需求资源需求n进入时间进入时间n处理时间处理时间n记账信息记账信息.job11job1m.输入井输入井预输入进程预输入进程输入机输入机预输入进程预输入进程通道通道通道通道内存内存.SPOOLing输入程序（输入程序（1）vs.SPOOLing输入进程（输入进程（n）输入机输入机有待输入作业有待输入作业 有空闲作业表有空闲作业表等待等待等待等待取一取一“空闲空闲”作业表为作业表为JCB作业状态改为作业状态改为“提交提交”申请输入井空间申请输入井空间作业内容作业内容输入井输入井填写填写JCB作业状态改为作业状态改为“

59、后备后备”作业调度作业调度1等待等待 “后备后备”作作业业唤醒唤醒SPOOLing 输入程序输入程序FTFTFTFT内存中已有内存中已有N道作业道作业等待等待输入井中有后备作业输入井中有后备作业等待等待访问磁盘中的作业表访问磁盘中的作业表根据根据JCB中的调度参数中的调度参数按照作业调度算法选一后备作业按照作业调度算法选一后备作业作业状态标记为作业状态标记为“执行执行”为该作业建立作业控制进程为该作业建立作业控制进程F作业调度程序（作业调度程序（1）TFTF有终止的作业控制进程有终止的作业控制进程等待等待取一终止的作业控制进程取一终止的作业控制进程撤销该作业控制进程并作善后处理撤销该作业控制进

60、程并作善后处理对应作业状态改为对应作业状态改为“完完成成”作业调度程序作业调度程序(1)因内存有因内存有N道作业道作业而等待而等待唤醒唤醒有等待有等待“完成完成”作业的假脱机输作业的假脱机输出程序出程序唤醒一个唤醒一个TF作业调度程序（作业调度程序（2）T.通道通道通道通道job11job1n.输出井输出井缓输出进程缓输出进程缓输出进程缓输出进程内存内存输出机输出机输出机输出机SPOOLing输出程序（输出程序（1）vs.SPOOLing输出进程输出进程（n）输出作业结果输出作业结果释放输出井空间释放输出井空间状态改为状态改为“空空闲闲”有等空闲有等空闲JCB的预输入进程的预输入进程唤醒一个唤

61、醒一个输出井有输出井有“完成完成”作作业业取一取一“完成完成”作作业业状态改为状态改为“退出退出”等待等待SPOOLing 输出程序FTTF8.11 稳定存储器稳定存储器(stable storage)n定义定义n不丢失信息的存储器称为稳定存储器不丢失信息的存储器称为稳定存储器n实现实现n不存在绝对可靠的存储介质不存在绝对可靠的存储介质n策略：冗余策略：冗余n在两种失效独立的介质上构建在两种失效独立的介质上构建n保存保存n将信息写到第一个存储块将信息写到第一个存储块n上述操作成功后，将相同信息写到第二存储块上述操作成功后，将相同信息写到第二存储块n仅当第二次传输也成功时，整个保存操作完成仅当第

62、二次传输也成功时，整个保存操作完成8.11 稳定存储器稳定存储器(stable storage)n实现实现n恢复恢复n鉴别两个数据块内容鉴别两个数据块内容n一对信息完全相同，且无检测到错误，正常一对信息完全相同，且无检测到错误，正常n其中一块检测到错误，用另一块取代其中一块检测到错误，用另一块取代n两块均未检测到错误，但内容不同，用第二块内容取两块均未检测到错误，但内容不同，用第二块内容取代第一块内容代第一块内容8.12 系统举例系统举例Linuxn涉及内容涉及内容n设备驱动，设备缓冲，文件管理设备驱动，设备缓冲，文件管理n主要特点主要特点n允许系统管理员动态添加或删除设备，其相应的驱动程序通

63、常允许系统管理员动态添加或删除设备，其相应的驱动程序通常以以DLL的形式动态加载，设备驱动程序可以采用高级语言编写，的形式动态加载，设备驱动程序可以采用高级语言编写，移植性好移植性好n除除NTFS外，支持多种可装卸的文件系统，如外，支持多种可装卸的文件系统，如FAT32、OS/2、HPFS、CDFS等支持映像文件等支持映像文件I/On设备管理子系统以设备管理子系统以I/O请求包请求包(I/O Request Package，IRP)方式驱动，每个方式驱动，每个I/O请求均以表示为请求均以表示为I/O请求包，请求包，I/O管理器管理器负责协调所有各组成部分之间的相互作用负责协调所有各组成部分之间的相互作用n通过系统进程通过系统进程(线程线程)提供异步提供异步I/O，在，在I/O请求的进程请求的进程(线程线程)不需要等待不需要等待I/O传输结果的情况下，请求者可以立即返回，具传输结果的情况下，请求者可以立即返回，具体体I/O操作由系统线程负责完成异步操作由系统线程负责完成异步I/O是通过异步过程调是通过异步过程调用用(Asynchronous Procedure Call，APC)实现的实现的应用程序应用程序系统服务系统服务IO管理程序文件系统磁盘驱动磁盘驱动光盘驱动光盘驱动磁带驱动磁带驱动Windows2000/XP IO子系统