文档介绍：万方数据
一种松竞争性缓存快速存取算法蔡昭权引言第卷第期年月计算机应用k文章编号：一摘要：在文件缓存调度中，每个文件都有固定的大小和被存取的消耗，为了响应对文件操作的一系列请求，把kk(k)关键词：分页；缓存；快速存取算法；竞争性分析中图分类号：；Awordspagingcachingon-line进入世纪后，网络应用规模和数据最逐步扩大，海量数据处理巾使用缓存方法的情况越来越频繁，因此迫切需要对经典的缓存处理算法进行改进以提高处理效率。对于文件缓存问题，通常给出一个有特定大小为的高速缓冲存储器和一个文件请求序列，每一个文件都有一个特定的大小和特定的存取消耗，并且在缓存器保存文件来满足请求，我们总希望尽量减小总存取消耗。特殊情况下，当一个请求文件不在缓存中时，把它存入缓存中，支付存取消耗，并从缓存中移除kSleatorTmjkh小可能消耗为畖。那么我们说一个文件缓存算法的竞争C(hk)个算法就是在线即时的。由于所有文件大小和消耗是一样的，问题就在于内存分SleatorTarjan近最少使用算法和许多其他确定性的在线分页方法的竞争比k(kh+1)说性能保证是至关重要的。类似的分类研究有：统一大小，统一消耗。一个简单随机的分页算法称作mardingD(1n)McGelehSleatorf{{个最佳的竞争比为的随机分页算法乜】。在确定性分页策略中为蠡’，这意味着任一请求序列对大部分后于使用容量为幕捍娴淖罴阉惴ㄊ荄。同样，标记算法显爪竞争比为。统一大小，任意消耗。文件缓存的特殊情况是当所有文件大小都一样时，即是所谓的加权缓存。对于加权缓存，ChrebakHkgreeddual(kh+1)p1Greedy算法产牛了许多著名的分页和有利缓冲策略，包括最近最少使用算法、先进先出算法、·算法和平衡算法。任意大小，消耗为蛳牡扔谖募笮 Ｊ躓Irani()Iranirr0(1b2k)WWW很蕈要的。例如，在浏览器和代理服务器上，远程文件为避免远程存取而存储于本地机上。在网络服务器上，磁盘文件为Irani1管理应用软件的缓存策略没有考虑文件大小，因此实际上它并不能产生很好的效果。允许任意消耗也同样是重要的。在许多情况下，文件消耗既不是同文件大小一致也不是简单地与文件大小成比例。例如，存取一个远程文件的消耗依赖于文件在网络中的传输距离。即使考虑距离，消耗也不一定和文件大小成比例，例如，节约措施下的文件传输。此外，一些应用程序也根据实(1970)CCFV0128．Oct2008．惠州学院网络中心，广东惠州；寤4笱Ъ扑慊蒲в爰际跸担本．甧Zhaoquanl'2(1NetworkUniversy,Beqing，如后收稿日期：一一；修回日期：——。516015China：瑆costthe鹪costA—．algorithmmanywellknowngeneralizedkThis．籧2Department
万方数据
=(|Il1)Credit[f]+kl推论杂贑／快速存取的松竞争性模型∽，该分解比对加权缓存的特殊情况的分解还要简单。件的消耗∽应高于占枣∽，不管它是否被存取。．F$costl快速存取算法分析第期蔡昭权：一种松竞争性缓存快速存取算法清空缓存中文件，的子集，如’∽；际情况为不同的文件分配不同的消耗。例如一些文件接收时要由浏览器显示，因而对用户来说，显示有效更