（计算机科学与技术专业论文）mems存储设备在计算机系统中应用的关键技术研究.pdf

国防科学技术大学研究生院学位论文 捅要 受超顺磁效应和机械转速的限制，磁介质存储密度和磁盘访问速度的提升已很困难。 同时，各种新型存储介质不断涌现。m e m s ( m i c r oe l e c t r o m e c h a n i c a ls y s t e m ，微机电系统) 存储器是一种新型存储器件，具有高密度、低功耗、非易失、多探针并行访问等特点，相 对于传统磁盘具有明显优势。可以填补r a m 和磁盘之间的性能差距，可在计算机系统中 承担多种角色，为新型高性能海量存储系统结构研究带来新思路和新机遇。 本文对m e m s 存储技术进行了深入研究，根据c m u 大学m e m s 存储设备原型，研 究了m e m s 存储设备存储原理、物理结构、逻辑结构、访问特性，并依据这个原型建立了 线性性能模型。 磁盘阵列r a i d 是提高存储带宽和可靠性最主要的技术途径。本文研究了m e m s 存储 设备在应用盘阵中的关键技术。研究工作主要包括以下几个方面： 1 ) m e m s 存储设备可代替磁盘构建r a i d ，通过单设备内多探针并行和多个设备间的并 行访问带来高性能，用信息冗余和备用空间带来高可靠性。模拟分析表明与传统磁盘 阵列相比，m e m s 存储阵列大幅提高了性能。 2 ) m e m s 存储设备可集成到磁盘中，作为磁盘的大容量非易失c a c h e ；也可替代n v r a m c a c h e ，作为r a i d 控制器中的c a c h e 。本文设计并实现了m e m sc a c h i n gd i s k ，并进 行了性能模拟分析。 3 ) m e m s 存储设备的价格比磁盘高，为了提高性价比，本文利用m e m s 存储设备的高性 能和磁盘的廉价特性，提出了3 种混合型盘阵结构：m e m s 盘镜像、日志盘备份和双 r a i d 结构，充分发挥了m e m s 存储设备快速访问的性能和磁盘顺序访问的特性，既 提高了性能，又降低了成本，具有较高的性价比。 4 ) 研究了m e m s 存储阵列的可靠性，深入研究不同的故障器件替换方案、不同的备用空 间方案对m e m s 存储阵列可靠性的影响。研究表明，m e m s 存储阵列具有比磁盘更 高的可靠性。 本文研究了m e m s 存储设备的管理技术，主要包括请求调度算法、数据布局、设备故 障管理和功耗管理四个方面。研究结果表明，磁盘的请求调度算法和故障处理策略在 m e m s 存储设备上同样使用；研究了一种更适合m e m s 存储设备机械定位特性的双向数 据布局策略；m e m s 存储设备的功耗比磁盘低很多。 m e m s 存储设备的二维数据存储特性，适合关系数据的存取。本文针对数据库应用领 域，研究了磁盘对表格型数据的存储方式，介绍了一种适合m e m s 存储设备的关系数据存 储策略t d l 。分析表明，t d l 策略显著提高了数据库查询的速度、主存利用率和c a c h e 利用率。 本文的研究工作为m e m s 存储设备在计算机系统中的应用奠定了基础，其中一些设计 第i 页 困防科学技术大学研究生院学位论文 思想和关键技术，对其它新型存储设备在计算机系统中的应用，同样具有参考价值和指导 意义。 策略 主题词：磁盘，m e m s 存储设备，m e m sc a c h i n gd i s k ，盘阵，o s 管理，t d l 第i l 页 国防科学技术大学研究生院学位论文 4b s t r a c t m a g n e t i cd i s k sh a v ed o m i n a t e ds e c o n d a r ys t o r a g ef o rd e c a d e s t h ec a p a c i t ya n da c c e s s s p e e do fm a g n e t i cd i s k sh a v er e a c h e dan e wl e v e l ，a n di th a sb e c o m i n gm o r ea n dm o r ed i f f i c u l t l oi m p r o v e 。髓e 躯g ed i s p a r i t yb e t w e e nm e m o r ya c c e s st i m e sa n dd i s ka c c e s st i m eh a sc r e a t e da p e r f o r m a n c eb o t t l e n e c ki nc o m p u t e rs y s t e m s m a n yn e ws t o r a g em e d i aa n dn e wt e c h n i q u e sh a v e a l w a y sb e e nc o m i n go u t m e m s b a s e ds t o r a g ei sa ni n t e r e s t i n gn e wt e c h n o l o g yt h a tp r o m i s e st o b r i n gf a s t ，n o n - v o l a t i l e ，m a s sd a t as t o r a g et oc o m p u t e rs y s t e m s m e m s - b a s e ds t o r a g ed e v i c e s m e m s - b a s e ds t o r a g ed e v i c e sh a v ea d v a n t a g e si np h r r s i e a ls i z e , s t o r a g ed e n s i t y ，a n de n e r g y c o n s e r v a t i o n i th a sb e e nan e w c h a l l e n g et ot r a d i t i o n a ls e c o n d a r ys t o r a g es y s t e m s i nt h i sp a p e r ，w es t u d ym e m s b a s e ds t o r a g ea n dt h ek e yt e c h n i q u e so fa p p l y i n g m e m s b a s e ds t o r a g et oc o m p u t e rs y s t e m s w es t u d yt h ea r c h i t e c t u r ea n ds t o r a g ep r i n c i p l e so f m e m s b a s e ds t o r a g e ，a n dd e s c r i b et h r e eg e n e r a t i o n so fm e m s - b a s e ds t o r a g em o d e l so fc i w t _ i i nd e t a i l s ，i n c l u d i n gp h y s i c a la r c h i t e c t u r e ，a c c e s s i n gf e a t u r e ，l o g i c a ld a t ap l a c e m e n t , a n ds oo n t h e n ，w eb u i l dt h ep e r f o r m a n c em o d e lo fm e m s - b a s e ds t o r a g eb a s e do nt h ec m u m o d e l r a i di ss t i l lt h em a i nw a yt oi m p r o v eb a n d w i d t ha n dr e l i a b i l i t y i no u rw o r k ，w es t u d yt h e k e yt e c h n i q u e so fu s i n gm e m s - b a s e ds t o r a g ei nd i s ka r r a y s w h a tw e h a v ed o n ea r ea sf o l l o w s ： ( o w eu s em e m s - b a s e ds t o r a g e st ob u i l dd i s ka r r a y si n s t e a do fd i s k s t h r o u g h t h e p a r a l l e l i s mw i t h i nas i n g l es t o r a g ed e v i c ea n dt h ep a r a l l e l i s ma m o n gm a n yd e v i c e s ，w ec a n o b t a i nh i 曲a c c e s sp e r f o r m a n c e s a l s o ，w ec a l lo b t a i nh i g hr e l i a b i l i t yt h r o u g hd a t ar e d u n d a n c i e s a n ds p a r es p a c e s n l es i m u l a t e dr e s u l t ss h o wt h a td i s ka r r a y sb u i l tw i t hm e m s b a s e ds t o r a g e h a v eh i g h e rp e r f o r m a n c et h a nt r a d i t i o n a ld i s ka r r a y s ( 2 ) w ei n t e g r a t em e m s b a s e ds t o r a g ei n t od i s k s ，a c t i n g 鑫st h ec a c h eo fd i s k s 。a l s o ，w e i n t e g r a t ei ti n t od i s ka r r a y s ，r e p l a c i n gt h en v r a mc a c h e ，a n da c t i n ga st h ed i s ka r r a yc a c h ei n t h ec o n t r o l l e r w es t u d yt h em a i nt e c h n i q u e st oi m p l e m e n tm e m sc a c h i n gd i s k ，a n dd o p e r f o r m a n c es i m u l a t i o na n dc o m p a r i s o n 。 ( 3 ) b e c a u s eo ft h eh i g hc o s to fm e m s b a s e ds t o r a g e ，w es t u d yt h r e ek i n d s o fh y b r i dd i s k a r r a y s ，b u i l tw i t hm e m s b a s e ds t o r a g e sa n dd i s k s m e m s m i r r o r ，l o g d i s k ，a n dd u a l s t r i p e 。 t h e yc a nt a k ea d v a n t a g eo f t h ef a s ta c c e s sf e a t u r eo f m e m s - b a s e ds t o r a g ea n d t h ea d v a n t a g e so f t h es e q u e n t i a la c c e s sf e a t u r eo fd i s k s t h e yc a nn o to n l yi m p r o v et h ep e r f o r m a n c e ，b u ta l s o d e c r e a s et h ec o s t s 。w ec a ng e tb e t t e rp e r f o r m a n c e c o s tr a t i o s 。 ( 4 ) w es t u d yt h er e l i a b i l i t yo fm e m s b a s e ds t o r a g ee n c l o s u r e s ，w h i c ho r g a n i z e da sr a i d 5 w es t u d yd e e p l yi n t od i f f e r e n tf a i l u r ed e v i c er e p l a c e m e n ts c h e m e s ，a n dd i f f e r e n ts p a r es p a c e s t r a t e g i e s 。强es t u d ys h o w st h a tm e m s - b a s e ds t o r a g ee n c l o s u r e sa r em o r er e l i a b i l i t yt h a nd i s k s w es t u d yf o u ra s p e c t so fo p e r a t i n gs y s t e mm a n a g e m e n to fm e m s b a s e ds t o r a g e s ：r e q u e s t s c h e d u l i n g ，d a t ap l a c e m e n t ，f a i l u r em a n a g e m e n t ，a n dp o w e rc o n s e r v a t i o n w es t u d y an e w b i p a r t i t el a y o u ts c h e m e ，w h i c hi sm o r es u i t a b l ef o r t h ep h y s i 酬p o s i t i o nf e a t u r eo fm e m s - b a s e d s t o r a g e s 第i i i 页 邈防科学技术大学研究生院学位论文 t h e t w od i m e n s i o n a id a t al a y o u tf e a t u r eo fm e m s b a s e ds t o r a g em a k e si tm o r es u i t a b l ei n m l a t i o n a ld a t a b a s e i nt h i sp a p e r ，w es t u d yt h ea p p l i c a t i o no fm e m s b a s e ds t o r a g ei nd a t a b a s e ， i n t r o d u c i n gan e w d a t ap l a c e m e n ts c h e m ef o rm e m s b a s e ds t o r a g e t d l 。强ea n a l y s i ss h o w s t h a tt d lc a n i m p r o v eq u e r ys p e e d ，m e m o r ya n dc a c h eu t i l i z a t i o n fw eh a v ed o n ei no u rw o r kh a si m p o r t a n te f f e c t si na p p l y i n gm e m s - b a s e ds t o r a g et o c o m p u t e rs y s t e m s s o m eo ft h ek e yt e c h n i q u e sa n dd e s i g ni d e a sa l ea l s oh e l p f u lf o ra p p l y i n g o t h e rn e ws t o r a g e si n t oc o m p u t e rs y s t e m s k e yw o r d s ：m a g n e t i cd i s k ，m e m s b a s e ds t o r a g e ，m e m sc a c h i n gd i s k ，d i s k a r r a y s ，o p e r a t i n gs y s t e mm a n a g e m e n t ，t d l 第i v 页 国防科学技术大学研究生院学位论文 表目录 表2 1m e m s 存储器参数表1 7 表2 2g 3m e m s 存储设备的基本性能参数表一1 7 表3 1r a i dl e v e l 性能比较2 2 表3 2四种实际负载统计表2 4 表4 1m e m s 存储设备在四种负载下的功耗4 6 表4 2 磁盘和m e m s 存储设备在三种负载下的功耗4 7 表5 1r e l a t i o ns m d e n t g r a d e 4 8 第1 v 页 国防科学技术大学研究生院学位论文 图1 1 图2 1 图2 2 图2 图2 图2 图2 图2 7 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 11 图3 1 2 图3 1 3 图3 1 4 图3 1 5 图3 1 6 图3 1 7 图3 1 8 图3 1 9 图3 2 0 图3 2 1 图4 1 图4 2 图4 3 图目录 2 0 0 8 年存储技术的成本和延迟开销图。l m e m s 存储设备平面视图7 m e m s 存储设备的立体视图。7 m e m s 存储设备数据组织整体视图9 柱面、磁道、扇区和逻辑块示意图9 优化顺序访问的l b n 映射方式1 1 y 轴寻址过程的分段常函数模型下的加速度和速度示意图1 4 x 轴和y 轴寻址时间分布图1 6 r a i d 0 2 0 r a i d l 2 l r a i d 3 。2 1 r a i d 5 。2 2 随机负载下各存储设备性能比较2 3 实际负载下各存储设备的性能比较2 5 四种设备组织成r a i d5 的性能比较2 5 四种设备组织成r a i d 5 形式的性能比较2 6 m e m sc a c h ed i s k 逻辑结构示意图2 7 m c d 存储层次结构图2 8 m e m sc a c h e 存储空间组织示意图2 8 不同负载下m e m sc a c h e 的性能比较2 9 m e m s 替代n v r a m 性能比较3 0 m e m s 镜像盘结构31 日志盘备份结构31 日志磁盘空间示意图3 2 双r a i d 结构3 3 m e m s 存储阵列在无替换操作下的m a r k o v 模型3 5 m e m s 存储阵列在替换操作下的m a r k o v 模型3 6 分布式备用空间示意图3 7 m e m s 存储阵列在采用分布式备用空间下的m a r k o v 模型3 7 a t l a s l 0 k 在不同调度算法下的性能分析4 0 m e m s 存储设备在不同调度算法下的性能分析4 1 探针不同区域中的访问时间4 2 第v 页 慰防科学技术大学研究生院学位论文 图4 4 不同布局策略下的平均访问时间4 3 图4 + 5m e m s 存储设备备用探针示意图4 4 图5 1n s m 方式存储示意图4 8 图5 2d s m 下记录存储示意图4 9 匿5 3p a x 下记录存储示意豳5 0 图5 4t d l 存储方式示意图5 1 图5 。5t d l 员式布局和c a c h e 的使用情况5 3 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：丛里竖盔篮遮查查i 土差狃丕统生座周煦差筵技盔煎窒 学位论文作者签名：签丝塑日期：卿年，2 月夕日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 。 ( 保密学位论文在解密后适用本授权书) 学位论文题目：丛里坚盔篮遮垒查i 土篡狃歪缠生应用鲍差缝撞盎盈塞 学位论文作者签名：垄丝笪 日期：胡年，月夕日 作者指导教师签名： t i n i t i a l l y o p e r a t i o n a l ( 3 2 ) 利用上面的公式，在前三年，5 个备用器件的情况下，数据丢失的可能性是1 7 5 ， 而单个m e m s 存储设备数据丢失的可能性是1 2 3 1 。当备用器件用完之后，存储阵列变 得不是很可靠，在一个月和一年内数据丢失的可麓性分别为0 2 3 5 和2 1 0 6 。 主机系统、维护人员以及终端用户可以监测到m e m s 存储阵列何时进入不可靠阶段， 及时调度一个维护操作。m e m s 存储阵列是存储系统的构造单元，一个存储阵列上的所有 u n h e a l t h y 嶙i 据都可以在一个备用的存储阵列上进行复制，这个过程也只需要一个小时。 假设m e m s 存储设备的带宽为1 7 m b s ，复制过程仅用到了整个m e m s 存储阵列总带宽的 1 2 。 3 。7 。2 替换操作下m e m sr a i d 5 的可靠性 在备用器件用完之后，m e m s 存储阵列可以调用维护服务进行设备替换。主要的替换 第3 5 页 露防科学技术大学研究生院学位论文 策略有两种：一种是在备用器件刚用完时的预防性替换；另一种是m e m s 存储阵列在 r a i d 5 ( d e g r a d e dr a i d 5m o d e ) 降级模式下的强制性替换操作。图3 1 9 给出了具有n 个数 据、个奇偶存储器、一个专角备用器件的m e m s 存储阵列，在替换操作的情况下的 m a r k o v 模型。其中p 0 、p 1 分别为强制替换和预防性替换所占的比例。假设替换故障器件 的时闻是独立酌面且服放指数分在。 预防性替换策略能够大幅度提高m e m s 存储阵列的可靠性，因为在替换后的几天或者 凡周的时间内m e m s 存储阵列还可以容忍另一个设备故障。强制性替换策略尽量推迟替换 操作，减少了在使用期限内维护的频率，同时也增加了数据丢失或者不可用的危险性。 图3 1 9m e m s 存储阵列在替换操作下的m a r k o v 模型 研究发现，备用器件采用预防性替换策略可以显著提高m e m s 存储阵列的m t t f 值， 比在采用相同替换速度，但没有备用器件时提高一到两个数量级。如果不采用预防性替换 策略，仅依靠在线备用器件，可靠性的提高是有限的。 m e m s 存储阵列的可靠性主要取决予故障器件替换时间。替换时闻从一天增加到一个 月，m e m s 存储阵列的m t t f 也相应地减少一到两个数量级。与非预防性替换策略相比， 预防性替换可以降低在相同可靠性需求下替换的紧急性。 活跃的数据存储器数目n 以及平均数据恢复时间u ，同样对m e m s 存储阵列的可靠 性有影响。总体丽言，随着n 的增大强的减小，m t t f 值减小，并且在给定的n 和娶的区 间内m t t f 在4 5 倍范围内变化。因此，n 和弘的值对m t t f 的影响比器件更换频率、p o 和p l 的影响要小。给定一个相对较大的替换时间( 一周) ，m t t f 主要依赖于n 而不是肛。 当替换趋向子被推迟时，在很短的数据重建时闻内数据丢失的可能性，相对于在较长的替 换时间内数据丢失的可能性来说是可以忽略的。然而，如果数据重建时间变得很短，可靠 性又会与数据重建速率相关。 3 7 3 分布式备用空间策略 m e m s 存储阵列中的备用空间可以采用分布形式，用户数据、奇偶校验数据、备用空 间在存储阵列中的存储器上平均分配，图3 2 0 给出了一般的分布式备用空间的形式。 采用分布式备用空间方式，在正常和数据重建模式下，比专用的备用设备恢复的数据 第筠页 国防科学技术大学研究生院学位论文 量要小，而且数据恢复可以并行完成，与专用备用设备串行恢复数据方式不同。因此，采 用分布式备用空间可以减少数据重建的时间、降低数据丢失的可能性；同时，分布式备用 空间涉及多个存储器，无形中又影响了m e m s 存储阵列的可靠性。 m e m s im e m s 2m e m s 3 m e m s 4 m 哐m s 5m e m s 6m e m s im d 哇s 2m e m s 3 m i m s 5 m e m s 6 d ld 2d 3p l s l d 6 所d 8 p 2s 2d 5 d l l d 1 2p 3s 3 d 9 d 1 0 一， d 1 6 p 4 8 4 d 1 3 d 1 4 d 1 5 p 5s 5 d 1 7 d 1 8 d l !d 2 0 s 6d 2 ld 2 2d 2 3d 2 4p 6 d 1 d 2 d 3p ld 4 d 6d 7d 8p 2d 5 d l l d 1 2p 3d 9d 1 0 d 1 6p 4d 1 3d 1 4 d 1 5 p 5 d 1 8d 1 7d 1 9d 2 0 d 2 3d 2 ld 2 2d 2 4p 6 a ) b e f o r ea n yf 缸l u m( b ) a n 盯m e m s 4m b 图3 2 0 分布式备用空间示意图 图3 2 l 给出了具有n 个存储器、采用分布式备用空间的m e m s 存储阵列的m a r k o v 模型。考虑到m e m s 存储阵列数据重建状态停留时间很短，可以通过将数据重建状态和正 常状态合二为一，同时增加从正常状态到数据丢失状态的直接转换来简化计算。从正常状 态直接到数据丢失状态的可能性很小，仅为n 入q j 。在数据重建时间t f 内，j 1 个存储器正 常工作的条件下，数据丢失的可能性是： 1 一e u - 1 刀u 1 ) 办，r 33 、 其中t r 总是比专用备用存储器方式下的相应时间要小。 图3 2 1m e m s 存储阵列在采用分布式备用空间下的m a r k o v 模型 分布式备用空间方式和专用备用存储器方式可以提供基本相当的可靠性。分布式备用 空间方式数据重建需要的时间更短，可靠性更高；另一方面，备用空间涉及到多个存储器， 又影响了可靠性，这两种作用相互平衡。在强制性非预防性替换情况下，专用方式和分布 式方式具有基本相同的m t t f 。一般情况下，存储器平均替换周期是几天或者几个星期， 数据重建时间一般只有几分钟。如果不采用预防性替换，在替换周期内数据丢失的可能性 要比重建时大的多。 采用分布备用空间，数据重建时间很短，数据重建过程对m e m s 存储阵列可靠性的影 响不是很大。采用预防性的替换操作，设备替换时间很短，分布备用空间方式在数据重建 第3 7 页 国防科学技术大学研究生院学位论文 期间数据丢失的可能性，与快速替换数据丢失的可能性相当。而且，在快速替换情况下， m e m s 存储阵列可以容忍另外一个设备故障。 3 8小结 本章主要研究m e m s 存储设备在盘阵中应用的关键技术。首先介绍了盘阵的相关知 识，然后研究了m e m s 存储设备在盘阵中应用的几种关键技术，主要包括：( 1 ) 替代磁盘， 比较了单个存储设备和盘阵在不同酶负载下的性能；q ) 作为盘阵的c a c h e ，黍j 用m e m s 存 储设备对作为单个磁盘的c a c h e 和作为盘阵的c a c h e 进行性能模拟，比较不同普通的c a c h e 和采用m e m sc 勰k 下的性能；o ) m e m s 存储器和磁盘混合的盘阵结构，详细会缨了 m e m s 镜像盘、日志盘备份、双r a p 结构三种结构。这三种结构是为了充分发挥m e m s 存储设备快速访问的特性和磁盘顺序访问的特性，具有较高的性价比。 第鳃页 垦防科学技术大学研究生院学位论文 第四章m e m s 存储设备的管理技术 m e m s 存储设备相对于磁盘，在性能、可靠性和功耗等方面都具有优势。本节主要是 研究m e m s 存储设备的物理结构对o s 管理的影响。主要包括o s 管理的四个方面：请求 调度算法、数据布局、设备故障管理和功耗管理f 2 3 】。首先证明磁盘的请求调度算法对m e m s 存储设备来说也是有效鲥3 l ；为了更有效的发挥m e m s 存储设备高速访问的特性，研究了 一种更适合m e m s 存储设备的机械定位特性的双向的数据布局策略；m e m s 存储设备内 部的冗余特性，使得m e m s 存储设备可以忍受可能导致中止操作或者数据丢失的设备故 障；丽显，m e m s 存储设备功耗管理很容易，因为它可以在停止和活跃状态之间快速切换。 4 。1m e m s 存储设备的请求调度算法 4 1 1 磁盘的请求调度算法 关于磁盘的请求调度算法在最近的凡年中已经有了深入的研究。首先将现有的四种调 度算法在磁盘和m e m s 存储设备上的性能进行比较。第一种是最简单的、性能最差的先来 先服务( f c f s ) ；第二种算法是循环查找( c l o o kl b n ) ，这种算法是按照l b n 舞序的方式进 行服务，也就是说当所有请求的l b n 都落后于当前请求的l b n 话，就从涉及到最小l b n 的请求开始服务；第三种是最短寻址时闻优先( s s t fl b n ) ，主要思想是选择具有最小寻址 延迟的请求，但是在实际应用中却很少使用。因为很少有主机操作系统具有用计算实际寻 址距离或者预测寻址时间的信息，考虑到磁盘l b n 到物理位置的映射的关系，大部分的 s s t f 算法使用的是最近访问的l b n 和黼标l b n 之闻豹距离作为访闻时闻的近似，这种 简化对磁盘是有效的；第四种是最短定位时间优先算法( s p t f ) ，选择具有最小定位延迟的 请求，对磁盘来说，s p t f 算法与其它算法显著的不同在予它需要考虑寻道时闻和旋转延 迟。 将四种调度算法应用到a m l a l o k 上，统计随机负载在不同的请求到达频率下a t l a s l o k 的响应时间。如图4 1 所示，f c f s 的性能是四种调度算法中性能最差的，同时，f c f s 的 性能随着负载请求的增加性能最快达到饱和。s s t fl b n 的性能比c l o o kl b n 要好， s p t f 的性能最好，磊且s p t f 性能达到饱和的速度最慢。 前三种调度算法( f c f s ，c l o o kl b n 和s s t fl b 可以利用主机的软件系统简单有 效盼实现。考虑到磁盘l b n 到物理位置的映射关系，实现这三种调度算法不需要详细的 设备信息，只需要根据请求的l b n 号来选择要服务的请求。s p t f 算法通常是在磁盘驱动 器的阑件中实现，s p t f 算法需要磁盘状态的准确信息、l b n 到物理位置的映射信息、寻 址时间和旋转延迟的准确预测信息等。 第3 9 页 国防科学技术大学研究生院学位论文 1 6 。 1 4 。 1 2 。 、 善1 驻 麓s 。 墨 鬣6 0 4 。 2 。 0 露一誓? 野9 学猕黟? 心| = 1 i “? + 、繁黟。猕? ；霹臻7 繁葛 一 7 缓 。一j 。急 = u 。 凳 ! i ，翥 ! j 。多蕊 0 - ? 夕夕二遵 ? ：菇彭二 。囊 瑟赢旷零= 。i 蠢。一溉勘一赫- 。i ，。趣z 弧i 1 0 0 1 5 02 0 0 请求到达频攀( h z ) 图4 。1a t l a s l o k 在不同调度算法下的性能分析 4 1 2m e m s 存储设备请求调度算法 为了方便豹将m e m s 存储设备应用到计算机系统中，m e m s 存储设备剩用与磁盘相 同的接口。为了证明现有的磁盘请求调度算法同样适用于m e m s 存储设备，将上节中四种 磁盘的请求调度算法应用到m e m s 存储设备上。多数的请求调度算法，如s s t f l b n 和 c l o o kl b n ，只需要知道l b n 的信息，将l b n 之间的距离作为定位时间的估计。s p t f 算法涉及到寻址时间和旋转延迟。丽m e m s 存储设备只存在x 轴和y 轴方向的寻址，没 有旋转延迟。与磁盘相同的是，寻址时间是一维的，接近一个线性的l b n 空间。与磁盘 不同的是，m e m s 存储设备在两个方向的寻址是并行完成的，选择较大的作为实际的寻址 时闻。由于x 轴方向存在稳定时闻，x 轴方向的寻址时阂总是比y 轴大。如果y 轴的寻 址时间比较大，s p t f 的性能仅比s s t f 略有优势。 利用d i s k s i m ，将磁盘的调度算法应用到m e m s 存储设备上，统计不同的请求到达频 率的随机负载下的平均响应时间。从图4 2 中可以看出，四种调度算法在m e m s 存储设备 上具有和磁盘类似的性能：f c f s 性能最差，s p t f 性能最好。但是，f c f s 和基于l b n 的 算法之闻的差距比磁盘小，因为在m e m s 存储设备寻址时间在整个服务时间中占很大比 例。c l o o kl b n 和s s t fl b n 性能差距要比磁盘小。 按照推测，s p t f 算法在m e m s 存储设备上不但比其它算法的性缝要好，而且好很多。 但是，结果显示，s p t f 的性能与s s t fl b n 、cl b n 的性能很接近。因为x 轴的稳定时 间对s p t f 的性熊有很大影响。如果x 轴上的稳定时闻很大，x 轴的寻址时闻就会毙y 轴 的大很多，s s t f 具有与s p t f 接近的性能。如果x 轴稳定时间比较小，y 轴的寻址时间 第毒0 页 国防科学技术大学研究生院学位论文 在整个寻址时间中占很大比例，s p t f 的性能就比s s t f 高出很多。实验数据表明，如果x 轴稳定时间为0 ，s p t f 的性能比其它三种算法高很多；稳定时间越长，s s t f 的性能就越 接近予s p t f 。 1 2 0 嚣麓盟鬻静嘿鬻跫蚪紫，瞿舞，警嚣臻嚣? 胛唧钟哟一= 一一 1 0 0 ，、8 0 目 星 客 毯 罾 露 售卜4 0 2 0 0 i u ub u u9 u ul j u ul t u uz i u u 请求到扶频搴( h z ) 圈4 。2m e m s 存储设备在不同调度算法下浆性麓分析 实验结果表明，m e m s 存储设备可以利用磁盘的调度算法，可以很容易的应用到计算 机系统中。同时，考虑到m e m s 存储设备与磁盘不同的物理特性，研究适合m e m s 存储 设备的请求调度算法也是研究的一个热点闻题。目前，针对m e m s 存储设备的请求调度算 法有s d f ( s h o r t e s td i s t a n c ef i r s 0 0 j 和z s p t f ( z o n e - b a s e ds h o r t e s tp o s i t i o n i n gt i m ef i r s t ) ! 川。 4 2 数据布局策略 空间分配和数据布局至今仍是磁盘研究的一个热f j 话题，同样也是m e m s 存储设备研 究的一个热点。本节主要研究m e m s 存储设备定位特性如何影响小粒度的局部数据和大粒 度的顺序数据传送，研究了一季孛双向数据布局策略，分析了这种策略的性能。 4 2 1小粒度非顺序访问 m e m s 存储设备数据访问具有与磁盘类似的特性，短距离寻址比长距离寻址要快。与 磁盘不同的是，由于弹簧的回复力的存在，使得不同位置上触动器作用力的影响不同。图 4 3 表示了弹簧作用力辩每个t i p 的访问区域不同缱置的影响。弹簧的作用力随着s l e d 位移 的增加而增大，对于短距离来说定位时间反而较长。因此，在考虑查找小粒度、常用的数 据项的时候，除了考虑寻蛙距离，还要考虑s l e d 距中心位置的距离。 第4 l 页 国防科学技术大学研究生院学位论文 o 4 2o 3 90 3 8 0 3 9o 4 2 n 2 30 2 l o 2 0o 2 lo 2 3 il u l l 曼ld i m e 坤 o ，4 l0 3 8o 3 80 3 3 o 4 l 黼l i q e mfm t 4 啪 i l l m n a i j i l i w o t j m i s m m l l f l u! ! ! !i o g m i l l m i l i g l 舢g o 川i o i n m l mm el i u g l l l m h 一 o 2 2n 2 0o 1 9o 2 0 o 2 2 i i 强兰；：；嚣嚣i 强：h 器a - a ：l o e ! i 琵琶搿煞 鬻驯；：i i ；i i ；蒿黧羹黧 瓴4 l瓴3 80 ，3 7o 3 so _ 4 l ：器矗： ：11 1 ：! i i ! ! ! 0 0 2o 2 0o 1 9o 2 0 o 2 2 。#：jlullit i l i ：。：- 0 4 l巍勰o ，3 s覆3 s龟毒l 鏊嚣：2：嚣：器= 1 ：譬d h l i - 氇2 2。t 2 0o ，1 9氇2 0o 笠 鎏篓i 黧强；篓蒌i 麓霎；i i 笺； 嚣嚣强 ：器器豁 o 4 2 o 触 o 强o 3 9o 2 o 2 3o 2 1氇2 0o 2 la 嚣 4 2 。2 大粒度顺序访问 图4 3 探针不同区域中的访问时间 m e m s 存储设备和磁盘的流传输速率相似：a t a l s l 0 k 的流传输速率是1 7 3 - 2 5 2 m b s ， m e m s 存储设备的流传输速率为7 5 9 m b s 。m e m s 存储设备的定位时间比磁盘低一个数 量级，对m e m s 存储设备来说，定位时间对于大批量数据传输影响很小。例如：一个2 5 6 k b 的读请求在x 轴不同位置上的服务时闻，在1 2 5 0 个柱面豹不同请求之闻的服务时闻仅差 1 0 。同时减少了大粒度、顺序传送的数据对局部性的需求。但是，对磁盘来说，寻址距 离是影响寻址时阆的重要因素。同样，对一个2 5 6 k b 大小的请求，长距离寻址时阗可以使 整个服务时间增加1 倍