磁盘调度算法

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,基于连续多媒体的磁盘调度算法研究,研 究 生：崔英志,指导教师：杨 武 教授,基于连续多媒体的磁盘调度算法研究,论文研究背景,1,连续多媒体应用及特点,2,磁盘调度算法研究现状,3,多级空间磁盘调度算法,4,工作总结与下一步工作,5,论文研究背景,互联网和计算机技术的发展，推动了传输数据的多元化，多媒体数据就是其中最典型的一种。,多媒体应用的出现促进了计算机硬件和软件技术的进一步发展。,特别是堆存储、视频压缩，以及高速网络等技术的推广，使得提供多媒体服务具有更高的可行性,2.,连续多媒体应用,互联网,2.,连续多媒体应用,实时性,信息量大,连续性,视频,、,声音,等数据以,实时传输协议,承载，并以,连续的流,的形式从源端向目的端传输，在目的端接收到一定缓存数据后就可以播放出来的,多媒体应用,。,2.,连续多媒体应用,体系结构,负载均衡,其他技术,服务质量保障,QoS,数据存储,网络性能,磁盘调度,3.,磁盘调度算法研究现状,公平性,寻道时间,吞吐量,实时性,优先级,稳定性,先来先服务：,FCFS,最短寻道时间优先：,SSTF,最短空闲时间优先：,LSF,LOOK,&,C-LOOK,“电梯”算法：,SCAN,最早截止期限优先：,EDF,SCAN-EDF,P-SCAN,SSEDO/SSEDV,FD-EDF,多级队列磁盘调度,：,BUCKET,分组交换调度：,GSS,MDSS,Cello,MARS,APEX,C-SCAN,传统算法,实时算法,多媒体算法,4.,多级空间磁盘调度算法,MSSDS,多级空间磁盘调度算法,MSSDS,：,Multi-Staged Spaces Disk Scheduling,封装器,调度器,条件抢占策略,优先级反转优化,避免出现“饿死”,初始优先级,截止期限约束,磁盘利用率,空间填充曲线,SFC,理论,三级空间,模型,4.1,空间填充曲线,Space-Filling Curve,，简称,SFC,Peano,、,Sweep,、,C-SCAN,、,Gray,、,Hilbert,、,Spiral,、,Diagonal,Giuseppe Peano,（,1858-1932,）,Peano,贯穿整个,2,维空间曲线中所有点,，,它覆盖空间整个区域中各个部分却,不相交,。,甚至可以扩展到,N,维超立方体空间,中。,Sweep,Diagonal,Hilbert,4.1,空间填充曲线的特点,空间中的每一,点,，曲线,只通过一次,它保留了点的“,邻近性,”，也就是说如果两个点在曲线上是相互邻近的，那么他们在空间上也,可能,是相互邻近的,空间上邻近的点,在空间填充曲线上也可能是邻近的,从,一维空间到,N,维空间,，空间填充曲线保持了空间数据之间的空间关系,空间填充曲线可以将,单位空间,上的问题转化为,单位间隔,上的问题，达到,将多维空间映射到一维空间,的目的，从而使问题的求解变得更容易。,4.2,算法模型,封装器,调度器,SFC1,SFC2,SFC3, ,P,1,P,D,P,2,截止时间,磁盘位置,基于,SFC,的优先级队列,4.2,算法模型,SFC处理实例,A,（,3,）,R1,R4,R7,R10,R13,R16,B,（,1,）,R2,R5,R8,R11,R14,C,（,2,）,R3,R6,R9,R12,R15,R1,、,R2,、,R3,、,R4,、,R5,、,R6,、,R7,、,R8,、,R9,、,R10,、,R11,、,R12,、,R13,、,R14,、,R15,、,R16,初始请求队列,R2,、,R5,、,R8,、,R11,、,R14,、,R3,、,R6,、,R9,、,R12,、,R15,、,R1,、,R4,、,R7,、,R10,、,R13,、,R16,填充请求队列,Diagonal,空间填充曲线,R2,、,R14,、,R5,、,R8,、,R3,、,R12,、,R7,、,R15,、,R6,、,R11,、,R9,、,R1,、,R10,、,R13,、,R4,、,R16,输出队列：,Sweep,Diagonal,4.3,封装器,支持,视频广播应用的,视频服务研究模型,Pana Viss,MSSDS-SFC1,：,基于初始优先级,1,MSSDS-SFC2,：,基于截止期限,2,MSSDS-SFC3,：,基于寻道时间,3,环境：,QoS,参数高达,12,（即,12,维），,每一个,QoS,参数（维）具有,16,个优先级别。,4.3.1 MSSDS-SFC1,：基于初始优先级,Diagonal,Gray,Hilbert,环境：,QoS,参数高达,12,（即,12,维），,每一个,QoS,参数（维）具有,16,个优先级别。,4.3.1 MSSDS-SFC1,：基于初始优先级,Diagonal,整体性能最好,4.3.2 MSSDS-SFC2,：基于截止期限,f,：平衡因子,最小化错过率,选择性错过,当,f=1,时，算法会在优先级,反转,和截止期限错过之间取得合理的平衡,其中，,Diagonal SFC,最好,4.3.3 MSSDS-SFC3,：基于寻道时间优化,MSSDS-SFC1,：,Diagonal,MSSDS-SFC2,：,Diagonal,MSSDS-SFC3,：,Sweep,R,MSSDS-SFC1,：基于初始优先级,MSSDS-SFC2,：基于截止期限,MSSDS-SFC3,：基于寻道时间,R = 3,4.4,调度器,非抢占调度,新到来的请求无法剥夺当前正在执行的磁盘请求所占用的资源,优先级反转情况明显,抢占调度,任何新的请求只要具有足够高的优先级，就可以抢占当前请求所占用的资源,可能造成“饿死”,条件抢占调度策略,1,优先级反转优化,2,避免出现“饿死”,3,4.4.1,条件抢占调度策略,显著高优先级,R,new,、,R,cur,、,q,、,q,滑动窗口,w,显著高优先级：,R,new, R,cur,- w,2. wMAX(Vc),时,仍然有可能出现“饿死”现象,q,中的请求具有显著高优先级时，如何,实现优先级反转,服务与提升策略,磁盘开始服务,q,中的某个请求之前，会首先检查,q,中是否存在具有“显著高优先级”的请求。,到达,序列,4.4.2,优先级反转优化,执行序列,R1,R2,R3,R4,R5,R6,R7,R1,R2,R5,R6,R3,R7,R4,4.4.3,避免“饿死”,扩展,与,重置策略,根据滑动窗口,w,的值不断,扩大或缩小,，调度算法将会在,非抢占调度,和,条件抢占调度,之间来回移动。,4.5 MSSDS,算法的特点,适应性,MSSDS,算法通过细微的调整就可以满足不同的需求，因此可灵活应用于不同的环境。,通用性,MSSDS,算法是其它磁盘调度算法的通用算法。如果忽略掉,3,个阶段的空间填充曲线，并将,w,设置为,0,，则算法就会和其它一维磁盘调度算法一样工作。,扩展性,MSSDS,算法可以通过扩展应用到多优先级调度或实时系统中。,5.,工作总结,多级空间磁盘调度算法,MSSDS,Multi-Staged Spaces Disk Scheduling,公平性,寻道时间,吞吐量,实时性,优先级,稳定性,现有磁盘调度算法,多媒体数据特点,空间填充曲线,SFC,理论,调度算法三级空间模型,封装器,调度器,初始优先级,截止期限,磁盘利用率,条件抢占策略,优先级反转优化,避免“饿死”,6.,下一步工作,进一步,完善,MSSDS,算法,，重点放在平衡因子,w,的调整方面,结合,缓冲技术,，对调度过程中的请求队列分级管理,研究多媒体数据流传输中的,网络特性,，融入对吞吐量、差错率、负载均衡等方面的研究。,采用高性能的,磁盘冗余、容错技术,，加强多媒体信息在数据分布存储方面的研究。,请各位专家批评指正！谢谢！,