19 第十四章 操作系统理论.pptx

第1页：第十四章操作系统理论

• 操作系统理论模型：自动机模型描述进程与资源
• 建立操作系统形式化理论

第2页：14.1 预备知识例

• 14-1自动驾驶的汽车汽车工作的抽象描述:
  • 有限个状态:直行、停止、左转、右转;
  • 有限个命令:启动、停止、左转、右转;
  • 有限控制器:汽车在某状态下接受某个命令转换到相应的状态。a b c d ……（汽车）有限控制器(汽车)单带有限自动机

第3页：14.1 预备知识例（续）

• 14-2邮局单人电话间汽车工作的抽象描述:
  • 有限个状态:直行、停止、左转、右转;
  • 有限个命令:启动、停止、左转、右转;
  • 有限控制器:汽车在某状态下接受某个命令转换到相应的状态。a b c d ……（汽车）有限控制器单带有限自动机

第4页：8.2.2 存储设备的物理特性卷尾标

• .信息块信息块信息块卷头标
  • 规格:1 in, 16磁道;0.5 in, 9磁道(现可达18磁道);每磁道一个磁头。
  • 操作:反绕,正向查找,反向查找,读,写, …
  • 地址:一维
  • 文件:顺序结构(一个文件占若干连续磁带块)
  • 存放信息:记录信息和控制信息。磁头间隙
• 1.磁带的物理特性:启停型、顺序访问型设备

第5页：8.2.2 存储设备的物理特性

2.磁盘的物理特性:旋转型设备移动臂(头)磁盘组的物理结构…………盘面0…盘面2盘面1盘面m-1柱面0柱面l-1柱面1扇区0扇区1扇区n-1引臂

第6页：8.2.2 存储设备的物理特性（续）

• 柱面号i盘面号j扇区号k块号b (一维地址)三维地址
• 编址方法:使相邻块物理上最近例子:柱面数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存储设备的物理特性
  • 最上、最下为伺侯面,不存放信息,用于磁头定位;
  • 若盘片数为S，盘面数m＝2S-2=2(S-1);
  • 每个盘面被分成2i个扇区,每个扇区含多个磁道。
  • 存储容量＝磁头数×磁道(柱面)数×每道扇区数×每扇区字节数三维数组[柱面数,盘面数,扇区数]按行存储的数组元素的顺序号就是磁盘的块号。

第7页：8.2.2 存储设备的物理特性（续3）

• ①三维地址(i , j , k)→一维地址b：b=i×m×n + j×n + k=(i×m + j)×n + k
• ②一维地址b→三维地址(i , j , k)：i=b÷(m×n)j=b mod (m×n)÷nk=b mod (m→n) mod n其中：m为盘面数, n为扇区数

第8页：8.2.2 存储设备的物理特性（续4）

扇区0扇区7扇区6扇区5扇区4扇区3扇区2扇区1未考虑读写延迟的扇区编号(无交错):

第9页：8.2.2 存储设备的物理特性（续5）

扇区0扇区7扇区3扇区6扇区2扇区5扇区1扇区4考虑读写延迟的扇区编号(单交错)：

第10页：8.2.2 存储设备的物理特性（续6）

扇区0扇区5扇区2扇区7扇区4扇区1扇区6扇区3考虑读写延迟的扇区编号(双交错)：

第11页：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 in charge of block I/O
• 通道方式(channel)special processor for dealing with I/O operations

第12页：8.3.1程序控制查询方式缺点

• 8.3.1程序控制查询方式缺点:
  • 处理机与设备串行工作;
  • 消耗大量处理机时间。内存映射输入输出:将设备地址映射为内存地址空间一部分,硬件提供专用的输入输出指令。F查询方式完成CPU启动设备结束

第13页：8.3.2中断驱动方式CPU

• 8.3.2中断驱动方式CPU
• 计算
• 启动设备
• 计算
• …
• 计算
• 中断处理
• 计算设备工作特点:CPU与设备并行工作设备多时对CPU打扰多

第14页：8.3.2中断驱动方式CPU（续）

8.3.3 DMA方式设备操作码内存地址计数器忙碌标志状态寄存器缓冲区DMA控制器opcodeoperandsbusystatus……CPU123内存4567

第15页：8.3.2中断驱动方式CPU（续3）

• 8.3.3 DMA方式.
• ①CPU将操作数送入operands寄存器;
• ②CPU将操作码送入opcode寄存器并启动DMA控制器;DMA将busy置位,不接受新命令, CPU可做其它操作;
• ③DMA控制设备与其缓冲区的数据传输;
• ④DMA控制设备其缓冲区与内存的数据传输;
• ⑤DMA控制器将内存地址寄存器加1同时将记数器减1，若计数器不为0,则转
• ③;
• ⑥DMA复位busy寄存器,并向CPU发中断”传输完”;
• ⑦CPU读入status,确认操作成功。

第16页：8.3.4 通道方式

• 1.指令系统
  • 基本操作:读、写、控制、转移、结束
  • 指令格式:
• 2.运控部件
  • 通道地址字CAW:存放下一条通道指令地址;
  • 通道命令字CCW:存放当前正在执行的通道指令;
  • 通道状态字CSW:存放通道、控制器、设备的状态;包括I/O完成信息、出错信息、复执次数等;
  • 通道数据字CDW:暂存设备与内存之间的I/O数据。
• 3.存储区域(与CPU共用内存)
  • 通道程序，I/O数据地址信息特征位传输字节数操作码
• 通道:负责I/O操作的处理器。以内存为中心,支持块传输。

第17页：8.3.4 通道方式（续）

4.通道程序执行过程通道程序执行流程按CAW取通道指令⇒CCW(CAW)+1⇒CAWCCW是结束指令向主机发中断请求结束F执行CCW一个通道程序可以控制传输多组数据。

第18页：8.3.4 通道方式（续3）

• 通道类型
• 字节多路通道(byte multiplexer channel)多个非分配型子通道，连接低速外围设备
• 数组选择通道(block selector channel)一个分配型子通道，连接多台高速设备
• 数组多路通道(block multiplexer channel)多个非分配型子通道，连接多台高速设备

第19页：8.3.4 通道方式（续4）

设备、通道、内存连接数组选择通道磁盘字节多路通道打印机输入机内存处理器磁带数组多路通道

第20页：8.4 设备分配与去配

• 独占型设备的分配与去配
  • 块型独占
  • 字符型独占
• 共享型设备的分配与去配
  • 块型共享

第21页：8.4.1 独占型设备的分配与去配

• 数据结构设备控制块(UCB)设备标识(设备号)设备状态相连通道占有设备进程通道控制块(CCB)通道标识通道类型等待队列占有通道进程系统设备表(SDT)UCB表指针等待队列设备数设备名……………………PtrSmmprinter……………………打印机的UCB表UCB1(printer1)UCB2(printer2)…………UCBm(printerm)

第22页：8.4.1 独占型设备的分配与去配（续）

• 用户使用独占型设备活动：申请，使用，使用，…，使用，释放
  • 申请:
• ①根据设备名查SDT表；
• ②P(Sm)；
• ③查UCB表找一空闲设备并分配。
  • 使用:
• ①分配通道(若通道占用则等待);
• ②IO数据传输;
• ③去配通道。
  • 释放:
• ①根据释放设备名找SDT表对应入口;
• ②根据设备号查UCB表，找到该设备去配;
• ③V(Sm)

第23页：8.4.2 共享型设备的分配与去配

用户使用共享型设备活动

使用，使用，…，使用

特征

⑴来自文件系统、虚拟存储系统、输入/输出＃管理程序;⑵每次读写一块；⑶通常经过缓存；⑷排队优化。

使用

IO传输

第24页：8.5 设备驱动

• 8.5.1通道程序
  • 通道指令序列所构成的程序;
  • 静态编制或根据I/O要求动态生成;
  • 执行1次I/O,或多次I/O;
  • 可与处理器的操作并行;
  • 多个通道程序可以并行。8.5.2设备启动通道程序形成后:
  • 处理器将通道程序起始地址放到内存指定单元;
  • 运行通道启动指令启动通道;
  • 由指定内存单元取通道程序起始地址⇒CAW;
  • 执行通道程序。

第25页：8.5 设备驱动（续）

8.5.3中断处理...形成通道程序...启动通道...中断处理...CPUCCW1CCW2…CCWi...CCWn数据区设备内存通道程序通道CAWCCWCSWCDW中断

第26页：8.6 设备调度

• 优化服务顺序
• 考虑因素
  • 公平性：防止饿死
  • 高效性：减少磁盘引臂移动量

第27页：8.6.1磁盘I/O参数

• 8.6.1磁盘I/O参数
• 读/写一个磁盘块需要时间Ta的计算一般由如下三个因素确定：
  • 寻道时间(seek time)将磁盘引臂移动到指定柱面所需要的时间;
  • 旋转延迟(rotational delay)指定扇区旋转到磁头下的时间;
  • 传输时间(transfer time)读/写一个扇区的时间。

第28页：8.6.1磁盘I/O参数（续）

• 8.6.1磁盘I/O参数
• 1.寻道时间Ts计算公式如下:Ts=m×n+s其中n为跨越磁道数,m为跨越一个磁道所用时间,s为启动时间。
• 2.旋转延迟Tr计算公式如下:Tr= 1/(2r)其中,r为磁盘转速(单位:周/分钟)。该公式给出的是平均旋转延迟,它是磁盘旋转一周时间的一半,即旋转半周所花费的时间。

第29页：8.6.1磁盘I/O参数3.传输时间T…

8.6.1磁盘I/O参数3.传输时间Tt计算公式如下：Tt=b/(r N)其中，b为读/写字节数,r为磁盘转速,N为一条磁道上的字节数。

第30页：8.6.1磁盘I/O参数

• 8.6.1磁盘I/O参数
• 因此，可将访问b个字节的时间Ta表示为:Ta=Ts+Tr+Tt=m×n+s+1/(2r)+b/(rN)
• 访问磁盘通常是以扇区(块)为单位的，令M为一个磁道上扇区的个数,则每扇区的字节数=每磁道字节数/每磁道扇区数=N/M则一个扇区的访问时间为：Ta=Ts+Tr+Tt=m×n+s+1/(2r)+1/(rM)

第31页：8.6.2 磁盘引臂调度算法磁盘引臂调度

(disk head scheduling)1.先到先服务(FCFS)请求序列:130, 42, 180, 15, 108, 68, 97移动量:(130-53)+(130-42)+(180-42)+(180-15)+(108-15)+(108-68)+(97-68)=63001542536897108130180199

第32页：8.6.2 磁盘引臂调度算法

2.最短查找时间优先(SSTF)请求序列:130, 42, 180, 15, 108, 68, 9701542536897108130180199移动量:(53-42)+(180-42)+(180-15)=314问题:存在饥饿和饿死问题。

第33页：23301542536897108130

3.扫描算法(SCAN)不停地双向往复扫描磁道到尽头,双向响应路径请求。请求序列:130, 42, 180, 15, 108, 68, 97移动量: (53-0)+(180-0)=

第34页：20301542536897108130

4.LOOK算法:又称电梯算法前进方向有请求,则响应;若前方没请求且反向有请求,则改变方向响应请求。否则,停止。请求序列:130, 42, 180, 15, 108, 68, 97移动量: (53-15)+(180-15)=

第35页：01542536897108130180

5.循环扫描(C-SCAN)单方向扫描响应路径请求;到头后快速移动到另一头继续扫描。请求序列:130, 42, 180, 15, 108, 68, 97移动量=(199-53)+(199-0)+(42-0)=387特点：所有磁道地位、最长等待时间相同。

第36页：0154253689710813…（续）

6.C-LOOK算法前进方向有请求,则响应;若前方没请求且反向有请求,则移到反向最远端请求位置继续沿原方向扫描响应请求。否则,停止。请求序列:130, 42, 180, 15, 108, 68, 97移动量=(180-53)+(180-15)+(42-15)=319015425368971081301801998.6.2磁盘引臂调度算法SCAN和LOOK存在”磁头粘性”(arm stickiness)问题。

第37页：8.6.2 磁盘引臂调度算法

• 7.N-step SCAN和冻结扫描(Freezing SCAN)
• N步扫描将磁盘请求队列分为若干个长度为N的子队列,每个队列内采用SCAN算法。例:磁道由外向内编号0~99,磁头当前位置20,向内移动,N=4请求序列:12, 5, 7, 30,60, 77, 13, 26,61, 80, 53, 66响应序列:20→30→12→7→5→13→26→60→77→80→66→61 →53当N很大时,接近SCAN算法当N=1时,蜕化为FCFS算法

第38页：8.6.2 磁盘引臂调度算法（续）

• FSCAN:请求队列被”冻结”。
  • 将磁盘请求分为两个子队列:
  • 服务队列
  • 请求队列
  • 用SCAN算法扫描服务队列,并为请求服务,服务期间新到达的请求入请求队列;
  • 扫描完成后交换两个队列的地位。

第39页：8.6.3 磁盘访问举例

例8-3：设有一个单磁头的磁盘,磁道由外向内编号0、1、2、…、199。磁头移动一个扇区(柱面?)所需时间为1ms ;每个磁道有100个扇区;磁盘转速6000r/min。当前引臂位置处于第100磁道,当前移动方向由外向内，并规定引臂向内扫描时为路径请求服务。对于如下磁道请求120、85、70、30，每个请求访问对应磁道上的一个扇区。采用C-LOOK引臂调度算法，问：(1)给出引臂移动序列，计算引臂移动量和寻道时间，忽略启动时间；(2)计算平均旋转延迟时间；(3)计算传输时间；(4)计算所有访问处理时间。

第40页：8.6.3 磁盘访问举例（续）

解答：(1)磁盘引臂移动序列为: 100→120→30→70→85，跨越磁道数：20+90+40+15=165。共需寻道时间165×1ms=165ms.(2) 1次访盘的旋转延迟为：Tr=1/(2r)=1/(2×(6000/m))=1/(2×(100/s))=5ms，4次访盘的旋转延迟为4×5ms=20ms.(3) 1次访盘的传输时间为：Tt=1/(rM)=1/((6000/m)×100)=1/((100/s)×100)=0.1ms，4次访盘的传输时间为4×0.1ms=0.4ms.(4)所有访问处理时间=165+20+0.4=185.4(ms)。

第41页：8.7 缓冲技术

• 8.7.1缓冲技术的引入缓冲技术:处理数据到达与离开速度不一致所采用的技术。
• Buffering vs. Caching
  • buffering: one data copy
  • caching: multiple data copy8.7.2硬缓冲与软缓冲
  • 硬缓冲区通常设在设备中,由硬件实现；
  • 软缓冲区通常设在内存系统空间中,由软件实现。

第42页：8.7.3 私用缓冲与公共缓冲

• 私用缓冲一个缓冲区与一个固定设备相联系,不同设备使用不同的缓冲区;
• 公共缓冲缓冲区由系统统一管理,所有缓冲区构成缓冲池,按需要动态分派给正在进行I/O传输的设备。

第43页：8.7.3 私用缓冲与公共缓冲（续）

• 8.7.4单缓冲、双缓冲与循环缓冲缓冲技术分为:单缓冲、双缓冲、多缓冲以及缓冲池4种。
  • 单缓冲:设备与进程之间设一个缓冲区;数据传输模式为”进程↔缓冲区↔设备”;处理器与设备对缓冲区的操作是串行;
  • 双缓冲:设备与进程之间设置两个缓冲区;数据传输时,两个缓冲区交替使用;提高处理器与设备之间的并行性。
  • 循环缓冲:设备与进程之间设置多个缓冲区,并链成环形。设置输入指针in和输出指针out。

第44页：8.7.3 私用缓冲与公共缓冲（续3）

• 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个空缓冲区空缓冲区空缓冲区

第45页：8.7.3 私用缓冲与公共缓冲（续4）

8.7.6缓冲技术的实现每个设备一个缓冲队列,队列的每块缓冲区动态向系统申请。⒈输入型设备输入设备缓冲区缓冲区缓冲区……进程空间I/O链通道程序操作系统输入型设备缓冲示图

第46页：8.7.6 缓冲技术的实现

进程方面I/O链空设备忙申请空缓冲启动设备由I/O链取一缓冲信息→进程空间释放空缓冲结束TTFF等待中断方面缓冲入I/O链有等待进程TF唤醒传输完毕申请空缓冲启动设备F结束T输入型设备缓冲技术的实现

第47页：8.7.6 缓冲技术的实现（续）

⒉输出型设备输出设备缓冲区缓冲区缓冲区……进程空间I/O链通道程序操作系统输出型设备缓冲示图

第48页：8.7.6 缓冲技术的实现（续3）

输出型设备缓冲技术的实现进程方面申请空缓冲信息→缓冲结束TTFF中断方面释放空缓冲区I/O链空F由I/O链取一缓冲启动设备传输结束T设备忙缓冲入I/O链启动设备传输完

第49页：8.7.6 缓冲技术的实现（续4）

⒊输入输出设备(磁带、磁盘)输出/输入设备缓冲区缓冲区缓冲区……进程空间I/O链通道程序操作系统输入输出型设备缓冲示图缓冲区头设备物理块号I/O方向标识等待进程缓冲区体缓冲区格式

第50页：8.7.6 缓冲技术的实现（续5）

进程输入申请空缓冲信息→进程空间填写头部设备工作缓冲区入I/O链尾启动设备等待释放空缓冲区结束FTF中断方面输入唤醒等待者释放空缓冲TFI/O链空由I/O链取一缓冲启动设备传输结束T进程输出申请空缓冲填写头部设备工作缓冲区入I/O链尾启动设备T信息→缓冲结束F

第51页：UNIX缓冲(P300～303)

• UNIX缓冲(P300～303)
• 字符型缓冲
  • 100个缓冲区,长度8字节(6字符+2指针);
  • 组成公共缓冲池,所有字符型设备公用;
  • 缓冲区或属于cfreelist,或属于某字符设备(eg. tty,lp)
• 块型缓冲
  • 50个缓冲区,长度514字节;
  • 组成公共缓冲池,所有块型设备公用;
  • 缓冲区可属于bfreelist and/or devtab
• 预先读入的块(breada)
• 延迟写出的块(bdwrite)

第52页：UNIX缓冲(P300～303)（续）

struct cblock {struct cblock *c_next;char info[6];}struct cblock *cfreelist;

第53页：UNIX缓冲(P300～303)（续3）

struct buf//actually a buffer header, shared by all mounted disks{ int b_flags;

第54页：UNIX缓冲(P300～303)（续4）

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:

第55页：UNIX缓冲(P300～303)（续5）

struct devtab

第56页：相关操作

相关操作：getblk(dev,blkno)

第57页：相关操作（续）

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

第58页：brelse(bp)

• brelse(bp)
• 参数：bp:缓冲区头指针
• 返回：无
• 步骤：
• 有等待者(b_flag&B_WANTED!=0),唤醒;
• bfreelist上有等待者,唤醒
• bp入av链

第59页：bread(dev,blkno)

• bread(dev,blkno)
• 参数：dev:设备号，blkno:设备块号
• 返回：载有信息的缓冲区bp
• 步骤：
• bp=getblk(dev,blkno)
• if (缓冲区数据有效)
• return(bp)

  第60页：bread(dev,blkno)（续）

  • breada(dev,blkno,rablkno)
  • 参数：dev:设备号，blkno:读块号，rablkno:预读块号
  • 返回：blk缓冲块指针rbp
  • 步骤：
  • rbp=getblk(dev,blkno)
  • if(信息无效)
  • 启动设备读入(d_actf/d_actl链)
  • rabp=getblk(dev,rablkno)
  • if (B_DONE)

    第61页：bwrite(bp)

    • bwrite(bp)
    • 参数：bp：缓冲区指针
    • 步骤：
    • 入设备d_act队列(若设备不忙启动设备)
    • if(! B_ASYNC)
    • sleep(等待IO完成事件)
    • 中断
    • bp入b链, (b_forw/b_back)
    • brelse(bp), (bp入av链)

    第62页：bdwrite(bp)

    • bdwrite(bp)
    • 参数: bp:缓冲区指针
    • 返回:无
    • 步骤：
    • 标记b_flags =| B_DELWRI | B_DONE
    • bp入设备b_forw/b_back队列
    • brelse(bp), (bp入av链)

    第63页：bawrite(bp)

    • bawrite(bp)
    • 参数：bp:缓冲区头指针
    • 返回：无
    • 步骤：
    • bp->b_flag =| B_ASYNC
    • bwrite(bp)
    • 中断
    • (入b_act队列)
    • 入av队列

    第64页：8.8 输入输出进程

    • 自主I/O方式:进程执行I/O操作;
    • 专门负责I/O传输的进程
      • 另外一种I/O模式—服务模式;
      • C/S Model
    • I/O实现:进程向I/O进程发消息;
    • 特点
      • 界面清晰,方便使用;
      • 两次进程切换,速度问题;

    第65页：8.9 RAID技术

    • 8.9 RAID技术
    • RAID
      • RedundantArray ofInexpensiveDiskscompared with SLEDs (Single Large Expensive Disks)
      • RedundantArray ofIndependentDisks

        第66页：@B1@RAID

        • RAID
          • RAID is a set of physical disks viewed by the operatingsystem as a single logical drive;
          • Data are distributed across an array of physical drives
          • Redundant disk capacity is used to store parity information,which guarantees data recoverability in case of disk failure.
        • Hardware RAID vs. Software RAID
          • hardware based: special controller;
          • Windows NT, 2000, UNIX support software RAID.
        • SCSI RAID vs. IDE RAID
          • performance: SCSI outperforms IDE;
          • price: IDE beats SCSI.8.9 RAID技术

        第67页：8.9.1 RAID级别

        • 8.9.1 RAID级别
        • RAID级别:行业标准规定的数据在多个磁盘上的存放方法。常见RAID级别: level0,…, level5;
        • RAID分条(stripping)数据存储方式
          • 位级分条(bit-level stripping)
          • 块级分条(block-level strpping)
        • RAID衡量指标
          • 速度:是否支持多个访问同时进行;
          • 可靠性:是否能够发现和改正错误;
          • 成本:是否有额外的开销和开销的大小。

        第68页：8.9.1 RAID级别（续）

        • 8.9.1 RAID级别1.Level0 (分条) :数据分条以块为单位连续的数据条循环存放在多个磁盘上。
          • 访问速度快；
          • 经济，空间利用率100％；
          • 无容错能力，可靠性差。block0block4block8……Disk1block1block5block9……Disk2block2block6block10……Disk3block3block7block11……Disk4控制器(4,5)(2,3)读请求写请求

        第69页：8.9.1 RAID级别（续3）

        • 8.9.1 RAID级别2.Level1 (镜像):数据分条以块为单位采用分布镜像(mirroring)方式存储,即完全相同的数据重复存放在两个盘上。block0block3block6……Disk1block1block4block7……Disk2block2block5block8……Disk3控制器(3,4)(8)读请求写请求block0block3block6……Disk4block1block4block7……Disk5block2block5block8……Disk6
          • 访问速度快;读一个盘、写两个盘;
          • 可靠性高;
          • 费用高,是无镜像磁盘数的2倍,空间利用率50％。

        第70页：8.9.1 RAID级别（续4）

        8.9.1 RAID级别3.Level2 (位级汉明纠错码奇偶校验与恢复):数据以位(bit)为单位分条,分布存放在多个数据磁盘上;汉明纠错码存放在纠错磁盘上。bit0……Disk1bit1……Disk2bit2……Disk3控制器(3,4,5)写请求bit3……Disk4bit4……Disk5bit5……Disk6bit6……Disk7

        第71页：8.9.1 RAID级别（续5）

        • 8.9.1 RAID级别
        • 纠错能力强,可靠性高;
        • 需要较多纠错盘存放汉明纠错码,成本较高;
        • 不能同时为多个请求服务,速度较慢:
          • 读操作:所有磁盘同时访问,数据与错误校验码被送到磁盘阵列控制器;
          • 写操作:必须同时访问所有数据盘和纠错盘。

        第72页：8.9.1 RAID级别（续6）

        • 8.9.1 RAID级别4.Level3 (位级单个奇偶校验):数据以位(bit)为单位分条,分布存放在多个数据磁盘上;只用一个冗余磁盘存放奇偶校验位。bit0……Disk1bit1……Disk2bit2……Disk3bit3……Disk4奇偶校验……Disk5
          • 有一定容错能力;
          • 存储代价较低;
          • 读写需要访问所有盘,多个读写不能并行。控制器(0,1)等待(3)写请求写请求

        第73页：8.9.1 RAID级别（续7）

        8.9.1 RAID级别5.Level4 (块级异或校验):数据分条以块为单位,用异或运算产生校验信息,校验信息保存在单独的磁盘上。block0block4block8……Disk1block1block5block9……Disk2block2block6block10……Disk3block3block7block11……Disk4P0-3P4-7P8-11……Disk5控制器(5,6)(11)读请求读请求

        第74页：8.9.1 RAID级别（续8）

        • 8.9.1 RAID级别
          • 读操作不进行异或校验,可以并行;
          • 写操作要更新异或校验信息,都访问校验盘,不能并行;写操作时校验信息更新:P’4~7=(block4 xor block4’)xor p4~7
          • 异或校验信息用于磁盘发生故障时数据块的恢复。例如:若block7所在的Disk4发生故障,要恢复block7。p4~7= block4XORblock5XORblock6XORblock7则p4~7XOR(block4XORblock5XORblock6)=全0XORblock7=block7所以block7= p4~7XOR(block4XORblock5XORblock6)

        第75页：8.9.1 RAID级别（续9）

        8.9.1 RAID级别6.Level5 (块级分布式异或校验):数据分条以块为单位,异或校验信息分散循环保存在各磁盘上。block0block4block8block12P16~19……Disk1控制器(1)(6)写请求写请求block1block5block9P12~15block16……Disk2block2block6P8~11block13block17……Disk3block3P4-7block10block14block18……Disk4P0~3block7block11block15block19……Disk5

        第76页：8.9.1 RAID级别（续10）

        • 8.9.1 RAID级别
          • 磁盘数量至少为3个;
          • 读操作可并行;
          • 不涉及相同数据盘和校验盘的写操作可以并行;
          • 对于单盘容量为S、数量为N的磁盘阵列,有效存储容量为: S×(N-1)磁盘利用率为: (N-1)/N
          • 任意磁盘发生故障,均可根据其它N-1个磁盘恢复;

        第77页：4 块级分布式异或校验支持支持块

        8.9.1 RAID级别表8-1 RAID级别的比较冗余(容错/开销)写并发性读并发性分条粒度Level无支持支持块0镜像不支持支持块1汉明纠错码奇偶校验与恢复不支持不支持位2单个奇偶校验不支持不支持位3块级异或校验不支持支持块

        第78页：4 块级分布式异或校验支持支持块（续）

        • 8.9.2硬件RAID与软件RAID
        • 硬件RAID是RAID技术主流,需RAID控制器、价格贵;
        • 软件RAID不需专用RAID器,成本低、性价比高;软件RAID问题:
          • 速度、可靠性不如硬件RAID;
          • 系统兼容性:同一台机器的不同操作系统的软件RAID的识别问题;
          • 操作系统的引导问题。

        第79页：8.10 虚拟设备

        概念

        利用共享型设备实现的数量较多、速度较快的独占型设备。

        引入

        用户直接使用独占型设备效率低。

        实现

        输入型虚拟设备

        输出型虚拟设备

        虚拟设备的例子1.SPOOLing输入2.SPOOLing输出

        第80页：@B1@用户使用独占型设备活动

        • 用户使用独占型设备活动：申请，使用，使用，…，使用，释放进程独占此设备8.10.1虚拟设备的引入
        • 缺点:
          • 速度: CPU与设备速度不匹配;
          • 设备利用率:占有期间不一定一直使用。

        第81页：8.10.1 虚拟设备的引入

        • 方法:在进程与独占型设备之间增加共享设备缓冲。内存进程共享型设备虚拟设备虚拟设备......独占设备间断传输连续传输

        第82页：8.10.2 虚拟设备的实现

        1.输入型虚拟设备的实现

        ①申请:

        分配一虚拟设备;

        分配一实设备;

        信息由实设备→虚拟设备;

        去配该实设备。

        ②使用

        信息由虚拟设备→进程空间。

        ③释放

        去配虚拟设备。

        第83页：8.10.2 虚拟设备的实现（续）

        2.输出型虚拟设备的实现

        ①申请

        分配一虚拟设备。

        ②使用

        信息由进程空间→虚拟设备。

        ③释放:

        分配一实设备;

        信息由虚拟设备→实设备;

        去配实设备;

        去配虚拟设备。

        第84页：8.10.3 虚拟设备举例

        • 假脱机系统SPOOLingSimultaneous Peripheral Operation On-Line由SPOOLing程序控制通道完成1.SPOOLing输入作业预输入(输入机→输入井)2.SPOOLing输出作业缓输出(输出井→输出机)

        第85页：8.10.3 虚拟设备举例（续）

        1.假脱机输入系统Job11……Job1m输入机通道磁盘预输入进程内存预输入进程作业…………输入井输入机通道作业

        第86页：8.10.3 虚拟设备举例（续3）

        0.3虚拟设备举例⑴假脱机输入程序假脱机输入有待输入作业等待有空闲作业表项等待取一空闲表目作为作业控制块作业状态标志为”提交”为作业申请输入井空间填写”作业控制块”作业状态标志为”后备”作业调度等待”后备”作业唤醒FFF由输入机传送作业到输入井

        第87页：8.10.3 虚拟设备举例（续4）

        • 0.3虚拟设备举例⑵输入井管理程序
        • 输入井是磁盘上的区域,存储分配、数据传输以块为单位;
        • 输入井管理程序管理输入井空间;
        • 输入井也可以由文件实现,预输入的作业保存在文件中。

        第88页：8.10.3 虚拟设备举例（续5）

        2.假脱机输出系统Job21……Job2n通道磁盘缓输出进程内存缓输出进程…………输出井通道输出机输出机结果结果

        第89页：8.10.3 虚拟设备举例（续6）

        0.3虚拟设备举例⑴假脱机输出程序假脱机输出输出井有”完成”作业等待取一个”完成”作业输出作业结果释放该作业所占输出井空间作业状态标志为”退出”有等待空闲作业控制块的预输入进程唤醒FF⑵输出井管理程序

        第90页：8.11 稳定存储器

        • (stable storage)
        • 定义:不丢失信息的存储器称为稳定存储器。
        • 实现
          • 不存在绝对可靠的存储介质;
          • 策略:利用冗余技术,在两种失效独立的介质上构建。
          • 保存
        • ①将信息写到第一个存储块;
        • ②上述操作成功后,将相同信息写到第二存储块;
        • ③仅当第二次传输也成功时,整个保存操作完成。

        第91页：8.11 稳定存储器（续）

        • 恢复:鉴别两个数据块内容
        • 一对信息完全相同,且无检测到错误,正常;
        • 其中一块检测到错误,用另一块取代;
        • 两块均未检测到错误,但内容不同,用第二块内容取代第一块内容。

        第92页：8.12 系统举例

        • Windows 2000/XP涉及内容：设备驱动、设备缓冲、文件管理。
        • 主要特点
        • ①系统管理员可动态添加或删除设备,相应的驱动程序通常以DLL的形式动态加载,设备驱动程序可以采用高级语言编写,移植性好;
        • ②除NTFS外,支持多种可装卸的文件系统,如FAT32、OS/2、HPFS、CDFS等。支持内存映像文件I/O;
        • ③设备管理子系统以I/O请求包(I/O Request Package，IRP)方式驱动,每个I/O请求均表示为I/O请求包, I/O管理器负责协调所有各组成部分之间的相互作用。
        • ④通过系统进程(线程)提供异步I/O, I/O请求的进程(线程)不需要等待I/O传输结果,请求者可以立即返回,具体I/O操作由系统线程负责完成。异步I/O通过异步过程调用(AsynchronousProcedure Call，APC)实现。

        第93页：8.12 系统举例（续）

        应用程序系统服务IO管理程序文件系统磁盘驱动光盘驱动磁带驱动…Windows2000/XP IO子系统