top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Which Data Structure Should be used for LRU cache?

+1 vote
527 views
Which Data Structure Should be used for LRU cache?
posted Mar 2, 2016 by Mohammed Hussain

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

The LRU(least recently used) caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache.
We use two data structures to implement an LRU Cache.

  1. A Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).
    The most recently used pages will be near front end and least recently pages will be near rear end.

  2. A Hash with page number as key and address of the corresponding queue node as value.

When a page is accessed, there can be 2 cases:
1. Page is present in the cache - If the page is already present in the cache, we move the page to the start of the list.
2. Page is not present in the cache - If the page is not present in the cache, we add the page to the list.

answer Mar 2, 2016 by Josita Sarwan
Similar Questions
+3 votes

Suppose we have the option of selecting Tree, Link list and Hash Table now the question is on what basis we should select each one for our use.

+4 votes

Give a good data structure for having n queues (n not fixed) in a finite memory segment. You can
have some data-structure separate for each queue. Try to use at least 90% of the memory space.

+1 vote

Which data structure will be best for storing very large numbers (for example a number having 10^3 digits). Additionally, I want to perform comparison operation on them..

...