操作系统：13第十四章 操作系统理

1、第十四章 操作系统理论操作系统理论模型：自动机模型 描述进程与资源建立操作系统形式化理论14.1 预备知识例14-1 自动驾驶的汽车汽车工作的抽象描述: 有限个状态: 直行、停止、左转、右转; 有限个命令: 启动、停止、左转、右转; 有限控制器: 汽车在某状态下接受某个命令 转换到相应的状态。a b c d （汽车）有限控制器(汽车)单带有限自动机14.1 预备知识例14-2 邮局单人电话间汽车工作的抽象描述: 有限个状态: 直行、停止、左转、右转; 有限个命令: 启动、停止、左转、右转; 有限控制器: 汽车在某状态下接受某个命令 转换到相应的状态。a b c d （汽车）有限控制器单带有限自

2、动机8.2.2 存储设备的物理特性卷头标信息块信息块信息块.卷尾标规 格: 1 in, 16磁道; 0.5 in, 9磁道(现可达18磁道); 每磁道一个磁头。操 作: 反绕, 正向查找, 反向查找, 读, 写, 地 址: 一维文 件: 顺序结构 (一个文件占若干连续磁带块 )存放信息: 记录信息和控制信息。磁头间隙磁带的物理特性: 启停型、顺序访问型设备8.2.2 存储设备的物理特性(Cont.)磁盘的物理特性: 旋转型设备移动臂(头)磁盘组的物理结构盘面 0盘面 2盘面 1盘面 m-1柱面 0柱面 l-1柱面 1扇区 0扇区 1扇区n-1引 臂柱面号i盘面号j扇区号k块号b (一维地址)三

3、维地址 编址方法: 使相邻块物理上最近例子: 柱面数l=2, 盘面数m=2, 扇区数n=4柱面号：0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1盘面号：0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1扇区号：0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3块 号: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 158.2.2 存储设备的物理特性(Cont.) 最上、最下为伺侯面, 不存放信息, 用于磁头定位; 若盘片数为 S，盘面数m2S-2=2(S-1); 每个盘面被分成2i个扇区, 每个扇区含多个磁道。 存储容量磁头数磁道

4、(柱面)数每道扇区数每扇区字节数 三维数组柱面数,盘面数,扇区数按行存储的数组元素的顺序号就是磁盘的块号。三维地址(i , j , k) 一维地址b： b=i m n + j n + k = (i m + j) n + k 一维地址b 三维地址(i , j , k) ： i=b (mn) j=b mod (mn) n k=b mod (mn) mod n其中：m为盘面数, n为扇区数8.2.2 存储设备的物理特性(Cont.)扇区0扇区7扇区6扇区5扇区4扇区3扇区2扇区1未考虑读写延迟的扇区编号(无交错):8.2.2 存储设备的物理特性(Cont.)扇区0扇区7扇区3扇区6扇区2扇区5扇区1

5、扇区4考虑读写延迟的扇区编号(单交错)：8.2.2 存储设备的物理特性(Cont.)扇区0扇区5扇区2扇区7扇区4扇区1扇区6扇区3考虑读写延迟的扇区编号(双交错)：8.2.2 存储设备的物理特性(Cont.)8.3 数据传输方式程序查询方式 (programmed I/O) (polling) CPU and Device can not work in parallel 中断驱动方式 (interrupt) CPU and device can work in parallel, too many interrupts for CPU直接内存方式 (DMA)DMA controller i

6、n charge of block I/O通道方式 (channel)special processor for dealing with I/O operations8.3.1 程序控制查询方式缺 点: 处理机与设备串行工作; 消耗大量处理机时间。内存映射输入输出: 将设备地址映射为内存地址空间一部分, 硬件提供专用的输入输出指令。F查询方式完成CPU启动设备结束8.3.2 中断驱动方式CPU计算启动设备计算计算中断处理计算设备工作特点: CPU与设备并行工作 设备多时对CPU打扰多8.3.3 DMA方式设备操作码内存地址计数器忙碌标志状态寄存器缓冲区DMA控制器opcodeoperands

7、busystatusCPU123内存45678.3.3 DMA方式(Cont.). CPU将操作数送入operands寄存器; CPU将操作码送入opcode寄存器并启动DMA控制器; DMA将busy置位, 不接受新命令, CPU可做其它操作; DMA控制设备与其缓冲区的数据传输; DMA控制设备其缓冲区与内存的数据传输; DMA控制器将内存地址寄存器加1同时将记数器减1，若计数器不为0, 则转; DMA复位busy寄存器, 并向CPU发中断”传输完”; CPU读入status, 确认操作成功。8.3.4 通道方式指令系统基本操作: 读、写、控制、转移、结束指令格式: 运控部件通道地址字CA

8、W: 存放下一条通道指令地址;通道命令字CCW: 存放当前正在执行的通道指令;通道状态字CSW: 存放通道、控制器、设备的状态; 包括I/O完成信息、出错信息、复执次数等;通道数据字CDW: 暂存设备与内存之间的I/O数据。存储区域 (与CPU共用内存)通道程序，I/O数据操作码传输字节数特征位地址信息通 道: 负责I/O操作的处理器。 以内存为中心, 支持块传输。8.3.4 通道方式(Cont.)通道程序执行过程通道程序执行流程按CAW取通道指令CCW(CAW)+1CAWCCW是结束指令向主机发中断请求结 束F执行CCW一个通道程序可以控制传输多组数据。通道类型字节多路通道(byte mul

9、tiplexer channel)多个非分配型子通道，连接低速外围设备数组选择通道(block selector channel)一个分配型子通道，连接多台高速设备数组多路通道(block multiplexer channel) 多个非分配型子通道，连接多台高速设备8.3.4 通道方式(Cont.)设备、通道、内存连接数组选择通道磁盘字节多路通道打印机输入机内存处理器磁带数组多路通道8.3.4 通道方式(Cont.)8.4 设备分配与去配独占型设备的分配与去配 块型独占 字符型独占共享型设备的分配与去配 块型共享8.4.1 独占型设备的分配与去配 数据结构设备控制块(UCB)设备标识(设备号

10、)设备状态相连通道占有设备进程通道控制块(CCB)通道标识通道类型等待队列占有通道进程系统设备表(SDT)设备名设备数等待队列UCB表指针printermSmPtr打印机的UCB表UCB1(printer1)UCB2(printer2)UCBm(printerm)8.4.1 独占型设备的分配与去配 用户使用独占型设备活动： 申请，使用，使用，使用，释放 申请: 根据设备名查SDT表； P(Sm)； 查UCB表找一空闲设备并分配。 使用: 分配通道(若通道占用则等待); IO数据传输; 去配通道。 释放: 根据释放设备名找SDT表对应入口; 根据设备号查UCB表，找到该设备去配; V(Sm) 8

11、.4.2 共享型设备的分配与去配 用户使用共享型设备活动： 使用，使用，使用 特征： 来自文件系统、虚拟存储系统、 输入/输出管理程序; 每次读写一块； 通常经过缓存； 排队优化。 使用： IO传输8.5 设备驱动8.5.1 通道程序通道指令序列所构成的程序;静态编制或根据I/O要求动态生成;执行1次I/O, 或多次I/O;可与处理器的操作并行;多个通道程序可以并行。8.5.2 设备启动通道程序形成后:处理器将通道程序起始地址放到内存指定单元;运行通道启动指令启动通道;由指定内存单元取通道程序起始地址CAW;执行通道程序。 8.5.3 中断处理.形成通道程序.启动通道.中断处理.CPUCCW1

12、CCW2CCWi.CCWn数据区设备内存通道程序通道CAWCCWCSWCDW中 断8.6 设备调度优化服务顺序考虑因素公平性：防止饿死高效性：减少磁盘引臂移动量8.6.1 磁盘I/O参数读/写一个磁盘块需要时间Ta 的计算 一般由如下三个因素确定：寻道时间(seek time) 将磁盘引臂移动到指定柱面所需要的时间;旋转延迟(rotational delay) 指定扇区旋转到磁头下的时间;传输时间(transfer time) 读/写一个扇区的时间。8.6.1 磁盘I/O参数寻道时间Ts 计算公式如下:Ts = mn +s其中 n 为跨越磁道数, m 为跨越一个磁道所用时间, s 为启动时间。

13、旋转延迟Tr 计算公式如下:Tr = 1/(2 r )其中, r 为磁盘转速(单位: 周/分钟)。该公式给出的是平均旋转延迟,它是磁盘旋转一周时间的一半,即旋转半周所花费的时间。8.6.1 磁盘I/O参数传输时间Tt 计算公式如下：Tt =b/( r N )其中，b 为读/写字节数, r 为磁盘转速, N 为一条磁道上的字节数。 8.6.1 磁盘I/O参数因此，可将访问b个字节的时间Ta表示为:Ta=Ts+Tr+Tt =mn+s+1/(2r)+b/(rN)访问磁盘通常是以扇区(块)为单位的， 令M 为一个磁道上扇区的个数, 则 每扇区的字节数=每磁道字节数/每磁道扇区数 =N/M 则一个扇区的

14、访问时间为：Ta=Ts+Tr+Tt =mn+s+1/(2r)+1/(rM)8.6.2 磁盘引臂调度算法磁盘引臂调度(disk head scheduling)先到先服务(FCFS) 请求序列: 130, 42, 180, 15, 108, 68, 97移动量: (130-53)+(130-42)+(180-42)+(180-15)+ (108-15)+(108-68)+(97-68)=6300 15 42 53 68 97 108 130 180 199最短查找时间优先(SSTF) 请求序列: 130, 42, 180, 15, 108, 68, 970 15 42 53 68 97 108

15、130 180 199移动量: (53-42)+(180-42)+(180-15)=314问题: 存在饥饿和饿死问题。8.6.2 磁盘引臂调度算法扫描算法(SCAN) 不停地双向往复扫描磁道到尽头, 双向响应路径请求。 请求序列: 130, 42, 180, 15, 108, 68, 97移动量: (53-0)+(180-0)=2330 15 42 53 68 97 108 130 180 1998.6.2 磁盘引臂调度算法LOOK算法: 又称电梯算法 前进方向有请求, 则响应; 若前方没请求且反向有请求, 则改变方向响应请求。 否则, 停止。 请求序列: 130, 42, 180, 15,

16、108, 68, 97移动量: (53-15)+(180-15)=2030 15 42 53 68 97 108 130 180 1998.6.2 磁盘引臂调度算法循环扫描(C-SCAN) 单方向扫描响应路径请求; 到头后快速移动到另一头继续扫描。 请求序列: 130, 42, 180, 15, 108, 68, 97移动量=(199-53)+(199-0)+(42-0)=387特点：所有磁道地位、最长等待时间相同。0 15 42 53 68 97 108 130 180 1998.6.2 磁盘引臂调度算法C-LOOK算法 前进方向有请求, 则响应; 若前方没请求且反向有请求, 则移到反向最远

17、端请求位置继续沿原方向扫描响应请求。 否则, 停止。 请求序列: 130, 42, 180, 15, 108, 68, 97移动量=(180-53)+(180-15)+(42-15)=3190 15 42 53 68 97 108 130 180 1998.6.2 磁盘引臂调度算法SCAN和LOOK存在”磁头粘性”(arm stickiness)问题。N-step SCAN和冻结扫描(Freezing SCAN)N步扫描 将磁盘请求队列分为若干个长度为N的子队列, 每个队列内采用SCAN算法。例: 磁道由外向内编号099, 磁头当前位置20,向内移动,N=4请求序列:12, 5, 7, 30,

18、 60, 77, 13, 26, 61, 80, 53, 66响应序列:2030127513266077806661 53 当N很大时, 接近SCAN算法 当N=1时, 蜕化为FCFS算法8.6.2 磁盘引臂调度算法FSCAN: 请求队列被”冻结”。 将磁盘请求分为两个子队列: 服务队列 请求队列 用SCAN算法扫描服务队列, 并为请求服务, 服务期间新到达的请求入请求队列; 扫描完成后交换两个队列的地位。8.6.2 磁盘引臂调度算法例8-3： 设有一个单磁头的磁盘, 磁道由外向内编号 0、1、2、199。 磁头移动一个扇区(柱面?)所需时间为 1ms ; 每个磁道有 100 个扇区; 磁盘转

19、速 6000r/min。 当前引臂位置处于第100磁道 , 当前移动方向由外向内， 并规定引臂向内扫描时为路径请求服务。 对于如下磁道请求 120、85、70、30，每个请求访问对应磁道上 的一个扇区。采用C-LOOK引臂调度算法，问：(1) 给出引臂移动序列，计算引臂移动量和寻道时间， 忽略启动时间；(2) 计算平均旋转延迟时间；(3) 计算传输时间；(4) 计算所有访问处理时间。8.6.3 磁盘访问举例解答：(1)磁盘引臂移动序列为: 100120307085， 跨越磁道数：20+90+40+15=165。 共需寻道时间1651ms=165ms.(2) 1次访盘的旋转延迟为：Tr=1/(2

20、r)=1/(2(6000/m)=1/(2(100/s)=5ms，4次访盘的旋转延迟为 45ms=20ms.(3) 1次访盘的传输时间为：Tt=1/(rM)=1/(6000/m)100)=1/(100/s)100)=0.1ms， 4次访盘的传输时间为40.1ms=0.4ms.(4)所有访问处理时间=165+20+0.4=185.4(ms)。8.6.3 磁盘访问举例8.7 缓冲技术8.7.1 缓冲技术的引入 缓冲技术: 处理数据到达与离开速度 不一致所采用的技术。Buffering vs. Cachingbuffering: one data copycaching: multiple data

21、copy8.7.2 硬缓冲与软缓冲 硬缓冲区通常设在设备中, 由硬件实现；软缓冲区通常设在内存系统空间中, 由软件实现。8.7.3 私用缓冲与公共缓冲 私用缓冲 一个缓冲区与一个固定设备相联系, 不同设备使用不同的缓冲区; 公共缓冲 缓冲区由系统统一管理, 所有缓冲区构成缓冲池, 按需要动态分派给正在进行I/O传输的设备。8.7.4 单缓冲、双缓冲与循环缓冲缓冲技术分为: 单缓冲、双缓冲、多缓冲以及缓冲池4种。 单缓冲: 设备与进程之间设一个缓冲区; 数据传输模式为”进程缓冲区设备”; 处理器与设备对缓冲区的操作是串行; 双缓冲: 设备与进程之间设置两个缓冲区; 数据传输时, 两个缓冲区交替使

22、用; 提高处理器与设备之间的并行性。循环缓冲: 设备与进程之间设置多个缓冲区, 并链成环形。 设置输入指针in和输出指针out。semaphore buf_avaiable; (init n)semaphore mutex; (init 1)1. 申 请 2. 释 放 P(buf_avaiable) P(mutex) P(mutex) 空缓区如冲入缓冲池链头 取缓冲池链头空缓冲区 V(mutex) V(mutex) V(buf_avaiable) 返回空缓冲区指针 缓冲池管理 8.7.5 缓冲池及其管理.head共 n 个空缓冲区空缓冲区空缓冲区8.7.6 缓冲技术的实现每个设备一个缓冲队列,

23、 队列的每块缓冲区动态向系统申请。 输入型设备输入设备缓冲区缓冲区缓冲区进程空间I/O链通道程序操作系统输入型设备缓冲示图进程方面I/O链空设备忙申请空缓冲启动设备由I/O链取一缓冲信息进程空间释放空缓冲结 束TTFF等待 中断方面缓冲入I/O链有等待进程TF唤醒传输完毕申请空缓冲启动设备F结 束T输入型设备缓冲技术的实现8.7.6 缓冲技术的实现 输出型设备输出设备缓冲区缓冲区缓冲区进程空间I/O链通道程序操作系统输出型设备缓冲示图8.7.6 缓冲技术的实现输出型设备缓冲技术的实现进程方面申请空缓冲信息缓冲结 束TTFF中断方面释放空缓冲区I/O链空F由I/O链取一缓冲启动设备传输结 束T设

24、备忙缓冲入I/O链启动设备传输完8.7.6 缓冲技术的实现 输入输出设备(磁带、磁盘)输出/输入设备缓冲区缓冲区缓冲区进程空间I/O链通道程序操作系统输入输出型设备缓冲示图缓冲区头设备物理块号I/O方向标识等待进程缓冲区体缓冲区格式8.7.6 缓冲技术的实现进程输入申请空缓冲信息进程空间填写头部设备工作缓冲区入I/O链尾启动设备等待释放空缓冲区结 束FTF中断方面输 入唤醒等待者释放空缓冲TFI/O链空由I/O链取一缓冲启动设备传输结 束T进程输出申请空缓冲填写头部设备工作缓冲区入I/O链尾启动设备T信息缓冲结 束F8.7.6 缓冲技术的实现UNIX缓冲(P300303)字符型缓冲100个缓冲

25、区, 长度8字节(6字符+2指针);组成公共缓冲池, 所有字符型设备公用;缓冲区或属于cfreelist, 或属于某字符设备(eg. tty,lp)块型缓冲50个缓冲区, 长度514字节;组成公共缓冲池, 所有块型设备公用;缓冲区可属于bfreelist and/or devtab预先读入的块(breada)延迟写出的块(bdwrite)struct cblock struct cblock *c_next; char info6;struct cblock *cfreelist; /free c blocks struct clist /associated with a character

26、 device int c_cc; /character count int c_cf; /pointer to first block int c_cl; /pointer to last block字符型设备缓冲struct buf /actually a buffer header, shared by all mounted disks int b_flags; /BUSY, ASYNC, DELWRI, DONE. struct buf *b_forw; /headed by devtab struct buf *b_back; struct buf *av_forw; /posit

27、ion 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 transferred after error bufNBUF块型设备缓冲(头部)15 14 13 12 1

28、1 10 9 8 7 6 5 4 3 2 1 0B_READ/B_WRITEB_DONEB_ERRORB_BUSYB_WANTEDB_RELOCB_ASYNCB_DELWRIb_flag:struct devtab /设备I/O队列 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 for this dev struct buf *d_actf; /head of I/O que

29、ue struct buf *d_actl; /tail of I/O queuechar buffersNBUF514; /块型缓冲区struct buf bfreelist; /缓冲区头部的链头相关操作：getblk(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

30、on second block bwrite(bp) /write the buffer, wait for completion, then releasebawrite(bp) /start the io, release buffer, 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 buffe

31、r, with no io impliedgetblk(dev,blkno)参数： dev:设备号，blkno: 设备块号返回：缓冲区指针bp步骤：块在b链中，且当前空闲由av链摘除，标记BUSY, 返回缓冲块指针块在b链中，但BUSY(其它进程在用)sleep(空闲事件发生)，由av链摘除，标记BUSY, 返回缓冲块指针不在b的链中，在av链上取到延迟写的块写出该块，分配下一个缓冲区不在b的链中，av链已空等待任意缓冲区变空闲的事件不在b的链中，在av链上得到空缓冲分配，由av链摘除，返回缓冲块指针brelse(bp)参数：bp: 缓冲区头指针返回：无步骤：有等待者(b_flag&B_WAN

32、TED!=0),唤醒;bfreelist上有等待者,唤醒bp入av链bread(dev,blkno)参数：dev:设备号，blkno: 设备块号返回：载有信息的缓冲区bp步骤：bp=getblk(dev,blkno)if (缓冲区数据有效)return(bp) /在cache中得到启动磁盘读(d_actf/d_actl链)sleep(等待读盘完成事件)中断bp入b_forw/b_back链, 标记BUSYreturn(bp) breada(dev,blkno,rablkno)参数：dev:设备号，blkno:读块号，rablkno:预读块号返回：blk缓冲块指针rbp步骤：rbp=getblk

33、(dev,blkno)if(信息无效)启动设备读入(d_actf/d_actl链)rabp=getblk(dev,rablkno)if (B_DONE) /缓冲区从b链得到brelse(rabp) /入av链else /缓冲区从av链得到启动设备读入(d_actf/d_actl链) /中断时入b链和av链iowait(rbp)return(rbp)bwrite(bp)参数：bp：缓冲区指针步骤：入设备d_act队列(若设备不忙启动设备)if(! B_ASYNC)sleep(等待IO完成事件)中断bp入b链, (b_forw/b_back) brelse(bp), (bp入av链)bdwrite

34、(bp)参数: bp: 缓冲区指针返回: 无步骤：标记b_flags =| B_DELWRI | B_DONEbp入设备b_forw/b_back队列brelse(bp), (bp入av链)bawrite(bp)参数：bp: 缓冲区头指针返回：无步骤：bp-b_flag =| B_ASYNCbwrite(bp)中断(入b_act队列)入av队列8.8 输入输出进程 自主I/O方式: 进程执行I/O操作; 专门负责I/O传输的进程另外一种I/O模式服务模式;C/S ModelI/O实现: 进程向I/O进程发消息;特 点界面清晰, 方便使用;两次进程切换, 速度问题;8.9 RAID技术RAIDR

35、edundant Array of Inexpensive Disks compared with SLEDs (Single Large Expensive Disks)Redundant Array of Independent Disks /独立磁盘冗余阵列Proposed by researchers at UC Berkeley David A. PattersonBackgrounddisk access speed increases slowly compared with CPUsolution: multiple parallel componentObjectiveenh

36、anced performancehigh reliabilityRAIDRAID is a set of physical disks viewed by the operating system as a single logical drive;Data are distributed across an array of physical drivesRedundant disk capacity is used to store parity information, which guarantees data recoverability in case of disk failu

37、re.Hardware RAID vs. Software RAIDhardware based: special controller;Windows NT, 2000, UNIX support software RAID.SCSI RAID vs. IDE RAIDperformance: SCSI outperforms IDE;price: IDE beats SCSI.8.9 RAID技术(Cont.)8.9.1 RAID级别RAID级别: 行业标准规定的 数据在多个磁盘上的存放方法。 常见RAID级别: level0, , level5; RAID分条(stripping)数据存

38、储方式位级分条(bit-level stripping)块级分条(block-level strpping)RAID衡量指标速 度: 是否支持多个访问同时进行;可靠性: 是否能够发现和改正错误;成 本: 是否有额外的开销和开销的大小。8.9.1 RAID级别(Cont.)Level0 (分条) : 数据分条以块为单位 连续的数据条循环存放在多个磁盘上。访问速度快； 经济，空间利用率100；无容错能力，可靠性差。block0block4block8Disk1block1block5block9Disk2block2block6block10Disk3block3block7block11Disk

39、4控 制 器(4,5)(2,3)读请求写请求8.9.1 RAID级别(Cont.)Level1 (镜像): 数据分条以块为单位 采用分布镜像(mirroring)方式存储, 即完全相同的数据重复存放在两个盘上。block0block3block6Disk1block1block4block7Disk2block2block5block8Disk3控 制 器(3,4)(8)读请求写请求block0block3block6Disk4block1block4block7Disk5block2block5block8Disk6访问速度快; 读一个盘、写两个盘;可靠性高;费用高, 是无镜像磁盘数的2倍,

40、 空间利用率50。8.9.1 RAID级别(Cont.)Level2 (位级汉明纠错码奇偶校验与恢复): 数据以位(bit)为单位分条, 分布存放在多个数据磁盘上; 汉明纠错码存放在纠错磁盘上。bit0Disk1bit1Disk2bit2Disk3控 制 器(3,4,5)写请求bit3Disk4bit4Disk5bit5Disk6bit6Disk78.9.1 RAID级别(Cont.)纠错能力强, 可靠性高;需要较多纠错盘存放汉明纠错码, 成本较高;不能同时为多个请求服务, 速度较慢:读操作: 所有磁盘同时访问, 数据与错误校验码被送到磁盘阵列控制器;写操作: 必须同时访问所有数据盘和纠错盘。

41、8.9.1 RAID级别(Cont.)Level3 (位级单个奇偶校验): 数据以位(bit)为单位分条, 分布存放在多个数据磁盘上; 只用一个冗余磁盘存放奇偶校验位。bit0Disk1bit1Disk2bit2Disk3bit3Disk4奇偶校验Disk5有一定容错能力;存储代价较低;读写需要访问所有盘, 多个读写不能并行。控 制 器(0,1)等待(3)写请求写请求8.9.1 RAID级别(Cont.)Level4 (块级异或校验): 数据分条以块为单位, 用异或运算产生校验信息, 校验信息保存在单独的磁盘上。block0block4block8Disk1block1block5block9

42、Disk2block2block6block10Disk3block3block7block11Disk4P0-3P4-7P8-11Disk5控 制 器(5,6)(11)读请求读请求8.9.1 RAID级别(Cont.)读操作不进行异或校验, 可以并行;写操作要更新异或校验信息, 都访问校验盘, 不能并行; 写操作时校验信息更新: P47=(block4 xor block4)xor p47异或校验信息用于磁盘发生故障时数据块的恢复。 例如: 若block7所在的Disk4发生故障, 要恢复block7。 p47= block4 XOR block5 XOR block6 XOR block7

43、 则 p47 XOR (block4 XOR block5 XOR block6) =全0 XOR block7=block7 所以 block7= p47 XOR (block4 XOR block5 XOR block6) 8.9.1 RAID级别(Cont.)Level5 (块级分布式异或校验): 数据分条以块为单位, 异或校验信息分散循环保存在各磁盘上。block0block4block8block12P1619Disk1控 制 器(1)(6)写请求写请求block1block5block9P1215block16Disk2block2block6P811block13block17D

44、isk3block3P4-7block10block14block18Disk4P03block7block11block15block19Disk58.9.1 RAID级别(Cont.)磁盘数量至少为3个;读操作可并行;不涉及相同数据盘和校验盘的写操作可以并行;对于单盘容量为S、数量为N的磁盘阵列, 有效存储容量为: S(N-1) 磁盘利用率为: (N-1)/N任意磁盘发生故障, 均可根据其它N-1个磁盘恢复;8.9.1 RAID级别(Cont.)表8-1 RAID 级别的比较Level分条粒度读并发性写并发性冗余(容错/开销)0块支持支持无1块支持不支持镜像2位不支持不支持汉明纠错码奇偶校

45、验与恢复3位不支持不支持单个奇偶校验4块支持不支持块级异或校验5块支持支持块级分布式异或校验8.9.2 硬件RAID与软件RAID硬件RAID是RAID技术主流, 需RAID控制器、价格贵;软件RAID不需专用RAID器, 成本低、性价比高; 软件RAID问题:速度、可靠性不如硬件RAID; 系统兼容性: 同一台机器的不同操作系统的软件RAID的识别问题; 操作系统的引导问题。8.10 虚拟设备概 念：利用共享型设备 实现的数量较多、速度较快的独占型设备。引 入：用户直接使用独占型设备效率低。实 现 输入型虚拟设备 输出型虚拟设备 虚拟设备的例子SPOOLing输入SPOOLing输出用户使用独占型设备活动：申请，使用，使用，使用，释放进程独占此设备8.10.1 虚拟设备的引入缺点:速 度: CPU与设备速度不匹配;设备利用率: 占有期间不一定一直使用。8.10.1 虚拟设备的引入(Cont.)方法: 在进程与