The Problem For this assignment, you will write a C++ program to simulate a Leve
ID: 3693166 • Letter: T
Question
The Problem For this assignment, you will write a C++ program to simulate a Level 1 write-back cache. You do not need to write any part of this assignment in assembler language. You may assume that the memory being simulated uses 32-bit words and byte addressing, just like the Intel x86 family. -- Input The input will be a series of parameters and test data within a file. The input will be in character format. The input data will comprise: a. Line size of the cache. b. Total size of the cache. c. Associativity of the cache. d. Total size of main memory. e. Address, type of access, and data for simulated memory accesses. f. Address of data to be displayed. There are only one instance of items a through d. Items e and f will repeat multiple times. All input data will comprise a character code (A-F) and one data value (or three for item e). -- Processing Read in the four primary variables (items a through d above). Validate them with the following rules: 1. All values must be greater than zero 2. All values must be multiples of a power of 2. Thus, 2, 4, 8, 16, 32, 64, and so forth are valid values; odd numbers such as 1, 13, or 111 are not valid, and even numbers which are not a multiple of a power of 2 are invalid, such as 6, 22, or 46. Thus, 384 is valid (multiple of 2 to the seventh power, or 128), while 386 is not. However, for this assignment, you only need to check that the values are even numbers. 3. Line size (a) may not exceed ten percent of the cache size. 4. Cache size may not exceed ten percent of the total size of main memory. The program should issue an error message and end if any of these tests fail, or if any of parameters a through d are omitted. Once parameters a through d have been validated, initialize the simulated memory system. Acquire memory for the cache and for the memory. You also may find it useful to establish a separate array for an associative memory. (These should all be separate variables.) Set all memory to zeroes, minus 1, or some other identifiable value. Then begin a processing loop. Read the input data and process all memory accesses. For write accesses, store the value in the cache. For read accesses, get the data from the cache if present, or from main memory if not, and move the data into the cache in that case. If a write access references a cache line which already has data, copy that data from the cache to the simulated main memory before storing the incoming value into the simulated cache. For item f, display the address, value in the simulated cache for that address, and data in simulated main memory for that address. -- Output Your program should produce the following lines of output as appropriate: Output Line 1: Invalid value n for item Replace item with the name (line size, cache size, et cetera) and n with the value from the file. Output Line 2: Item n too large Replace item with cache size or line size, and n with the value from the file. Output Line 3: Input address xxxxxxxx invalid Replace xxxxxxxx with the address field from the memory access line (input type E) Output Line 4: Address: xxxxxxxx memory:nnnnnnnn cache:mmmmmmmm Replace xxxxxxxx with the address field from the memory data display field (input type F), nnnnnnnn with the simulated memory contents for that address, and mmmmmmmm with the simulated cache contents for that address. If the cache line is not valid, display -1 for that value. Sample Input File: A 16 B 2048 C 2 D 32768 E 0 W 22222222 E 8 W 1234 E 32 W 1233 E 16 W 888 F 0 E 4 W 33333333 F 8 E 1028 W 3231 E 16388 W 5657 F 0 F 4 F 8 F 12 F 16 F 1024 F 1028 F 16384 F 16388Explanation / Answer
// 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);
// 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);
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.