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