Hybrid Page Replacement Algorithm in real time Operating System

Authors

  • Pallab Banerjee  Assistant Professor, Department of Computer Science and Engineering, Amity University Jharkhand, Ranchi, India
  • Biresh Kumar  Assistant Professor, Department of Computer Science and Engineering, Amity University Jharkhand, Ranchi, India
  • Amarnath Singh  Assistant Professor, Department of Computer Science and Engineering, Amity University Jharkhand, Ranchi, India
  • Shipra Sinha  B.Tech Scholar, Department of Computer Science and Engineering, Amity University Jharkhand, Ranchi, India
  • Medha Sawan  B.Tech Scholar, Department of Computer Science and Engineering, Amity University Jharkhand, Ranchi, India

DOI:

https://doi.org//10.32628/CSEIT2062123

Keywords:

Page Replacement, Page Fault, Page Hit, Page Miss, LRU (Least Recently Used)

Abstract

Programming codes are of variable length. When the size of codes becomes greater than that of primary memory, the concept of virtual memory comes into play. As the name suggests, virtual memory allows to outstretch the use of primary memory by using storage devices such as disks. The implementation of virtual memory can be done by using the paging approach. Allocation of memory frames to each and every program is done by the operating system while loading them into the memory. Each program is segregated into pages as per the size of frames. Equal size of pages and frames enhance the usability of memory. As, the process or program which is being executed is provided with a certain amount of memory frames; therefore, swap out technique is necessary for the execution of each and every page. This swap out technique is termed as Page Replacement. There are many algorithms proposed to decide which page needs to be replaced from the frames when new pages come. In this paper, we have proposed a new page replacement technique. This new technique is based on the approach of reading and counting of the pages from secondary storage. Whenever the page fault is detected, the needed page is fetched from the secondary storage. This process of accessing the disc is slow as compared to the process in which the required page is retrieved from the primary storage. In the proposed technique, the pages having least occurrence will be replaced by the new page and the pages having same count will be replaced on the basis of LRU page replacement algorithm. In this method, the paged are retrieved from the secondary storage hence, possibility of page hit will be increased and as a result, the execution time of the processes will be decreased as the possibility of page miss will be decreased.

References

  1. Sanjay Kumar Panda and Saurav Kumar Bhoi, “An Effective Round Robin Algorithm using Min-Max Dispersion Measure”, International Journal on Computer Science and Engineering, 4(1), pp. 45-53, January2012.
  2. Sorav Bansal and Dharmendra S. Modha CAR: Clockwith Adap- tive Replacement FAST’04 - 3rd USENIX Conference on File and Storage Technologies,2004.
  3. G. Glass and P. Cao, Adaptive Page Replacement Basedon Memory Reference Behavior, Proceedings of 1997ACM SIG- METRICS Conference, May 1997, pp.115-126.
  4. S. Jiang, and X. Zhang, “LIRS: An Efficient Policy to improve Buffer Cache Performance”, IEEE Transactions on Computers, pp. 939-952,2005
  5. Nimrod Megiddo and Dharmendra S. Modha ARC: ASelf-tuning, Low Overhead Replacement Cache USENIX File and Storage Technologies Conference (FAST), San Francisco, CA,2003.
  6. N. Meigiddo, and D. S. Modha, “ARC: A Self-Tuning, Low overhead Replacement Cache”, IEEE Transactions on Computers, pp. 58-65,2004.
  7. S. Bansal, and D. Modha, “CAR: Clock with Adaptive Re- placement”, FAST-’04 Proceedings of the 3rd USENIX Confer- ence on File and Storage Technologies, pp.187-200,2004.
  8. Theodore Johnson and Dennis Shasha. 2q: a lowover head high performance buffer management replacement algorithm In Pro- ceedings of the Twentieth International Conference on. very Large Databases, pp.439-450, Santiago, Chile,1994.
  9. J. E. O’neil, P. E. O’neil and G. Weikum, “An optimality Proof of the LRU-K Page Replacement Algorithm”, Journal of the ACM, pp. 92-112,1999.
  10. A. Janapsatya, A. Ignjatovic, J. Peddersen and S. Parameswaran, “Dueling CLOCK: Adaptive cache replacement policy based on the CLOCK algorithm”, Design, Automation and Test in Europe Conference and Exhibition, pp. 920-925,2010
  11. Implementation of a page replacement algorithm with temporal filtering for Linux, vashundra rathod, pramia chavan, journal of engineering &applied sciences volume 2, no. 6, june2013.
  12. S. Jiang, X. Zhang, and F. Chen, “CLOCK-Pro: An Effective Im- provement of the CLOCK Replacement”, ATEC ’05 Proceedings of the annual conference on USENIX Anuual Technical Confer- ence, pp. 35,2005.
  13. Kaveh Samiee,” WRP: Weighting Replacement Policy to Im- prove Cache Performance”, International Journal of Hybrid In- formation Technology, Vol.2, No.2, April,2009.
  14. Song Jiang, Feng Chen and Xiaodong Zhang, CLOCK Pro: An Effective Improvement of the CLOCK Replacement, USENIX Annual Technical Conference,2005.
  15. Pooja khulbe, Shruti pant, “HYBRID LRU Page Replacement Algorithm” , International Journal of Computer Applications (0975 – 8887) Volume 91 – No.16, April2014.
  16. Performance analysis of LRU page replacement algorithm. Inter- national Journal of Engineering Research and Applications (IJE- RA) Vol. 3. Issue 1. pp.2070-2076 Klues K. Rhoden B. Zhu Y. Waterman A. Brewer E. (2010).
  17. A. S. Sumant, and P. M. Chawan, “Virtual Memory Management Techniques in 2.6 Linux kernel and challenges”, IASCIT Interna- tional Journal of Engineering and Technology, pp. 157-160,2010.
  18. A. Janapsatya, A. Ignjatovic, J. Peddersen and S.Parameswaran, “Dueling CLOCK: daptive cache replacement policy based on the CLOCK algorithm”, Design, Automation and Test in Europe Conference and Exhibition,pp. 920-925,2010.
  19. Amit S. Chavan, Kartik R. Nayak, Keval D. Vora, Manish D.Purohit and Pramila M. Chawan, " A Comparison of PageRe- placement Algorithms", IACSIT International Journal ofEngi- neering and Technology, Vol.3, No.2, April 2011pp.171-174.
  20. Jisha.P. Abraham, Sheena Mathew "A novel approach to im- prove processor performance with page replacement techniques" Proceedings of the International Conference on Information and Communication Technologies, ICICT 2014,3-5 December2014.
  21. Song Jiang and Xiaodong Zhang, Token-ordered LRU: an effec- tive page replacement policy and its implementation in Linux sys- tems, Performance Evaluation 60 5–29,2005.
  22. Mr.C.C.Kavar, Mr. S.S.Parmar “Performance Analysis of LRU Page Replacement Algorithm with Reference to different Data Structure"International Journal of Engineering Research and Applications (IJERA) Vol. 3, Issue 1, January – February2013,pp.2070-2076.
  23. A comparison of page replacement algorithm. IACSIT Interna- tional Journal of Engineering and Technology. Vol. 3. No. 2 Kavar C. C. Parmar S. S. (2013).
  24. Abraham Silberschatz, Peter B. Galvin and Greg Gagne, Operat- ing System Concepts (UK: Wiley,2010).
  25. Page Replacement, S. Jananee, ISSN 2348-1196 (print) Interna- tional Journal of Computer Science and Information Technology Research ISSN 2348-120X (online) Vol. 2, Issue 3, pp: (90-99), Month: July - September2014.
  26. Ali Khosrozadeh, SanazPashmforoush, Abolfazl Akbari, Maryam Bagheri, NedaBeikmahdavi. , "Presenting a Novel Page Replacement Algorithm Based on LRU”, Journal of Basic and Applied Scientific Research, 2(10)10377-10383,2012.
  27. Optimal Page Replacement Algorithm,https://www.geeksforgeeks.org/optimal-page-replacement-algorithm

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2020-04-30

Issue

Volume 6, Issue 2, March-April-2020

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Pallab Banerjee, Biresh Kumar, Amarnath Singh, Shipra Sinha, Medha Sawan, " Hybrid Page Replacement Algorithm in real time Operating System, IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 6, Issue 2, pp.433-439, March-April-2020. Available at doi : https://doi.org/10.32628/CSEIT2062123