In a computer architecture Cache memory have been introduced to balance performance and cost of the system. To improve the performance of a cache memory in terms of hit ratio and good response time system needs to employ efficient cache replacement policy. Unified Buffer cache management, Program Counter-based Classification, Detection based Adaptive Replacement, Robust Adaptive buffer Cache management scheme and Block Pattern Based Buffer Cache Management are some of the existing policies. But they have some disadvantages like they were not able to exploit both recency and frequency information, some of them could not exploit all type of reference regularities, some of them have high memory overhead. So we require more advanced policies to improve the performance. In this work we are proposing the block access pattern based replacement policy which predicts future request of a block based on history of response time for respective data block. Block access pattern based replacement policy leads to effective improvement in buffer cache hit ratio and reduced response time.

Buffer Cache, Access Patterns, Cache Replacement Policies, Buffer Cache Management Techniques

[1] Hou Fang, zhao Yue-long, Hou fang, �A cache management algorithm based on page miss cost�, in proceedings of International conference on Information Engineering and computer science, ICIECS, ISBN: 978-1-4244-4994-1 pp. 1-4, 2009.
[2] Prof.P. K. Biswas, "Lecture series on digital computer organization," Internet: http://nptel.iitm.ac.in, Sep 2009.
[3] M. J. Bach, �Operating system the design of the UNIX�, Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1986.
[4] A. S. Tanenbaum, A. S.Woodhull, �Operating systems design and implementation�, Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1987.
[5] Donghee Lee, et.al.,.�On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies�,SIGMETRICS�99 Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems, pages 134-143, NY, USA, 1999.
[6]E. J. O�Neil, P. E. O�Neil, and G. Weikum., �The LRU-K Page Replacement Algorithm for Database Disk Buffering� , ACM Conference on SIGMOD, pg. no. 297�306, 1993.
[7] K. So and R. N. Rechtschaffen, �Cache operations by MRU change.� IEEE Trans. Computers, vol. 37, no. 6, pp. 700�709, 1988.
[8] L. A. Belady, �A study of replacement algorithms for a virtual-storage computer,� IBM Syst. J., vol. 5, no. 2, pp. 78-101, 1966.
[9] Alfred V. Aho, Jeffrey D. Ullman, et.al., �Principles of Optimal Page Replacement�, Journal of ACM, Vol 18, Issue 1, Pages 80-93,Jan 1971.
[10] R. Turner and H. Levy, �Segmented FIFO Page Replacement�, In Proceedings of SIGMETRICS ,1981.
[11] A. Dan and D. Towsley, �An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes�, in Proceedings of ACM SIGMETRICS, Boulder, Colorado, United States, pp. 143�152,1990.
[12] Y. Smaragdakis, S. Kaplan, and P. Wilson, �EELRU: simple and effective adaptive page replacement,� in Proceedings of ACM SIGMETRICS international conference on Measurement and modeling of computer systems, New York, USA, pg. no. 122�133, 1999.
[13] T. Johnson and D. Shasha, �2Q : A Low Overhead High Performance Buffer Management Replacement Algorithm� , In Proceedings of the 20th International Conference on VLDB, pg. no. 439�450, 1994.
[14] D. Lee, J. Choi, J. Kim, S. Noh, S. Min, Y. Cho, and C. Kim, �LRFU: A Spectrum of Policies that Subsumes the LRU and LFU Policies�, IEEE Transactions on Computers, vol. 50, Issue no. 12, pp.1352-1361, Dec. 2001
[15] N. Megiddo and D. S. Modha, �ARC: A self-tuning, low overhead replacement cache,� in Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST), pg no. 115�130, Mar 2003.
[16] S. Jiang and X. Zhang, �LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance,� in Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pg. no. 31�42, June 2002.
[17] Seon-yeong Park, et.al., �CFLRU: A Replacement Algorithm for Flash Memory�, CASES`06, October 23�25, Seoul, Korea ,2006.
[18] LI Zhan-sheng, et.al.,�CRFP: A Novel Adaptive Replacement Policy Combined the LRU and LFU�, IEEE 8th International Conference on Computer and Information Technology Workshops, 2008.
[19] Andhi Janapsatya, Aleksandar Ignjatovi�c, et.al., �Dueling CLOCK: Adaptive Cache Replacement Policy Based on The CLOCK Algorithm�, 2010.
[20] T. Puzak, et.al,�Analysis of cache replacement algorithms,� Ph.D. dissertation, Dep. Elec. Comput. Eng., Univ. Massachusetts, Feb.1985.
[21] F. Zhou, R. von Behren, and E. Brewer, �AMP: Program context specific buffer caching,� in Proceedings of the USENIX Technical Conference, Apr. 2005
[22] C. Gniady, A. R. Butt, and Y. C. Hu, �Program-counter based pattern classification in buffer caching�, in Proceedings of 6th Symposium on Operating System Design and Implementation ,pg. no. 395�408, Dec. 2004.
[23] J. M. Kim, J. Choi, J. Kim, S. H. Noh, S. L.Min, Y. Cho, and C. S. Kim,�A low-overhead, high-performance unified buffer management scheme that exploits sequential and looping references,� in 4th Symposium on Operating System Design and Implementation ,pg. no. 119�134, Oct. 2000.
[24] Jongmoo Choiy, Sam H. Nohz, Sang LyulMiny, Yookun Cho, �An Adaptive Block Management Scheme Using On-Line Detection of Block Reference Patterns�, International Workshop on Multi-Media Database Management Systems, Proceedings , pg no. 172 � 179, Dayton, Aug 1998.
[25] Yifeng Zhu, Hong Jiang,�RACE: A Robust Adaptive Caching Strategy for Buffer Cache�, IEEE Transaction on computers, 2007.
[26] Urmila Shrawankar, Reetu Gupta, �Block Pattern Based Buffer Cache Management�, The 8th International Conference on Computer Science and Education, April 26-28, Colombo, 2013.
[27] Reetu Gupta, Urmila Shrawankar, �Managing Buffer Cache by Block Access Pattern�, IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 6, November 2012.
[28] P. Cao, et.al., �Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling,� ACM Transactions on Computer Systems, vol. 14, Issue 4, pp. 311�343, 1996.
[29] R. H. Patterson, G. A. Gibson, E. Ginting, D. Stodolsky, and J. Zelenka, �Informed prefetching and caching,� in Proceedings of the fifteenth ACM symposium on Operating systems principles (SOSP), New York, USA: ACM Press, 1995.
[30] A. Jaleel, C. Jean, S. C. Steely, �ShiP: Signature Based Hit Predictor for High Performance Caching�, ACM International symposium on Computer Architectur, pg 430-431, 2011.
[31] Zhiyang Ding,et.al., �An Automatic Prefetching and Caching System�, IEEE, 2010.
[32] Heung Seok Jeon, �Practical Buffer Cache Management Scheme based on Simple Prefetching�, IEEE Transactions on Consumer Electronics, Volume.- 52, Issue - 3, August 2006.
[33] G. Keramidas, P. Petoumenou, S. kaxiras, �Cache Replacement Based on Reuse Distance Prediction�, Computer Design IEEE International Conference, page no- 245-250, Oct 2007.
[34] G. Keramidas, P. Petoumenou, S. kaxiras, � Instruction Based Reuse Distance Prediction for Efficient Cache Management�, Pet International Symposium on System, Architecture, Modeling and Simulations, page no. 48-49, July 2009.