0

我分享我的逻辑。我需要知道它是否正常。

我创建了一个数组，用于存储每个页面的出现总数。

例如 - 如果页面要求的顺序是 { 1,2,3,1,2}。让我们称之为“ seq”数组。

然后数组 = { 2,2,1 } 。让我们称之为“ count”数组

现在，我遍历seq并为其分配一个帧，直到我没有耗尽所有帧或者该帧尚未在内存中。然后我把它推到框架号。及其剩余的编号。最小优先级队列的发生次数。

    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++;

但是，这个算法似乎是不正确的。我不明白为什么。我在这里找到了正确的算法，但我不明白为什么我的算法不起作用。

4

1 回答 1

1

让我们看看以下页面出现：

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

让我们假设这 2 个页面可以保存在内存中。根据您的算法，当 3 第一次到达时，将替换 2，因为 1 的出现次数很高，这不是最优的。

在最优页面替换算法中，页面替换的标准是基于页面将被再次引用的时间。

我建议你阅读这个问题的编辑http://www.codechef.com/AUG14/problems/CLETAB一旦它出来。

于 2014-08-05T10:34:45.187 回答