Page Replacement Policies in Operating System

---

Page Replacement

---

As studied in Demand Paging, only certain pages of a process are loaded initially into the memory. This allows us to get more processes into the memory at the same time. but what happens when a process requests for more pages and no free memory is available to bring them in. The following steps can be taken to deal with this problem:

 Put the process in the wait queue, until any other process finishes its execution thereby freeing frames.

 Or, remove some other process completely from the memory to free frames.

 Or, find some pages that are not being used right now, and move them to the disk to get free frames.

This technique is called Page replacement and is most commonly used. We have some great algorithms to carry on page replacement efficiently.

---

Basic Page Replacement

• Find the location of the page requested by the ongoing process on the disk. 
• Find a free frame. If there is a free frame, use it. If there is no free frame, use a page-replacement algorithm to select any existing frame to be replaced, such frame is known as a victim frame.
• Write the victim frame to disk. Change all related page tables to indicate that this page is no longer in memory.
• Move the required page and store it in the frame. Adjust all related page and frame tables to indicate the change.
• Restart the process that was waiting for this page.

---

FIFO Page Replacement

A very simple way of Page replacement is FIFO (First in First Out) As new pages are requested and are swapped in, they are added to the tail of a queue and the page which is at the head becomes the victim. It's not an effective way of page replacement but can be used for small systems.

---

LRU Page Replacement

LRU stands for Least Recently Used. As the name suggests, this algorithm is based on the strategy that whenever a page fault occurs, the least recently used page will be replaced with a new page. So, the page not utilized for the longest time in the memory (compared to all other pages) gets replaced.

---

Thrashing

---

Thrashing is a process that spent more time in paging than executing. 

In other words, it means, that the process doesn't have enough frames to hold all the pages for its execution, so it is swapping pages in and out very frequently to keep executing. 

Sometimes, the pages which will be required in the near future have to be swapped out. Initially, when the CPU utilization is low, the process scheduling mechanism, to increase the level of multiprogramming loads multiple processes into the memory at the same time, allocating a limited number of frames to each process. 

As the memory fills up, the process starts to spend a lot of time for the required pages to be swapped in, again leading to low CPU utilization because most of the processes are waiting for pages. Hence the scheduler loads more processes to increase CPU utilization, and as this continues at a point in time the complete system comes to a stop.

To prevent thrashing we must provide processes with as many frames as they really need "right now".

Happy Exploring!