Como implementar um esquema de armazenamento em cache LRU? Quais estruturas de dados devem ser usadas?
Recebemos o número total possível de páginas que podem ser referidos. Nós também recebemos cache (ou memória) tamanho (Número de frames que o cache pode armazenar em um momento). O esquema de armazenamento em cache LRU deve remover o frame menos usado recentemente quando o cache está cheio e uma nova página que não está em cache é referenciada.
Usamos duas estruturas de dados para implementar um cache LRU.
1. Uma fila que é implementada usando uma lista duplamente ligada. O tamanho máximo da fila será igual ao número total de frames disponíveis (tamanho do cache).
As páginas mais recentemente usadas estará perto do início e as páginas menos recentes estarão perto da extremidade traseira.
2. Um Hash com número de página como chave e o endereço do nó na fila correspondente como valor.
Quando uma página é referenciada, a página requerida pode estar na memória. Se estiver na memória, precisamos separar o nó da lista e trazê-lo para a frente da fila.
Se a página necessária não está na memória, nós trazemos a que está na memória. Em palavras simples, podemos adicionar um novo nó para a frente da fila e atualizar o endereço de nó correspondente no hash. Se a fila está cheia, isto é, todos os frames estão cheios, que remover um nó a partir do final de fila, e adicionar o novo nó para a frente da fila.
Nota: Inicialmente nenhuma página está na memória.
Abaixo a implementação em C será apresentada:
// A C program to show implementation of LRU cache
#include <stdio.h>
#include <stdlib.h>
// A Queue Node (Queue is implemented using Doubly Linked List)
typedef struct QNode
{
struct QNode *prev, *next;
unsigned pageNumber; // the page number stored in this QNode
} QNode;
// A Queue (A FIFO collection of Queue Nodes)
typedef struct Queue
{
unsigned count; // Number of filled frames
unsigned numberOfFrames; // total number of frames
QNode *front, *rear;
} Queue;
// A hash (Collection of pointers to Queue Nodes)
typedef struct Hash
{
int capacity; // how many pages can be there
QNode* *array; // an array of queue nodes
} Hash;
// A utility function to create a new Queue Node. The queue Node
// will store the given 'pageNumber'
QNode* newQNode( unsigned pageNumber )
{
// Allocate memory and assign 'pageNumber'
QNode* temp = (QNode *)malloc( sizeof( QNode ) );
temp->pageNumber = pageNumber;
// Initialize prev and next as NULL
temp->prev = temp->next = NULL;
return temp;
}
// A utility function to create an empty Queue.
// The queue can have at most 'numberOfFrames' nodes
Queue* createQueue( int numberOfFrames )
{
Queue* queue = (Queue *)malloc( sizeof( Queue ) );
// The queue is empty
queue->count = 0;
queue->front = queue->rear = NULL;
// Number of frames that can be stored in memory
queue->numberOfFrames = numberOfFrames;
return queue;
}
// A utility function to create an empty Hash of given capacity
Hash* createHash( int capacity )
{
// Allocate memory for hash
Hash* hash = (Hash *) malloc( sizeof( Hash ) );
hash->capacity = capacity;
// Create an array of pointers for refering queue nodes
hash->array = (QNode **) malloc( hash->capacity * sizeof( QNode* ) );
// Initialize all hash entries as empty
int i;
for( i = 0; i < hash->capacity; ++i )
hash->array[i] = NULL;
return hash;
}
// A function to check if there is slot available in memory
int AreAllFramesFull( Queue* queue )
{
return queue->count == queue->numberOfFrames;
}
// A utility function to check if queue is empty
int isQueueEmpty( Queue* queue )
{
return queue->rear == NULL;
}
// A utility function to delete a frame from queue
void deQueue( Queue* queue )
{
if( isQueueEmpty( queue ) )
return;
// If this is the only node in list, then change front
if (queue->front == queue->rear)
queue->front = NULL;
// Change rear and remove the previous rear
QNode* temp = queue->rear;
queue->rear = queue->rear->prev;
if (queue->rear)
queue->rear->next = NULL;
free( temp );
// decrement the number of full frames by 1
queue->count--;
}
// A function to add a page with given 'pageNumber' to both queue
// and hash
void Enqueue( Queue* queue, Hash* hash, unsigned pageNumber )
{
// If all frames are full, remove the page at the rear
if ( AreAllFramesFull ( queue ) )
{
// remove page from hash
hash->array[ queue->rear->pageNumber ] = NULL;
deQueue( queue );
}
// Create a new node with given page number,
// And add the new node to the front of queue
QNode* temp = newQNode( pageNumber );
temp->next = queue->front;
// If queue is empty, change both front and rear pointers
if ( isQueueEmpty( queue ) )
queue->rear = queue->front = temp;
else // Else change the front
{
queue->front->prev = temp;
queue->front = temp;
}
// Add page entry to hash also
hash->array[ pageNumber ] = temp;
// increment number of full frames
queue->count++;
}
// This function is called when a page with given 'pageNumber' is referenced
// from cache (or memory). There are two cases:
// 1. Frame is not there in memory, we bring it in memory and add to the front
// of queue
// 2. Frame is there in memory, we move the frame to front of queue
void ReferencePage( Queue* queue, Hash* hash, unsigned pageNumber )
{
QNode* reqPage = hash->array[ pageNumber ];
// the page is not in cache, bring it
if ( reqPage == NULL )
Enqueue( queue, hash, pageNumber );
// page is there and not at front, change pointer
else if (reqPage != queue->front)
{
// Unlink rquested page from its current location
// in queue.
reqPage->prev->next = reqPage->next;
if (reqPage->next)
reqPage->next->prev = reqPage->prev;
// If the requested page is rear, then change rear
// as this node will be moved to front
if (reqPage == queue->rear)
{
queue->rear = reqPage->prev;
queue->rear->next = NULL;
}
// Put the requested page before current front
reqPage->next = queue->front;
reqPage->prev = NULL;
// Change prev of current front
reqPage->next->prev = reqPage;
// Change front to the requested page
queue->front = reqPage;
}
}
// Driver program to test above functions
int main()
{
// Let cache can hold 4 pages
Queue* q = createQueue( 4 );
// Let 10 different pages can be requested (pages to be
// referenced are numbered from 0 to 9
Hash* hash = createHash( 10 );
// Let us refer pages 1, 2, 3, 1, 4, 5
ReferencePage( q, hash, 1);
ReferencePage( q, hash, 2);
ReferencePage( q, hash, 3);
ReferencePage( q, hash, 1);
ReferencePage( q, hash, 4);
ReferencePage( q, hash, 5);
// Let us print cache frames after the above referenced pages
printf("%d ", q->front->pageNumber);
printf("%d ", q->front->next->pageNumber);
printf("%d ", q->front->next->next->pageNumber);
printf("%d ", q->front->next->next->next->pageNumber);
return 0;
}
Output:
5 4 1 3
Fonte
http://www.geeksforgeeks.org/implement-lru-cache/
Nome | Comentário | |
---|---|---|
Ainda não há nenhum problema relacionado a esse conteúdo |