对页面访问序列影响LRU页面置换算法的研究

页面置换算法是操作系统中虚拟存储管理的一个重要部分。改进页面置换算法，可以降低页面失败率，从而有效地提高系统性能。现有的应用于虚拟存储管理的页面置换算法主要是Least Reference Used（LRU）页面换算法。文中利用页面访问间隔数，分析不同的页面访问序列对LRU算法的影响，把页面访问序列分为LRU-友好页面访问序列、LRU-不友好页面访问序列、不友好页面访问序列三类，为改进LRU页面置换算法提供了依据。     

一种改进的自适应页面置换算法

研究缓冲区页面置换策略和算法(特别是自适应页面置换策略和算法),提出一种基于双管理链的自适应页面置换算法HA。HA算法是对DMC(2c)算法的改进,它引入动态置换点,同时,根据缺页失败数确定算法的工作链,并根据页面访问序列的局部特征选择效率较高的页面置换策略。实验结果表明,HA算法能有效地减少缺页失败数,降低缺页率,特别是在处理第三种模式的页面访问序列时,该算法的缺页率较改进前的算法可降低近30%。     

一种结合预调方式的页面置换算法

内存是一种非常重要的资源,在现代操作系统中,对内存的管理都引入了虚拟存储技术,而分页系统是实现虚拟存储技术的主要方法。因页面置换算法对操作系统的性能起着重要的作用,因此如何置换页面就显得尤为重要,很多算法因需要特别硬件的支撑而应用得不太广泛。分析了几种应用比较广的页面置换算法存在的问题,提出了一种结合预调方式的页面置换算法,该算法从理论上可以降低缺页率并提高命中率。     

对传统页面置换算法的分析与研究

随着虚拟存储技术在操作系统中的应用,大大提高了操作系统的性能,其中页面置换算法是虚拟存储管理的重要组成部分,页面置换算法的优劣将直接影响系统的整体性能。随着大量有着不同读写速度的外存设备共存于系统中,单一置换算法同样影响着系统的整体性能。     

基于探测的自适应页面置换算法研究

页面置换算法是虚拟存储管理的重要组成部分,页面置换算法的优劣将直接影响系统的整体性能。本文在分析传统页面置换算法存在不足的基础上,介绍一种能够弥补传统页面置换算法存在不足的基于探测的自适应页面置换算法,同时分忻了该算法的性能,并且指出了进一步的研究方向。     

LRU页面置换算法的改进与实现

为简化嵌入式虚拟内存的实现,改善嵌入式虚拟内存的性能,在对常见页面置换算法进行对比分析的基础上,提出一种改进的最久未使用页面置换算法。该算法基于内存管理单元、跨页访问计数器、访问次序寄存器、溢出中断处理等软硬件相结合的技术。实验结果表明,该算法能提高嵌入式系统的页面置换效率,提升系统的整体性能,可广泛应用于各种物联网系统和嵌入式系统。     

LRU算法的研究及实现

本文主要介绍页面置换算法中的LRU算法(leastrecentlyused),并将LRU算法与另外一些常用页面置换算法进行了比较。同时探讨了LRU算法的实现问题。     

一种对LRFU置换策略的自适应改进

数据库缓冲区页面置换算法对磁盘数据库的性能有着重要的影响,页面置换算法主要有基于访问时间的置换策略、基于访问次数的置换策略、两者结合的置换策略等。LRFU算法是一系列结合LRU和LFU置换策略的置换算法,很好地实现了两种置换策略的结合,但却没有给出一种在不同的应用场景中进行动态调整的机制。提出了一种对LRFU算法进行动态调整的方法,模拟测试发现改进的LRFU算法都不同程度地提高了缓冲区命中率。     

面向Flash存储的页面置换算法综述

Flash存储设备与传统针对磁盘构成的存储系统设计不同,具有许多新的特征,如读、写以及删除操作的I/O开销并不对称,因此要对Flash存储的页面置换算法进行重新设计。面向Flash存储的普适页面置换算法以及专门性的页面置换算法是当前算法的两大类型。普适性的页面置换算法可以减少二级存储设备中的写回操作,具有较高的性能。以Flash系统为基础所提出的专门性页面置换算法,考虑了Flash存储的特性,同时也针对特定的应用信息进行设计,最大限度提高了存储设备的性能,为类似Flash存储的页面置换算法的研究提供了参考的经验。     

基于属性重要性的WUM数据预处理方式

为了降低Web日志数据的规模,并能从预处理后的数据中发现更有价值的访问模式,在引入知识的信息量的基础上,给出了单个属性相对于属性集的重要性量化值的概念,并采用了操作系统中LRU页面置换算法的思想,提出了基于属性重要性的WUM数据预处理方式。实验证明：该方式可以删除不具有挖掘价值的、因用户短期行为而访问的Web日志记录,剔除掉噪音数据,从而有效减小了日志挖掘的复杂度。     

Exploiting the least recently used page replacement algorithm

Many implementations of paged virtual memory systems employ demand fetching with least recently used (LRU) replacement. The stack characteristic of LRU replacement implies that a reference string which repeatedly accesses a number of pages in sequence will cause a page fault for each successive page referenced when the number of pages is greater than the number of page frames allocated to the program's LRU stack. In certain circumstances when the individual operations being performed on the referenced string are independent, or more precisely are commutative, the order of alternate page reference sequences can be reversed. This paper considers sequences which cannot be reversed and shows how placement of information on pages can achieve a similar effect if at least half the pages can be held in the LRU stack.     

Token-ordered LRU: an effective page replacement policy and its implementation in Linux systems

Most computer systems use a global page replacement policy based on the LRU principle to approximately select a Least Recently Used page for a replacement in the entire user memory space. During execution interactions, a memory page can be marked as LRU even when its program is conducting page faults. We define the LRU pages under such a condition as false LRU pages because these LRU pages are not produced by program memory reference delays, which is inconsistent with the LRU principle. False LRU pages can significantly increase page faults, even cause system thrashing. This poses a more serious risk in a large parallel systems with distributed memories because of the existence of coordination among processes running on individual node. In the case, the process thrashing in a single node or a small number of nodes could severely affect other nodes running coordinating processes, even crash the whole system. In this paper, we focus on how to improve the page replacement algorithm running on one node.

After a careful study on characterizing the memory usage and the thrashing behaviors in the multi-programming system using LRU replacement. we propose an LRU replacement alternative, called token-ordered LRU, to eliminate or reduce the unnecessary page faults by effectively ordering and scheduling memory space allocations. Compared with traditional thrashing protection mechanisms such as load control, our policy allows more processes to keep running to support synchronous distributed process computing. We have implemented the token-ordered LRU algorithm in a Linux kernel to show its effectiveness.     

Page replacement algorithm for large-array manipulation

The Least Recently Used (LRU) method is the technique that is most often used for a page replacement algorithm. However, LRU may not be an effective method for some large-array manipulation. A method for solving this problem is presented in this paper. In this method, the Operating System (OS) automatically detects loops that are not suitable for the LRU method. There is no necessity to modify application programs nor any additional overhead as long as sufficient real memory is provided. Therefore this method is most suitable for practical use. It functions on the basis of information about the relationship between the working set size and the window size, and indication of whether the detected page fault is caused by an instruction fetch or an operand fetch, etc. The results of experiments and improvements are also shown.     

CC-NUMA系统中面向页迁移的反向页表技术

页迁移技术是实现CC-NUMA访存局部性优化的一种重要策略,其实现涉及到虚存系统中物理地址到虚拟地址的转换,传统做法需要遍历所有进程的虚拟地址空间,效率低、开销大.针对此问题,介绍了一种在操作系统内核中高效实现物理地址到虚拟地址转换的技术-一反向页表技术,并着重阐述了反向页表在页迁移策略中的应用.     

基于内存池的应用程序级页面置换算法

计算机处理海量数据时,内外存数据的交换是影响系统效率的关键因素之一。本文在分析系统级页面置换算法不足的基础上,提出应用程序级页面置换的概念,同时详细介绍其在Windows操作系统下的实现,并在人脸识别系统中对算法进行验证,结果表明本算法执行效率优于原始算法。     

基于Objrmap的区分实时进程页的页面置换算法

本文深入分析了Linux 2.6的新技术--基于对象的逆向映射Objrmap的基本原理,探讨了区分实时进程页的置换策略的可能性,并提出了基于区分实时进程页的页面置换算法,增 强了Linux系统的实时性。改进的算法具有优异的时空性能,同时不影响系统的高并发度和进程间的内存共享。实验表明,改进算法在重载条件下,实时进程的缺页次数明显少于 原算法。     

Ubase数据库系统缓冲管理器的实现

缓冲区技术是减少系统对外存访问的重要方法之一。文章分析了Ubase数据库系统缓冲管理器的基本功能,对常用页面替换算法的性能进行了比较,最终选择Love/Hate算法代替LRU算法实现了Ubase数据库系统的缓冲管理,降低了系统的开销,提高了Ubase数据库系统的性能。     

Huge Page Friendly Virtualized Memory Management

With the rapid increase of memory consumption by applications running on cloud data centers,we need more efficient memory management in a virtualized environment.Exploiting huge pages becomes more critical for a virtual machine's performance when it runs large working set size programs.Programs with large working set sizes are more sensitive to memory allocation,which requires us to quickly adjust the virtual machine's memory to accommodate memory phase changes.It would be much more efficient if we could adjust virtual machines'memory at the granularity of huge pages.However,existing virtual machine memory reallocation techniques,such as ballooning,do not support huge pages.In addition,in order to drive effective memory reallocation,we need to predict the actual memory demand of a virtual machine.We find that traditional memory demand estimation methods designed for regular pages cannot be simply ported to a system adopting huge pages.How to adjust the memory of virtual machines timely and effectively according to the periodic change of memory demand is another challenge we face.This paper proposes a dynamic huge page based memory balancing system(HPMBS)for efficient memory management in a virtualized environment.We first rebuild the ballooning mechanism in order to dispatch memory in the granularity of huge pages.We then design and implement a huge page working set size estimation mechanism which can accurately estimate a virtual machine's memory demand in huge pages environments.Combining these two mechanisms,we finally use an algorithm based on dynamic programming to achieve dynamic memory balancing.Experiments show that our system saves memory and improves overall system performance with low overhead.     

一个基于IA-64体系的内存管理大页面的实现模型

本文提出了一种基于IA-64体系结构的内存页面大页面化的模型，可执行文件ELF的Data Segment使用大页面。由于转换解析缓冲区（TLB）能映射更大的虚拟内存范围，从而可减小未命中率，因此可以提高使用大页面的高性能计算（HPC）应用程序或使用大量虚拟内存的任何内存访问密集型应用程序系统性能。