Question & Answer: Maintain a page table as an array. Use page number as an index to the array. The array should include an R…..

// 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;
}