（计算机应用技术专业论文）数据广播中cache替换算法的研究.pdf

硕士学位论文 摘要 在以网络为计算中心的时代，迅速发展的无线数字通讯网络和便携 式计算设备引入了一种全新的移动计算范型。然而，移动性约束使得移 动客户惑是戮连或者掇骞一令较窜懿囊主媾簸露宽，戮致移动诗冀无法 适成数据敏感的应用环境。同时，漩入式系统中节点的资源受限特性极 大地影响着嵌入式应用的广泛推广，c a c h e 替换算法是克服嵌入式系统节 点存储资源受戳舄限性的重要技术之一，因此，研究数攥广播中的c a c h e 西换；去具旃较大酶臻泛恁义稚实爝价值。 数据广播环境中，用户注意力的频繁转移使得简单的c a c h e 管理算 法( 如l r u 算法) 不能满熙移动环境数据缓存的需要。本文主要研究数据 ，“季萋环境中蘩予代侩豹数攥骜换舅法，它是一耱考虑了数据访超壤枣帮 广播频率综合因素的c a c h e 替换算法。文章介绍了两种实用的基于代价 的c a c h e 数据替换算法基于访问记录的替换算法和带锁的循环淘汰 p i x 算法。翦者是根据翅户的访阍历史来蓣测瞧来访翊彳亍为的算法，酋先 嗣用访问目恚梅造概率霞，然后筛选出访闯襁率较小静一个数据集，并 从此数据集中选择出广播概率最大的替换项。后者是适用列c a c h e 的考 虑p i x 代价的f i f o 算法，同时，为避免重要数掘被替换，引入了带锁机 麓。阉簧统豹l r u 算法辛罄毙较，它们复杂度低在会孛率稻镌应延霹这嚣 项性能指标上都有一定程度的提高，有效改善了系统的高性能和低功耗。 熬于访问记录的替换算法在命中率性能指标上的改进尤为显著，带锁的 镶繇淘汰p i x 算法麓肇实矮，减少了复杂豹硬件设计电鼹，有效隆低了 功耗。试验证明，这两种算法尤其适应于存储空闯小瓣乎持设备，怒一 种非常实用的算法。 荚键谪；甄遽，c a c h e 鬻灌，数据广獾，数据饕换 数据广援中c a c h e 替换算法的研究 a b s t r a c t r e c e n ta d v a n c e si nw i r e l e s s d a t an e t w o r k i n ga n dp o r t a b l ec o m p u t i n g ， d e v i c e sh a v ee n g e n d e r e dan e wp a r a d i g mo fc o m p u t i n g ，c a l l e dm o b i l e c o m p u t i n g i nam o b i l ec o m p u t i n gs y s t e m ，u s e r sa c c e s si n f o r m a t i o na n y t i m e a n y w h e r ew i t ht h e i rh a n d l e dd e v i c e s ，e v e nw h e nt h e ya r em o v i n g 。h o w e v e r ， m o b i l i t yc o n s t r a i n sr a i s e sd i f f i c u l t i e sf o rm o b i l eu s e r s ，b e c a u s em o b i l e c l i e n t sm a yo f t e nb ed i s c o n n e c t e df r o ms t a t i o n a r ys e r v e rm a c h i n e so rm a y h a v eal o wb a n d w i d t hc h a n n e lf o rs e n d i n gm e s s a g e st os e r v e r s a tt h es a m e t i m e ，t h ec h a r a c t e r is t i co fn o d e ss t o r a g er e s o u r c el i m i t e di nt h ee m b e d d e d s y s t e ma f f e c t st h ee x t e n s i v ep o p u l a r i t yo fa p p l i c a t i o no ft h ee m b e d d e d s y s t e m 。c a c h er e p l a c e m e n ta l g o r i t h m si so n eo ft h ei m p o r t a n tt e c h n o l o g yt o c o n q u e rt h el i m i t a t i o n c o n s e q h e 撞t l y ，t h es t u d yo ft h ea l g o r i t h mi n d a t a b r o a d c a s th a sg r e a tt h e o r e t i c a lm e a n i n ga n dp r a c t i c a lv a l u e t h e “e q u e n ts h i f to fu s e ra t t e n t i o nr e s u l t st h es i m p l ec a c h em a n a g e a l g o r i t h m ( e g l r u ) c a nn o ts a r i s f yt h en e e do fm o b i l i t ye n v i r o n m e n t t h e p a p e rs t u d i e sm a i n l yt h ed a t ar e p l a c e m e n ta l g o r i t h m sb a s e do nc o s tw h i c h c o n s i d e r sd a t aa c c e s sp r o b a b i l i t ya n db r o a d c a s tf r e q u e n c ya tt h es a m et i m e t h i sp a p e ri n t r o d u c e st w oc o s t - b a s e dr e p l a c e m e n ta l g o r i t h m s ，i n c l u d i n g r e p l a c ea l g o r i t h mb a s e do na c c e s s i n gh i s t o r i c sa n df i f op i xr e p l a c e m e n t a l g o r i t h mw i t hl o c k t h ef o r m e ri st h ea l g o r i t h mw h i c hf o r e c a s t st h ef u t u r e v i s i t i n gb e h a v i o ra c c o r d i n gt o t h e v i s i t i n gh i s t o r yo fu s e r f i r s t l yt h e p r o b a b i l i t yf i g u r ei sf a b r i c a t e db yv i s i t i n gl o g ，a n dad a t a s e tw i t hl e s s e r v i s i t i n gp r o b a b i l i t yi ss c r e e n e do u t 。f i n a l l yt h er e p l a c e m e n tt e r mw i t ht h e b i g g e s tb r o a d c a s tp r o b a b i l i t yi ss e l e c t e d t h el a t t e ri ss u i t a b l ef o rf i f op i x w i t hl o c kt oa v o i dr e p l a c e m e n to fi m p o r t a n td a t a c o m p a r e dw i t ht r a d i t i o n a l l r ua l g o r i t h m s ，t h et w oa l g o r i t h m si m p r o v eh i tr a t i oa n dr e s p o n s ed e l a y t i m e ，t h ef i r s tw a yi n d i c a t e st h a tt h ei m p r o v e m e n to fh i tr a t i op e r f o r m a n c e i se s p e c i a l l yo b v i o u s t h e s e c o n dw a yi ss i m p l e ra n dr e d u c e sc o m p l e x h a r d w a r ec i r c u i t t h er e s u l t so fe x p e r i m e n t si n d i c a t et h a tt h e ya r ep r a c t i c a l a l g o r i t h m s ，e s p e c i a l l yf o rh a n d l e dd e v i c e sw i t hs m a l lc a p a c i t yo fs t o r a g e k e yw o r d s ： d i s c o n n e c t i o n ， c a c h em a n a g e m e n t ，d a t ab r o a d c a s t ，d a t a r e p l a c e m e n t l l 硕士学位论文 图2 1 图2 2 图2 3 图2 4 图3 1 图4 1 图4 2 图5 1 图5 2 图5 3 图5 4 插图索引 数据广播的基本概念模型4 三个广播程序示例1 0 产生一个服务器广播程序1 2 两盘广播中l i x 算法的替换过程17 给定访问记录的无向概率图2 3 基本列c a c h e 体系结构3 1 带锁的循环淘汰p i x 算法的缓存替换过程演示图3 3 算法c a c h e 命中率的比较4 0 算法c a c h e 响应延时的比较4 1 在d e l t a = 5 情况下，用户访问习惯的影响4 2 向前看间隔紧密关联阈值参数的影响4 2 数据“播中c a c h e 替换算法的研究 附表索引 表2 。1 显示的怒在各种客户访问概率情况下预期的延时，1 1 表2 2c a c h e 荫8 个块时的l r u 访问情况1 4 表2 3l r u 靼隧程替巍法懿失效率跳较1 5 表3 1 列举了统计分析的主要结果2 i 表5 。1b u 纪添格式3 8 l i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得靛研究成采。除了文串符羯舔| 薹标注雩l 用静漆容外，本论 文不包含任何其他个人戏集体己缀发表或撰筲的成果作品。对本文 的研究做出燕臻贡献的个人和集体，均己在文中以明确方式标明。 本人完全意谈到本声明酶法律后采由本人露撼。 终者签名：删马 日期：& 归歹年；月i - b 学位论文版权使用授权书 本学位论文作者完全了解学校有关保整、使用学位论文的趣窥， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 凝，竞诲论文被查阕秘偻阅。本人授权潮惫大学可以将本学位论文 的全部或部分内容编入脊关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存和汇编本学位论文。 本学位论文霾予 1 、保密口，在年解密后适甩本授权书。 2 、不，保密叮。 ( 谤在潋土藕纛方框悫抒“了”) 作者签名：专l 坞 警拜签名胁发、 日期：抄g 年弓月a7 日 基麓：年胃b 塞兰! i i 兰，：。；，。一 _ # _ _ # l = = l d _ _ _ _ _ _ _ l i l l _ _ ! = ! - _ = - _ _ _ 目= = j 目_ 日e 2 。；_ 。一一 1 。1 研究目的和意义 第1 章绪论 从计算机诞生至今，计算技术随着计算环境的变化而不断发展，已 经经历了三个阶段。在最初的集中式计算阶段，大型计算机向人们提供 了大规模计算和集中管理信息的能力；后来，随着网络技术的发展和个 人工作站的普及，计算技术从集中式计算发展到了分布式计算阶段。在 分布式计算阶段，通过各种基于i n t e r n e t 的分布式应用人们可以方便的获 取和交换信息；如今，随着移动计算设备和无线数字通讯技术的发展， 分布式计算正逐步向移动计算阶段过渡。移动计算环境基础设施，尤其 是高性能的广域无线通讯网络的研究为移动计算系统的实现提供了可能 性，人们离真正的移动计算已经越来越近。今天，人们可以通过个人数 字代理访问诸如天气预报、股票价格和电子邮件等简单应用，面向智能 手机的w a p 应用也取得了一定的成功。移动计算突破了对时间和地域的 限制，成为了一种无处不在、无时不在的计算。 现存在的移动计算所依赖的无线移动计算环境，包括交通信息系统、 医院信息系统、公共安全应用和无线教室，都是一种非对称的通信环境。 它的显著特点是从服务器到客户端的下行流通信容量不对称于从客户端 返回到服务器的上行流通信容量。这种通信的不对称表现在两个方面： 第一个是服务器相对于客户端的不对称，原因是物理通信媒质的带宽限 制。像上面所说的无线环境中，静态服务器有较高的带宽，具有强有力 的广播能力而移动客户端没有或仅有较小的传输能力。另一个次要方面 是客户端相对于服务器的不对称。例如，一个信息检索系统中，客户端 的数目远大于服务器的数目。那么这种系统也是非对称的，服务器和网 络并不能同时处理多个客户产生的请求。 由于非对称通信环境主要表现在服务器相对于客户端的不对称，也 就是说，服务器的下行传输带宽比客户端的上行传输带宽要大得多。为 了利用这一点，在广播磁盘项目中服务器采取了数据广播的方式。利 用这种方法，一个服务器不断的并且重复的向客户群广播数据，客户只 需要被动的从广播中接收所需要的数据。 数据广播环境主要关注两个方面的问题，服务器方面和移动客户端 方面。服务器端最主要的挑战是该如何组织用于广播的数据。广播数据 数据r m 搔中c a c h e 替换算法的研究 _ _ # _ e = 自_ e ! j 自_ # ! = = 自_ ! j j _ _ _ e j 自e _ _ - _ - _ i i i i i i l l , i _ _ _ _ _ _ _ = e = = _ _ ；2 一 的组织和调度方式对移动客户接收数据的性能有很大影响。移动客户端 方面最主要的问题就是本地缓存的替换策略。传统c a c h e 在缩短微处理 器和低速主存之间性能差距上起着重要的作用，在移动计算环境中，由 于数据广播的特点和移动设备的体积和存储容量的限制，常见的c a c h e 替换算法有很多值得做的工作。因此，我们选择移动环境中的c a c h e 技 术作为突破口，着重从算法级研究适合数据广播环境的移动客户端的 c a c h e 替换算法。 本课题来源于s o c 中高性能、低功耗c a c h e 结构的研究与实现( 湖 南省自然科学基金项目) ，编号：0 4 j j 3 0 0 8 。在嵌入式处理器中，c a c h e 存储器通常占芯片面积的大部分，其功耗也是整个微处理器所需功耗的 主要部分，例如，s t f o n g a r ms a l10 片上c a c h e 的功耗消耗就占整个芯片 功耗的4 3 ”1 。因此c a c h e 是优化s o c 性能和功耗的好目标，研究高性 能低功耗c a c h e 存储器是当前s o c 体系结构研究的重要方向之一。 1 2 论文工作 研究高性能、低功耗的c a c h e 可以从设各级、电路级、体系结构级、 算法级等方面来改进存储器系统的性能和功耗。本文主要是针对特定的 移动计算环境一数据广播环境，从算法级来研究移动客户端的c a c h e 管 理技术，以实现c a c h e 乃至整个系统的高性能和低功耗。 c a c h e 替换算法是已经探讨得比较成熟的问题，但传统的c a c h e 替换 算法主要是考虑了命中率对性能的影响，而在无线数据广播环境中，由 于移动环境断连的影响和手持设备资源的限制，数据的响应延时指标是 和命中率指标同等重要的问题，所以，无线移动计算环境中移动客户端 的c a c h e 替换算法应该是一种基于代价的替换算法。本文提出了两种基 于代价的c a c h e 替换算法：基于访问记录c a c h e 替换算法和带锁的循环 淘汰p i x 算法。前者是在概率图基础上的一种通用的低开销的c a c h e 替 换算法；后者是在列c a c h e 基础上的一种简单实用，不需要复杂硬件电 路的c a c h e 替换算法。本文详细介绍了这两种方法的基本思想和实现过 程，并在命中率和响应延时两项性能指标上，和传统的l r u 算法作了比 较。 1 3 论文结构 论文的后续章节按以下方式组织 硕士学位论文 第二章论述数据广播环境中的c a c h e 技术。由于本文是研究数据广播 环境中客户端c a c h e 的替换算法。所以本章首先详细描述了数据广播环 境的定义特点、约束条件和数据广播环境的基础模型。然后，介绍了广 播环境中服务器端数据广播程序的属性、产生和调度过程。最后，分析 传统的c a c h e 替换算法及其在数据广播中的局限性，并介绍基于代价的 c a c h e 替换算法的基本思想。 第三章详细讲述了基于访问记录的c a c h e 替换算法。首先介绍了基 于访问纪录替换算法的可行性。然后，具体介绍算法的实现过程，包括 概率无向图的构造过程和筛选过程。最后，分析这种算法的时间复杂度 和空间复杂度。 第四章详细讲述了移动列c a c h e 中的带锁循环淘汰p i x 算法。首先， 通过介绍列c a c h e 的基本思想和实现机制，探讨如何将列c a c h e 引入到 无线数据广播环境中来。然后，描述了适合广播环境和列c a c h e 的带锁 的循环淘汰p i x 算法。具体介绍了基本原理和实现过程。最后，分析了 这种算法的时间复杂度和空间复杂度。 第五章是试验部分。首先，给出了高性能低功耗的评价公式，然后， 将基于访问记录的替换算法、带锁的循环淘汰p i x 算法和传统的l r u 算 法作了比较。详细描述了原始实验数据的获取、处理和试验过程的实现， 通过对命中率和平均响应延时两项性能指标的比较，试验结果表明算法 达到了预期的设计目标，尤其适用于存储能力比较小的手持设备。同时， 这一章还给出了相关参数对试验的影响。 最后结论对全文工作进行总结。列举了论文工作的主要贡献，并且 对进步的研究提出了展望。 数据广播中c a c h e 替换算法的研究 第2 章数据广播环境中的c a c h e 技术 2 1 数据广播环境 数据广播环境就是采用了数据广播的非对称通信环境。它既具有移动 计算环境的共性和约束条件，又具有自身的特点。下面将详细讨论数据 广播环境的基础模型，移动计算环境的约束和数据广播的个性特点。 2 1 1 数据广播环境基础模型 在未来的移动环境中，个人通讯网络p c nf p e r s o n a lc o m m u n i c a t i o n n e t w o r k ) 为软件系统提供网络通讯平台，它允许用户在任何时问、任何地 点使用各种接入手段访问网络上的资源。虽然个人通讯网络的体系结构 还没有最终确定，但在现有数字无线网络的基础上，它的典型的支持移 动计算系统模型如图2 1 所示。 图2 1 数据广播的基本概念模型 图2 1 显示【3 】是一个典型的数据广播的基本概念模型。它由三类计算 设备组成： 具有无线通信接口并且支持数据广插的固定主机( m s s ) 没有无线通信接口的固定主机( f h ) 移动计算设备( m u ) 整个网络由有线网络作为主干例络，所有主机通过固定网络连接在 一起，固定网络中的侮个m s s 负责建立一个无线网络单元，也就是图中 一起，固定网络中的侮个m s s 负责建立一个无线网络单元，也就是图中 硕士学位论文 _ e 目_ _ e _ 0 = = = = # = = | = j ! _ _ i = _ ，_ _ _ - ，_ = _ _ _ _ e e j 自l e e _ j 自| e e = = e 4 = j e 詈 的无线广播单元或无线局域网单元，单元内的m u 与m s s 之间通过无线 网络连接。相对于可靠性不高的无线网络单元，我们将固定网络部分称 为可信部分。而无线网络单元发送的信号可以覆盖的范围叫做一个区间 ( c e l l1 。总之，由图所示的移动计算环境中，m u 可以从任何一个无线网 络单元经由m s s 连接到固定网络上。 无线网络单元的覆盖范围取决于它们采用的无线通信技术，卫星系统 的一个区间的直径可以超过4 0 0 英里，蜂窝系统发射器的信号覆盖范围 直径为凡英里，而无线局域网的区间半径就只有几十米。为了更有效地 利用频道，支持很多的用户，无线网络的一个发展趋势是区间的小型化。 移动主机移动时可能穿越区间的边界，进入另一个m s s 所覆盖的区间。 这个过程叫做越区切换( h a n d o f f ) 。越区切换将对链路管理和位置管理造 成影响。尤其在数据传输中对越区切换的处理会比较复杂，因为这种情 况下对数据丢失率有严格的限制【4 l 。 移动主机的特点也差别很大。个人通讯网络必须既能够支持小型轻便 的计算设备，同时也可以支持功能强大的较重的设备。移动主机依靠电 池提供能量，通过网络接口发送和接受消息，以及c p u 处理数据、磁盘 和内存访问是主要的消耗能量的操作。因此，在电池容量的限制下，移 动设备可能会经常地主动或被动关闭网络接口使自己处于断连状态，或 者降低时钟颇率进入休眠模式( d o z em o d e ) 。 2 1 2 数据广播环境的约束 2 1 2 1 移动设备的约束 移动设备的种类很多，从体积小、计算能力弱的智能手机和个人数 字助理( p d a ) ，到体积较大、计算能力较强的掌上电脑和便携式计算设 备。和个人电脑、工作站等固定设备相比，这些移动设备在设计时需要 考虑设备的便携性。因此产生了移动设备的两个重要约束：资源相对贫 乏和不安全。其中资源的贫乏性是移动设备额外设计要求造成的。不安 全性是设备可移动性的直接后果。 由于便携性的需要，在设计移动设备是需要考虑一下三个目标：降 低电源消耗，减轻重量和小型化。同时，移动设备设计还需要考虑普通 设备设计所需要考虑的各种硬件需求。这些附加的设计需求必然会导致 具有同等计算和存储能力的移动设备具有更高的代价。因此，在价格比 较接近时，移动设备在处理器速度、内存大小和磁盘容量等主要计算资 源方面均低于相应的固定设备。而且使携性能越好的设备，其资源就越 贫乏。 数据广播中c a c h e 替换算法的研究 虽然在过去的几年内各种小型手持设备的计算速度越来越快，存储 容量也越来越大。但同时个人桌面系统的计算和存储能力也得到了日新 月异的发展。实际上，每当新的技术可以增加移动设备的资源时，类似 的技术通常也可以应用到固定设备上增加他们的计算资源。而便携性的 要求始终是移动设备的设计负担。因此，资源的相对匮乏是移动设备的 一个内在性质，硬件技术上的进步无法消除固定设备和移动设备资源上 的差距。 移动设备的另一个约束是它更加不安全和容易毁坏。移动设备被设 计得容易携带，因而人们在携带它的同时也使得它更容易丢失或被窃取。 同时，和固定设备所在的机房相比，移动设备的使用环境更加恶劣，更 容易导致移动设备的损坏。在移动计算系统中，移动设备的不安全性和 不健壮性意味着它所存储的数据的不安全性和不健壮性。 综上所述，移动设备的资源和安全限制使得它们不适合数据的永久 存储。存储容量的限制使得不能把所有相关数据直接存储到本地，安全 性限制使得数据更容易泄漏或毁坏。 2 1 2 2 移动网络的约束 支持无线数据传输的移动网络有很多，主要可以分为蜂窝系统、基于 包交换的广域无线网、无线局域网和卫星系统四类【5 1 6 】。 第二代蜂窝系统采用数字调制技术和高级呼叫处理技术，可以提供类 似i s d n 的服务。因此它们在提供语音服务的同时也可以提供数据传输服 务。目前主要的第二代蜂窝系统有欧洲和我国使用的g s m ( g l o b a ls y s t e m f o rm o b i l e ) 系统和主要在美国使用的t d m a ( t i m ed i v is i o nm u l t i p l ea c c e s s ) 和c d m a ( c o d ed i v i s i o nm u l t i p l ea c c es s ) 标准。这类网络的错误率高、传 输速率低，其有效数据传输率为9 k 到1 4 k b p s 。 早期蜂窝系统的低传输率、低可靠性和高通讯代价等缺点迫使人们考 虑开发公共的广域数据网络。它们采用包交换技术来进行数据传输，因 此可以更有效地利用频道。其中最典型的例子就是c d p d ( c e l l u l a rd i g i t a l p a c k e td a t a ) 系统，它可以利用己有的蜂窝系统的网络设备提供面向数据 的服务。这类系统的主要目标是向行人和车辆提供大范围、高移动性、 低传输速率的服务，其有效数据传输率为9 6 k b p s 。 无线局域网可以向低移动性的用户提供高速无线数据通讯能力，它通 常被看成是对有线网络的扩充。虽然它的有效数据传输率可以达到 1 u m b p s 以上，但是其覆盖直径通常只有几十米，大约只能包括一个实验 室或一层楼，因此不能支持真正意义上的移动性。 卫星系统可以覆盖的范围最广，可以覆盖整个大陆甚至全球。但是目 6 硕士学位论文 前商用卫星系统的代价太高，因此只在专门领域得到了应用。卫星系统 的传输信道分为上行信道和下行信道两个方向，具有不同的传输速率。 例如。r b c o m i n 系统的上行信道传输率为2 4 k b p s ，下行信道传输率为 4 8 k b p s 。 移动设备在户外移动时只能通过无线网络保持连接，而在室内工作时 可以使用无线网络，也可以使用更加高速可靠的有线网络接口。上面的 分析说明广域无线网络的数据传输速率和可靠性都远远低于有线网络。 而且在同一个移动网络覆盖范围内，由于多路干扰或者移动设备位置的 改变等因素，网络性能也会有比较大的变化。同时，外部环境的干扰， 如地形或屏蔽等，也会影响网络性能甚至导致移动设各失去网络连接。 考虑到实际环境中无线网络往往相互覆盖【7 】这一特点，移动设备可以 随着位置和信号的变化来选择合适的网络。由于不同的无线网络的数据 传输率，可靠性和用户拥挤程度不同，移动客户还会面临更大的变化范 围。 虽然随着无线通讯技术的发展，人们可以预期在不远的将来出现更 快、更可靠、更便宜的无线通讯网络。尤其是未来的3 g ( t h i r dg e n e r a t i o n ) 技术提供了更高的数据传输性能保证。但是由于资金和频道等资源的限 制，在全球范围内部属一个统一的高速可靠无线网络的设想是不现实的。 由于一个基站所使用的频率是有限的，因此在用户稠密的地区就需要更 多的基站提供更可靠的服务，而在用户稀少的地区就可以部署少量的基 站。因此即使在未来的无线网络中，由于移动速度，干扰和容量限制的 影响，它们在性能和可靠性上也远不能达到有线网络。 上面讨论了移动设备自身的约束使得它们不适合做数据的永久存储 地。而移动网络的间断性使得我们不能假定移动设备总是和数据服务器 保持可靠的网络连接。这要求我们在设计移动计算系统时要兼顾自身资 源和网络资源的使用，并且对移动设备在失去网络连接时仍然能够自治 地运行。 2 1 2 3 移动性的约束 有了小型化便携计算设备和无线通讯网络的支持，用户可以在任何 时间、任何地点，以及在移动中访问数据。计算设备( 节点) 的移动性是移 动计算环境最基本的特征。由于移动性从根本上打破了分布式系统的计 算节点固定的假定，所以它将对计算模式和系统设计产生深刻影响。 综上述所，移动计算环境的特点可以归纳为以下三个约束： 手持设备的资源都相对贫乏、安全性差。由于能源和便携性的限 制，手持设备必须牺牲计算能力，存储能力和其它能力来提高移 7 数据广播中c a c h e 替换算法的研究 动性。但在提高便携性的同时也增大了移动设备丢失和损坏的可 能性。 网络的性能变化范围很大，连接时断时续。无线网络，尤其是广 域无线网络的网络带宽、传输延迟和通讯费用和有线主干网络都 有数量级上的差异，移动计算系统必须能够同时适应高性能的有 线网络和低性能的无线网络。 计算节点位置不固定。在移动计算系统中，计算设备在移动的同 时还要保持计算的连续性。这必然会影响系统对计算节点的拓扑 结构和系统配置的依赖关系。 2 1 3 断连操作 移动客户的断连( d i s c o n i l e c t ) 和传统分布式计算中的连接失败是有 本质区别的，移动计算机的主动断接不是一种故障，而是一种工作方式， 可以认为是有计划的连接失败，是可以预见的。移动计算机在移动过程 中，由于使用方式、电源、无线通信费用、网络条件等因素的限制，一 般不采用保持持续联网的工作方式，而是间歇性入网、断接。当然，也 有一些连接失败的情况，当移动设备移动到网络没有覆盖的区域时会导 致断连；移动网络的通讯质量剧烈变化时可能导致断连。我们把用户主 动断开网络连接的情况称为主动断连，把网络故障导致移动设备无法保 持网络连接的情况称为被动断连。在主动断连的情况下，用户可以预见 断连的出现，因此可以预先采取一定的准备措施。 断连的频繁出现极大地改变了移动环境中客户访问数据的模式，对移 动计算系统的设计带来了新的挑战。例如，b a r b a r a 和i m i e l i n s k i 把移动 客户看成可以在s l e e pm o d e ( 断连状态) 和a w a k em o d e ( 连接状态) 来回切换 的计算节点【8 1 。传统的分布式系统把断连和其它网络故障一样视为灾难 性事件，从网络中断开的节点不能继续进行操作。而在设计移动计算系 统时必须把断连看成是系统的一种可能的运行状态，并提供一定的机制 允许处于断连中的客户仍然可以透明地请求、浏览和修改数据。同时， 移动设备和移动网络的约束又增加了支持断连操作的难度1 9j 。 通过前面的分析我们可以看出这些约束都是移动环境的内在特性，断 连是这些约束的集中表现，不能依赖硬件技术的发展来解决。因此移动 计算研究的主要目的就是从分布系统的模型，结构和算法等方面研究能 够解决上述约束的，适合于移动计算环境的理论和系统。这也是本文工 作的出发点和价值。 8 硕士学位论文 2 1 4 数据广播的个性特点 广播技术是服务器利用无线网络固有的广播能力将数据库中经常被 大部分用户访问的公共热点数据组织起来，对这些空中数据及其索引合 理组织后，经由m s s ( 移动支持结点) 向无线网络单元内所有m c ( 移 动客户机) 广播。数据广播的最主要优点如下【4 】： 很好的可伸缩性，因为系统的性能并不取决于有多少客户在侦听， 它可以支持大量m c 同时接收，而且不管接收的客户数有多少， m s 8 的广播代价并不改变，这就允许大规模的移动用户同时访问 被广播的热点数据。 无线广播的接受者( m c ) 只要在信号的覆盖范围内，可以自由 移动而不影响接收。 即使在断连时，也允许m c 访问到新数据。 节约有限带宽：m c 从数据广播中获取数据，可以避免或减少与 服务器间的上行网络通信。 便于发送新数据：服务器可以利用数据广播，将新产生的数据发 送给m c ，即使m c 事先不知道这些数据的存在。 数据广播环境主要针对非对称的通信环境，它着重关注两个方面的 问题，服务器方面和移动客户端方面【i 们。服务器端最主要的挑战是广播 的数据该如何组织。媒介串行化的性质排斥了数据的随机访问，因此， 广播磁盘上数据的分布对性能而言是一个关键的因素。而且，带宽本质 上是一个固定的资源，增加某些数据项的广播频率必然会降低其他数据 项的广播频率。移动客户端方面最主要的问题就是本地缓存的替换策略。 后面我们将详细讲述服务器应该如何构造多级广播磁盘，以及传统的 c a c h e 替换算法为什么不能适应数据广播环境。 对数据广播环境的假设如下： 数据只能以只读的方式被访问； 移动客户机的数目和访问要求是固定的； 移动客户端并不链接上行的通信链路； 2 2 服务器广播程序 2 2 1 广播程序的特型 在数据广播通信环境中，一个服务器必须构造广播程序来满足移动客 9 数据广播中c a c h e 替换算法的研究 户的需要。最简单的广播程序是频率响应均匀的广播( f l a tb r o a d c a s t ) ， 也就是当广播的数据是所有移动客户所需要的情况下，服务器把这些数 据简单组织起来周期性的进行广播。一个频率响应均匀的广播如图2 2 所示。这种广播可看成是客户端存储结构的额外一层，也就是说，当移 动客户端一个应用程序运行时，它首先从本地内存或磁盘中检索数据， 如果没有命中，则监听广播等待所需数据的到来。 在频率响应均匀的广播中，所有数据项的广播频率是一样的即不 管数据项对移动客户的重要与否，移动客户都必须等待相同的时间。早 期的基于广播的数据库系统像d a t a c y c l e 已经采用了这种方法。 现在采用的多是广播磁盘的算法，并不是把广播媒介看成是一个单 一的频率均匀的磁盘，而是把广播组织成多个不同大小、以不同频率旋 转的磁盘。一般情况下，把访问需求较高的热点数据放到频率较高的快 速磁盘上，而把访问需求较低的冷数据放到频率较低的慢速磁盘上。这 样，当移动客户访问热点数据时，响应延时比频率响应均匀的广播要短 得多，但是，当访问冷数据时，却比频率响应均匀的广播要长。因此， 这是广播程序组织时要考虑的一个折衷问题。 理论上，服务器广播程序的产生可以看成是个带宽分配问题。给 定所有移动客户的访问概率，服务器可以决定分配给每个数据项的最优 带宽百分比。然后，根据每个数据项带宽分配的百分比，随机产生服务 器广播程序。但是，由于两个相同数据项到达时间间隔的随机性，这种 随机产生广播程序的方法在最小的期望延时方面并不是最优的。 图2 2 三个广播程序示例 图2 2 显示1 了带宽的均衡问题。图2 2 中三个长度相等的数据项构 成了一个数据组，对于同一个数据组有三个不同的广播程序。程序( a ) 是一个频率响应均匀的广播，而程序( b ) 和( c ) 中数据项a 的广播是 数据项b 和c 的两倍。程序( b ) 是一个不对称的广播，它把对数据项a 的广播聚簇在一起。相反，程序( c ) 是一个对称的广播，广播中两个相 l o 硕士学位论文 同数据项的到达时间问隔是相等的。我们把程序( c ) 称为多级磁盘广播。 表2 1 各种访问概率下的期望延时 访问概率期望的延时( 广播单位) ab c频率响应均 不对称多级磁盘 匀广播( a )广播( b )广播( c ) 0 3 3 30 3 3 30 3 3 31 5 01 7 51 6 7 o 5 00 2 5o 2 51 5 0 1 6 3 1 5 0 o 7 5o 1 2 5o 1 2 51 5 01 4 41 2 5 0 9 00 0 50 0 51 5 01 3 31 1 0 1 oo 0o 01 5 01 2 51 o o 表2 1 显示的是在各种客户访问概率情况下预期的延时。从表2 1 中 我们可以看出：( 1 ) 当数据项具有相同的访问概率时，频率响应均匀的 广播性能是最好的。这也证明了广播磁盘最基本的约束，由于带宽是固 定的，增加一个数据项的广播比率必然降低其他数据项的广播比率。( 2 ) 数据项访问概率越不对称，非频率响应均匀广播的性能就越好。( 3 ) 多 级磁盘广播的性能总是比不对称广播的性能要好。这是因为多级广播是 对称的广播，两个相同数据项的到达时间间隔是相等的，于是，对于移 动客户随机到达请求的响应延时是这个间隔的一半。相反，不对称广播 两个相同数据项的到达时间间隔是不相等的。在这种情况下，在较大时 间间隔中移动客户发出随机请求的概率比在较短时间间隔中发出请求的 概率要大。于是，响应延时会随着时间间隔变化的增加而增加。 相比不对称广播，多级磁盘广播除了性能更优以外还有以下几个好 处：( 1 ) 有一些预取技术必须知道某个数据项准确的广播时间 1 2 1 ，多级 磁盘广播能满足这种预取技术的要求。( 2 ) 多级磁盘广播数据项广播的 规律性有利于使用休眠技术来降低功耗。( 3 ) 把数据项按照广播频率分 类，这些类可以被移动客户的c a c h e 管理策略所利用。( 4 ) 多级磁盘广 播引入了周期性的概念，周期性对于广播内容的更新和修改是十分重要 的。因为这些理由，我们主张广播程序应该有以下一些特性： 相同数据项广播的时间间隔应该是固定的。 对于重复广播的周期，应该有一个好的定义。 少量的广播频率数目。 在以上约束下，可用的广播带宽应尽可能被使用。 数据广播中c a c h e 替换算法的研究 2 2 2 多级磁盘广播的产生 我们将描述一个满足特定的访问概率分布广播磁盘模型【l3 1 ，这个模型 有三个参数可以调整。第一个是广播磁盘的数目，它决定着广播数据项 的频率的数目。第二个是每个磁盘数据项的数目。第三个是广播的频率 是多少。这些参数决定了广播的大小和绝对的到达速率。例如，当增加 一些数据项到快速磁盘上，很明显会增加慢速磁盘上数据项的响应延时。 所以，我们直觉的应该在快速磁盘上配置较少的数据项。 图2 3 显示 13 】的是一个多级磁盘广播产生的例子。在已知所有数据项 访问概率分布和广播磁盘数的情况下，我们需要把这些数据项分配到广 播磁盘上。如图2 3 所示，现有三个广播磁盘，磁盘d 1 的广播频率是磁 盘d 2 的两倍，磁盘d 3 的四倍。因此，t e lf r e q r j = 4 ，r e l f r e q 侣j = 2 ， r e lf r e q j = 1 。每个磁盘将按照各种磁盘广播频率的最小公倍数分成很多 块( c h u n k ) 。在这里最小公倍数是4 ，所以，慢速广播磁盘d 3 分成四块， 磁盘d 2 分成两块，磁盘d 3 分成一块。值得注意的是，不同磁盘的块的 大小可以是不相同的。结果，整个广播的主周期( m a j o rc y c l e ) 包含了四 个子周期( m i n o rc y c l e ) 。每个子周期由每个磁盘的一块组合而成，个 周期有1 6 个数据项。按照传统的存储体系结构概念，这个广播创造了一 个三级的存储体系结构，d 1 是最小且最快的一级，d 3 是最大且最慢的 一级。 图2 3 产生一个服务器广播程序 在这个多级磁盘广播程序中，当不能正好把一个磁盘分成所要求的 块的数目时，有一些广播槽( s l o t ) 将没有被使用。当然，那些空槽并不 会被浪费，它们能被用于广播额外的信息，像索引、更新或者无效信息。 甚至，当移动客户在需求驱动模式下使用一个上行链路通道时，服务器 硕士学位论文 可以利用这些槽来广播移动客户所需要的数据项。更何况，当广播磁盘 的个数很少而广播的数据项数目很多时，没有使用的槽的数目仅占非常 小的一点比例。另外，如果必要的话，磁盘的相对频率可以调整以减少 未使用槽的数目。 对磁盘相对广播频率唯一的限制是它们必须表示为正整数。正整数能 很明白显示不同磁盘之间广播频率的差异。比如当一个慢速磁盘每旋转 9 8 次另磁盘就旋转1 4 1 次。可是，表示为正整数也可能使像以上这样 的广播磁盘的整个周期很长。所以，相对频率应该小心的选择且尽可能 表示成简单的比率l l ”。 2 3 常见的c a c h e 替换算法及局限性 断连是移动计算环境尤其是无线非对称通信环境的基本特性。由于代 价昂贵或者是上行链接无效，使得移动客户将与服务器断开连接。当不 使用数据广播时，断连的客户仅仅只能依靠缓存到本地的数据。可是， 这些数据并不是完全适用的，首先，在很多情形下要百分之百准确预测 断连期间将要访问到的数据是不可能的。其次，下载到本地的数据当服 务器或其他用户更新时将变得很陈旧而不可用。最后，在断连时，客户 也许要上传重要的数据。所以，数据广播关心的另一个重要方面是移动 客户端的c a c h e 管理问题【1 4 l 。下面我们首先将讨论常见的几种替换算法 及其它们的局限性。 在传统的台式计算机中，由于主存中的块比c a c h e 中的块多，所以当 要从主存调入一个块到c a c h e 中时，会出现该块所映像到的一组( 或一 个) c a c h e 块已全被占用的情况。这时，需强迫腾出其中的一块，以接纳 新调入的块。那么应该替换哪一块昵? 这就是替换算法所要解决的问题。 直接映像c a c h e 中的替换很简单，因为只有一个块，别无选择。而 在组相联和全相