MSDDS磁盘调度算法.ppt

基于连续多媒体的磁盘调度算法研究,研 究 生：崔英志 指导教师：杨 武 教授,基于连续多媒体的磁盘调度算法研究,论文研究背景,互联网和计算机技术的发展，推动了传输数据的多元化，多媒体数据就是其中最典型的一种。 多媒体应用的出现促进了计算机硬件和软件技术的进一步发展。 特别是堆存储、视频压缩，以及高速网络等技术的推广，使得提供多媒体服务具有更高的可行性,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,4.1 空间填充曲线的特点,空间中的每一点，曲线只通过一次 它保留了点的“邻近性”，也就是说如果两个点在曲线上是相互邻近的，那么他们在空间上也可能是相互邻近的 空间上邻近的点在空间填充曲线上也可能是邻近的 从一维空间到N维空间，空间填充曲线保持了空间数据之间的空间关系,空间填充曲线可以将单位空间上的问题转化为单位间隔上的问题，达到将多维空间映射到一维空间的目的，从而使问题的求解变得更容易。,4.2 算法模型,封装器,调度器,SFC1,SFC2,SFC3, ,P1,PD,P2,截止时间,磁盘位置,基于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,4.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 调度器,非抢占调度 新到来的请求无法剥夺当前正在执行的磁盘请求所占用的资源 优先级反转情况明显 抢占调度 任何新的请求只要具有足够高的优先级，就可以抢占当前请求所占用的资源 可能造成“饿死”,4.4.1 条件抢占调度策略,显著高优先级 Rnew、Rcur、q、q 滑动窗口w 显著高优先级：Rnew Rcur - 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. 工作总结,公平性,寻道时间,吞吐量,实时性,优先级,稳定性,现有磁盘调度算法,多媒体数据特点,空间填充曲线SFC理论,调度算法三级空间模型,6. 下一步工作,进一步完善MSSDS算法，重点放在平衡因子w的调整方面 结合缓冲