Application of B-trees for Design of Optimal Page Replacement Technique in Modern Operating Systems

Year : 2025 | Volume : 03 | Issue : 02 | Page : 23 30
    By

    Sai Ganesh Palli,

  • Manas Kumar Yogi,

  1. Undergraduate Student, Department of Computer Science and Engineering, Pragati Engineering College (A), Surampalem, Andhra Pradesh, India
  2. Assistant Professor, Department of Computer Science and Engineering, Pragati Engineering College (A), Surampalem, Andhra Pradesh, India

Abstract

Algorithms related to replacing the memory pages in operating systems are critical components of modern operating systems that manage virtual memory efficiently. Current algorithms such as LRU (Least Recently Used), Clock algorithms as well as FIFO (First-In-First-Out), often struggle with the increasing demands of contemporary applications and larger memory hierarchies. This research work proposes a novel approach utilizing B-tree data structures to design an optimal page replacement technique. The proposed methodology leverages the inherent properties of B-trees: balanced structure, logarithmic search time, and efficient insertion/deletion operations, to maintain temporal and spatial locality information. Our analysis demonstrates that B-tree-based page replacement can achieve superior performance in terms of page fault rates, search efficiency, and adaptability to varying workload patterns. This study presents the theoretical foundation, algorithm design, performance analysis, and comparative evaluation with existing techniques, providing insights into the practical implementation of B-trees for memory management in modern operating systems.

Keywords: B-trees, page replacement, virtual memory, operating systems, memory management, cache optimization

[This article belongs to International Journal of Data Structure Studies ]

How to cite this article:
Sai Ganesh Palli, Manas Kumar Yogi. Application of B-trees for Design of Optimal Page Replacement Technique in Modern Operating Systems. International Journal of Data Structure Studies. 2025; 03(02):23-30.
How to cite this URL:
Sai Ganesh Palli, Manas Kumar Yogi. Application of B-trees for Design of Optimal Page Replacement Technique in Modern Operating Systems. International Journal of Data Structure Studies. 2025; 03(02):23-30. Available from: https://journals.stmjournals.com/ijdss/article=2025/view=232918


References

  1. Midorikawa ET, Piantola RL, Cassettari HH. On adaptive replacement based on LRU with working area restriction algorithm. ACM SIGOPS Oper Syst Rev. 2008 Oct 1; 42(6): 81–92.
  2. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to algorithms. MIT press; Cambridge, Massachusetts. 2022 Apr 5.
  3. Kumar A, Boehm M, Yang J. Data management in machine learning: Challenges, techniques, and systems. In Proceedings of the 2017 ACM International Conference on Management of Data. 2017 May 9; 1717–1722.
  4. Tanenbaum AS, Bos H. Modern operating systems. Pearson Education, Inc.; London. 2015.
  5. Graefe G. Modern B-tree techniques. Found Trends Databases. 2011 Aug 19; 3(4): 203–402.
  6. Aho AV, Denning PJ, Ullman JD. Principles of optimal page replacement. J ACM. 1971 Jan 1; 18(1): 80–93.
  7. Kavar CC, Parmar SS. Improve the performance of LRU page replacement algorithm using augmentation of data structure. In 2013 IEEE Fourth International Conference on Computing, Communications and Networking Technologies (ICCCNT). 2013 Jul 4; 1–5.
  8. Titinchi AA, Halasa N. A New Method to Enhance LRU Page Replacement Algorithm Performance. Int J Sci Technol Res. 2020 Feb; 9(02): 4185–4190.
  9. Silberschatz A, Galvin PB, Gagne G. Operating system concepts essentials. Wiley Publishing; Hoboken, New Jersey. 2013 Nov 18.
  10. Huang S, Wei Q, Feng D, Chen J, Chen C. Improving flash-based disk cache with lazy adaptive replacement. ACM Trans Storage. 2016 Feb 26; 12(2): 1–24.
  11. Garmpis A. Alg_OS—A web‐based software tool to teach page replacement algorithms of operating systems to undergraduate students. Comput Appl Eng Educ. 2013 Dec; 21(4): 581–5.
  12. Liu S, Seemakhupt K, Pekhimenko G, Kolli A, Khan S. Janus: Optimizing memory and storage support for non-volatile memory systems. In Proceedings of the 46th International Symposium on Computer Architecture. 2019 Jun 22; 143–156.
  13. Sharma N, Singh BM, Singh K. QoS-based energy-efficient protocols for wireless sensor network. Sustain Comput: Inform Syst. 2021 Jun 1; 30: 100425.
  14. Hazarika A, Poddar S, Rahaman H. Survey on memory management techniques in heterogeneous computing systems. IET Comput Digit Tech. 2020 Mar; 14(2): 47–60.
  15. Cederman D, Gidenstam A, Ha P, Sundell H, Papatriantafilou M, Tsigas P. Lock‐Free Concurrent Data Structures. Programming multi‐core and many‐core computing systems. USA: John Wiley & Sons, Inc.; 2017 Jan 24; 59–79.
  16. Gelenbe E. A unified approach to the evaluation of a class of replacement algorithms. IEEE Trans Comput. 2009 May 29; 100(6): 611–8.
Regular Issue Subscription Original Research
Volume 03
Issue 02
Received 12/10/2025
Accepted 15/10/2025
Published 24/10/2025
Publication Time 12 Days
67

Login


My IP

PlumX Metrics