22.1.5. Page Replacement Algorithms

Use of efficient page replacement algorithms must be used, such as the second chance page page replacement which approximates LRU by using FIFO along with the reference bit.

Efficient page replacement algorithms are necessary for managing memory effectively. One such algorithm is the 'second chance' page replacement, which is a variation of the Least Recently Used (LRU) algorithm. It works by allowing pages that have been recently used (indicated by a reference bit) a 'second chance' before they are replaced. If a page is referenced, its reference bit is set to '1'. If the page needs to be replaced and its reference bit is '1', instead of replacing it immediately, the bit is cleared, and the page is given another chance. If it is referenced again, its bit is set back to '1', otherwise, it will be replaced in the next cycle if still unreferenced.

Think of this as a cafe that serves customers. If a customer orders coffee and is about to leave (the page about to be replaced), but has finished only half of their coffee (indicating it has been referenced), the cafe allows them to stay a little longer. If they finish their coffee in that time, they get to stay. Otherwise, they leave the next time a new customer (new page) arrives.

Writes into the disk are very expensive. So, we use a write back mechanism instead of write through. So, this virtual memories use a write back mechanism a page is replaced.

The write-back mechanism is used to optimize memory writing operations because writing to disk is slow and resource-intensive. With this approach, when a page in memory (main memory) is modified, it is not immediately written back to the disk. Instead, it is marked as 'dirty', and updated only when that page is chosen for replacement. Thus, a page can be kept in memory for a longer time without involving costly write operations until it is absolutely necessary to update the disk.

Imagine you’re writing notes for school. Instead of erasing and rewriting every time you make a mistake, you keep your notes on a piece of paper until you're done. Only then do you copy the final, clean version into your notebook, avoiding messy erasing and re-writing along the way.

So, use of dirty bit to avoid writing unchanged pages back to the disk.

The dirty bit is a flag associated with a page in memory that indicates whether it has been modified (i.e., it has been 'dirtied') since it was loaded from disk. If the dirty bit is off, it means that the page hasn't changed and therefore does not need to be written back to the disk when it is replaced. This greatly reduces the number of write operations to disk, optimizing performance and reducing latency.

Think of a librarian organizing books. If a book is borrowed but not marked with any notes or highlights (dirty bit is off), it can just be put back on the shelf without any further action. If it's marked with notes (dirty bit is on), then the librarian needs to update the catalog before putting it back, which takes more time.

That the TLB acts as a cache for address translation from the page table.

The Translation Lookaside Buffer (TLB) is a special cache used to speed up the translation of virtual addresses to physical addresses. Instead of going to the page table in the main memory every time a virtual address needs to be translated, the CPU checks the TLB first. If the required mapping is found in the TLB, the CPU can proceed directly, significantly speeding up memory access. This means that frequently accessed pages can be accessed much faster, improving overall system performance.

Consider a city as a large database of addresses. Normally, you would need to pull out a large map (the page table) every time you want to find an address. However, if you have a small notebook (the TLB) with the most common addresses noted, you can quickly find them without rummaging through the entire map. This saves a lot of time when looking for commonly used locations.

If a process routinely accesses more virtual memory than it has physical memory due to insufficient physical memory it suffers thrashing.

Thrashing occurs when the operating system spends more time swapping pages in and out of memory than executing processes. This typically happens when the working set of a process (the set of pages it needs most frequently) does not fit into the available physical memory, leading to excessive page faults. When thrashing happens, the overall system performance decreases as more time is wasted on managing memory rather than executing the processes.

Imagine a classroom where there are too many students and not enough desks. When students spend most of their time moving chairs around instead of learning, it detracts from their actual education. Similarly, when computers are thrashing, they waste processing power on managing memory instead of performing tasks.

--