Hong-Bin Tsai
ABSTRACT
Page replacement algorithm is one of the core components in modern operating systems. It decides which victim page to evict from main memory by analyzing attributes of pages referenced. The evicted page is then moved to backing store in the memory hierarchy, and moved back to main memory once referenced again. The technique that utilizes storage as part of memory is called swapping. However, there is a non-trivial performance gap between memory and storage. For example, performance of permanent storage like Solid-State Disk (SSD) is much slower, e.g. 104 longer write latency, than DRAM [9]. As a result, swapping between main memory and storage causes system performance to a discernible drop. Nevertheless, a higher hit ratio of page replacement algorithm implies less I/O waits to storage, and consequently a better performance overall.
In this paper we propose a log-based page replacement algorithm that assumes better hints for page replacement can be approached through analysis of page reference history. The algorithm selects victim page that holds lowest reference rate in a window-sized log. A simulation shows that our method outperforms conventional page replacement algorithms by 11+ at best.
- pmem.io, Persistent Memory Programming, http://pmem.io/.Google Scholar
- Stress-ng. http://kernel.ubuntu.com/~cking/stress-ng/.Google Scholar
- M. D. Assunção, R. N. Calheiros, S. Bianchi, M. A. Netto, and R. Buyya. Big Data computing and clouds: Trends and future directions. Journal of Parallel and Distributed Computing, 79--80:3--15, 2015. Special Issue on Scalable Systems for Big Data Management and Analytics. Google ScholarDigital Library
- L. A. Bélády. A Study of Replacement Algorithms for a Virtual-storage Computer. IBM Syst. J., 5(2):78--101, June 1966. Google ScholarDigital Library
- C. P. Chen and C.-Y. Zhang. Data-intensive applications, challenges, techniques and technologies: A survey on Big Data. Information Sciences, 275:314 -- 347, 2014. Google ScholarCross Ref
- Chen, Kaimeng and Jin, Peiquan and Yue, Lihua. A Novel Page Replacement Algorithm for the Hybrid Memory Architecture Involving PCM and DRAM. In Network and Parallel Computing: 11th IFIP WG 10.3 International Conference, NPC 2014, Ilan, Taiwan, September 18--20, 2014. Proceedings, pages 108--119, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. Google ScholarCross Ref
- S. R. Dulloor, S. Kumar, A. Keshavamurthy, P. Lantz, D. Reddy, R. Sankaran, and J. Jackson. System Software for Persistent Memory. In Proceedings of the Ninth European Conference on Computer Systems, EuroSys '14, pages 15:1--15:15, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- M. Z. Farooqui, M. Shoaib, and M. Z. Khan. A Comprehensive Survey of Page Replacement Algorithms. IJARCET), January, 2014.Google Scholar
- S. Mittal and J. S. Vetter. A Survey of Software Techniques for Using Non-Volatile Memories for Storage and Main Memory Systems. IEEE Transactions on Parallel and Distributed Systems, 27(5):1537--1550, May 2016. Google ScholarDigital Library
- O. Mutlu. Memory scaling: A systems architecture perspective. In 2013 5th IEEE International Memory Workshop, pages 21--25, May 2013. Google ScholarCross Ref
- E. J. O'Neil, P. E. O'Neil, and G. Weikum. The LRU-K Page Replacement Algorithm for Database Disk Buffering. SIGMOD Rec., 22(2):297--306, June 1993. Google ScholarDigital Library
- Y. Park and H. Bahn. Efficient Management of PCM-based Swap Systems with a Small Page Size. 15:476--484, 2015.Google Scholar
- Y.-S. Yoo, H. Lee, Y. Ryu, and H. Bahn. Page Replacement Algorithms for NAND Flash Memory Storages. In Proceedings of the 2007 International Conference on Computational Science and Its Applications - Volume Part I, ICCSA'07, pages 201--212, Berlin, Heidelberg, 2007. Springer-Verlag. Google ScholarDigital Library
Index Terms
- A page replacement algorithm based on frequency derived from reference history
Recommendations
Time-shift replacement algorithm for main memory performance optimization
Page replacement algorithms of main memory in modern operating systems are crucial in system performance. When memory is full, a page replacement algorithm exploits temporal locality and frequency of page references to evict the page that is least ...
Improving of cache memory performance based on a fuzzy clustering based page replacement algorithm by using four features
Internet is one of the most influential new communication technologies has influenced all aspects of human life. Extensive use of the Internet and the rapid growth of network services have increased network traffic and ultimately a slowdown in internet ...
High performance cache replacement using re-reference interval prediction (RRIP)
ISCA '10Practical cache replacement policies attempt to emulate optimal replacement by predicting the re-reference interval of a cache block. The commonly used LRU replacement policy always predicts a near-immediate re-reference interval on cache hits and ...
Comments