Least Recently Used

• Download Least_Recently_Used.zip - 5.7 KB

Introduction

This program is an implementation of Least Recently Used (LRU) Algorithm used in implementing memory management.

The Least Recently Used algorithm is used in memory management when a page table is full then an entry must be removed before you add a new entry to the page table. There are several algorithms. One of them is optimal which looks at the future and checks which entry in the page table that we won't see soon and remove that. Even though this algorithm is the best, but you do not know or can not tell what the future entries are.

URL uses the same idea except that it looks at the history and which entries that we barely used and choose them as the victims in the page replacement.

Here is an example:

If we have this string of entries 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 and we the page size is 3 then we start with 7, add to the page since we have an empty slot and the same with 0 and 1. Once we get to 2, we need to decide which one of the entries should be replaced with the new if the new one is not already in the page table. We scan the history from right to left until we see the oldest in this case 7 and replace it with 2 and so on.

Using the code

Using the code is straight forward. The main function of the LRU class is process which takes an input string and process it. It calls print for each step in processing the input string. The constructor takes the size of the page.

Using the algorithm

LRU lru(3);
lru.process("7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1");

void LRU::process ( std::string str ) 
{
    std::list<char> history;

    for ( size_t i = 0; i < str.length(); i = i + 2 )
    {
        if ( __current_empty == __page_size ) 
        {
             
            if ( __page[ str [ i ] ] == false )
            {
                char c = history.front();
                history.pop_front();
 
                __page.erase( c );

                __page[ str [ i ] ] = true;
            }

            history.push_back( str [ i ] );

        } 
        else 
        {

            if ( __page [ str [ i ] ] == false )
            {
                __page [ str [ i ] ] = true;

                __current_empty++;
            }

            history.push_back( str [ i ] );
        }

        __print__( str [ i ] );
    }
}

This is the actual implementation of the algorithm. __current_empty keeps track of the empty slots in the page. and map is used to represent a page. A doubly linked list is used to keep track of the history of used numbers.

The way it works is I used map structure to represent a page, and doubly linked list to keep the history of the entries. I used doubly linked list because you could push, pop from the front and the end of the list easily. It is also good to keep history of the entries using this structure because you do not have to search for the victim each time you want to choose one. The front of the list will be your victim always and each time you add an entry to the page, just push it to the back of the list. I use map because it works like a hash which is a better alternative for this implementation. Every time you add an entry, you check if the page is already full, then we need to choose a victim ( the front of the list) and replace it with the new entry, and then push it to the end of the list. If it is already in the map, just add it to the history list and do nothing.

If you have any questions, feel free to email me or post comments.