CODEWITHSUNDEEP
c++arraysalgorithm
user249375
user249375

Reputation:

implementing LRU in C++

I am trying to implement LRU Page Replacement. I was able to get FIFO algorithm to work. But i am not sure how to keep track of the least recently used?

I am reading in a file. its structured like first number is pid(1) and second number is the ref(45) and so forth Like:

1 45
1 46
1 45
1 44
2 76
2 75
2 77
2 77

So, i am using a class array, and parsing the file line by line and if its not in the array to put the pid and ref there in that index. If the array is full then go back to the beginning ad start all over.

class pagetable
{

public:
int pid;
int ref;
int faults;
pagetable();
};
pagetable* page = new pagetable[frames];

I am prompting for the number of frames. I am prompting for the file name and storing it in

ifstream inputStream;

Then i can call my LFU function and grab each pid and ref to check.

int runsimLFU(ifstream &inputStream, pagetable* page, int frames ){

int i =0;
int j=0;
bool flag = false;
int cnt=0;
int index = 0;
int value = 0;

while(1){

  inputStream >> pid;
  inputStream >> ref;

      page[count].pid = pid;
      page[count].ref = ref;
  pagefaults++;

Something like this i can keep grabbing each line of the file.

this is how i am searching the array

bool findinarray(pagetable* page, int frames, int pid, int ref)
{

 for(int i=0; i < frames+1; i++) {
    if(page[i].pid == pid && page[i].ref == ref)
    {
        return true;

    }
 }
    return false;

 }

Two questions

1) I am unsure how to keep track of the LRU. i would imagine a second array and a counter variable but thats as far as i can see what to do.

2) once i know the LRU and when the incoming pid, ref is not in the array i stuff that into the array at index LRU number?

Thank you

Upvotes: 0

Views: 2475

Answers (1)

Tony Delroy
Tony Delroy

Reputation: 106068

In general, you have two competing needs for an LRU:

  • quickly find an entry - suggesting an array lookup, hash table, or binary map as an index, and
  • quickly prepend/append/remove an entry - suggesting a linked-list

If you address either requirement separately, you end up with brute-force inefficiencies. You could coordinate two containers yourself - ideally wrapping them into a LRU class to provide some encapsulation and improve reliability. Alternatively, boost multi-index containers address such requirements: www.boost.org/libs/multi_index/

Upvotes: 1

Related Questions