Hello all,

What can be the possible data structure that can be used to implement
the Least Recently Used Page (LRU) Replacement Algorithm efficiently?

Any suggestions,
Thanks,
Anunay

[ Post a follow-up to this message ]

Anunay wrote:
> Hello all,
>
> What can be the possible data structure that can be used to implement
> the Least Recently Used Page (LRU) Replacement Algorithm efficiently?
>

What is the best way to ask your homework questions on usenet ?

Which of the data-structures below have you considered:

* table/array + lineair search.
* heap/stack
* linked list
* double linked list
* hash table
* binary tree
* btree, more trees here

HTH,
AvK

[ Post a follow-up to this message ]

moi <avk@localhost> writes:

> Anunay wrote: 
>
> What is the best way to ask your homework questions on usenet ?

Ok, some more help:

> Which of the data-structures below have you considered:
>
> * table/array + lineair search.
> * heap/stack
> * linked list
> * double linked list
> * hash table
> * binary tree
> * btree, more trees here


To find the best thing, you have to have:
- a way to enumerate things,
- a way to evaluate things,
- a way to compare what two things evaluate to.

For the enumeration of data-structures, you can make use of your
imagination, or just read the Table of Contents of any data structure
text book (or read Moi's answer above, but is it exhaustive?).

For the evaluatation of things, here we're considering data structures
and algorithms, you need to do complexity analysis and obtain an
expression of the time and space complexities of each case.  Note that
you have to evaluate to a vector:

- space complexities of the data structure,
- time and space complexities for the (RECENTLY-USED page) operation,
- time and space complexities for the (GET-LEAST-RECENTLY-USED) operation.

(perhaps also you'll want to consider (ADD-PAGE page) and (REMOVE-PAGE
page) if the set of page may changes).


For the comparison, it's rather easy, we'll rely on logic and maths to
compare the complexities.

--
__Pascal Bourguignon__                     http://www.informatimago.com/
Kitty like plastic.
Confuses for litter box.
Don't leave tarp around.

[ Post a follow-up to this message ]

Pascal Bourguignon wrote:
> moi <avk@localhost> writes:
>
> 
>

>
> For the enumeration of data-structures, you can make use of your
> imagination, or just read the Table of Contents of any data structure
> text book (or read Moi's answer above, but is it exhaustive?).


I don't think so.

> For the evaluatation of things, here we're considering data structures
> and algorithms, you need to do complexity analysis and obtain an
> expression of the time and space complexities of each case.  Note that
> you have to evaluate to a vector:
>
>     - space complexities of the data structure,
>     - time and space complexities for the (RECENTLY-USED page) operation,
>     - time and space complexities for the (GET-LEAST-RECENTLY-USED) operat
ion.
>
> (perhaps also you'll want to consider (ADD-PAGE page) and (REMOVE-PAGE
> page) if the set of page may changes).

Also, the implementation can benefit from hardware support.
[ hardware pageregisters eg have a page-dirty && page-accessed bitty ]

Plus: "usage patterns" ::
* how often is a page referenced, until it finaly drops off ?
* what is the fraction of pages that is actually referenced more than
once, intil it drops off ?
* what is the cost of a read ?
* what is the cost of a write ?
* what is the cost of memory, compared to disk space
* what is the speed of memory (bus), compared to disk ?
* what is the cost of cleverness, compared to bare metal ?
* what is the cost of omitting an item from a bullet list ?

>
> For the comparison, it's rather easy, we'll rely on logic and maths to
> compare the complexities.
>

Ok, I suggest you do the math, Pascal.
I am not good at math.
Moi is only able to make lists :-]

HTH,
AvK

[ Post a follow-up to this message ]