lru_cache.cpp File Reference

An implementation of LRU Cache. Lru is a part of cache algorithms (also frequently called cache replacement algorithms or cache replacement policies). More...

#include <cassert>
#include <cstdint>
#include <iostream>
#include <list>
#include <unordered_map>

Include dependency graph for lru_cache.cpp:

Go to the source code of this file.

Classes
class	others::lru_cache::LRUCache
	LRU cache class. More...

Namespaces
namespace	others
	for vector
namespace	lru_cache
	Implementation of the LRU caching algorithm

Functions
template<typename T>
void	lru_tests::log (T msg)
	A function to print given message on console.
static void	lru_tests::test_1 ()
	A simple test case The assert statement will check expected hist and miss to resultant hits and miss.
static void	lru_tests::test_2 ()
	A test case contains hits more than cache size The assert statement will check expected hist and miss to resultant hits and miss.
static void	lru_tests::test_3 ()
	A simple test case The assert statement will check expected hist and miss to resultant hits and miss.
static void	lru_tests::run_tests ()
	A function to invoke all test cases.
int	main ()
	Main function.

Detailed Description

An implementation of LRU Cache. Lru is a part of cache algorithms (also frequently called cache replacement algorithms or cache replacement policies).

Logic

• Discards the least recently used items first.
• This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item.
• General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits.
• In such an implementation, every time a cache-line is used, the age of all other cache-lines changes

Algorithm explanation

For a cache of page frame x:

• Check if the page is present in cache.
• If not present, then check is the cache is full or not:
• If the cache is full, REMOVE the last element from the cache.
• If the element is present in cache, then shift that element to first position in cache from its original position.
  • This way you can keep the least recently used elements in the last and most recently used in front of the cache.

Every time a requested page is not found in cache, that is a miss or page fault, and if the page is present in cache, then its a hit.

Data Structure used

• In the algorithm below we used two different data structure, one is linked list and other one is a hash map
• The linked list is used to contain the pages and the hash map contains the pages and their address.
• Every time a new page is requested, we first check in the hash map if the page is present or not.
• If not present, and the cache is full, we simply delete the last entry in the cache.
• If present, we shift that page from its current location to beginning of the cache and update the address in hash map for that page.

Author

Nitin Sharma

Definition in file lru_cache.cpp.

Function Documentation

log()

template<typename T>

void lru_tests::log

(

T

msg

)

A function to print given message on console.

Template Parameters

T	Type of the given message.

Returns

void

Definition at line 149 of file lru_cache.cpp.

                {
    // It's just to avoid writing cout and endl
    std::cout << "[TESTS] : ---> " << msg << std::endl;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 252 of file lru_cache.cpp.

           {
    lru_tests::run_tests();
 
    // Usage
    others::lru_cache::LRUCache cache(4);
    cache.refer(1);
    cache.refer(2);
    cache.refer(3);
    cache.refer(4);
    cache.refer(5);
    cache.refer(5);
 
    cache.display();
 
    std::cout << "Hits: " << cache.getHits()
              << " Miss: " << cache.getPageFault() << std::endl;
    return 0;
}

run_tests()

void lru_tests::run_tests ( )

static

A function to invoke all test cases.

Returns

void

Definition at line 239 of file lru_cache.cpp.

                        {
    test_1();
    test_2();
    test_3();
    log("");
    log("TESTS COMPLETED!");
}

test_1()

void lru_tests::test_1 ( )

static

A simple test case The assert statement will check expected hist and miss to resultant hits and miss.

Returns

void

Definition at line 160 of file lru_cache.cpp.

                     {
    uint64_t expected_hits = 2;
    uint64_t expected_pageFault = 4;
 
    log("Running Test-1...");
 
    others::lru_cache::LRUCache cache(4);
    cache.refer(1);
    cache.refer(2);
    cache.refer(5);
    cache.refer(1);
    cache.refer(4);
    cache.refer(5);
 
    log("Checking assert statement...");
    assert(cache.getHits() == expected_hits &&
           cache.getPageFault() == expected_pageFault);
    log("Assert successful!");
    log("Test-1 complete!");
}

test_2()

void lru_tests::test_2 ( )

static

A test case contains hits more than cache size The assert statement will check expected hist and miss to resultant hits and miss.

Returns

void

Definition at line 187 of file lru_cache.cpp.

                     {
    uint64_t expected_hits = 4;
    uint64_t expected_pageFault = 2;
 
    log("Running Test-2...");
 
    others::lru_cache::LRUCache cache(4);
    cache.refer(1);
    cache.refer(1);
    cache.refer(1);
    cache.refer(1);
    cache.refer(1);
    cache.refer(5);
 
    log("Checking assert statement...");
    assert(cache.getHits() == expected_hits &&
           cache.getPageFault() == expected_pageFault);
    log("Assert successful!");
    log("Test-2 complete!");
}

test_3()

void lru_tests::test_3 ( )

static

A simple test case The assert statement will check expected hist and miss to resultant hits and miss.

Returns

void

Definition at line 214 of file lru_cache.cpp.

                     {
    uint64_t expected_hits = 1;
    uint64_t expected_pageFault = 5;
 
    log("Running Test-3...");
 
    others::lru_cache::LRUCache cache(4);
    cache.refer(1);
    cache.refer(2);
    cache.refer(3);
    cache.refer(4);
    cache.refer(5);
    cache.refer(5);
 
    log("Checking assert statement...");
    assert(cache.getHits() == expected_hits &&
           cache.getPageFault() == expected_pageFault);
    log("Assert successful!");
    log("Test-3 complete!");
}