MSDDS磁盘调度算法课件

MSDDS磁盘调度算法本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！MSDDS磁盘调度算法本课件PPT仅供大家学习使用基于连续多媒体的磁盘调度算法研究论文研究背景1连续多媒体应用及特点2磁盘调度算法研究现状3多级空间磁盘调度算法4工作总结与下一步工作5基于连续多媒体的磁盘调度算法研究论文研究背景1连续多媒体应论文研究背景互联网和计算机技术的开展，推动了传输数据的多元化，多媒体数据就是其中最典型的一种。多媒体应用的出现促进了计算机硬件和软件技术的进一步开展。特别是堆存储、视频压缩，以及高速网络等技术的推广，使得提供多媒体效劳具有更高的可行性论文研究背景互联网和计算机技术的开展，推动了传输数据的多元化2.连续多媒体应用互联网2.连续多媒体应用互联网2.连续多媒体应用实时性信息量大连续性视频、声音等数据以实时传输协议承载，并以连续的流的形式从源端向目的端传输，在目的端接收到一定缓存数据后就可以播放出来的多媒体应用。2.连续多媒体应用实时性信息量大连续性视频、声音等数据以2.连续多媒体应用体系结构负载均衡其他技术服务质量保障QoS数据存储网络性能磁盘调度2.连续多媒体应用体系结构负载均衡其他技术服务质量保障Q3.磁盘调度算法研究现状公平性寻道时间吞吐量实时性优先级稳定性……先来先效劳：FCFS最短寻道时间优先：SSTF最短空闲时间优先：LSFLOOK&C-LOOK“电梯〞算法：SCAN最早截止期限优先：EDFSCAN-EDFP-SCANSSEDO/SSEDVFD-EDF多级队列磁盘调度：BUCKET分组交换调度：GSSMDSSCelloMARSAPEXC-SCAN传统算法实时算法多媒体算法3.磁盘调度算法研究现状公平性寻道时间吞吐量实时性优先级4.多级空间磁盘调度算法MSSDS多级空间磁盘调度算法MSSDS：Multi-StagedSpacesDiskScheduling封装器调度器条件抢占策略优先级反转优化避免出现“饿死”初始优先级截止期限约束磁盘利用率空间填充曲线SFC理论三级空间

模型4.多级空间磁盘调度算法MSSDS多级空间磁盘调度算法封4.1空间填充曲线Space-FillingCurve，简称SFCPeano、Sweep、C-SCAN、Gray、Hilbert、Spiral、DiagonalGiuseppePeano（1858-1932）Peano贯穿整个2维空间曲线中所有点，它覆盖空间整个区域中各个部分却不相交。甚至可以扩展到N维超立方体空间中。SweepDiagonalHilbert4.1空间填充曲线Space-FillingCurve4.1空间填充曲线的特点空间中的每一点，曲线只通过一次它保存了点的“邻近性〞，也就是说如果两个点在曲线上是相互邻近的，那么他们在空间上也可能是相互邻近的空间上邻近的点在空间填充曲线上也可能是邻近的从一维空间到N维空间，空间填充曲线保持了空间数据之间的空间关系空间填充曲线可以将单位空间上的问题转化为单位间隔上的问题，达到将多维空间映射到一维空间的目的，从而使问题的求解变得更容易。4.1空间填充曲线的特点空间中的每一点，曲线只通过一次空4.2算法模型封装器调度器SFC1SFC2SFC3…………P1PDP2截止时间磁盘位置基于SFC的优先级队列4.2算法模型封装器调度器SFC1SFC2SFC3……4.2算法模型SFC处理实例A（3）R1,R4,R7,R10,R13,R16B（1）R2,R5,R8,R11,R14C（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、R14、R5、R8、R3、R12、R7、R15、R6、R11、R9、R1、R10、R13、R4、R16输出队列：4.2算法模型SFC处理实例A（3）B（1）C（2）R1SweepDiagonal4.3封装器支持视频广播应用的视频服务研究模型PanaVissMSSDS-SFC1：基于初始优先级1MSSDS-SFC2：基于截止期限2MSSDS-SFC3：基于寻道时间3SweepDiagonal4.3封装器支持视频广播应用的环境：QoS参数高达12〔即12维〕，每一个QoS参数〔维〕具有16个优先级别。：基于初始优先级DiagonalGrayHilbert环境：：基于初始优先级DiagonalGrayHilbert环境：QoS参数高达12〔即12维〕，每一个QoS参数〔维〕具有16个优先级别。：基于初始优先级Diagonal整体性能最好环境：：基于初始优先级Diagonal整体性能最好：基于截止期限f：平衡因子最小化错过率选择性错过当f=1

时，算法会在优先级反转和截止期限错过之间取得合理的平衡其中，DiagonalSFC最好：基于截止期限f：平衡因子最小化错过率选择性错过当f=1时：基于寻道时间优化MSSDS-SFC1：DiagonalMSSDS-SFC2：DiagonalMSSDS-SFC3：SweepRMSSDS-SFC1：基于初始优先级MSSDS-SFC2：基于截止期限MSSDS-SFC3：基于寻道时间R=3：基于寻道时间优化MSSDS-SFC1：DiagonalRM4.4调度器非抢占调度新到来的请求无法剥夺当前正在执行的磁盘请求所占用的资源优先级反转情况明显抢占调度任何新的请求只要具有足够高的优先级，就可以抢占当前请求所占用的资源可能造成“饿死〞条件抢占调度策略1优先级反转优化2避免出现“饿死”34.4调度器非抢占调度条件抢占调度策略1优先级反转优化2条件抢占调度策略显著高优先级Rnew、Rcur、q、q’滑动窗口w显著高优先级：Rnew<Rcur-w2.w<MAX(Vc)时仍然有可能出现“饿死〞现象q’中的请求具有显著高优先级时，如何实现优先级反转条件抢占调度策略显著高优先级2.w<MAX(Vc)时仍效劳与提升策略磁盘开场效劳q中的某个请求之前，会首先检查q’中是否存在具有“显著高优先级〞的请求。到达序列优先级反转优化执行序列R1R2R3R4R5R6R7R1R2R5R6R3R7R4效劳与提升策略到达序列优先级反转优化执行序列R1R2R3R4扩展与重置策略根据滑动窗口w的值不断扩大或缩小，调度算法将会在非抢占调度和条件抢占调度之间来回移动。扩展与重置策略4.5MSSDS算法的特点适应性MSSDS算法通过细微的调整就可以满足不同的需求，因此可灵活应用于不同的环境。通用性MSSDS算法是其它磁盘调度算法的通用算法。如果忽略掉3个阶段的空间填充曲线，并将w设置为0，那么算法就会和其它一维磁盘调度算法一样工作。扩展性MSSDS算法可以通过扩展应用到多优先级调度或实时系统中。4.5MSSDS算法的特点适应性5.工作总结多级空间磁盘调度算法MSSDS——Multi-StagedSpacesDiskScheduling公平性寻道时间吞吐量实时性优先级稳定性……现有磁盘调度算法多媒体数据特点空间填充曲线SFC理论调度算法三级空间模型封装器调度器初始优先级截止期限磁盘利用率条件抢占策略优先级反转优化避免“饿死”5.工作总结多级空间磁盘调度算法MSSDS公平性寻道时间6.下一步工作进一步完善MSSDS算法，重点放在平衡因子w的调整方面结合缓冲技术，对调度过程中的请求队列分级管理研究多媒体数据流传输中的网络特性，融入对吞吐量、过失率、负载均衡等方面的研究。采用高性能的磁盘冗余、容错技术，加强多媒体信息在数据分布存储方面的研究。6.下一步工作进一步完善MSSDS算法，重点放在平衡因子请各位专家批评指正！

谢谢！请各位专家批评指正！

谢谢！MSDDS磁盘调度算法本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！MSDDS磁盘调度算法本课件PPT仅供大家学习使用基于连续多媒体的磁盘调度算法研究论文研究背景1连续多媒体应用及特点2磁盘调度算法研究现状3多级空间磁盘调度算法4工作总结与下一步工作5基于连续多媒体的磁盘调度算法研究论文研究背景1连续多媒体应论文研究背景互联网和计算机技术的开展，推动了传输数据的多元化，多媒体数据就是其中最典型的一种。多媒体应用的出现促进了计算机硬件和软件技术的进一步开展。特别是堆存储、视频压缩，以及高速网络等技术的推广，使得提供多媒体效劳具有更高的可行性论文研究背景互联网和计算机技术的开展，推动了传输数据的多元化2.连续多媒体应用互联网2.连续多媒体应用互联网2.连续多媒体应用实时性信息量大连续性视频、声音等数据以实时传输协议承载，并以连续的流的形式从源端向目的端传输，在目的端接收到一定缓存数据后就可以播放出来的多媒体应用。2.连续多媒体应用实时性信息量大连续性视频、声音等数据以2.连续多媒体应用体系结构负载均衡其他技术服务质量保障QoS数据存储网络性能磁盘调度2.连续多媒体应用体系结构负载均衡其他技术服务质量保障Q3.磁盘调度算法研究现状公平性寻道时间吞吐量实时性优先级稳定性……先来先效劳：FCFS最短寻道时间优先：SSTF最短空闲时间优先：LSFLOOK&C-LOOK“电梯〞算法：SCAN最早截止期限优先：EDFSCAN-EDFP-SCANSSEDO/SSEDVFD-EDF多级队列磁盘调度：BUCKET分组交换调度：GSSMDSSCelloMARSAPEXC-SCAN传统算法实时算法多媒体算法3.磁盘调度算法研究现状公平性寻道时间吞吐量实时性优先级4.多级空间磁盘调度算法MSSDS多级空间磁盘调度算法MSSDS：Multi-StagedSpacesDiskScheduling封装器调度器条件抢占策略优先级反转优化避免出现“饿死”初始优先级截止期限约束磁盘利用率空间填充曲线SFC理论三级空间

模型4.多级空间磁盘调度算法MSSDS多级空间磁盘调度算法封4.1空间填充曲线Space-FillingCurve，简称SFCPeano、Sweep、C-SCAN、Gray、Hilbert、Spiral、DiagonalGiuseppePeano（1858-1932）Peano贯穿整个2维空间曲线中所有点，它覆盖空间整个区域中各个部分却不相交。甚至可以扩展到N维超立方体空间中。SweepDiagonalHilbert4.1空间填充曲线Space-FillingCurve4.1空间填充曲线的特点空间中的每一点，曲线只通过一次它保存了点的“邻近性〞，也就是说如果两个点在曲线上是相互邻近的，那么他们在空间上也可能是相互邻近的空间上邻近的点在空间填充曲线上也可能是邻近的从一维空间到N维空间，空间填充曲线保持了空间数据之间的空间关系空间填充曲线可以将单位空间上的问题转化为单位间隔上的问题，达到将多维空间映射到一维空间的目的，从而使问题的求解变得更容易。4.1空间填充曲线的特点空间中的每一点，曲线只通过一次空4.2算法模型封装器调度器SFC1SFC2SFC3…………P1PDP2截止时间磁盘位置基于SFC的优先级队列4.2算法模型封装器调度器SFC1SFC2SFC3……4.2算法模型SFC处理实例A（3）R1,R4,R7,R10,R13,R16B（1）R2,R5,R8,R11,R14C（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、R14、R5、R8、R3、R12、R7、R15、R6、R11、R9、R1、R10、R13、R4、R16输出队列：4.2算法模型SFC处理实例A（3）B（1）C（2）R1SweepDiagonal4.3封装器支持视频广播应用的视频服务研究模型PanaVissMSSDS-SFC1：基于初始优先级1MSSDS-SFC2：基于截止期限2MSSDS-SFC3：基于寻道时间3SweepDiagonal4.3封装器支持视频广播应用的环境：QoS参数高达12〔即12维〕，每一个QoS参数〔维〕具有16个优先级别。：基于初始优先级DiagonalGrayHilbert环境：：基于初始优先级DiagonalGrayHilbert环境：QoS参数高达12〔即12维〕，每一个QoS参数〔维〕具有16个优先级别。：基于初始优先级Diagonal整体性能最好环境：：基于初始优先级Diagonal整体性能最好：基于截止期限f：平衡因子最小化错过率选择性错过当f=1

时，算法会在优先级反转和截止期限错过之间取得合理的平衡其中，DiagonalSFC最好：基于截止期限f：平衡因子最小化错过率选择性错过当f=1时：基于寻道时间优化MSSDS-SFC1：DiagonalMSSDS-SFC2：DiagonalMSSDS-SFC3：SweepRMSSDS-SFC1：基于初始优先级MSSDS-SFC2：基于截止期限MSSDS-SFC3：基于寻道时间R=3：基于寻道时间优化MSSDS-SFC1：DiagonalRM4.4调度器非抢占调度新到来的请求无法剥夺当前正在执行的磁盘请求所占用的资源优先级反转情况明显抢占调度任何新的请求只要具有足够高的优先级，就可以抢占当前请求所占用的资源可能造成“饿死〞条件抢占调度策略1优先级反转优化2避免出现“饿死”34.4调度器非抢占调度条件抢占调度策略1优先级反转优化2条件抢占调度策略显著高优先级Rnew、Rcur、q、q’滑动窗口w显著高优先级：Rnew<Rcur-w2.w<MAX(Vc)时仍然有可能出现“饿死〞现象q’中的请求具有显著高优先级时，如何实现优先级反转条件抢占调度策略显著高优先级2.w<MAX(Vc)时仍效劳与提升策略磁盘开场效劳q中的某个请求之前，会首先检查