Theoretical Presentation 2

Basic concepts.
What is a TLB?
The Translation Look-aside Buffer is where all the most recently used pages go, so when the memory management unit searches for a page, it searches first in this cache.

What is a page table?
This is the structure where it's stored the information about which virtual address correspond to a specific physical address.

What is a frame page?
A frame page is a space with a fixed size in the physical memory, usually the frame pages and the pages in the page table have the same size.

What does swapping means?
So let's imagine that our RAM has no space to allocate memory for another process, so instead of deleting a page frame and lost the data, the memory management unit stores a page frame in a hard drive and then assign the page frame to the new process. The partition where you store the page frames actually it's know as Virtual Memory on Microsoft Windows, in GNU/Linux this is called swap.


How Memory works:

Every process has a memory space, when a program is running uses virtual memory addresses that its translated into the real (physical) address.

If  the space needed it's too big, swap a page frame to disk (decide which with a LRU or FIFO algorithm).

When a process needs to access info in the memory:

-First extracts page number

-Exctracts offset

-check in TLB, translate virtual to physical address

-if not in TLB, trap to OS and add to TLB

-Get info that's in the physical page frame




Are there any other algorithm for swap out pages?
Yes, but before showing you other algorithms, you need to know which could be the optimal page replacement algorithm. This algorithm considers many pages to swap, every page it's going to be accesed at a determinated time, so the page A it's gonna be accesed at time 2, page D at time 3, page C at time 4, page and page B it's going to be accesed at time 6, for example, so the optimal algorithm choose the page with the longest time to be accessed and swap it out. In this example, the algorithm would have chosen the page B.

But there is a problem, we cannot predict the future, so we can't use this technique.
Based on the optimal algorithm, there are many others that try to be like it. We have::

• Not Recently Used (NRU)
• This algoritm divide the pages in four classes:
• Class 0: Not Referenced, Not Modified
• Class 1: Not Referenced, Modified
• Class 2: Referenced Not Modified
• Class 3: Referenced, Modified
• It choose a random page that isn't empty from the lowest class to swap.
• First In, First Out (FIFO)
•  This one is explained above in the presentation.
• Second chance
• This is a modified version of FIFO, this algorithm checks if the page it's actually in use before it is deleted, if so, it goes to the end of the list and has a second chance.
• Clock
• This is kind of similar to second chance, but this one uses a circular linked list and there's a pointer that is showing which is the oldest page.
• Least Recently Used (LRU)
• This one is explained above in the presentation.
• Not Frecuently Used (NFU)
• This uses a counter, when a page is used increases its counter, so later it sees for the page with the lower counter and swap it.

You can view the presentation here