08第八章 设备与IO管理1

第八章设备与I/O管理,设备及其分类设备的物理特性IO传输方式（查询、中断、通道、DMA）设备分配与去配设备驱动设备调度缓冲技术输入输出进程RAID技术虚拟设备,8.1设备及其分类,用途存储型设备磁盘，磁带，光盘IO型设备扫描仪，打印机，mouse，keyboard，monitor，网络设备网卡，交换机，etc.,8.1设备及其分类,管理共享型设备（块型）多个进程的IO操作以块为单位可以交叉独占型设备（块型）多个进程的IO操作以块为单位不宜交叉独占型设备（字符型）多个进程的IO操作以字符为单位不能交叉,IO设备的物理特性传输一字节发生一次中断存储设备的物理特性磁带的物理特性,8.2设备的物理特性,磁盘组的物理特性,盘面0,盘面1,盘面2,盘面m-1,扇区1,扇区0,扇区n-1,柱面0,柱面l-1,.,引臂,柱面号i盘面号j扇区号k,块号b（一维地址）,（三维地址）,编址方法：使相邻块物理上最近例子：l=2;m=3;n=3柱面号：000000000111111111盘面号：000111222000111222扇区号：012012012012012012块号：01234567891011121314151617,三维地址一维地址：b=imn+jn+k一维地址三维地址：i=b(mn)j=bmod(mn)nk=bmod(mn)modn,未考虑读写延迟的扇区编号：,考虑读写延迟的扇区编号(单交错)：,考虑读写延迟的扇区编号(双交错)：,光盘的物理特性:读取原理:pit/land螺旋线,22188圈(展开5.6km),内侧转速:530转/分;外侧转速:200转/分(密度均匀,读取速度均匀),14个bit构成一个symble,42个symble构成一个frame,98个frame构成一个sector,Sector2352bytes,588bits的frame各包含24字节,Preamble:16bytes,前12bytes为:00FFFFFFFFFFFFFFFFFFFF00后随3bytes扇区编号,最后字节为mode,2048字节,288字节,8.3I/O传输方式,IO操作演变历史程序查询方式(programmedIO)(polling)CPUandDevicecannotworkinparallel中断方式(interrupt)CPUanddevicecanworkinparallel,toomanyinterruptsforCPU通道方式(channel)specialprocessorfordealingwithiooperations直接内存方式(DMA)DMAcontrollerinchargeofblockio,8.3.1程序控制查询方式,CPU启动设备,完成,F,T,缺点:处理机与设备串行工作;消耗大量处理机时间.,8.3.2中断驱动方式,CPU计算启动设备计算计算中断处理计算,设备:,工作,特点:CPU与设备并行工作设备多时对CPU打扰多,8.3.3DMA方式,数据传输,CPU,DMA控制器,内存,缓冲,磁盘,中断,DMA请求,总线,磁盘控制器,回答,DMA编程,启动中断状态,8.3.3DMA方式,.,CPU通过设置DMA控制器实现DMA编程，同时启动磁盘控制器由磁盘读入数据至内部缓冲区并进行和校验；DMA控制器向磁盘控制器发出读请求，并将内存地址放在地址总线上；磁盘控制器将字节传到内存指定单元；磁盘控制器向DMA控制器发送回答；DMA控制器将内部地址寄存器加1同时将记数减1，重复上述过程直至计数器为0，此时DMA控制器向CPU发出中断信号.,8.3.4通道方式,通道负责IO操作的处理机指令系统基本操作：控制、读、写、转移、结束指令格式：（操作码，传输量，特征位，地址）运控部件CAW，CCW，CSW，CDW存储区域（与CPU共用内存,通道内有缓冲区）通道程序，IO数据（channeldoeshaveitsbuffers）,通道程序执行过程：,按CAW取通道命令CCW,（CAW）+1CAW,是通道结束命令,执行此命令,F,向CPU发中断,一个通道程序可以控制若干设备进行多次IO传输。,T,通道类型,字节多路通道(bytemultiplexerchannel)多个非分配型子通道，连接低速外围设备数组选择通道(blockselectorchannel)一个分配型子通道，连接多台高速设备数组多路通道(blockmultiplexerchannel)多个非分配型子通道，连接多台高速设备,设备、通道、内存连接,选择通道,磁盘,字节多路通道,打印机,输入机,内存储器,处理机,磁带,数组多路通道,8.4设备的分配与去配,独占型设备的分配与去配块型独占字符型独占共享型设备的分配与去配块型共享,数据结构设备控制块(UCB)通道控制块(CCB),设备标识设备状态相连通道占有设备进程,通道标识通道状态通道类型占有通道进程,系统设备表(SDT),设备类总数设备等待队列UCB表指针lpmSm,UCBUCBUCB,独占型设备的分配与去配用户使用独占型设备活动：申请，使用，使用，使用，释放申请：(1)根据设备类查SDT表(2)P(Sm)(3)查UCB表找一空闲设备并分配使用：(1)分配通道(2)IO传输(3)去配通道释放：(1)找SDT表对应入口(2)查UCB表，去配(3)V(Sm),8.4设备的分配与去配,共享型设备的分配与去配用户使用共享型设备活动使用，使用，使用特征来自文件系统；每次读（写）一块；通常经过缓冲；排队优化。使用分配通道；IO操作；释放通道,8.5设备驱动,通道程序CCW指令序列静态编制或动态生成设备启动通道启动中断处理通道向CPU发的中断,8.5设备驱动,设备,CAWCCWCDWCSW,.形成通道程序.地址CAW.启动通道.中断处理.,启动,中断,内存,CPU,通道,8.5设备驱动,设备,CAWCCWCDWCSW,.形成通道程序.地址CAW.启动通道.中断处理.,启动,中断,内存,CPU,通道,8.5设备驱动,设备,CAWCCWCDWCSW,.形成通道程序.地址CAW.启动通道.中断处理.,启动,中断,内存,CPU,通道,8.5设备驱动,设备,CAWCCWCDWCSW,.形成通道程序.地址CAW.启动通道.中断处理.,启动,中断,内存,CPU,通道,8.6设备调度,优化服务顺序考虑因素公平性防止饿死高效性减少磁盘引臂移动量,磁盘引臂调度(diskheadscheduling),先到先服务（FCFS）请求序列：130，42，180，15，108，68，97,移动量:(130-53)+(130-42)+(180-42)+(180-15)+(108-15)+(108-68)+(97-68)=630,磁盘引臂调度(diskheadscheduling),最短寻找时间优先（SSTF）请求序列：130，42，180，15，108，68，97,移动量:(53-42)+(180-42)+(180-15)=314,磁盘引臂调度(diskheadscheduling),SCAN（LOOK）请求序列：130，42，180，15，108，68，97,SCAN移动量:(53-0)+(180-0)=233LOOK移动量:(53-15)+(180-15)=203,01542536897108130180199,LookScan,磁盘引臂调度(diskheadscheduling),C-SCAN（C-LOOK）请求序列：130，42，180，15，108，68，97,特点：所有磁道地位最长等待时间相同问题：diskheadstickiness（磁头粘性）,磁盘引臂调度(diskheadscheduling),N-stepSCAN（N步扫描）将磁盘请求队列分为若干个长度为N的子队列，每个队列内采用SCAN算法例子：磁道由外向内编号0-99,磁头当前位置20,向内移动,N=412,5,7,30,60,77,13,26,61,80,53,66203012751326607780666153当N很大时，接近SCAN算法当N=1时，蜕化为FCFS算法,磁盘引臂调度(diskheadscheduling),FSCAN（FreezingSCAN，冻结扫描)将磁盘请求分为两个子队列，服务队列请求队列用SCAN算法扫描服务队列，并为请求服务，服务期间新到达的请求入请求队列扫描完成后交换两个队列的地位,8.6.1磁盘I/O参数,首先分析一下读/写一个磁盘块需要多少时间。它一般由如下三个因素确定：寻道时间（seektime）：将磁盘引臂移动到指定柱面所需要的时间；旋转延迟（rotationaldelay）：指定扇区旋转到磁头下的时间；传输时间（transfertime）：读/写一个扇区的时间。,8.6.1磁盘I/O参数,寻道时间Ts计算公式如下：Ts=mns其中，n为跨越磁道数，m为跨越一个磁道所用时间，s为启动时间。旋转延迟Tr计算公式如下：Tr=1/(2r)其中，r为磁盘转速。该公式给出的是平均旋转延迟，它是磁盘旋转一周时间的一半，即旋转半周所花费的时间。,8.6.1磁盘I/O参数,传输时间Tt计算公式如下：Tt=b/(rN)其中，b为读/写字节数，r为磁盘转速，N为一条磁道上的字节数。,8.6.1磁盘I/O参数,因此，可将访问时间Ta表示为：访问磁盘通常是以扇区（块）为单位的，令M为一个磁道上扇区的个数，则一个扇区的访问时间为：,例题,例8-1设有一个只有一个移动磁头的磁盘，磁道由外向内编号0、1、2、199，磁头移动一个磁道所需时间为1ms，每个磁道有100个扇区，磁盘转速6000r/m。采用CLOOK引臂调度算法，当前引臂位置处于第100磁道，当前移动方向由外向内，并规定引臂向内扫描时为路经请求服务。对于如下磁道请求120、85、70、30，每个请求访问对应磁道上的一个扇区，问：(1)给出引臂移动序列，计算引臂移动量和寻道时间，忽略启动时间；(2)计算平均旋转延迟时间；(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)。,8.7缓冲技术,设备处理数据到达与离开速度不一致所采用的技术。Bufferingvs.Cachingbuffering:onedatacopycaching:multipledatacopy(slow多,fast少)硬缓冲与软缓冲硬缓冲区通常设在设备中软缓冲区通常设在内存系统空间中私用缓冲与公共缓冲一个缓冲区与一个固定设备相联系，不同设备使用不同的缓冲区利用率低缓冲区由系统统一管理，按需要动态分派给正在进行I/O传输的设备,Varbuf_num:semaphore;(initn)mutex:semaphore;(init1)1.申请2.释放(1)P(buf_num)P(mutex)(2)P(mutex)空缓冲入链尾(3)取链头空缓冲V(mutex)(4)V(mutex)V(buf_num),缓冲池管理,tail,8.7.5缓冲技术实现：输入设备,io链,进程方面：,中断方面：,IO链空,设备忙,申请空缓冲,启动设备,等待,由io链取一缓冲,信息进程空间,释放空缓冲,缓冲入io链,有等待进程,唤醒,传输完毕,申请空缓冲,启动设备,F,T,F,T,F,T,T,F,8.7.5缓冲技术实现：输出设备,进程方面：,中断方面：,申请一空缓冲,信息缓冲,设备忙,启动设备,缓冲入io链,传输完,T,F,F,T,释放空缓冲,io链空,取一缓冲,启动设备,T,F,8.7.5输入输出设备：(磁带、磁盘),块型缓冲区：,进程空间,缓冲,IO设备,缓冲,缓冲,.,io链,进程方面(输入)：,进程方面(输出)：,中断方面：,申请空缓冲,填写头部,设备工作,入io链尾,启动设备,信息进程,释放缓冲,申请空缓冲,填写头部,信息缓冲,设备工作,启动设备,入io链,输入,唤醒等待者,释放空缓冲,io链空,取一缓冲,启动设备,F,T,F,T,T,F,F,T,等待,UNIX缓冲,字符型缓冲100个缓冲区，长度8字节(6字符+2指针)组成公共缓冲池，所有字符型设备公用缓冲区或属于cfreelist,或属于某字符设备(eg.tty,lp)块型缓冲50个缓冲区，长度514字节组成公共缓冲池，所有块型设备公用缓冲区可属于bfreelistand/ordevtab预先读入的块(breada)延迟写出的块(bdwrite),字符型设备缓冲structcblockstructcblock*c_next;charinfo6;structcblock*cfreelist;/freecblocksstructclist/associatedwithacharacterdeviceintc_cc;/charactercountintc_cf;/pointertofirstblockintc_cl;/pointertolastblock,structbuf/actuallyabufferheader,sharedbyallmounteddisksintb_flags;/BUSY,ASYNC,DELWRI,DONE.structbuf*b_forw;/headedbydevtabstructbuf*b_back;structbuf*av_forw;/positiononfreeliststructbuf*av_back;intb_dev;intb_wcount;/transfercountchar*b_addr;/lowordercore(buffer)addresschar*b_xmem;/highordercore(buffer)addresschar*b_blkno/block#ondevicecharb_error;char*b_resid;/wordnottransferredaftererrorbufNBUF,块型设备缓冲（头部）,1514131211109876543210,B_READ/B_WRITE,B_DONE,B_ERROR,B_BUSY,B_WANTED,B_RELOC,B_ASYNC,B_DELWRI,b_flag:,structdevtab/设备IO队列chard_active;/busyflagchard_errcnt;/errorcountstructbuf*b_forw;/firstbufferforthisdevstructbuf*b_back;/lastbufferforthisdevstructbuf*d_actf;/headofIOqueuestructbuf*d_actl;/tailofIOqueue,charbuffersNBUF514;/块型缓冲区structbufbfreelist;/缓冲区头部的链头,相关操作：getblk(dev,blkno)/assignabufferforthegivenblockbread(dev,blkno)/readablock(ifnecessary),returnbufpointerbreada(dev,blkno,rablkno)/readinfirstblock,likeread;butalsostartioonsecondblockbwrite(bp)/writethebuffer,waitforcompletion,thenreleasebawrite(bp)/starttheio,releasebuffer,nowaitforcompletionbdwrite(bp)/releasebuffer,markitsothatifitisgrabbedforanotherpurpose,itwillbewrittenoutbeforebeinggivenupbrelse(bp)/releasethebuffer,withnoioimplied,getblk(dev,blkno),参数：dev:设备号，blkno:设备块号返回：缓冲区指针bp步骤：块在b链中，且当前空闲由av链摘除，标记BUSY,返回缓冲块指针块在b链中，但BUSY(其它进程在用)sleep(空闲事件发生)，返回缓冲块指针不在b的链中，在av链上取到延迟写的块写出该块，分配下一个缓冲区不在b的链中，av链已空等待任意缓冲区变空闲的事件不在b的链中，在av链上得到空缓冲填写头部，由av链摘除，出旧b链，如新b链，返回缓冲块指针,brelse(bp),参数：bp:缓冲区头指针返回：无步骤：If有等待者(b_flagElsebfreelist上有等待者,唤醒bp入av链,bread(dev,blkno),参数：dev:设备号，blkno:设备块号返回：载有信息的缓冲区bp步骤：bp=getblk(dev,blkno)if(缓冲区数据有效)return(bp)/在cache中得到启动磁盘读(d_actf/d_actl链)sleep(等待读盘完成事件)中断唤醒return(bp),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)/缓冲区从b链得到brelse(rabp)/入av链else/缓冲区从av链得到启动设备读入(d_actf/d_actl链)/中断时入av链iowait(rbp)return(rbp),bwrite(bp),参数：bp：缓冲区指针步骤：入设备d_act队列(若设备不忙启动设备)if(!B_ASYNC)sleep(等待IO完成事件)中断唤醒brelse(bp),(bp入av链),bdwrite(bp),参数:bp:缓冲区指针返回:无步骤：标记b_flags=|B_DELWRI|B_DONEbrelse(bp),(bp入av链),bawrite(bp),参数：bp:缓冲区头指针返回：无步骤：bp-b_flag=|B_ASYNCbwrite(bp)中断入av队列,8.8输入输出进程,专门负责IO传输的进程另外一种IO模式服务模式C/SModel特点界面清晰,方便使用两次进程切换,速度问题,8.9RAID技术,RAID:RedundantArrayofInexpensiveDiskscomparedwithSLEDs(SingleLargeExpensiveDisks)RedundantArrayofIndependentDisks/独立磁盘冗余阵列ProposedbyresearchersatUCBerkeleyDavidA.PattersonBackgrounddiskaccessspeedincreasesslowlycomparedwithCPUsolution:multipleparallelcomponentObjectiveenhancedperformancehighreliability,RAID技术,RAIDRAIDisasetofphysicaldisksviewedbytheoperatingsystemasasinglelogicaldriveDataaredistributedacrossanarrayofphysicaldrivesRedundantdiskcapacityisusedtostoreparityinformation,whichguaranteesdatarecoverabilityincaseofdiskfailureHardwareRAIDvs.SoftwareRAIDhardwarebased:specialcontrollerWindowsNT,2000,UNIXsupportsoftwareRAIDSCSIRAIDvs.IDERAIDperformance:SCSIoutperformsIDEprice:IDEbeatsSCSI,8.9.1RAID级别,Howtoorganizedataacrossmultipledisks?Industrystandardsschemelevels:level0,level5level6,level7level01/10level03/30level05/50level15/51,Level0,blockstripinghighdatatransfercapacityeconomynofaulttolerance,d0,d1,d2,d3,d11,Level1,Mirror(mirroring)highperformance（读一个盘，写两个盘）highrecoverabilityexpensive,d0,d1,d2,d3,.,Level0+1,RAID01/10highreliabilityhighavailability（读一个盘，写两个盘）expensive,d0,d1,d2,d3,d4,d5,d6,d7,Level5,blockstrip+distributedparity容错好较经济（浪费一张盘）速度（支持写并行，如写d6和d5）,JBOD-SPAN,NotastandardRAIDleveljustbundleofdisksnoperformanceimprovementnosafetyguarantee,d1,d2,d3,d4,d5,RAIDlevel015N#ofdisks2,3,423,4,5CapacitySNSN/2S(N-1)Storeefficiency100%50%(N-1)/NFaulttoleranceno23Availability122Randomread435Randomwrite432Sequentialread524Sequentialwrite433Cost$,8.9.2RemarkonSoftwareRAID,Pros:costlesssimplicityCons:performancebootvolumelimitation/导引卷不能是RAIDlevelsupport:only0,1,5aresupportedOScompatibility:multipleproblemothersoftwarecompatibilityreliabilitysoftwarebugs,BenefitfromRAID,Increasedread/writespeedImproveddatareliabilityEnlargedstoragecapacitymultipledisksviewedasasinglevolume,8.10虚拟设备,概念利用共享型设备实现的数量较多、速度较快的独占型设备引入用户直接使用独占型设备效率低实现输入型虚拟设备输出型虚拟设备虚拟设备的例子SPOOLing输入SPOOLing输出,8.7.1虚拟设备引入,用户使用独占型设备活动：申请，使用，使用，使用，释放缺点：速度：CPU与设备速度不匹配设备利用率：占有期间不一定一直使用,进程独占此设备,方法：在进程与独占型设备之间增加共享设备缓冲,虚拟设备,虚拟设备,虚拟设备,虚拟设备,进程,独占设备,共享设备（如磁盘）,间断传输,连续传输,8.10.2虚拟设备的实现,输入型虚拟设备的实现申请：分配一虚设备分配一实设备信息由实设备虚设备去配该实设备使用：信息由虚设备进程空间释放：去配虚设备,输出型虚拟设备的实现申请：分配一虚设备使用：信息由进程空间虚设备释放：分配一实设备信息由虚设备实设备去配实设备去配虚设备,8.10.2虚拟设备的实现,8.10.3虚拟设备的例子,SPOOLing输入作业预输入（输入机输入井）SPOOLing输出作业缓输出（输出井输出机）SPOOLingSimultaneousPeripheralOperationOn-Line由SPOOLing程序控制通道完成,作业控制块(JobControlBlock),作业存在标志，其中保存系统管理作业需要的全部信息。JCB内容：作业标识用户标识作业状态调度参数作业位置资源需求进入时间处理时间记账信息,.,.,job11,job1m,.,输入井,预输入进程,输入机,预输入进程,内存,.,SPOOLing输入程序（1）vs.SPOOLing输入