（计算机软件与理论专业论文）视频服务器磁盘io混合调度技术.pdf

华中科技大学硕士学位论文 捅要 ? i 在视频服务中，视频流需要高带宽、连续地播放：并且追求最大的并发视频流 数目也是视频服务的要求。由于磁盘i 0 带宽的限制，传统磁盘i 调度难以满足 视频服务的需求。在实际应用中，大多数视频服务器不仅仅存储视频数据，还存储 有大量的非实时数据，而非实时数据的提取需要有合理的响应时间。因此，必须研 究一种高效的磁盘混合调度策略。 现有的磁盘调度算法，如s c a n 、s s t f 、e d f 、e d i z s c a n 等都难以适合视频 流的实时提取，更不用说能高效处理磁盘混合调度。y d i o m s 是一种新的磁盘i o 混合调度策略，它采用两层调度结构：在第一层中， 分别接受和处理实时请求和非实时请求。视频数据的磁盘请求进入实时请求队列， 采用最小空闲期优先( l e a s tl a x i t yf i r s t ，l l f ) 实时算法调度。离散的非实时请求 先进行分片处理，然后依据非实时磁盘请求的平均响应时间，给它们设定一个 d e a d l i n e 值，使其实时化，最后按照请求到达的先后顺序在非实时请求队列中排队。 在第二层中，d i o m s 采用一种新的基于滑动窗口的l l f 调度算法( l l f w i n d o w ) 处理磁盘请求混合提交。首先将第一层实时请求队列和非实时请求队列中的所有请 求进行混合，形成混合l l f 实时队列。然后，决定滑动窗口( 自适应的最大优化窗 口) 大小，对窗口内的请求进行磁盘寻道优化最后将优化后的窗内请求提交给最 终磁盘服务队列。 d i o m s 在l i n u x 2 4 9 内核中实现。实际系统测试表明d i o m s 是一种高效的磁 盘混合调度策略，它完全满足实时请求和非实时请求调度的要求；并且提高了磁盘 的吞吐率，追求了最大的并发视频流数目。 关键词：视频服9 嘉f ：盘面磁盘混咨镝焘：实时瀣 受丽爱；。ic ：妊：最步 蝴期优先 鞠央卜调肛 潼霾赫 华中科技大学硕士学位论文 a b s t r a c t v i d e os t r e a m sm u s tb ec o n t i n u o u s l yp l a y e db a c k ，s ov i d e od a t am u s tb er e t r i e v e d f r o m s t o r a g ed i s k si n ar e a l - t i m ef a s h i o n u s u a l l y , v i d e od a t aa n dn o n r e a l - t i m ed a t ae x i s t i nt h es a m es e r v e r s o ，t op r o v i d es u i t a b l er e s p o n s et i m ew i t hn o n r e a l - t i m er e q u e s t s m u s tb e g u a r a n t e e d v i d e os t r e a m sn e e dh i g hb a n d w i d t h h o w e v e r , d i s k y ob a n d w i d t hi s - l i m i t e d ，t h e r e b y , h o w t oi m p r o v ed i s k st h r o u g h p u tm u s ta l s ob ec o n s i d e r e d i nar e s u l t ，a m i x e d s c h e d u l i n ga l g o r i t h m f i tf o ra b o v e r e q u i r e m e n t sm u s t b ei m p l e m e n t e d s o m e e x i s t i n gd i s ks c h e d u l i n ga l g o r i t h m s ，s u c h a ss c a n ，s s t f , e d f , e d f - s a c n ， a n ds oo n ，o n l yf o c u so ne i t h e rd i s kt h r o u g h p u to rr e a l t i m er e q u i r e m e n t t h e ya l la r e n t f i tf o ra b o v et h r e er e q u i r e m e n t s d i o m si san e wd i s ky om i x e ds c h e d u l i n gs t r a t e g ya n du s e sat w o l e v e ld i s k s c h e d u l i n ga r c h i t e c t u r e i nt h ef i r s tl e v e l ，t w oq u e u e s ( r e a l t i m eq u e u ea n dn o n r e a l t i m e q u e u e ) a r ep r e s e r v e d v i d e or e q u e s t si nt h er e a l t i m eq u e u ea r ep r o c e s s e db yt h el l f ( l e a s tl a x i t yf i r s os c h e d u l i n ga l g o d t h m ，w h i l ed i s c r e t er e q u e s t sj o i nt h en o n - r e a l - t i m e q u e u e i nt h ef c f s ( f i r s tc o m ef i r s ts e r v e ) o r d e r , a f t e r t h e y a r ed i v i d e di n t os m a l l e ro n e s i f t h e y a r e l a r g e t h a n 4 k b y e s i no r d e rt h a tr e a l t i m e r e q u e s t s a r e a t d e l a y e db y n o n r e a l - t i m er e q u e s t si nl a r g es i z e w eg i v ee a c hd i s c r e t er e q u e s tad e a d l i n e ，w h i c hi s s m a l l e rt h a nl o o m s ，a c c o r d i n gt oa v e r a g e r e s p o n s e t i m eo f n o n r e a l - t i m er e q u e s t s t h u s ， n o n r e a l t i m er e q u e s t sa r ev i e w e da sr e a l t i m er e q u e s t sa n d t h e ym a y b ea l s op r o c e s s e d b yt h el l fs c h e d u l i n ga l g o r i t h m i nt h es e c o n dl e v e l ，aw i n d o w - b a s e dl l fa l g o r i t h m ( l l f w i n d o w ) i si m p l e m e n t e da n di n t r o d u c e da sf o l l o w s ：f i r s t l y , t h er e a l - t i m eq u e u e a n dt h en o n r e a l t i m eq u e u ea r em i x e di n t oam i x e dl l f q u e u e t h e n ad y n a m i cw i n d o w ( i e m a x i m u ms c a nw i n d o w ) i sd e c i d e d ，i nw h i c ht h es e e k i n gt i m e so ft h er e q u e s t s w i l lb eo p t i m i z e d l a s t l y , t h e r e q u e s t si nt h ew i n d o w a r es u b m i r e dt op h y s i c a ld i s kd r i v e d 1 0 m si s i m p l e m e n t e d i nt l l el i n u x 2 4 9 k e r n e l e x p e r i m e n t a l r e s u l t ss h o w d i o m ss a t i f i e sa b o v et h r e er e q u i r e m e n t s k e y w o r d s ：v o ds e r v e r ；d i s ky o ；d i s km i x e ds c h e d u l i n g ；r e a l t i m ed i s ks c h e d u l i n g ； d i o m s ：l l f i l 华中科技大学硕士学位论文 1 绪言 本章介绍了视频服务器的一些基本知识，使得读者对视频服务器的设计有所了 解，并从视频播放的特征和q o s 要求中引出磁盘i o 调度的必要性、要达到的目标 以及任务。最后介绍了本文的创新与贡献以及本文内容组织。 1 1 问题的提出 近几年来，i n t e m e t 服务飞速向多媒体宽带数据业务发展，在线视频点播 ( v i d e o o n d e m a n d ) 日益成为人们追求高生活质量的一项内容。可喜的是，最近一 些年来，在计算机技术、通讯技术和多媒体技术等方面的发展已使视频点播成为可 能。视频点播用户的剧烈增长、视频节目的海量存储以及视频播放的高带宽、连续 性对视频点播的主体即视频服务器的设计提出很高的要求。 视频数据是与时间相关的，它必须连续地播放( 例如：m p e g 1 电影剪辑约需 1 5 m b p s ) ，否则，会产生电影画面的不连续，使用户难以接受，这在视频点播服务 的商业应用中是不允许的。因而，视频数据必须实时地从磁盘读取。另外，视频服 务器的设计还要求最大的并发视频流数目，这就需要高性能的存储i o 支持。因此， 对磁盘i o 进行优化，提高它的吞吐率也是重要的设计内容。总之，视频服务器磁 盘i o 的性能决定了视频服务器的总体性能【l 】。 视频服务器中广泛存有视频数据和非实时数据，称之为混合数据。两者对磁盘 调度算法的要求各不相同，因而，对磁盘进行混合调度就必不可少。 现有的磁盘调度算法，如s c a n 、s s t f 、e d f 、e d f s c a n 等都难以适合视频 流的实时提取，更不用说能高效处理磁盘混合调度。 磁盘i o 调度是视频服务器设计的关键部分，它影响并决定着视频服务器的整 体性能。本文专注于视频服务器的磁盘i o 调度技术，研究和实现视频流的实时提 取这一关键性问题。 本项目由武汉市重大科技攻关项目资金资助。 l 华中科技大学硕士学位论文 1 2 视频服务器简介 1 2 1 视频点播所需的主要协议 用户通过i n t e m e t 来享受视频点播服务，因此需要网络协议进行规范视频数据 的传输和交互控制。然而，t c p i p 协议最初是为非实时数据业务而设计的1 2 l 。t c p 协议是面向连接的，它的超时重传机制和拥塞控制机制虽带来了数据传输的可靠 性，但它对视频的实时传输极为不利，因而i e t f 组织针对网上多媒体数据的传输 发布了一系列协议，主要是r t s p 协议、r t p 协议和r t c p 协议。图1 1 是协议栈 的层次结构图： 图1 1网络多媒体协议栈层次结构图 r t s p ( r e a lt i m es t r e a m i n gp r o t o c 0 1 ) 协议【3 j ：负责用户与视频服务器之间的交 互。r t s p 协议与h t t p 协议类似，但它提供比h t t p 协议更多的操作原语。例如 s e t u p 、p l a y 、p a u s e 、t e a r d o w n 等1 1 种，这些方法构成了用户的v c r 控 制，实现了真正意义上的视频点播。r t s p 位于网络协议传输层之上，既可用t c p 华中科技大学硕士学位论文 协议传输，也可用u d p 协议传输。详细内容见r f c 2 3 2 6 。 r t p r t c p ( r e a lt i m et r a n s p o r tp r o t o c o l r t pc o n t r o lp r o t o c 0 1 ) 协议【4 1 ：这两 个协议配套使用，r t p 负责视频数据的打包传输，r t c p 监视数据传输的质量。r t c p 是r t p 数据传输过程中来自用户的网络状况反馈信息，用它来调整r t p 的数据传 输参数从而保证r t p 传输的质量。它们存在于u d p 协议之上，使用一对随机的奇 偶相连的u d p 端口号。详细内容见r f c l 8 8 9 和r f c l 8 9 0 。 这三个协议实现了在线视频点播的基本工作流程，详见图1 2 。 r 、 一 r t s p v o d c l j e n t r t p s e r v e r r t c p。 l， 图1 2 r t s p 、r t p r t c p 工作流程图 1 2 2 视频服务器的设计内容及体系结构 视频服务器的设计包括很多方面，例如缓存管理、数据预取、磁盘数据存放、 磁盘调度、r t s p 服务器软件、r t p 数据传输等【6 1 0 因而，视频服务器的设计是一个 大的系统工程。 d i s k f 习 s e r v e r i f l 、一， b u f f e f s d a t a n e t w o r k l r e t r i e v a l。i t r a n s m i s s i o n1 图1 3v o d 服务器结构图 3 华中科技大学硕士学位论文 总体来讲，视频服务器的设计关注两大方面，一是视频数据的提取，二是视频 数据的传输，见图1 3 所示”1 。每个方面都包括大量的设计内容，例如：磁盘数据 存放、磁盘i o 调度以及缓存管理技术都是属于视频数据提取的研究范畴。本文研 究其中之一的磁盘i j o 调度技术。 1 3 磁盘i o 调度的任务 1 3 1 视频播放的特征及q o s 要求 通常，一部电影有数十兆或数千兆，要在一个小时左右的时间内播放完。因而， 视频播放的数据吞吐率非常高，在网络传输上所需的带宽也非常大。视频数据一般 是经过压缩的，压缩算法的不同，其大小和播放所需要的带宽也不一样，详见表1 1 所示 6 i 。 表11 不同视频流吞吐率详表 视频流m p e g i m p e g 2h 2 6 l h d t v ( 压缩后)h d t v ( 未压缩1 l 吞吐率 1 5 m b p s2 m b p s6 4 k b p s 2 m b p s2 0 m b p s1 g b p s 表1 1 显示了视频播放需要高带宽这一特征。连续性是视频播放的又一特征， 视频数据是与时间相关的，它必须保持时间上的同步，不允许停顿。所以，视频服 务器对它的实时支持非常重要。 视频播放的另一特征是低延迟和高响应。用户与服务器间端到端的延迟应在 4 0 m s 一下，这样才不会影响视频播放的质量。同样，这也需要服务器对实时的支 持。 视频服务器必须保证视频点播的服务质量( q o s ，q u a l i t yo fs e r v i c e ) 。根据与 客户端协商的q o s 参数提取和传输视频数据，既要保证视频流传输的带宽，也要保 证最小的延迟和延迟抖动。前者依靠磁盘驱动的实时性来解决，后者依靠缓存管理 来满足。 4 华中科技大学硕士学位论文 1 3 2 磁盘i o 调度的目标及任务 视频播放的特征以及它需要的q o s 保证对视频服务器的设计提出了新的要求， 即需要操作系统对视频播放的支持。磁盘i o 调度、缓存管理和c p u 调度都需要做 出响应的修改。 除了有实时磁盘i o 调度的支持外，寻求能同时并发播放的最大视频流数是视 频服务器设计的另一个重要目标，这需要高性能磁盘i o 的支持。由此，磁盘i o 调度有两大目标1 8 1 9 j ： 满足每个视频流的q o s 要求； 追求视频流的最大并发数，即在有限的可用资源条件下，使被服务的视 频流的数目最大化。 磁盘i o 是现代计算机系统中的瓶颈，更是视频服务应用中的障碍。磁盘i o 调度的两大目标引出磁盘i o 调度的任务。第一，应对传统磁盘i o 进行实时性改 造，来满足第一个目标；第二，有效地利用磁盘i o 带宽，达到磁盘最大的吞吐率， 实现高性能磁盘i o ，追求视频流的最大并发数。 1 4 创新及贡献 本文在对磁盘调度、视频流的实时提取以及实时任务和非实时任务混合调度等 有关领域进行大量研究的基础上，针对视频服务器的设计有如下的创新点： 非实时任务的分片，给其设定最迟执行时间，使非实时任务实时化， 与实时任务一起进行实时调度； l l f w i n d o w 实时磁盘调度算法。本算法在有效地调度实时请求的基础 上，尽努力地提高了非实时任务的响应时间。并且，还对磁盘任务进 行了寻道优化，提高了磁盘的吞吐率。 磁盘i o 混合调度( d 1 0 m s ) 技术在l i n u x 操作系统内核中的成功实 现。 华中科技大学硕士学位论文 1 5 内容组织 本文分为五章，各章内容如下： 在第一章的绪言中，简要地介绍了视频服务器的基本知识，使读者对视频服务 器的设计有一个基本的了解；磁盘i o 调度是视频服务器设计的关键，在这一章中， 还阐述了磁盘i o 调度的必要性、目标以及任务。 第二章详细介绍了磁盘i o 调度的背景知识。包括最基本的磁盘驱动知识和实 时调度的基本理论、现有的各种传统的、实时的和混合磁盘调度算法，并对算法进 行归纳总结和数学描述，最后研究了磁盘数据存放和缓存管理技术，这与磁盘i o 调度密切相关。 第三章详细阐述了新的磁盘混合调度技术，包括实时请求和非实时请求分别如 何处理，最后如何提交和如何进行寻道优化，提高磁盘吞吐率，并对其进行了数学 分析和实验分析。 第四章报告了磁盘混合调度的实现技术，在阐述实现技术之前，详细分析了 l i n u x 块设备驱动和某些内核机制，这是实现磁盘混合调度技术的基础。 第五章结束全文，对本文的研究工作进行了总结，并对进一步地工作提出了展 望。 华中科技大学硕士学位论文 2 磁盘i o 调度研究背景 本章介绍了现代磁盘驱动和实时调度的基本理论知识，这是本文的基础。随后 研究了传统磁盘调度算法、实时磁盘调度算法和磁盘i o 混合调度算法，并对实时 磁盘调度进行了数学描述和分类，这是对实时磁盘调度的一个比较详尽的论述。最 后介绍了影响磁盘i o 调度性能的一些因素，也给出了必要的论述和数学模型。 2 1 基础知识 2 1 1 现代磁盘驱动 在研究磁盘i o 调度以前，我们先来了解一下磁盘驱动的一些基本知识。 图2 1 磁盘驱动结构图 磁盘属于块设备，它以块为大小进行读写。我们的视频服务器采用的是i d e 磁 盘。现代i d e 磁盘大都由多磁头多盘片构成，见图2 1 ( a ) 所示。磁头( h e a d ) 可 沿盘片半径移动，盘片以中心轴( s p i n d l e ) 高速旋转，致使磁头可覆盖整个盘片。 图2 1 ( b ) 展示了盘片正面图。同，i i , 圆为磁道( t r a c k ) ，数据就记录在磁道上，每 条磁道分为多个扇区( s e c t o r ) ，磁盘数据以扇区为单位存放。扇区大小是一定的， 一般为5 1 2 字节。每条磁道拥有相同的扇区，所以每条磁道的数据容量是一样的。 华中科技大学硕士学位论文 由于从内到外磁道的周长不断增加，而数据容量不变，所以磁道数据存放的密度不 断变小【 o a i , 1 2 。 磁盘驱动得到i 0 请求命令后，首先要寻找数据块所在位置，这要经过两个步 骤。第一步是磁头沿半径的移动过程，寻找数据块所在的磁道，这花费的时间称之 为寻道时间( s e e k _ t i m e ) ，平均为9 4 m s 第二步是盘片的旋转过程，找到数据块 所在的扇区，这步所需要的时间称之为旋转延迟( r o t a t i o n a l )，对个_latency 7 2 0 0 r p m 的现代磁盘来讲，旋转延迟大约为4 2 m s 。找到数据块的磁盘位置后，磁 盘驱动就开始了数据的读取传输，将数据读到内存，这个过程需要的时间称之为数 据传输时间( d a t at r a n s f e rt i m e ) l i 。 磁盘利用率直接与i o 请求的大小相关。总的来说，一个磁盘u o 请求的服务 时间由三部分组成：s e e kt i m e ，r o t a t i o n a l l a t e n c y , d a t at r a n s f e rt i m e 。在这三个 时间中，只有d a t at r a n s f e rt i m e 直接贡献于磁盘利用率，见如下公式： d i s ku t f f i z a t i o n ： 里竺竺：! 堡! 业! ：至竺! 一 s e e k t i m e + r o t a t i o n a l l a t e n c y + d a t a t r a n s f e r t i m e 现在举一个实例：对一个传输率为5 m b p s 的磁盘读取1 2 8 k b 的数据块( 假设数 据连续存放) ，那磁盘服务总时间为9 4 + 4 2 + 2 5 = 3 8 6 ( m s ) ，磁盘利用率为：2 5 3 8 6 t o 6 5 。由此看来，欲提高磁盘利用率，减小寻道时间和旋转延迟就是关键【1 3 1 。 2 1 2 实时调度基本理论 在实时系统中，一个任务运行的正确性不仅仅取决于运行结果逻辑上的正确 性，还要求满足时限，即任务必须在截止期( d e a d l i n e ) 内完成。例如，m p e g 编 码的视频流以连续帧的方式播放，播放前c p u 必须对视频进行解码，不仅要解码 无误，还要在当前帧播放前完成，否则，会造成跳帧或停顿，影响播放质量。 通常，实时任务可分为三类i j 。最常见的是周期性( p e r i o d i c ) 实时任务，这 类任务每隔么丁时间重新发生，图2 2 中a 与b 就是周期性实时任务；第二类如图 2 2 中任务c 所示，为不定期任务，或称为非周期性任务，它是不定期重复发生； 最后还有一类，比较少见，那就是零星任务，如图2 2 中x 任务，它是偶尔发生。 华中科技大学硕士学位论文 卜曲趾一卜叫零等务不多舭务 a bcca ba bxc_ab l 吐口_ l 。 实时任务n 的调度必须考虑两个参数，任务的释放时间，f ( r e l e a s et i m e ) 和截 止期限d i ( d e a l i n e ) ，进而由这两个参数决定任务调度的开始时间p ，( s t a r t - t i m e ) 和完成时间正( f u l f i l l t i m e ) 1 5 1 。 r e l e a s et i m e ：任务能开始执行的最早时间 d e a d l i n e ：任务能被完成的最迟时间 s t a r t t i m e ：任务实际开始执行的时间 f u l f i l l t i m e ：任务实际被完成的时间 为了满足实时任务能在截止期限内完成，我们必须保证n 玩和卉旗。一个简 单的表示实时任务调度的例子如图2 3 所示。特别的，由于磁盘任务是原子操作， 是不可抢占的，因此对磁盘任务而言，任务的服务时间。定义为：c ，= 项一 r e l e a s et i m es t a r t - t i m ef u l f i l l - t i m ed e a d l i n e 图2 3实时磁盘任务调度示意图 根据实时任务d e a d l i n e 的紧迫性和满足d e a d l i n e 的实际情况，实时系统可分为 两类：软实时系统( s o f t r e a l t i m es y s t e m ) 和硬实时系统( h a r d r e a l - t i m es y s t e m ) ”。软实时系统不过分强调满足所有任务的d e a d l i n e ，一个都不能失去，这就意味 着一个任务偶尔失去d e a d l i n e 也是正确的。与之相比较，硬实时系统确不然。硬实 时系统非常严格，即使失去个d e a d l i n e 都是不可接受的，甚至会造成灾难性后果。 视频服务器属于软实时系统。由于视频服务器中有数据预取和缓存管理，磁盘 i o 请求即使失去d e a d l i n e ，也不会产生很大影响。当然，大量的i o 请求都不能按 9 华中科技大学硕士学位论文 时完成，也会带来严重后果，影响用户在线视频点播质量。所以，实时磁盘i o 调 度还是要尽量满足d e a d l i n e ，实现一个实时性能好的软实时磁盘i o 调度。 实时任务的调度有两种方式：事件驱动和时间驱动。一个重要的事件发生，造 成c p u 中断，实时任务开始执行，这就是事件驱动方式。时间驱动方式就是每隔 么r 时间激发实时任务的执行，属于一种时间中断方式。两种方式各有利弊：事件 驱动在系统低负载时响应迅速，但高负载时容易失败；时间驱动方式与事件驱动方 式恰恰相反。究竟采用哪种方式取决于实时系统本身的应用要求。 2 2 磁盘调度算法研究 2 2 1 传统磁盘调度算法 传统磁盘调度早期广泛采用先来先服务( f i r s tc o m ef i r s ts e r v i c e ，f c f s ) 算法， 此算法按请求到来的先后顺序执行，没有任何寻道优化，磁盘吞吐率极低，只是实 现简单而已，不过，现在很少采用了 1 2 1 0 经过改进后的传统磁盘调度算法主要是专注于减少寻道磁盘时间，例如：最少 寻道时间优先算法( s h o r t e s ts e e kt i m ef i r s t ，s s t f ) 和电梯调度算法( s c a n ) 8 , 1 5 , 1 6 , 1 7 , 1 8 , 1 9 。 ? s s t f 算法总是优先服务寻道时间最短的i o 请求。它虽注重了寻道优化，但是 会造成一些寻道时间很长的请求长时间得不到服务，甚至会在磁盘i o 拥挤时造成 饿死现象，它不适合视频的实时读取。 s c a n 电梯调度算法是磁头由内向外和由外向内扫描磁盘，按磁道顺序依次服 务请求，酷似电梯升降。s c a n 算法实现寻道优化，效率比较高，像l i n u x 等很多 操作系统都采用这一算法，不过它也是一个非实时算法。 另外，在s c a n 电梯调度算法的基础上，又有一些变种。例如：c 。s c a n ， f d s c a n 。c s c a n 调度算法始终单项扫描磁盘，磁头到达外磁道后又重回到内磁 道，或者相反。f d s c a n 调度算法在每次扫描前决定此次扫描是否可行，如果不 行，就放弃。f d s c a n 调度算法的开销很大，但是可靠。 1 0 华中科技大学硕士学位论文 2 2 2 实时磁盘调度算法 传统磁盘i o 调度意在减小寻道时间，提高磁盘i o 的吞吐率，而视频服务不 仅要求吞吐率，更重要的是保证视频服务的实时性。几种典型的实时磁盘调度算法 如下【6 1 3 , 1 7 , 2 0 , 2 1 , 2 2 ： e d f 算法即最早截止期优先调度算法。在e d f 算法中，任务完全按d e a d l i n e 的大小顺序调度，因而，它是最简单的实时磁盘调度算法。e d f 算法非常公平，不 会造成任务长时间得不到服务。然而，磁盘服务时间取决于请求数据的位置和当前 磁头所在的位置，所以e d f 算法会造成磁盘任意地寻道，导致极低的磁盘吞吐率。 e d f s c a n 算法在e d f 算法的基础上进行了寻道优化。一般情况下，磁盘按 e d f 算法服务请求，如果请求有相同的d e a d l i n e ，就采用s c a n 算法服务这些请求。 由于此算法的寻道优化仅局限于拥有相同d e a d l i n e 的请求，所以它的效率取决于具 有相同d e a d l i n e 请求的数目，因而效率是有限的。 g s s ( g r o u ps w e e p i n gs t r a t e g y ) 算法i z 3 j 将连续视频流的请求分成多个组，在组 内采用s c a n 算法进行磁盘寻道优化，组间使用轮转策略。它性能的优劣取决于如 何分组，这是比较困难的。它还要合适大小的缓存支持，某个视频流的请求在这一 轮是第一个执行，在下一轮或许是最后一个，因此就需要足够大的缓存容纳数据。 周期性调度算法【2 4 2 5 1 ( s c h e d u l i n g i nr o u n d s ) 将连续视频流的请求分成多个时 间片，在一个周期内服务所有请求的一片，周而复始地执行。在周期内实现s c a n 算法，有寻道优化；周期大小的设定保证了视频流的实时性。这是一种效率比较高 的策略。 总体上讲，视频流有两种编码格式，一种是固定比特率( c o n s t a n t - b i t - r a t e ， c b r ) 编码，这种编码每秒播放的数据量是一定的，很有规律，对其实时调度较为 容易；另一种是可变比特率编码( v a r i a b l e b i t - r a t e ，v b r ) ，每秒播放的数据量是 变化不定的，对这种编码的视频流进行磁盘调度有其特殊性。不过，对v b r 视频流， 人们提出了针对性的调度策略【7 】【8 | 【2 6 1 ： c d l - e d f 策略：按固定数据长度( c o n s td a t al e n g t h ，c d l ) 存放的v b r 流，由于其d e a d l i n e 不同，我们就可以采用e d f 算法。 c t l r o u n d 策略：按固定时洲长度( c o n s tt i m el e n g t h ，c t l ) 存放的 l l 华中科技大学硕士学位论文 v b r 流，由于其在时间上的规律性，我们采用周期性调度策略。 附某些经典算法的算法描述： 算法描述：s s t f 1 ) 设定任务集t = t o ，乃，列，a ，为任务乃的磁道位置。 2 ) l o o p ：口为磁头当前所在磁道位置，如果i7 = o ，有l 吼一a l = m i n 1 a ，一a t ，调度任 务瓦，回到l o o p 继续。 算法描述：s c a n 1 ) 设定任务集7 1 = ，死乃，丁0 ，啦为任务正的磁道位置。 2 ) 按磁头扫描顺序排序磁盘任务的磁道位置，假定为a s ( o ) a s ( 1 ) a s f n ) ，则调度结 果为t s = t s 竹1 1 s 。t s 哟。 算法描述：e d f s c a n 1 ) 假定r = 最小d e a d l i n e 的任务集。 2 ) 如果i t i = i ( 任务集r 中只有一个请求) ，服务这个请求；否则，假定，f 是r 中在s c a n 方向上第一个任务，服务，。回到第一步继续。 2 2 3 实时磁盘调度的数学模型 用一个四元组( n 吐，瓯b ，) 来描述一个实时磁盘任务正。其中，n 和吐分别表示 实时任务的释放时间和截止期，为数据的磁盘位置，b 。表示要服务磁盘数据大小。 假设输入7 1 = t o , t ，l 为要调度的实时任务集，那输出序列t z = t z c o j 丁知卜t z r n ) 则 为磁盘调度的结果。 当磁盘按r ，乃调度顺序服务正时，磁头从位置a ，移到a 位置去提取数据b ， 那么任务乃调度的开始时间岛和完成时间石可由下面的等式表示： 1 0 ，如果( i = o ) ； 1 i m a x r , ，：一1 ) ，否则。 ，= e 。+ c 公式中变量岛，是任务l 一，服务完后进而服务正所需要的时间，包括数据传输 一_ _ - _ _ _ 一 华中科技大学硕士学位论文 时间和磁盘消耗( 寻道和旋转等待时间) 。由于不同厂商生产的磁盘有不同的磁盘 参数，所以。叫，的计算公式也就有所不同，这里不详述。 如果所有的任务丁劾( 对i = 0 到h ) 都满足它们的实时要求，即r g ( o j 猁和厶” 砬”那么调度序列t z 称之为可行的调度。假设第一个任务的释放时间r z ( o ) = d ， 那任务t z ( o ) 7 z a ) t z ( n ) 的总服务时间为厶脚一r z ( o ) ，即f z ( n ) 。定义总的磁盘数据提取量 b = ：b ，调度磁盘任务集t z 的磁盘吞吐率是b f z ( ) 。 获得的磁盘吞吐率与整个调度的最后完成时间成反比，欲取得最大的磁盘吞吐 率，必须最小化调度的最后完成时间。我们可以形式化实时磁盘调度问题如下： 定义2 1 ：实时磁盘调度给定一个实时磁盘任务集r = t o , 乃，矗1 ，找到了一 个可行的调度t z = t z ( o ) 丁新，卜t z ( n j ，这个调度在满足r z ( o j 删和厶”：d z ( o 的条件下寻 求m i n f z ( 2 ，。 这个问题能被一个完全图g = r 习模拟，其中v = t ，t 有两个属性参数n 和 4 ，从乃到巧的边长为c 。，c 。为正转而服务巧所花费的时间。目标是遍历整个图 ( 每个结点仅访问一次) ，寻求最小路径长度。这个问题已被证明是一个p 难度问 题，只能寻求最优解。 2 2 4 实时磁盘调度分类 在上两部分中我们列举了很多实时磁盘调度策略，根据算法本身的特点和与缓 存的关系，我们将磁盘调度策略进行了归类，分为主动磁盘调度和被动磁盘调度 1 1 1 8 1 。 主动磁盘调度( a c t i v ed i s ks c h e d u l i n g ) ：g s s 策略和s c h e d u l i n gi n r o u n d s 策略为主动磁盘调度策略。它们只需要服务器给出最初的读取 命令，就可以在视频长时间的播放过程中主动地往缓存里送视频数据。 这需要固定缓存地址的两倍缓存管理策略的支持。对视频流的读取而 邑主动磁盘调度策略因为能自主地对磁盘请求进行有效地组织，所以 效率极高；另外，磁盘y o 带宽也容易控制。 被动磁盘调度( p a s s i v ed i s ks c h e d u l i n g ) ：e d f 算法和e d f s c a n 算 1 3 华中科技大学硕士学位论文 法是被动磁盘调度算法。它们所服务的每个磁盘请求都得由系统下达磁 盘读取命令。它们对缓存没有特殊的要求，只需要在磁盘请求命令中下 带d e a d l i n e 参数。 主动磁盘调度和被动磁盘调度在实现上有所不同，但都需要对操作系统进行大 量的改造： 主动磁盘调度需要完全改动操作系统的缓存管理算法和磁盘调度算法，另起炉 灶，使之成为有机的整体。这从实现技术上讲，是可以实现的，就是要开发一个多 媒体专用的操作系统。但是从软件工程的角度来看，主动磁盘调度的开发成本很大， 操作系统原本实现得非常好的缓存管理算法和设备驱动算法都要丢弃，代码复用太 少，致使工作量很大。但是专门改造后的效果会很好。究竟采不采用主动磁盘调度， 这需要整体权衡。 相比较而言，被动磁盘调度实现起来就较简单，只需要在设备驱动之上缓存之 下加上一层，这一层处理磁盘请求的实时性问题和磁盘性能问题。它不需要特殊的 缓存支持，可以利用操作系统现有的缓存管理策略。当然，改用更适应视频流播放 的缓存技术也未尝不可。 2 2 5 磁盘混合调度 视频服务器不仅要能处理像音频、视频这样的连续数据的请求，同时还要能够 处理像文本、图象这样离散数据的请求【2 7 加1 。连续数据是与时间相关的，它们要求 采用实时磁盘调度算法处理；离散数据虽没有实时要求，但是必须尽可能地让它们 有合理的响应时问。因此，针对视频服务器中存储媒体的不同要求，就必须采用磁 盘混合调度策略，方面保证实时请求不失去它的截止期( d e a d l i n e ) ：另一方面要 尽努力地( b e s t - e f f o r t ) 调度非实时请求，让它们有合理的响应时间。 视频服务器中存储的两类数据可分别采用不同的调度算法 2 9 , 3 0 , 3 1 1 ： 视频数据由实时应用程序( r e a l t i m e a p p l i c a t i o n ) 读取，它主要关注数据读取 的实时性，可采用e d f ，e d f s c a n 等实时算法处理： 非实时数据由非实时应用程序( b e s t e f f o r t a p p l i c a t i o n ) 读取，它不需要实时读 出，但要有合理的响应时间，它主要关注磁盘的吞吐率，所以可采用s s t f ，s c a n 1 4 华中科技大学硕士学位论文 等传统磁盘调度算法处理。 如图2 4 所示，混合磁盘调度一般都采用两层结构。第一层根据不同任务的特 点采用各自适用的调度算法，进入各自的任务队列排队：第二层是磁盘i o 混合调 度的关键技术难点，即混合请求选择器。这个算法要采用某种适用的策略调度第一 层各个队列中的任务，它必须保证磁盘混合调度的两大要求的实现( 见上文) 。 在国外，有两所大学对磁盘混合调度进行了有效的研究，一个是美国华盛顿大 学圣路易斯分校的大规模并行实时存储项目m a r s 另一个是美国德克萨斯州立大 学奥斯汀分校的c e l l o 磁盘调度。现分别介绍如下： m a r s l 3 2 1 ：第一层分为实时任务调度和非实时任务调度，分布采用e d f 算法和 f c f s ( 先来先服务) 算法；第二层混合请求选择器算法采用d d r ( d e f i c i tr o u n d r o b i n ) 算法，即对第层两个队列采用轮转策略，并对每个队列依据数据容量分 配权值，每轮按权值大小占据磁盘读写控制权。 c e l l o i 3 3 1 ：第一层的任务队列依据请求的不同特点分为多个队列，采用多个调度 策略，这一层划分得更细，算法更适用；第二层依据实际带宽的不同，分为两个时 间片分别调度第一层中适合的任务，这个算法复杂。 图2 4 混合磁盘调度层次结构图 1 5 华中科技大学硕士学位论文 2 3 影响磁盘i o 调度的相关问题 磁盘i 0 调度并不是孤立的，它上与缓存相连，下与磁盘数据打交道，这两者 必然对磁盘调度产生影响。 2 3 1 磁盘数据存放 由于数据的存放直接影响磁盘的寻道时间和旋转延迟，所以数据的存放与磁盘 调度密切相关。现叙述如下【6 3 4 ，3 5 3 6 】： 分散存放：数据块分散存放在磁盘的任意地方。可想而知，数据的读取会造成 大量的寻道和等待延迟开销，降低磁盘的吞吐率。 连续存放：一个文件的所有数据块连续存放在磁盘上。连续存放比分散存放会 产生更好的性能，但它将造成粹片问题。 分片连续存放：将一个文件分成多片，一个片的所有数据块连续存放，但是片 可分散存放。分片连续存放比连续存放有更少的粹片问题，只是分片大小要根据情 况合理地决定。 由于视频数据的海量存储，视频服务器一般都采用多个磁盘设备。于是，系统 有两种在磁盘设备间分配数据的技术： ， 数据条块化( d a t as t r i p i n g ) ：为了实现一个大的逻辑扇区，多个磁盘的许多物 理扇区被并行存取。 数据交叉化( d a t ai n t e r l e a v i n g ) ：一个磁盘的许多请求能独立于其它磁盘的众 多请求而被处理。一个请求所有片能分布在多个磁盘上。 多个磁盘设备间的数据分布策略依赖于应用程序的特点，不过需要充分考虑如 下两个因素： 每个磁盘的使用效率：为了提高磁盘利用率，要尽可能地减少磁盘寻道和旋转 等待延迟开销。 磁盘间的负载均衡：尽量保证每个磁盘的负载相当，不要让某个磁盘负载过重 而影响整体效率。 1 6 华中科技大学硕士学位论文 2 3 2 磁盘i o 与缓存 缓存技术也是视频服务器设计中的一项重要内容【3 “。视频数据从磁盘读取，经 由b u f f e r ，最后拷贝到应用程序的用户空间。缓存的传统作用是平衡c p u 与磁盘设 备之间的速度差异，但在视频服务器中，它有独特的作用。一是有利于满足i o 请 求的实时要求，平滑视频播放的抖动延迟；二是b u f f e r 的大小与磁盘的效率直接有 关。缓存( b u f f e r ) 是操作系统中有限