17.4.1. Reference Bit Strategy

Consider the reference string 2 0 1 6 4 2 0 1 6 4 0 1 0 3 1 2 1. Now here I have 4 page frames, let us say my physical memory only has 4 page frames available and these are the set of memory accesses. Initially, there is nothing in the physical memory. The first 4 misses are compulsory, and I bring in 0, 2, 1, 6. 0, 2, 1, 6 missed and then what happens next is explained further.

The reference string indicates the order of page requests to the physical memory. Here, because the memory only has 4 frames, the first 4 page requests (0, 2, 1, 6) will lead to page faults. Since there is no data in memory initially, these requests fail to find the pages - thus leading to compulsory page faults. Each new request for pages that aren’t currently in memory results in another page fault.

Think of the physical memory like a small locker with only room for four items. The first four items you try to store (pages requested) will fit, but when you try to put in a fifth item (the next request), you have to remove one of the items currently in the locker if it is already full.

Now, 0 is accessed again; it is not there in physical memory. So, 0 will again lead to another page fault. It will replace the oldest one which is now 2. Then 1 is referenced again (not a miss), and so on.

Once the pages are in memory, if a page is requested that is already in memory, it won’t lead to a page fault – that’s a ‘hit’. However, if it’s not in memory, you have to replace a page. In this case, each time a page fault occurs, the algorithm looks for the oldest page loaded in memory to replace. For example, asking for page 0 again replaces page 2, which was the oldest.

Imagine going to a library that only has space for 4 books. If you go back to get a book you already borrowed, you can check it out without issue. But if you seek a new book and the library is full, they must take back the oldest book you borrowed to make room for the new one.

The fault rate is calculated out of 12 references; 9 resulted in a fault. Therefore, the fault rate is 9 by 12 or 0.75.

The page fault rate is a metric that measures how many of the total requests resulted in faults. Here, there were 12 requests and 9 of them were faults, resulting in a fault rate of 0.75. This means 75% of the time, the requested page was not in memory.

If you borrowed 12 books and had to go back to the library to pick up another 9, this reflects inefficient use of the library’s limited space. The higher the number, the more times you're forced to make unnecessary library trips.

FIFO is a simple algorithm but a poor replacement policy as it evicts the oldest page without considering how often it is being used. It does not cater to the frequency of page accesses.

FIFO (First In, First Out) simply replaces the oldest page in memory regardless of how often it has been accessed. This lack of consideration may lead to efficient pages being replaced simply because they have been in memory longer, even if they are still actively used.

Consider a queue in a cafeteria. If the first person in line gets their order processed no matter how many times they return to the line, they may end up being replaced by someone who hasn’t ordered much, simply because they were there longer.

The optimal algorithm replaces the page that will not be referenced for the longest time in the future, providing the best theoretical performance metrics.

The optimal page replacement algorithm is based on future predictions of page requests, replacing the page that won’t be used again for the longest duration. While this method can theoretically minimize faults, it is impractical to implement, as we cannot predict future requests.

Imagine planning your grocery shopping while having foreknowledge of the next month’s meals. If you knew exactly when you'd need a certain ingredient, like flour, you'd keep it longer than something you wouldn’t need soon, and only swap it out when necessary. But, we can’t foresee future needs accurately in real life.

With LRU you replace the page that has not been accessed for the longest time. This is more practical than optimal because it analyzes the accessed history.

The LRU algorithm focuses on the past usage of pages. It replaces the least recently accessed pages instead of the oldest. This reflects the principle that pages that were used recently are likely to be used again soon, offering better performance than FIFO.

Think of your closet: if you always wear your most recently used clothes, it makes sense to choose the oldest unworn clothes for donation, rather than simply tossing out the oldest ones in the closet. LRU thus captures which clothing you are least likely to wear again soon.

Implementing LRU is difficult due to the need to track the last access of pages, requiring special hardware support. Two common approaches are counter-based and stack-based solutions.

To accurately implement LRU, systems must effectively track page access which can be resource-intensive. This has led to the development of approximations, such as using counter-based methods to log access time or stack-based methods to reorder accesses.

In a restaurant, rather than tracking every time a dish is served, a chef could use a list to mark which dishes are used the most frequently to decide which to keep in rotation. This makes it easier than trying to remember the last time every dish was made.

One way to approximate LRU is to use a reference bit that indicates whether a page was accessed in a specific time epoch. This information can then help decide which pages to replace.

The reference bit operation collects data on whether a page was accessed during specific time periods. By resetting these bits after set intervals (epochs), the system can establish which pages are least accessed, aiding in replacement choices.

Think of it as a weekly check of your pantry. If you notice items that haven’t been used for weeks, it may be time to throw them out (replace them) rather than the brand new items you just bought.

--