implémentation de LRU en C++

Question

J'essaye d'implémenter le remplacement de page LRU. J'ai réussi à faire fonctionner l'algorithme FIFO. Mais je ne suis pas sûr de savoir comment garder la trace du moins récemment utilisé?

Je lis dans un fichier. sa structure comme premier numéro pid (1) et le deuxième numéro est l'arbitre (45) et ainsi de suite comme:

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

, je suis en utilisant un tableau de classe et analyse de la ligne de fichiers en ligne et si son pas dans le tableau pour mettre le pid et ref là dans cet index. Si le tableau est plein, retournez au début de l'annonce et recommencez partout.

class pagetable 
{ 

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

Je demande le nombre de trames. Je PROMPTING le nom de fichier et le stocker dans

ifstream inputStream; 

Alors je peux appeler ma fonction LFU et saisir chaque pid et ref pour vérifier.

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

Quelque chose comme ça je peux continuer à saisir chaque ligne du fichier.

c'est comment je suis à la recherche du tableau

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; 

} 

Deux questions se

1) Je ne suis pas sûr comment garder une trace de la LRU. J'imagine un deuxième tableau et une variable de compteur mais c'est aussi loin que je peux voir quoi faire.

2) une fois que je connais le LRU et quand le pid entrant, ref n'est pas dans le tableau je bourre cela dans le tableau au numéro d'index LRU?

Merci

Answer 1

En général, vous avez deux besoins concurrents pour une LRU:

• trouver rapidement une entrée - ce qui suggère une recherche de tableau, table de hachage, ou d'une carte binaire comme un index, et
• rapidement précédez/append/supprimer une entrée - suggérant une liste chaînée

Si vous adresse ces deux exigences séparément, vous vous retrouvez avec inefficacités force brute. Vous pouvez coordonner vous-même deux conteneurs, en les enveloppant idéalement dans une classe LRU pour assurer l'encapsulation et améliorer la fiabilité. Les conteneurs multi-index boost peuvent également répondre à ces exigences: www.boost.org/libs/multi_index/