一种改进的Pseudo-LRU替换算法

Pseudo-LRU替换算法可以避免复杂的硬件设计,所以在很多流行的Cache内存系统被使用.但是该算法的主要缺点是二叉树结构的顶层节点不能包含所有底部叶子节点的信息,在某些情况下会做出错误的替换决策.针对PLRU算法存在的问题,在分析PLRU算法的原理的基础上,通过增加处理二叉树顶层节点信息的逻辑,得到一种新的替换算法.测试结果表明,这种新的替换算法使Cache命中率提高到98.73%.

信息中心网络内缓存替换算法性能分析与优化

信息中心网络（information centric networking,ICN）是一类受到广泛关注的新型互联网体系结构.通过对网络内（in-network）缓存的充分利用,信息中心网络可以极大地增强内容分发效率.网络内缓存的管理机制一直是信息中心网络研究中的热点问题.分析了网络内缓存的基准缓存替换最近最少使用（least recently used,LRU）算法的性能,指出多跳LRU缓存中广泛存在的＂缓存退化＂问题：在首个缓存节点发生缺失的内容请求也很难被下游的缓存命中.针对这一问题,提出一种基于预过滤的O（1）复杂度的改进算法.在原有缓存前放置一个仅记录内容标识的预过滤缓存,完成对原始内容请求的整形,使得预处理后的请求流量可以更容易被后面几跳缓存命中.基于真实互联网拓扑的实验表明,在信息中心网络典型应用场景下,预过滤LRU的缓存命中率可以达到LRU的2~3倍.

操作系统中页面置换算法的对比研究

在操作系统的页面置换过程中,采取何种算法,需要进行分析,才能提高系统的性能。在Windows XP中,用Visual C++实现先进先出页面置换算法和最少使用页面置换算法,并用数据对这两种页面置换算法进行仿真实验,对实验结果进行了分析和比较。

对LRU页面置换算法的理论改进

在对内存进行虚拟管理时 ,页面置换算法的好坏直接影响着系统的性能 .现有的常用算法有四五种 ,文章对其中比较合理的算法——最近最少使用算法 ( LRU)进行理论上的改进 .

页面置换算法的Z规格说明

虚拟存储系统中,如果使用段页式存储管理或者页式存储管理,当发生缺页,而主存中已没有空闲页架时,则需要选一页淘汰,进行页面置换.本文首先简要介绍先进先出算法(FIFO)和最近最少使用算法(LRU)的原理.接着对这两种算法用Z规格说明语言进行了比较详尽的描述.最后给出了一些操作模式的前置条件,并对系统中的一个定理进行了证明.

子页感知的闪存页面置换算法

根据闪存的独特物理特性,提出了子页感知的闪存页面置换算法.该算法引入了子页技术和基于相似概率的部分更新机制,既可以提高闪存存储系统的性能,又可计算每个内存页的置换值,并选择了置换值最小的内存页为牺牲页.实验结果表明,新算法在页面命中率、读/写操作次数、运行时间方面均具有优势.

基于两级LRU机制的大流检测算法

高速网络中及时准确地识别大流量对象对网络测量、控制和管理有重要的意义.该文提出了一种基于两级LRU机制的大流检测算法并分析了新算法中的参数与平均误差之间的关系.新算法通过增加一级用于过滤小流的LRU提高测量准确性.算法分析表明:新算法具有10Gbps的线速处理能力.该文基于实际互联网数据进行了实验对比,结果显示:与现有算法相比,新算法具有更高的测量准确性和实用性.

一种新的基于LRU的大流检测算法

针对LRU(Least Recently Used)算法大流漏检率过高的问题,提出了一种采用CBF(Counting Bloom Filter)和LRU两级结构的大流检测算法。该算法根据大流占用带宽较大、持续时间较长的特点在CBF中引入时间窗口机制来滤出可能的大流,然后将流信息记录在LRU中作进一步筛选。从理论上分析了影响该算法性能的因素,考虑了在存储资源一定的条件下,如何设置参数以发挥该算法最大效能的问题。最后基于实际的互联网数据进行了对比验证。结果表明,与同类算法相比,该算法在有效降低大流漏检率的同时,提高了大流流量的测量精度。

改进的CHOKe公平性主动队列管理算法

针对主动队列管理算法中的CHOKe算法对非响应流的惩罚力度不够、精确度不高的问题,提出一种新的惩罚非响应流算法———LRU-CHOKe。该算法以最近最少使用(LRU)击中取代CHOKe击中,提高CHOKe击中的有效性;利用路由器队列击中,自适应丢包,并结合新的丢包策略来加强对非响应流的惩罚,从而提高网络带宽公平性。仿真结果表明,LRU-CHOKe相比CHOKe和HCHOKe算法能更加有效地惩罚非响应流,实现更为公平的带宽分配。

一种自适应cache替换策略的研究与设计

由于I/O工作流多样性,单纯的LRU或LFU类型的算法都无法提高缓冲区的效率。自适应双栈LRU(下文简称AD-LRU)替换算法很好的解决了上面的问题,其中LRS存放低recency的页面,HRS存放高recency且高频率的页面,利用它们的效率来调整它们的大小。实验证明,有效的提高了缓冲区的命中率。

基于PIN LRU算法的路网最短路径研究

在陕西省交通地理信息系统数据存储与导航的实际应用中,由于路网数据量庞大,直接利用最短路径算法计算会出现内存溢出,导致无法完成计算。针对此问题,本文提出利用R Tree与最近最少使用(Least Recently Used,LRU)算法缓存优化管理相结合的锁定最近最少使用(Pin Least Recently Used,PIN LRU)算法对实际路网进行最短路径计算。与LRU、基于四叉树的空间数据缓存策略模型(Spatial Least Recently Frequently Used,SLRFU)算法相比,该算法在10个途经点路径检索时的耗时为5000 ms,SLRFU算法耗时为30000 ms,LRU算法耗时为75000 ms。试验测试证明,该算法检索响应高效,可解决计算实际数据过程中因内存溢出而导致系统崩溃的问题。

个性化服务用户模型研究

以数字图书馆为研究对象,提出了一种个性化服务用户模型构架,并对实现过程中的几个关键问题,包括用户模型表示方法、用户模型的建立以及更新算法进行了详细论述,最后在个性化文本过滤算法基础上,得到在实际的数字图书馆中的验证结果。用户兴趣的提取采用支持向量机分类算法和无监督聚类算法相结合的隐式方式获得;在考虑最近到达的兴趣与用户原有兴趣序列的综合影响的基础上,用户兴趣的更新采用最近最少使用淘汰算法。实验结果表明,该模型具有隐式获取用户兴趣、用户模型更新命中率高等特点。

基于内容的代理服务器高速缓冲器研究

该文提出了一种新的加强代理服务器CACHE的技术。首先给出CHACE内容的标题层、逻辑层、物理层的三层模型。对其内容进行索引,以便比较、查询。并给出了考虑文件存储空间、访问时间的LRU算法,保证CACHE中内容总是最相关、使用率高的内容。提高了具有相同目的用户的访问效率。

基于LRU和扩展CBF的网络大流检测

高速网络流量检测中的大流检测已成为当前一种重要的、高效准确的可扩展流量测量机制,针对CBF(Count Bloom Filter)容易溢出的问题,将扩展的CBF应用于流量测量,防止过滤器溢出,并且结合LRU链表存储机制,共同应用于网络大流检测之中。经理论分析,所研究的流量测量算法LRU_MCBF(Least Recently Used_Multiple Count Bloom Filter)占用空间小,时间复杂度低;通过仿真实验验证了LRU_MCBF在大流测量中漏报率和错报率较低,能实现高速网络环境下大流对象的准确提取。

一种有效的混合式P2P Web缓存系统HCache

针对当前P2P Web缓存系统中副本过多的问题,提出了一种有效的混合式P2P Web缓存系统:HCache。HCache根据用户对网页的访问特点及网页的优先级,对网页进行有选择的缓存,进而减少P2P Web缓存系统中的副本个数。根据Web对象当前的流行度,对LRU替换策略进行了改进(ELRU),提高了P2P Web缓存的命中率。在日志驱动的模拟实验表明,HCache缓存系统提高了Web缓存的命中率和性能。

基于LRU的隐通道监测

在多级安全系统中,隐通道能够使通信双方以违反安全策略的方式传递信息,带来不必要的安全隐患,而现有的标识和消除隐通道的方法对系统性能影响较大。深入研究隐通道的带宽特征,当不同安全级主体使用隐通道进行通信时,针对主体对共享资源属性操作频度的不同,提出了一种基于LRU(least recently used)的隐通道监测方法。该方法无需标识共享资源属性,只针对使用隐通道的主体进行处理,从空间和时间上都较大地改善了监测隐通道所带来的性能损失。

基于IOS的虚拟家居漫游系统的设计与实现

通过立方体全景图和视频的无缝拼接技术实现了基于IOS端的三维虚拟家居漫游系统.当服务器在网络数据请求次数比较多时,CDN网络技术将访问中心服务器的请求分配给最近或者最合理的边缘服务器,大幅降低用户的等待时间,有效地避免中心服务器访问拥堵问题.并且Web服务端通过HLS协议将整个视频流数据切成许多小的TS文件,向客户端提供接近实时的视频流服务.同时为了减少对服务器的访问次数,系统运用2种最近最少使用算法策略实现资源的本地缓存.最后采用苹果公司开发的GCD多线程编程方法同时进行房间全景图的渲染准备工作和房间过渡视频的下载.实验结果表明,当网络速度较慢时,客户端能较快地获取资源;系统运行效率较高,主线程不会出现阻塞的情况;房间场景过渡较自然,视觉感受比较流畅.

聚类的逻辑文件复制服务机制研究

网格环境下资源的管理和调度是一个非常复杂且具有挑战性的问题。在数据密集型应用中,数据文件的读取延迟时间是至关重要的。提出了一种基于聚类预处理的数据文件复制算法(CBR),将传输带宽满足一定条件的网格结点通过聚类方法构成一个"逻辑区域";并介绍了一种改进的LRU算法,考虑了其他计算任务需要的数据文件请求,避免删除未来将使用的数据文件。通过实验证明,该算法得到的计算任务完成时间优于其他两种算法。

嵌入式GPU存储管理单元的设计与实现

针对嵌入式图形处理器(Graphics Processing Unit,GPU)中存储管理单元工作频率低以及转换后援缓冲区命中率低的问题,设计并实现了一种适用于嵌入式GPU的存储管理单元。存储管理单元采用两级页表匹配的方式,实现从虚拟地址空间到物理地址空间的映射。将存储管理单元中转换后援缓冲区设计为三级流水线结构,以提高存储管理单元的工作频率。使用改进的伪最近最少使用算法,以提高转换后援缓冲区的命中率。基于中芯国际0.13μm工艺库,使用DC(Design Compiler)工具对设计的存储管理单元进行综合,并在VU440开发板上进行系统级验证。结果表明,采用设计的存储管理单元的嵌入式GPU系统可以正常工作,所提设计的最高工作频率可达235 MHz,转换后援缓冲区的命中率有所提高。与相关设计相比,所提设计的工作频率和转换后援缓冲区的命中率较高。

HFB:一种闪存上的块页混合缓存管理方法

闪存有多种优良特性,但是它却还具有较严重的缺点,这使得闪存的性能不高,成为了系统的性能瓶颈。该文提出了一种名为HFB(hybrid flash buffer)的高效闪存缓存管理方法。HFB方法提供页和块两种粒度的缓存管理策略,发挥两种不同粒度替换策略的优势,可以适应随机和顺序性的工作负载。HFB优先减少在闪存上较耗时的写操作,也减少了读和擦除操作。HFB采用八叉树组织缓存数据,实现了对数据的高效管理。该文对HFB进行了理论分析,并采用DiskSim模拟器和实际工作负载对其进行评测。理论分析和实验结果表明:HFB的加权缓存命中率高于其他典型的闪存缓存管理方法。