CODEWITHSUNDEEP
c++arraysalgorithmpriority-queuepage-replacement
user3080029
user3080029

Reputation: 563

How to code the optimal page replacement algorithm?

I am sharing my logic. I need to know if its fine.

I created an array which stores the total number of occurrences for each page.

For ex - If sequence of page requirements is { 1,2,3,1,2}. Lets call it "seq" array.

Then array = { 2,2,1 } . Lets call it "count" array

Now, I iterate through seq and allocate it a frame till I don't exhaust all the frames or if the frame is not already in memory. Then I push it the frame no. and its remaining no. of occurrences to a min priority queue.

    for (int i = 1; i <= M; ++i)
    {
        if (frameAssigned[arr[i]] != 0)    //frame already assigned
        {
            count[arr[i]]--;
            PQ.push(ii(count[arr[i]], arr[i]));
            continue;
        }

        if (freeFrames >= 1)
        {
            frameAssigned[arr[i]] = presentFrame++; //presentFrame=0 initially
            freeFrames--;
            noOfReplacements++;
            count[seq[i]]--;
            PQ.push(ii(count[seq[i]], seq[i]));
            continue;
        }

    //Now, if all free frames are exhausted, I do the following. Replace the page which is 
    //occurring the minimum number of times.

    ii temp = PQ.top(); // ii = pair<int,int>
    PQ.pop();
    int frameNumber = temp.second;
    count[seq[i]]--;
    if (seq[arr[i]] >= 0) PQ.push(ii(count[seq[i]], seq[i]));
    frameAssigned[arr[i]] = frameAssigned[custNumber];
    frameAssigned[custNumber] = 0;
    noOfReplacements++;

However, this algorithm seems to be incorrect. I don't understand why. I found the correct algorithm here, but I don't understand why mine doesn't work.

Upvotes: 0

Views: 3250

Answers (1)

Bhoot
Bhoot

Reputation: 2633

Let us look at the following page occurrence:

1,2,3,2,3,2,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1

Let us assume that the 2 pages can be held in memory. According to your algorithm, when 3 will arrive for the first time, 2 will be replaced because number of occurrences of 1 is quite high , which is not optimal.

In the optimal page replacement algorithm, the criteria for page replacement is based on the time after which the page will be referenced again.

I recommend you to go through the editorial of this problem http://www.codechef.com/AUG14/problems/CLETAB once it is out.

Upvotes: 1

Related Questions