17.3.1. Implementation Challenges

So, FIFO although is very simple, I find out the oldest page in memory and replace it, this is the algorithm, it’s a poor replacement policy why it evicts the oldest page in the system and it does not take care whether this page is being heavily used currently or not.

In First-In-First-Out (FIFO) page replacement, the operating system replaces the oldest page in memory when a new page needs to be loaded. The key issue with this method is that it only considers how long a page has been in memory, without regard for how frequently it is accessed. Therefore, it might replace a page that is still being used actively, which can lead to higher page fault rates.

Think of a library where books are arranged in the order they were returned. When a new book has to be shelved, the librarian removes the first book that was returned, regardless of whether it is still popular among the readers. This can lead to readers being unable to find the books they want, even though they are still in demand.

So, this one is called the optimal page replacement algorithm what is the basic idea of the algorithm, I replace the page that will not be referenced for the longest time in future. This is where is the why it is impractical, I want to replace that page which will not be referenced for the longest time in future.

The optimal page replacement algorithm is a theoretical concept where the system replaces the page that won’t be needed for the longest time in the future. While it provides the lowest possible page fault rate, it is impractical because it requires knowledge of future references, which is not possible in real-time systems.

Imagine a bus stop where a bus driver needs to decide which passengers to let off next, based on who will stay on the bus the longest. Since they cannot see ahead to know who will get off where, it makes planning impossible. They may end up letting off passengers who would have gotten off next, resulting in delays.

The basic idea is that you replace that page in memory that has not been accessed for the longest time in the past.

The Least Recently Used (LRU) algorithm enhances page replacement by targeting the page that has not been accessed for the longest period. However, tracking which pages have been recently accessed requires additional hardware support, making it more complex and sometimes impractical.

Consider your computer desktop as a workspace. If you were to clean your desk, you would likely put away the papers you haven't looked at in a while, assuming you probably won't use them again soon. However, this only works if you can remember which ones you've used recently, similar to how LRU uses access history.

Now, as we told LRU is difficult to implement in practice because how do we keep track of the last page access, this is the problem requires special hardware support.

While LRU is a theoretically sound approach to page replacement, its implementation requires additional hardware tracking of page access time or order. Such tracking creates overhead, and frequent memory accesses can overwhelm the system if it needs to check access history every time a page is referenced.

Think of a classroom where students need to remember when they last used their textbooks for a subject. While it’s beneficial for classroom management, having each student constantly keep track of their usage requires significant effort and is prone to forgetfulness.

The first way to the way to approximate LRU is the use of the reference bit which we have which we have already studied earlier that reference bit tells me that within a given epoch of time whether I have referenced a page or not.

To overcome LRU's implementation difficulties, systems often use a reference bit system. This method tracks whether pages have been accessed recently within set time intervals or epochs, allowing estimates of usage without needing complete historical tracking.

Imagine a library that doesn't keep a complete log of every time a book is borrowed but marks books with a tag each time they are touched. This way, they can easily identify which books are currently being used and which are not, making the decision of which to return easier.

Now we come to the clock algorithm or the second chance page replacement algorithm this is another approximation of the LRU technique.

The clock replacement algorithm organizes pages in a circular fashion and uses a pointer to track which pages have been accessed. When replacing a page, the algorithm checks the reference bits: if a page is referenced, it gets a 'second chance' and the reference bit is reset. This continues until a page with a reference bit of 0 is found for replacement.

Picture a clock where each hour represents a borrowed book. If a book hasn’t been checked out recently (reference bit is 0), it can be returned. If it has (reference bit is 1), it simply gets noted for next time. This system prevents the loss of frequently used items in a practical way.

--