C++

Forum

 
Implementing LRU algorithm

ResidentBiscuit (4459)
I've been working on getting an LRU algorithm working correctly, but it seems no matter what I try, it keeps performing as well, if not worse, than my FIFO implementation. I really don't know what is wrong with this thing and it's got me quite frustrated. Part of me wants to just abandon what I have and restart, but that would be 4th time I've rewritten this thing and I just need to get it done. If someone can give me some pointers as to what's going wrong that would be awesome:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
unsigned int lru(frame frameV[], int refStr[], int sz)
{
    unsigned int faults = 0;
    int clock = 0;
    for(unsigned int i = 0; i < REF_STR_SZ; i++)
    {
        clock++;
        if(pageFault(frameV, refStr[i], sz, clock))
        {
            int smallestClock = frameV[0].luTime;
            faults++;
            int leastUsed = 0;  //Index of least recently used
            for(int j = 1; j < sz; j++)
            {
                if(frameV[j].luTime < smallestClock)
                {
                    leastUsed = j;
                    smallestClock = frameV[j].luTime;
                }
            }
            frameV[leastUsed].pageRef = refStr[i];
            frameV[leastUsed].luTime = clock;
        }
    }

    return faults;
}

inline bool pageFault(frame frameV[], int ref, int sz, int clock)
{
    for(int i = 0; i < sz; i++)
    {
        if(frameV[i].pageRef == ref)
        {
            frameV[i].luTime = clock;  //Updates reference time for use in LRU algo
            return false;
        }
    }
    return true;
}
toum (353)
One possible problem is that your frame array is not ordered.

As a consequence every time you have a page fault you have to scan through your entire array to find the LRU.

Maybe you could try to reorder your array at every operation. Basically you'd only have to shift a number of elements 1 slot to the right and insert an element in the 1st position.
It would have a cost, but you would not have to search for the LRU anymore.
Also, a data structure with fast insertion and deletion of elements might be more efficient than an array for doing this.

My 2 cents.
ResidentBiscuit (4459)
Well I'm not concerned with speed of it as I'm working with a small data set. I'm concerned with it reporting the wrong number of page faults for a given reference string.
Topic archived. No new replies allowed.