2016秋季多媒体技术第五章多媒体存储与信息检索技术学习专业课件.ppt

5.3.3针对磁盘请求的调度方法(续3)-例子5.3.3针对磁盘请求的调度方法(续4)SCAN根据数据所在磁道位置来调度从最里-最外，时间可能会长；这些区域的请求不公，长时间等待可能会被移出队列UnidirectionalSCAN5.3.3针对磁盘请求的调度方法(续5)UnidirectionalSCAN5.3.3同时存在流的可行性条件请求流5.3.3同时存在流的可行性条件(续1)请求流的响应时间第i个流的响应时间Ri=Wi(等待时间)+Si(服务时间)5.3.3针对请求流的调度方法有效的调度请求序列，避免失掉其时间限EDF-SCAN算法：EarliestDeadlineFirstschedulingLongseek-longseektimeSCAN-EDF调度:在有效性和紧迫性之间做均衡EDF-SCANSCAN-EDFSCAN-EDF5.3.3针对请求流的调度方法(续1)GroupSweepingscheduling针对具有很强周期性和规则性的流，这些流存取存储系统中同样大小的数据条带(段),并采用光滑缓冲区来代替指定时间限来达到流连续的目的GSS方法将同时发生的流集合分成许多组，每组包含许多请求，组在roundrobincycles内获得服务。一个流分配到同一个组，直到流结束，当一组流获得服务时，存储系统连续为组内的单个流服务。组内采用SCAN算法提供服务组在固定周期内获得服务，因此服务的顺序也是固定的，但组内的请求并不是按固定顺序服务令n表示同时发生流的个数，g表示组的个数，n个流分成g组g=1，所有请求分成一个组，则GSS即成为SCAN算法g=n，每个流单独成一组，因此，所有流在一个roundrobincycle内获得服务，GSS方法按固定循环周期来调度流请求5.3.3针对请求流的调度方法(续2)Start-upLatency初始潜伏时间例如，FIFO调度方法，根据到达时间来调度服务请求FIFO调度的延迟和缓冲机制5.3.3针对请求流的调度方法(续3)SCAN算法导致的延迟和缓冲GSS算法导致的延迟和缓冲5.3.3针对请求流的调度方法(续4)依赖于组的数目，初始潜伏时间和缓冲区大小受到影响如何找到最优的组数目？光滑缓冲区应足以存储每个流的一个数据段和一个请求组存取的数据段，因此GSS方法中光滑缓冲区的大小Bb如下由于一组请求采用SCAN调度方法，组内请求服务只需很短的寻址时间Sr,每个请求传输K个数据块，每个磁道包含b个块，因此每个请求传输ceil(k/b)个磁道数据，假设数据按磁道传输，则每个请求的旋转潜伏时间和数据传输时间如下(数据段的第一个和最后一个块可能会跨磁道，因此磁盘旋转数目可能+1)每次请求存取时间为:5.3.3针对请求流的调度方法(续5)每组内的第一个请求被服务时，均有不同的寻址时间，因此每组第一个请求的寻址时间为sg，服务g组n个请求的循环时间Tc为:由于每组的回放时间大于等于循环时间，因此有缓冲区大小Bb随数据段包含的块数目k增加而增加，因此，数据段包含的块数目应减少到最小，使得光滑缓冲区最小，最优的k如下：5.3.3针对请求流的调度方法(续6)求解最优的数据段块数目算法求解最优组数目算法GSS调度策略示意图5.3.3数据迁移(DataMigration)存储系统在不同的存储设备上存储数据对象当存储设备类型一致时，对象存储和检索具有累死的存取潜伏期当存储设备类型不一致时，则具有不同的存取潜伏期因此，存储设备的类型影响了对象的存取潜伏期一种安排不同类型存储设备的通用方法就是层次存储系统(HierarchicalStorageSystems(HSS))所有或大部分对象存储在具有长潜伏期的存储设备上，当有请求存取这些对象的时候，系统将这些对象从长潜伏期设备转移到短潜伏期设备上，可以显著改进请求流的响应时间在HSS中，数据迁移就是将第三级存储设备中的数据移到第二级设备上5.3.3数据迁移(DataMigration)(续1)跨层的多媒体数据对象转移有如下几种方法Staging:分段方式Timeslicing：时间分片方式Pipelining：流水线方式并使用三种流水线方法来减少初始潜伏期和分段缓冲区大小正常的流水线方法空间有效的流水线方法分割的流水线方法5.3.3缓存置换策略(CacheReplacementPolicy)前面主要介绍有效存储和检索多媒体的方法缓存置换主要介绍如何有效的从存储系统中传输多