Priority Cache Object Replacement by Using LRU, LFU and FIFO algorithms to Improve Cache Memory Hit Ratio

Authors

  • Akbari Bengar Akbari Bengar * Department of Computer Engineering, Savadkooh Branch, Islamic Azad University, Savadkooh, Iran.

https://doi.org/10.48314/tsc.v1i1.33

Abstract

Due to the increasing performance between CPU and cache memory, the use of replacement algorithms is very important in various aspects of high-performance computing environments such as e-commerce systems, cache memory management in microprocessors, object management in operating systems, and iteration strategies in information distribution systems and etc. Database server cache performance is an important issue in e-commerce systems. Managing the entry and exit of cache objects with replacement algorithms can reduce the workload of the database server and improve server performance. The algorithms determine which objects remain in the cache memory and which ones go out to make room for new objects. In this way, the algorithms not only decrease user access time, but also enhance the performance of the system. Most of these algorithms are developed by the famous LRU and LFU schemes and can fix their flaws; but unlike them, they are difficult to implement. This research proposes a priority object replacement algorithm that is easy to implement. The algorithm, called  Priority Cache Object Replacement Algorithm (PCORA), is based on prioritizing cache memory objects according to three parameters. Experiments show that the proposed algorithm has a better hit ratio than other algorithms and can effectively improve cache memory performance.

Keywords:

Operating systems, Cache memory management, e-commerce systems, Replacement algorithms, Hit ratio, Performance

References

  1. [1] Kushwah, J. S., & Tamrakar, S. (2017). An extensive review of webs caching techniques to reduce cache pollution. Imperial journal of interdisciplinary research, 6(13), 111–118. https://rntujournals.aisect.org/assets/upload_files/articles/3b39342f735878fb7ee90c670784dc89.pdf
  2. [2] Wang, Y., Yang, Y., Han, C., Ye, L., Ke, Y., & Wang, Q. (2019). LR-LRU: A PACS-oriented intelligent cache replacement policy. IEEE access, 7, 58073–58084. https://doi.org/10.1109/ACCESS.2019.2913961
  3. [3] Wang, Y. L., Kim, K. T., Lee, B., & Youn, H. Y. (2018). A novel buffer management scheme based on particle swarm optimization for SSD. The journal of supercomputing, 74(1), 141–159. https://doi.org/10.1007/s11227-017-2119-2
  4. [4] Ooka, A., Eum, S., Ata, S., & Murata, M. (2018). Compact CAR: Low-overhead cache replacement policy for an ICN router. IEICE transactions on communications, 101(6), 1366–1378. https://doi.org/10.1587/transcom.2017EBP3299
  5. [5] Tailor, P. M., & Morena, R. D. (2017). A survey of database buffer cache management approaches. International journal of advanced research in computer science, 8(3), 409–414. https://www.academia.edu/64178716/A_survey_of_database_buffer_cache_management_approaches
  6. [6] Negrão, A. P., Roque, C., Ferreira, P., & Veiga, L. (2015). An adaptive semantics-aware replacement algorithm for web caching. Journal of internet services and applications, 6(1), 4. https://doi.org/10.1186/s13174-015-0018-4
  7. [7] Yang, P., Wang, Q., Ye, H., & Zhang, Z. (2019). Partially shared cache and adaptive replacement algorithm for NoC-based many-core systems. Journal of systems architecture, 98, 424–433. https://doi.org/10.1016/j.sysarc.2019.05.002
  8. [8] Samiee, K. (2009). A Replacement algorithm based on weighting and ranking cache objects. International journal of hybrid information technology, 2(2), 93–104. https://B2n.ir/kk7780
  9. [9] Akbari Bengar, D., Ebrahimnejad, A., Motameni, H., & Golsorkhtabaramiri, M. (2020). A page replacement algorithm based on a fuzzy approach to improve cache memory performance. Soft computing, 24(2), 955–963. https://doi.org/10.1007/s00500-019-04624-w
  10. [10] Akbari-Bengar, D., Ebrahimnejad, A., Motameni, H., & Golsorkhtabaramiri, M. (2020). Improving of cache memory performance based on a fuzzy clustering based page replacement algorithm by using four features. Journal of intelligent & fuzzy systems, 39(5), 7899–7908. https://doi.org/10.3233/JIFS-201360
  11. [11] Arya, G. P., Prasad, D., & Rana, S. S. (2018). An improved page replacement algorithm using block retrieval of pages. International journal of engineering & technology, 7(4.5), 32–35. https://doi.org/10.14419/IJET.V7I4.5.20004
  12. [12] Wu, H., Luo, Y., & Li, C. (2021). Optimization of heat-based cache replacement in edge computing system. The journal of supercomputing, 77(3), 2268–2301. https://doi.org/10.1007/s11227-020-03356-1
  13. [13] Do, C. T., Choi, H. J., Kim, J. M., & Kim, C. H. (2015). A new cache replacement algorithm for last-level caches by exploiting tag-distance correlation of cache lines. Microprocessors and microsystems, 39(4–5), 286–295. http://dx.doi.org/10.1016/j.micpro.2015.05.005
  14. [14] Shin, D., Cho, K., & Bahn, H. (2020). File type and access pattern aware buffer cache management for rendering systems. Electronics, 9(1), 164. https://www.mdpi.com/2079-9292/9/1/164
  15. [15] Akbari, B. D., Jazayeri, R. H., & Berenjian, G. (2012). An improvement in WRP block replacement policy with reviewing and solving its problems. (In Persian). Advances in computer research. 3, 67–75. https://www.sid.ir/paper/328710
  16. [16] Anwar, U., Paik, J. Y., Jin, R., & Chung, T. S. (2017). Log-buffer aware cache replacement policy for flash storage devices. IEEE transactions on consumer electronics, 63(1), 77–84. https://doi.org/10.1109/TCE.2017.7931973
  17. [17] Jia, G., Han, G., Wang, H., & Wang, F. (2018). Cost aware cache replacement policy in shared last-level cache for hybrid memory based fog computing. Enterprise information systems, 12(4), 435–451. https://doi.org/10.1080/17517575.2017.1295321
  18. [18] Hajiakhondi-Meybodi, Z., Abouei, J., & Raouf, A. H. F. (2018). Cache replacement schemes based on adaptive time window for video on demand services in femtocell networks. IEEE transactions on mobile computing, 18(7), 1476–1487. https://doi.org/10.1109/TMC.2018.2864164
  19. [19] He, J., Jia, G., Han, G., Wang, H., & Yang, X. (2017). Locality-aware replacement algorithm in flash memory to optimize cloud computing for smart factory of industry 4.0. IEEE access, 5, 16252–16262. https://doi.org/10.1109/ACCESS.2017.2740327
  20. [20] Talaat, F. M., Ali, S. H., Saleh, A. I., & Ali, H. A. (2020). Effective cache replacement strategy (ECRS) for real-time fog computing environment. Cluster computing, 23(4), 3309–3333. https://doi.org/10.1007/s10586-020-03089-z
  21. [21] Jiang, L., & Zhang, X. (2020). Cache replacement strategy with limited service capacity in heterogeneous networks. IEEE access, 8, 25509–25520. https://doi.org/10.1109/ACCESS.2020.2970783
  22. [22] Sheu, J. P., & Chuo, Y. C. (2016). Wildcard rules caching and cache replacement algorithms in software-defined networking. IEEE transactions on network and service management, 13(1), 19–29. https://doi.org/10.1109/TNSM.2016.2530687
  23. [23] Kang, D. H., Han, S. J., Kim, Y. C., & Eom, Y. I. (2017). CLOCK-DNV: A write buffer algorithm for flash storage devices of consumer electronics. IEEE transactions on consumer electronics, 63(1), 85–91. https://doi.org/10.1109/TCE.2017.014700
  24. [24] Lee, M. C., Leu, F. Y., & Chen, Y. (2015). Pareto-based cache replacement for YouTube. World wide web, 18(6), 1523–1540. https://doi.org/10.1007/s11280-014-0318-9
  25. [25] Karami, A., & Guerrero-Zapata, M. (2015). An ANFIS-based cache replacement method for mitigating cache pollution attacks in Named Data Networking. Computer networks, 80, 51–65. https://doi.org/10.1016/j.comnet.2015.01.020
  26. [26] Kim, S., Hwang, S.-H., & Kwak, J. W. (2018). Adaptive-Classification CLOCK: Page replacement policy based on read/write access pattern for hybrid DRAM and PCM main memory. Microprocessors and microsystems, 57, 65–75. https://doi.org/10.1016/j.micpro.2018.01.003
  27. [27] Ma, T., Qu, J., Shen, W., Tian, Y., Al-Dhelaan, A., & Al-Rodhaan, M. (2018). Weighted greedy dual size frequency based caching replacement algorithm. IEEE access, 6, 7214–7223. https://doi.org/10.1109/ACCESS.2018.2790381
  28. [28] Monazzah, A. M. H., Farbeh, H., & Miremadi, S. G. (2016). LER: Least-error-rate replacement algorithm for emerging STT-RAM caches. IEEE transactions on device and materials reliability, 16(2), 220–226. https://doi.org/10.1109/TDMR.2016.2562021
  29. [29] Motwani, A., Swain, D., Motwani, N., Vijan, V., Awari, A., & Dash, B. (2020). Enhancing multi-level cache performance using dynamic r-f characteristics. Machine learning and information processing (pp. 277–286). Singapore: Springer Singapore. https://doi.org/10.1007/978-981-15-1884-3_26
  30. [30] Nomura, H. (2020). Experimental investigation of lazy evaluation method in replacement algorithm for long-term re-reference cache management. Bulletin of networking, computing, systems, and software, 9(1), 83–90. http://bncss.org/index.php/bncss/article/view/142
  31. [31] Olanrewaju, R. F., Azman, A. W., & Yaacob, M. (2016). Intelligent web proxy cache replacement algorithm based on adaptive weight ranking policy via dynamic aging. Indian journal of science and technology, 9(36), 1–7. https://doi.org/10.17485/ijst/2016/v9i36/102159
  32. [32] Paulson, H., & Ramachandran, D. R. (2017). Page replacement algorithms–challenges and trends. International journal of computer & mathematical sciences ijcms, 6(9), 112–116. https://b2n.ir/nu5851
  33. [33] Priya, B. K., Kumar, S., Begum, B. S., & Ramasubramanian, N. (2019). Cache lifetime enhancement technique using hybrid cache-replacement-policy. Microelectronics reliability, 97, 1–15. https://doi.org/10.1016/j.microrel.2019.03.011
  34. [34] Zhao, Y., Ma, T., Hao, Y., Shen, W., Tian, Y., & Al-Dhelaan, A. (2019). ICRA: index based cache replacement algorithm for cloud storage. International journal of sensor networks, 29(1), 48–57. https://doi.org/10.1504/IJSNET.2019.097556
  35. [35] Yuan, Y., Shen, Y., Li, W., Yu, D., Yan, L., & Wang, Y. (2017). PR-LRU: A novel buffer replacement algorithm based on the probability of reference for flash memory. IEEE access, 5, 12626–12634. https://doi.org/10.1109/ACCESS.2017.2723758
  36. [36] Chen, X., Wang, Y., Xie, X., Hu, X., Basak, A., Liang, L., ... & Xie, Y. (2021). Rubik: A hierarchical architecture for efficient graph neural network training. IEEE transactions on computer-aided design of integrated circuits and systems, 41(4), 936–949. https://doi.org/10.1109/TCAD.2021.3079142
  37. [37] Alsharif, N. (2022). Fake opinion detection in an e-commerce business based on a long-short memory algorithm. Soft computing, 26(16), 7847–7854. https://doi.org/10.1109/TCAD.2021.3079142
  38. [38] He, X., & Lin, M. (2022). Reliable auxiliary communication of UAV via relay cache optimization. Computer communications, 186, 33–44. https://doi.org/10.1016/j.comcom.2021.11.024

Downloads

Published

2025-01-20

Issue

Vol. 1 No. 1 (2025): Transactions on Soft Computing (TSC)

Section

Articles

How to Cite

Priority Cache Object Replacement by Using LRU, LFU and FIFO algorithms to Improve Cache Memory Hit Ratio. (2025). Transactions on Soft Computing , 1(1), 1-13. https://doi.org/10.48314/tsc.v1i1.33