0

我正在尝试实现 LRU 页面替换。我能够让 FIFO 算法工作。但我不确定如何跟踪最近最少使用的？

我正在阅读一个文件。它的结构类似于第一个数字是 pid(1)，第二个数字是 ref(45)，依此类推：

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

所以，我正在使用一个类数组，并逐行解析文件，如果它不在数组中，则将 pid 和 ref 放在该索引中。如果数组已满，则返回开始广告重新开始。

class pagetable
{

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

我提示输入帧数。我提示输入文件名并将其存储在

ifstream inputStream;

然后我可以调用我的 LFU 函数并获取每个 pid 和 ref 来检查。

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

像这样的东西我可以继续抓取文件的每一行。

这就是我搜索数组的方式

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;

 }

两个问题

1) 我不确定如何跟踪 LRU。我会想象第二个数组和一个计数器变量，但这就是我所能看到的。

2）一旦我知道LRU并且当传入的pid，ref不在数组中时，我将其填充到索引LRU编号的数组中？

谢谢

4

1 回答 1

1

通常，您对 LRU 有两个相互竞争的需求：

  • 快速找到一个条目 - 建议使用数组查找、哈希表或二进制映射作为索引，以及
  • 快速添加/附加/删除条目 - 建议链接列表

如果您分别解决任一要求，最终会导致暴力效率低下。您可以自己协调两个容器 - 理想情况下将它们包装到 LRU 类中以提供一些封装并提高可靠性。或者，boost 多索引容器可以满足此类要求：www.boost.org/libs/multi_index/

于 2012-11-12T04:25:23.533 回答