0

LRUページ置換を実装しようとしています。FIFOアルゴリズムを動作させることができました。しかし、最近使用されていないものを追跡する方法がわかりませんか？

ファイルを読み込んでいます。その構造化された最初の数はpid（1）で、2番目の数はref（45）などです。

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

したがって、私はクラス配列を使用しており、ファイルを1行ずつ解析し、配列にない場合は、そのインデックスに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;

 }

2つの質問

1）LRUを追跡する方法がわかりません。私は2番目の配列とカウンター変数を想像しますが、それは私が何をすべきかを見ることができる限りです。

2）LRUを知ったら、着信pidが配列にない場合、インデックスLRU番号で配列に詰め込みますか？

ありがとうございました

4

1 に答える 1

1

一般に、LRU には次の 2 つの競合するニーズがあります。

  • エントリをすばやく見つけます - 配列ルックアップ、ハッシュ テーブル、またはバイナリ マップをインデックスとして提案します。
  • エントリをすばやく先頭に追加/追加/削除する - リンクされたリストを提案する

いずれかの要件に個別に対処すると、力ずくで非効率になります。2 つのコンテナーを自分で調整することもできます。理想的には、それらを LRU クラスにラップして、カプセル化を提供し、信頼性を向上させます。あるいは、ブースト マルチインデックス コンテナがそのような要件に対応しています: www.boost.org/libs/multi_index/

于 2012-11-12T04:25:23.533 に答える