The week's pick
Random Articles
Reseach Article
Recency and Prior Probability (RPP) based Page Replacement Policy to Cope with Weak Locality Workloads having Probabilistic Pattern
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 59 - Number 15 |
| Year of Publication: 2012 |
| Authors: Bhatta Jagdish, Saud Arjun Singh |
10.5120/9623-4269
|
Bhatta Jagdish, Saud Arjun Singh . Recency and Prior Probability (RPP) based Page Replacement Policy to Cope with Weak Locality Workloads having Probabilistic Pattern. International Journal of Computer Applications. 59, 15 ( December 2012), 16-21. DOI=10.5120/9623-4269
Abstract
Development of efficient block replacement policy is the topic of much research in operating system as well as database management systems. Among variety of page replacement algorithms Least Recently Used (LRU) algorithm is simple, flexible and has low overhead. LRU replaces page that is not accessed for longest time. But LRU makes bold assumption on recency factor only, which made LRU misbehave with weak locality workloads. This paper proposes a new Recency and Prior Probability (RPP) based page replacement policy for block replacement. The RPP combines recency and prior probability associated with the pages while selecting the victim frame from memory. If a page, to be used, has probability n times higher than another page, the page will get log(n) more chances to stay in the memory than lower probability pages. Hence with RPP, it is possible to prevent pages having higher probability of use from being replaced
References
- P. Cao, E. W. Felten, and K. Li, "Application-controlled File Caching Policies", Proc. USENIX Summer 1994 Technical Conf. , pp. 171-182, June 1994.
- R. Karedla, J. S. Love, and B. G. Wherry. Caching strategies to improve disk performance. IEEE Computere, 27(3):38 46, March 1994.
- T. Johnson and D. Shasha, "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm," Proc. 20th Int'l Conf. Very Large Data Bases, pp. 439-450, Sept. 1994.
- E. J. O'Neil, P. E. O'Neil, and G. Weikum, "The LRU-K Page Replacement Algorithm for Database Disk Buffering", Proc. 1993 ACM SIGMOD Int'l Conf. Management of Data, pp. 297-306, May 1993.
- J. T. Robinson and N. V. Devarakonda, "Data Cache Management Using Frequency-Based Replacement," Proc. 1990 ACM SIGMETRICS Conf. Measuring and Modeling of Computer Systems, pp. 134-142, May 1990.
- Song Jiang and Xiaodong Zhang, Making LRU Friendly to Weak Locality Workloads: A Novel Replacement Algorithm to Improve Buffer Cache Performance, IEEE Transactions on Computers, Vol. 54, and No. 8, August 2005, pp 939-952.
- D. Lee, J. Kim, S. Noh, S. Min, Y. Cho, and C. Kim, "On the Existence of a Spectrum of Policies that Subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU) Policies", Proc. 1999 ACM SIGMETRICS Conf. Measuring and Modeling of Computer Systems, pp. 134-143, May 1999.
- Kirby McMaster, Samuel Sambasivam, Nicole Anderson 2010, A case study of Belady's anomaly and binomial distribution, Proceedings of Informing Science & IT Education Conference (InSITE)
- Glass, G. and Cao, P. 1997. Adaptive Page Replacement Based on Memory Reference Behavior, In Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS'97), pp 115-126.
- Smaragdakis, Kaplan, S. , and Wilson, P. 1999. EELRU: Simple and Effective Adaptive Page Replacement, In Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS'99), Atlanta, pp 122-133.
- Gyan Prakash Joshi, 2007, Calculation Of Control Parameter?? That Results Into Optimal Performance In Terms Of Page Fault Rate In The Algorithm Least Recently Frequently Used(LRFU) For Page Replacement, Master's Thesis, Tribhuvan University, Central Department of Computer Science and Information Technology.
- Corbató, F. J. 1968. A paging experiment with the Multics system. In Honor of P. M. Morse, pp 217–228, MIT Press, 1969. Also as MIT Project MAC Report MAC-M-384.
- Jiang, S. , Chen, F. , Zhang, X. 2005. CLOCK-Pro: An effective improvement of the CLOCK replacement. In Proceedings of the 10th Annual USENIX Technical
- Bansal, S. and Modha, D. S. 2004. CAR: Clock with Adaptive Replacement, In Proceedings of the USENIX Conference on File and Storage Technologies (FAST'04), San Francisco, pp 187-200
- Megiddo, N. and Modha, D. S. 2003. ARC: A Self-Tuning, Low Overhead Replacement Cache, In Proceedings of the USENIX Conference on File and Storage Technologies (FAST'03), San Francisco, pp 115-130.
- BP-Wrapper: A System Framework Making Any Replacement Algorithms (Almost) Lock Contention Free Xiaoning Ding, Song Jiang, Xiaodong Zhang, pp 370.
- Choi, J. et al. 1999. An Implementation Study of a Detection-Based Adaptive Block Replacement Scheme, USENIX Annual Technical Conference, 239-252.
- Choi, J. et al. 2000. Towards application/file-level characterization of block references: a case for fine-grained buffer management. In: Proceeding ot the 25th International Conference on Measurement and Modeling of Computer Systems, Santa Clara, CA. (SIGMETRICS'00), pp 286-295.
- Sabeghil, M. and Yaghmaee, M. H. 2006. Using fuzzy logic to improve cache replacement decisions. IJCSNS International Journal of Computer Science and Network.
- Kim, J. M. et al. 2000. A low-overhead high-performance unified buffer management scheme that exploit sequential and looping references. In Symposium on Operating System Design and Implementation, San Diego. OSDI' 2000 USENIX, pp 119-134.
- Bagchi, S. , Nygaard, M. 2004. A Fuzzy Adaptive Algorithm for Fine Grained Cache Paging. 8th International Workshop (SCOPES'04), Netherlands, pp 200-213.
Index Terms
Keywords