Click here to Skip to main content
12,254,932 members (60,807 online)
Click here to Skip to main content
Add your own
alternative version

Stats

28.2K views
312 downloads
7 bookmarked
Posted

Least Recently Used

, 24 Nov 2007
Rate this:
Please Sign up or sign in to vote.
An implementation of Least Recently Used (LRU) Algorithm

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Fekri Kassem
Web Developer
United States United States
Hi,
My name is Fekri. I love programming so much. I program 5-10 hours a day. I work for volt information science.

You may also be interested in...

Comments and Discussions

 
QuestionPossible problem?? Pin
betaisao14-May-08 8:41
memberbetaisao14-May-08 8:41 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160426.1 | Last Updated 24 Nov 2007
Article Copyright 2007 by Fekri Kassem
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid