2nd Theoretical Assignment - Page Replacement

Hi there, in this post I will explain how the page replacement algorithms work.
So first, what is the page replacement algorithm for?

 In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. - Wikipedia

In our nachos, the page replacement algorithm will decide which page is going to be swapped out in  order to allocate a new one. For this, Martin C. Rinard mentions two algorithms in his notes: FIFO, and LRU.

FIFO

FIFO means, like many of you may already know, First-In First-Out, so this algorithm is going to swap the first page brought into memory, regardless of whether it has been accessed recently or not.

An example would be:
Sequence: 1, 2, 3, 1, 4 (Using a 3 sized memory)
1-> [1]
2->[1, 2]
3->[1, 2, 3]
1->[1, 2, 3] #1 is accessed again
4->[2, 3, 4] #And yet is swapped in the next turn

This is a downside of the algorithm, it may eject a heavily used page.

A pseudo-code for this algorithm would be:

  
fifo(page):
   #If the memory is not full yet
    if len(memory) < memory_size:
       #And the page is not already in memory 
        if page not in memory:
            #Add the page to memory
            memory.append(page)
    #If the memory is full
    elif len(memory) == memory_size:
        #And the page is not already in memory
        if page not in memory:
           #swap out the first added page ( index 0 on the queue)
            swap_out = memory.pop(0)
           #Add the page to memory at the end
            memory.append(page)

An example run of a python script using this pseudo-code and data from the OS notes:

LRU:

LRU, Least Recently Used, works as it sounds, it will swap out the least page used. For this the algorithm uses a queue, in which the pages brought to memory will be added to the beginning of the queue. When a page fault occurs, the algorithm swaps out  the last page on the queue.

Sequence: 1, 2, 3, 1, 4 (Using a 3 sized memory)

1->[1] - [1]

2->[1, 2] - [2, 1]

3->[1, 2, 3] - [3, 2, 1]

1->[1, 2, 3] - [1, 3, 2] # 1 is accessed, the queue updates

4->[1, 4, 3] - [4, 1, 3] #a page fault occurs, 2 is the least recently used, so it's ejected.

A pseudo-code for this algorithm would be:

  
LRU(page):
    #If the memory is not full yet.
    if len(queue) < memory_size:
        #And the page is not already in the queue
         if page not in queue:
            #Add the page to the beginning of the queue.
            queue.insert(0, page)
       #else if its already in the queue
        else:
           #Pop the page out, and add it at the beginning
            queue.pop(queue.index(page))
            queue.insert(0, page)
    #If the memory is already full
    if len(queue) == memory_size:
       #And the page is not in the queue
        if page not in queue:
            #swap out the last page in the queue, and add the new one to the beginning
            swap_out = queue.pop()
            queue.insert(0, page)
       #Else if it's already in the queue
        else:
            #Pop the page out, and add it at the beginning
            queue.pop(queue.index(page))
            queue.insert(0, page)

An example run of a python script using this pseudo-code and data from the OS notes:

LRU Vs FIFO

To test the algorithm, a sequence of 20 random pages were used to obtain averages between 100 samples. Five different pages were used(from 1 to 5).

So, according to this, in average FIFO gets more page faults than LRU in every memory size bellow 7.

This also concludes an interesting fact, at n + 2 size(n being the number of different pages), both algorithms bring the same results. So in this case in which, n = 5, from 7 onwards the page faults in both LRU and FIFO will be the same providing the sequence is the same for both.

And that's all for the page replacement, if you have any doubt or observations, feel free to write in the comment section bellow. 

Download the python source

References:

http://people.csail.mit.edu/rinard/osnotes/

Wikipedia