22.1.4. Techniques to Reduce Miss Penalty

This virtual memory which we have described as the caching memory between the main memory and disk, this caching mechanism between main memory and disk is challenging because the cost of page faults is very high. If you have a miss in the main memory you have to go to physical memory. And we saw that this could be very high up to 100s of times slower, 1000s of times slower than accessing the main memory. So, the cost of page faults is very high.

When a program tries to access data that is not currently in the main memory (often referred to as a 'page fault'), the system must retrieve it from the disk. This process is significantly slower than accessing data in RAM, sometimes taking hundreds to thousands of times longer. Consequently, minimizing the frequency of these page faults is crucial to maintaining system performance.

Think of page faults like searching for an item in a huge warehouse. If the item is stored in a readily accessible area (like in a small room next to you), it takes only a moment to retrieve it. However, if you have to go all the way to the back of the warehouse, it becomes a much more time-consuming task. Frequent page faults are like constantly having to go to the back of the warehouse.

We use large page tables to take advantage of the spatial locality. Because misses in the main memory has a high penalty, we need to have techniques to reduce such miss penalty. So, what are these techniques? We use large pages to take advantage of spatial locality and reduce miss rates.

Spatial locality refers to the tendency of programs to access a relatively small set of data or instructions repeatedly. By utilizing larger page sizes (like 4 KB, 8 KB, or more), we can capture and store more of this frequently accessed data in physical memory, thereby reducing the rate of page faults since there is a higher probability that needed data will be found more efficiently within those larger pages.

Imagine packing a suitcase for a trip. If you pack in large groups of clothes (like outfits for each day) instead of individual items, you are less likely to miss grabbing something you need. Larger page sizes work similarly; they increase the chances of having the required data in memory together.

Mapping between virtual addresses to physical addresses is made fully associative so that a page can potentially be mapped to any large into to any page frame. So, I can I should be able to put my page potentially into any page frame in main memory.

Fully associative mapping means that any page can be stored in any frame of the physical memory. This flexibility maximizes the chances of keeping frequently accessed pages in memory, which helps to minimize page faults. The higher the potential mapping situations, the better we can utilize memory space and retrieve data quickly.

Think of this mapping as having a giant bookshelf where any book can fit in any slot, rather than a rigid system where only specific books go in specific places. This flexibility allows for better organization and quicker access to your most read books.

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

Page replacement algorithms decide which pages to discard when new pages need to be loaded into memory. The 'second chance' algorithm provides pages with a second chance if they have been accessed, approximating the least recently used (LRU) strategy. This helps to maintain the most frequently accessed pages in memory, effectively reducing page faults.

Consider a library where some books are borrowed. If a book hasn't been borrowed in a while, it stands a chance of being put back on the shelf for new arrivals, but if it’s currently borrowed, it gets a 'second chance' to stay checked out. This helps the library manage its limited space more effectively.

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.

A write-back mechanism means that changes made to a page in memory are not immediately written to the disk. Instead, these changes are stored in a 'dirty' page and only written back to the disk when the page is replaced. This drastically reduces the number of write operations to the disk, saving time and resources.

Think of the write-back mechanism like a notepad where you jot down ideas. You don’t have to submit your notes every time you write something; you only summarize and submit them later, saving you time and effort until you’re ready to finalise what’s important.

The TLB acts as a cache for address translation from the page table. So frequently accessed page table entries are therefore put in a TLB. Due to the use of the TLB to access the page table on every access, I don’t have to go to the main memory right, and this improves the performance heavily.

The Translation Lookaside Buffer (TLB) is a small cache that stores the most frequently accessed entries of the page table. When a reference to memory is made, the system first checks the TLB before accessing the slower main memory. If the required address is found in the TLB, the access is significantly faster, reducing overall time spent handling page translations.

Imagine using a smart address book on your phone. If a contact is saved, you can quickly find their number without flipping through all your contacts. The TLB works similarly; it speeds up the retrieval of often-requested addresses.

--