操作系统08.pptx

《操作系统08.pptx》由会员分享，可在线阅读，更多相关《操作系统08.pptx（88页珍藏版）》请在三一办公上搜索。

1、第八章 设备与I/O管理,设备及其分类设备的物理特性IO传输方式（查询、中断、通道、DMA）设备分配与去配设备驱动设备调度缓冲技术输入输出进程RAID技术虚拟设备,*设备及其分类,用途存储型设备磁盘，磁带，光盘IO型设备扫描仪，打印机，mouse，keyboard，monitor，网络设备网卡，交换机，etc.,*设备及其分类,管理共享型设备（块型）多个进程的IO操作以块为单位可以交叉独占型设备（块型）多个进程的IO操作以块为单位不宜交叉独占型设备（字符型）多个进程的IO操作以字符为单位不能交叉,IO设备的物理特性传输一字节发生一次中断存储设备的物理特性 I/O传输必须以完整的块为基本单位,设

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 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

3、 15 16 17,三维地址一维地址：b=imn+jn+k一维地址三维地址：i=b(mn)j=b mod(mn)n k=b mod(mn)mod n,未考虑读写延迟的扇区编号：,考虑读写延迟的扇区编号(单交错)：,考虑读写延迟的扇区编号(双交错)：,*I/O 传输方式,IO操作演变历史程序查询方式(programmed IO)(polling)CPU and Device can not work in parallel 中断方式(interrupt)CPU and device can work in parallel,too many interrupts for CPU通道方式(chan

4、nel)special processor for dealing with io operations直接内存方式(DMA)DMA controller in charge of block io,*程序控制查询方式,CPU启动设备,完成,F,T,缺点:处理机与设备串行工作;消耗大量处理机时间.,*中断驱动方式,CPU计算启动设备计算计算中断处理计算,设备:,工作,特点:CPU与设备并行工作 设备多时对CPU打扰多,*DMA方式,DMA控制器内部：操作码寄存器、操作数寄存器、忙碌标记寄存器、状态寄存器，控制寄存器用以指明所用端口号、I/O传输方向、传输单位等。DMA控制器通过总线与设备、内存

5、相连。无论DMA位置何处，都可以独立CPU直接访问总线。,*DMA方式,CPU将操作量送到DMA控制器的操作数寄存器，包括内存起始地址、传输数量等；CPU将操作码送到DMA控制器的操作码寄存器以启动DMA控制器，DMA控制器将忙碌寄存器置位，表明此期间不接受新命令；DMA控制器与设备交往，数据：设备缓冲区；DMA控制器复制数据：缓冲区内存空间；记数器减1，重复上述过程直至计数器为0，此时DMA控制器向CPU发出中断信号.,.,*通道方式,通道负责IO操作的处理机指令系统基本操作：控制、读、写、转移、结束指令格式：（操作码，传输量，特征位，地址）运控部件CAW，CCW，CSW，CDW存储区域（与

6、CPU共用内存,通道内有缓冲区）通道程序，IO数据（channel does have its buffers）,*通道方式,通道是专门负责I/O操作的处理机，除DMA数据块传输功能之外，通道具有更加强大的I/O传输功能.相同点：(1)以内存为中心；(2)支持块传输.不同点：通道是专门的处理机，有自己的指令系统，可以实施复杂的I/O控制.,1.通道指令系统,(1)基本操作空操作:不执行任何操作,顺取下一条指令;读操作:从指定设备输入一批数据;写操作:向指定设备输出一批数据;控制操作:控制外部设备机械性动作,如磁带反绕、磁盘引臂移动、打印纸换页等;转移操作:实现指令的非顺序执行;结束操作:通道程

7、序执行完毕,向主机发送通道中断信号.(2)指令格式,2.通道运控部件,(1)通道地址字(CAW)：记录下一条通道指令存放的地址,其功能类似于中央处理机的指令计数器PC.(2)通道命令字(CCW)：保存正在执行的通道指令,其作用相当于中央处理机的指令寄存器.(3)通道状态字(CSW)：记载通道、控制器、设备的状态.包括I/O传输完成信息,出错信息,复执次数等;(4)通道数据字(CDW)：暂存内存与设备之间I/O传输的数据.,3.通道存储区域,与主机共享同内存,通道使用内存具有如下两个用途:(1)保存通道程序:通道程序是通道指令的有序序列,由系统中的输入输出进程根据用户进程的I/O要求来确定.通道

8、程序可能是事先编制好的,也可能是临时动态产生的.(2)保存交换数据:对于输入操作来说,内存地址空间用于保存将由输入设备读入的数据;对于输出操作来说,内存地址空间保存将向输出设备输出的数据.,通道程序执行过程：,按CAW取通道命令CCW,（CAW）+1 CAW,是通道结束命令,执行此命令,F,向CPU发中断,一个通道程序可以控制若干设备进行多次IO传输。,T,通道类型,字节多路通道(byte multiplexer channel)多个非分配型子通道，连接低速外围设备数组选择通道(block selector channel)一个分配型子通道，连接多台高速设备数组多路通道(block multi

9、plexer channel)多个非分配型子通道，连接多台高速设备,设备、通道、内存连接,选择通道,磁盘,字节多路通道,打印机,输入机,内存储器,处理机,磁带,数组多路通道,*设备的分配与去配,独占型设备的分配与去配块型独占字符型独占共享型设备的分配与去配块型共享,数据结构设备控制块(UCB)通道控制块(CCB),设备标识设备状态相连通道占有设备进程,通道标识通道状态通道类型占有通道进程,系统设备表(SDT),设备类 总数 设备等待队列 UCB表指针 lp m Sm,UCBUCBUCB,独占型设备的分配与去配用户使用独占型设备活动：申请，使用，使用，使用，释放 申请：(1)根据设备类查SDT表

10、(2)P(Sm)(3)查UCB表找一空闲设备并分配 使用：(1)分配通道(2)IO传输(3)去配通道 释放：(1)根据释放设备类找SDT表对应入口(2)查UCB表，去配(3)V(Sm),8.4 设备的分配与去配,共享型设备的分配与去配用户使用共享型设备活动使用，使用，使用特征来自文件系统；每次读（写）一块；通常经过缓冲；排队优化。使用分配通道；IO操作；释放通道,*设备驱动,通道程序CCW指令序列静态编制或动态生成通道程序的执行可与处理机的操作并行 设备启动通道启动中断处理通道向CPU发的中断,*设备驱动,设备,CAWCCWCDWCSW,.形成通道程序.地址CAW.启动通道.中断处理.,启动,

11、中断,内存,CPU,通道,*设备驱动,设备,CAWCCWCDWCSW,.形成通道程序.地址CAW.启动通道.中断处理.,启动,中断,内存,CPU,通道,*设备驱动,设备,CAWCCWCDWCSW,.形成通道程序.地址CAW.启动通道.中断处理.,启动,中断,内存,CPU,通道,*设备驱动,设备,CAWCCWCDWCSW,.形成通道程序.地址CAW.启动通道.中断处理.,启动,中断,内存,CPU,通道,*设备调度,优化服务顺序考虑因素公平性防止饿死高效性减少磁盘引臂移动量,磁盘引臂调度(disk head scheduling),先到先服务（FCFS）按照输入输出请求的次序为各个进程服务 请求序

12、列：130，42，180，15，108，68，97,移动量:(130-53)+(130-42)+(180-42)+(180-15)+(108-15)+(108-68)+(97-68)=630,磁盘引臂调度(disk head scheduling),最短寻找时间优先（SSTF）：优先为距磁头当前所在位置最近柱面的请求服务 请求序列：130，42，180，15，108，68，97,移动量:(53-42)+(180-42)+(180-15)=314 缺点:“磁道歧视”,该算法缺乏公平性，存在饥饿和饿死问题.,磁盘引臂调度(disk head scheduling),SCAN（LOOK）请求序列：1

13、30，42，180，15，108，68，97,SCAN移动量:(53-0)+(180-0)=233LOOK移动量:(53-15)+(180-15)=203,0 15 42 53 68 97 108 130 180 199,Look Scan,磁盘引臂调度(disk head scheduling),C-SCAN（C-LOOK）请求序列：130，42，180，15，108，68，97,特点：所有磁道地位最长等待时间相同问题：diskhead stickiness（磁头粘性）,磁盘引臂调度(disk head scheduling),N-step SCAN（N步扫描）将磁盘请求队列分为若干个长度为

14、N的子队列，每个队列内采用SCAN算法例子：磁道由外向内编号0-99,磁头当前位置20,向内移动,N=412,5,7,30,60,77,13,26,61,80,53,662030127513266077806661 53当N很大时，接近SCAN算法当N=1时，蜕化为FCFS算法,磁盘引臂调度(disk head scheduling),FSCAN（Freezing SCAN，冻结扫描)将磁盘请求分为两个子队列，服务队列请求队列用SCAN算法扫描服务队列，并为请求服务，服务期间新到达的请求入请求队列扫描完成后交换两个队列的地位,*磁盘I/O参数,首先分析一下读/写一个磁盘块需要多少时间。它一般由

15、如下三个因素确定：寻道时间（seek time）：将磁盘引臂移动到指定柱面所需要的时间；旋转延迟（rotational delay）：指定扇区旋转到磁头下的时间；传输时间（transfer time）：读/写一个扇区的时间。,*磁盘I/O参数,寻道时间Ts计算公式如下：Ts=mns其中，n为跨越磁道数，m为跨越一个磁道所用时间，s为启动时间。旋转延迟Tr计算公式如下：Tr=1/(2r)其中，r为磁盘转速。该公式给出的是平均旋转延迟，它是磁盘旋转一周时间的一半，即旋转半周所花费的时间。,*磁盘I/O参数,传输时间Tt计算公式如下：Tt=b/(rN)其中，b为读/写字节数，r为磁盘转速，N为一条磁

16、道上的字节数。,*磁盘I/O参数,因此，可将访问时间Ta表示为：访问磁盘通常是以扇区（块）为单位的，令M为一个磁道上扇区的个数，则一个扇区的访问时间为：,例题,例8-1设有一个只有一个移动磁头的磁盘，磁道由外向内编号0、1、2、199，磁头移动一个磁道所需时间为1ms，每个磁道有100个扇区，磁盘转速6000r/m。采用CLOOK引臂调度算法，当前引臂位置处于第100磁道，当前移动方向由外向内，并规定引臂向内扫描时为路经请求服务。对于如下磁道请求120、85、70、30，每个请求访问对应磁道上的一个扇区，问：(1)给出引臂移动序列，计算引臂移动量和寻道时间，忽略启动时间；(2)计算平均旋转延迟

17、时间；(3)计算传输时间；(4)计算所有访问处理时间。,例题,解答：(1)磁盘引臂移动序列为:100120307085，跨越磁道数：20+90+40+15=165。共需寻道时间1651ms=165ms.(2)1次访盘的旋转延迟为：Tr=1/(2r)=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)。,*缓冲技术,设备处理

18、数据到达与离开速度不一致所采用的技术。Buffering vs.Cachingbuffering:one data copycaching:multiple data copy(slow多,fast少)硬缓冲与软缓冲 硬缓冲区通常设在设备中 软缓冲区通常设在内存系统空间中 私用缓冲与公共缓冲 一个缓冲区与一个固定设备相联系，不同设备使用不同的缓冲区 利用率低 缓冲区由系统统一管理，按需要动态分派给正在进行I/O传输的设备,Var buf_num:semaphore;(init n)mutex:semaphore;(init 1)1.申请 2.释放(1)P(buf_num)P(mutex)(2)

19、P(mutex)空缓冲入链尾(3)取链头空缓冲 V(mutex)(4)V(mutex)V(buf_num),缓冲池管理,tail,缓冲技术实现：输入设备,io链,进程方面：,中断方面：,IO链空,设备忙,申请空缓冲,启动设备,等待,由io链取一缓冲,信息进程空间,释放空缓冲,缓冲入io链,有等待进程,唤醒,传输完毕,申请空缓冲,启动设备,F,T,F,T,F,T,T,F,缓冲技术实现：输出设备,进程方面：,中断方面：,申请一空缓冲,信息缓冲,设备忙,启动设备,缓冲入io链,传输完,T,F,F,T,释放空缓冲,io链空,取一缓冲,启动设备,T,F,输入输出设备：(磁带、磁盘),块型缓冲区：,进程空

20、间,缓冲,IO设备,缓冲,缓冲,.,io链,进程方面(输入)：,进程方面(输出)：,中断方面：,申请空缓冲,填写头部,设备工作?,入io链尾,启动设备,信息进程,释放缓冲,申请空缓冲,填写头部,信息缓冲,设备工作,启动设备,入io链,输入,唤醒等待者,释放空缓冲,io链空,取一缓冲,启动设备,F,T,F,T,T,F,F,T,等待,UNIX缓冲,字符型缓冲100个缓冲区，长度8字节(6字符+2指针)组成公共缓冲池，所有字符型设备公用缓冲区或属于cfreelist,或属于某字符设备(eg.tty,lp)块型缓冲50个缓冲区，长度514字节组成公共缓冲池，所有块型设备公用缓冲区可属于bfreelis

21、t and/or devtab预先读入的块(breada)延迟写出的块(bdwrite),字符型设备缓冲struct cblock struct cblock*c_next;char info6;struct cblock*cfreelist;/free c blocks,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 bu

22、f*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 transferred after error bufNBUF,块型设备缓冲（头部）,15 14 13 12 11

23、 10 9 8 7 6 5 4 3 2 1 0,B_READ/B_WRITE,B_DONE,B_ERROR,B_BUSY,B_WANTED,B_RELOC,B_ASYNC,B_DELWRI,b_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 for this dev struct buf*d_actf;/head of IO queue

24、 struct buf*d_actl;/tail of IO queue,char 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 on second b

25、lock bwrite(bp)/write the buffer,wait pletion,then releasebawrite(bp)/start the io,release buffer,no wait pletionbdwrite(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 implied,*输入输出进程,专门负责IO

26、传输的进程另外一种IO模式服务模式C/S Model特点界面清晰,方便使用两次进程切换,速度问题,*RAID技术,RAID:Redundant Array of Inexpensive pared with SLEDs(Single Large Expensive Disks)Redundant Array of Independent Disks/独立磁盘冗余阵列Proposed by researchers at UC BerkeleyDavid A.PattersonBackgrounddisk access speed increases pared with CPUsolution:

27、multiple ponentObjectiveenhanced performancehigh reliability,RAID技术,RAIDRAID is a set of physical disks viewed by the operating system as a single logical driveData are distributed across an array of physical drivesRedundant disk capacity is used to store parity information,which guarantees data rec

28、overability in case of disk failureHardware RAID vs.Software RAIDhardware based:special controller Windows NT,2000,UNIX support software RAIDSCSI RAID vs.IDE RAIDperformance:SCSI outperforms IDEprice:IDE beats SCSI,*RAID级别,RAID级别:行业标准规定的数据在多个磁盘上的存放方法。常见RAID级别:level0,level5;RAID分条(stripping)数据存储方式位级分

29、条(bit-level stripping)块级分条(block-level stripping)RAID衡量指标速 度:是否支持多个访问同时进行;可靠性:是否能够发现和改正错误;成 本:是否有额外的开销和开销的大小.,Level0(数据分条),数据分条以块为单位,连续的数据条循环存放在多个磁盘上。,访问速度快；经济，空间利用率100；无容错能力，可靠性差。,Level1(镜像,mirroring):,数据分条以块为单位,采用分布镜像方式存储,即完全相同的数据重复存放在两个盘上。,访问速度快;读一个盘、写两个盘;可靠性(恢复性)高;费用高,是无镜像磁盘数的2倍,空间利用率50。,Level2(

30、位级汉明纠错码校验与恢复):,数据以位(bit)为单位分条,分布存放在多个数据磁盘上,汉明纠错码存放在纠错磁盘上。,Level2(位级汉明纠错码校验与恢复):,纠错能力强,可靠性高;发现2个错误,纠正1个错误.需要较多纠错盘存放汉明纠错码,成本较高;不能同时为多个请求服务,速度较慢:读操作:所有磁盘同时访问,数据与错误校验码被送到磁盘阵列控制器;写操作:必须同时访问所有数据盘和纠错盘。,数据以位(bit)为单位分条,分布存放在多个数据磁盘上;只用一个冗余磁盘存放奇偶校验位。,bit0,Disk1,bit1,Disk2,bit2,Disk3,bit3,Disk4,奇偶校验,Disk5,有一定容错

31、能力;存储代价较低;读写需要访问所有盘,多个读写不能并行。,控 制 器,(0,1),等待(3),写请求,写请求,Level3(位级单个奇偶校验),Level4(块级异或校验):,数据分条以块为单位,用异或运算产生校验信息,校验信息保存在单独的磁盘上。,block0block4block8,Disk1,block1block5block9,Disk2,block2block6block10,Disk3,block3block7block11,Disk4,P0-3P4-7P8-11,Disk5,控 制 器,(5,6),(11),读请求,读请求,Level5(块级分布式异或校验),数据分条以块为单位

32、,异或校验信息分散循环保存在各磁盘上。,block0block4block8block12P1619,Disk1,控 制 器,(1),(6),写请求,写请求,block1block5block9P1215block16,Disk2,block2block6P811block13block17,Disk3,block3P4-7block10block14block18,Disk4,P03block7block11block15block19,Disk5,Level5(块级分布式异或校验),校验码计算:p47=block4 XOR block5 XOR block6 XOR block7若bloc

33、k7发生故障，可通过下式恢复block7=p47 XOR block4 XOR block5 XOR block6,Level 5(Cont.),磁盘数量至少为3个;读操作可并行;不涉及相同数据盘和校验盘的写操作可以并行;对于单盘容量为S、数量为N的磁盘阵列,有效存储容量为:S(N-1)磁盘利用率为:(N-1)/N任意磁盘发生故障,均可根据其它N-1个磁盘恢复;,*RAID级别(Cont.),*Remark on Software RAID,Pros:cost lesssimplicityCons:performanceboot volume limitation/导引卷不能是RAIDleve

34、l support:only 0,1,5 are supportedOS compatibility:multiple problemother patibilityreliabilitysoftware bugs,Benefit from RAID,Increased read/write speedImproved data reliabilityEnlarged storage capacitymultiple disks viewed as a single volume,*虚拟设备,概念利用共享型设备实现的数量较多、速度较快的独占型设备引入用户直接使用独占型设备效率低实现输入型虚拟设

35、备输出型虚拟设备虚拟设备的例子SPOOLing输入SPOOLing输出,*虚拟设备引入,用户使用独占型设备活动：申请，使用，使用，使用，释放缺点：速度：CPU与设备速度不匹配设备利用率：占有期间不一定一直使用,进程独占此设备,方法：在进程与独占型设备之间增加共享设备缓冲,虚拟设备,虚拟设备,虚拟设备,虚拟设备,进程,独占设备,共享设备（如磁盘）,间断传输,连续传输,*虚拟设备的实现,输入型虚拟设备的实现申请：分配一虚设备分配一实设备信息由实设备虚设备去配该实设备使用：信息由虚设备进程空间释放：去配虚设备,输出型虚拟设备的实现申请：分配一虚设备使用：信息由进程空间虚设备释放：分配一实设备信息由虚

36、设备实设备去配实设备去配虚设备,*虚拟设备的实现,*虚拟设备的例子,SPOOLing输入作业预输入（输入机输入井）SPOOLing输出作业缓输出（输出井输出机）SPOOLingSimultaneous Peripheral Operation On-Line由SPOOLing程序控制通道完成,.,.,job11,job1m,.,输入井,预输入进程,输入机,预输入进程,内存,.,SPOOLing输入程序（1）vs.SPOOLing输入进程（n）,输入机,有待输入作业,有空闲作业表,等待,等待,取一“空闲”作业表为JCB,作业状态改为“提交”,申请输入井空间,作业内容输入井,填写JCB,作业状态改

37、为“后备”,作业调度等待“后备”作业,唤醒,SPOOLing 输入程序,F,T,F,T,F,T,F,T,内存中已有N道作业,等待,输入井中有后备作业,等待,访问磁盘中的作业表根据JCB中的调度参数按照作业调度算法选一后备作业,作业状态标记为“执行”,为该作业建立作业控制进程,F,作业调度程序,T,.,.,job11,job1n,.,输出井,缓输出进程,缓输出进程,内存,输出机,输出机,SPOOLing输出程序（1）vs.SPOOLing输出进程（n）,输出作业结果,释放输出井空间,状态改为“空闲”,是否有等待空闲JCB的预输入进程,唤醒一个,输出井有“完成”作业,取一“完成”作业,状态改为“退出”,等待,SPOOLing 输出程序,F,T,T,F,*稳定存储器(stable storage),定义不丢失信息的存储器称为稳定存储器实现不存在绝对可靠的存储介质策略：冗余在两种失效独立的介质上构建保存将信息写到第一个存储块上述操作成功后，将相同信息写到第二存储块仅当第二次传输也成功时，整个保存操作完成,*稳定存储器(stable storage),实现恢复鉴别两个数据块内容一对信息完全相同，且无检测到错误，正常其中一块检测到错误，用另一块取代两块均未检测到错误，但内容不同，用第二块内容取代第一块内容,