Write a program that simulates the FIFO and LRU page-replacement algorithms. You
ID: 3717800 • Letter: W
Question
Write a program that simulates the FIFO and LRU page-replacement algorithms. Your program should accept four command-line arguments specifying the page size, the total virtual memory size, the page-replacement algorithm to use, and the number of frames allocated. The page and virtual memory sizes should be specified by their binary logs. Thus, the following command would simulate a page size of 1KB and a virtual memory size of 64KB, using LRU page-replacement with 8 frames allocated:
> ./simulate-paging 10 16 LRU 8
Your program should read lines from standard input, each containing a hexadecimal number representing the virtual address of a memory reference. With each memory reference, your program should update an internal page table, keeping track of the number of page faults generated using pure demand paging. Your program should also maintain any other data structures necessary to implement the two page-replacement algorithms. Your program should terminate upon encountering EOF. It should then print the total number of page faults and exit.
To assist with testing, two sample input files are available on iLearn. sample_references.txt contains a list of virtual addresses that when used with a page size of 256 bytes correspond to the reference string used during lecture and in the book. ( Google docs link to file: https://drive.google.com/file/d/1QEat_sPYrRaExZOoXcT7syWCWq__JX7h/view?usp=sharing )
For example:
> ./simulate_paging 8 12 LRU 3 < sample_references.txt
12 page faults
belady_references.txt contains a list of virtual addresses that when used with a page size of 16KB corresponds to the reference string that demonstrates Belady's anomaly (Google docs link to file: https://drive.google.com/file/d/1yUzinym2fmAHs9aBorRiApWTkAV6hanF/view ) :
> ./simulate_paging 16 20 FIFO 3 < belady_references.txt
9 page faults
> ./simulate_paging 16 20 FIFO 4 < belady_references.txt
10 page faults
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
//Declare variables
int pageSize, memSize, pagingMode, frameNumber;
//Define method
int isInArray(int findme, int array[], int size){
//Declare variable
int index = 0;
//Do
do{
//If condition satisfies
if (array[index] == findme)
//Return
return index;
index++;
}while (index < size);
//Return
return -1;
}
//Define method
int searchArrayBackwardsFrom(int findme, int start, int array[], int size){
//Assign value
int index = start;
//Do
do{
//If condition satisfies
if (array[index] == findme)
//Return
return index;
//Decrement
index--;
}while (index >= 0);
//Return
return -1;
}
//Define method
int fifo(int prefs[], int size){
//Declare variables
int replace = 0, numOfPageFaults = 0, i;
//Create instance
int *frames = (int *)malloc(frameNumber * sizeof(int));
//Loop
for (i = 0; i < 3; i++){
//Assign value
frames[i] = -1;
}
for (i = 0; i < size; i++){
//If condition satisfies
if (isInArray(prefs[i], frames, frameNumber) < 0){
//Assign value
frames[replace % frameNumber] = prefs[i];
//Increment value
replace++;
//Increment value
numOfPageFaults++;
}
}
//Return
return numOfPageFaults;
}
//Define method
int lru (int prefs[], int size){
//Declare variables
int numOfPageFaults = 0, index, i, j, innerIndex = 0, referece, t;
//Create instance
int *frames = (int *)malloc(frameNumber * sizeof(int));
//Loop
for (i = 0; i < 3; i++){
//Assign value
frames[i] = -1;
}
//Create instance
int *b = (int *)malloc(frameNumber * sizeof(int));
//Create instance
int *c2 = (int *)malloc(frameNumber * sizeof(int));
//Assign value
frames[innerIndex] = prefs[innerIndex];
//Increment
numOfPageFaults++;
//Increment
innerIndex++;
//Loop
for (i = 1; i< size; i++){
//Assign value
index = 0;
//If condition satisfies
if (isInArray(prefs[i], frames, frameNumber) < 0){
//Assign value
index = frameNumber;
//Increment value
numOfPageFaults++;
//If condition satisfies
if (innerIndex < frameNumber){
//Assign value
frames[innerIndex] = prefs[i];
//Increment value
innerIndex++;
}
else{
//Loop
for (referece = 0; referece < frameNumber; referece++){
//Assign value
c2[referece] = 0;
//Loop
for (j = i - 1; j < pageSize; j--){
//If condition satisfies
if (frames[referece] != prefs[j])
//Increment value
c2[referece]++;
//Otherwise
else
break;
}
}
//Loop
for (referece = 0; referece < frameNumber; referece++)
//Assign value
b[referece] = c2[referece];
//Loop
for (referece = 0; referece < frameNumber; referece++){
//Loop
for (j = referece; j < frameNumber; j++){
//If condition satisfies
if (b[referece]<b[j]){
//Assign value
t = b[referece];
//Assign value
b[referece] = b[j];
//Assign value
b[j] = t;
}
}
}
//Loop
for (referece = 0; referece < frameNumber; referece++){
//If condition satisfies
if (c2[referece] == b[0])
//Assign value
frames[referece] = prefs[i];
}
}
}
}
//Return
return numOfPageFaults;
}
//Define main
int main(int argc, char *argv[]){
//Assign value
pageSize = atoi(argv[1])/10;
//Assign value
memSize = atoi(argv[2])*4;
//If condition satisfies
if (strcmp(argv[3], "FIFO") == 0){
//Assign value
pagingMode = 0;
}
//Otherwise
else{
//Assign value
pagingMode = 1;
}
//Assign value
frameNumber = atoi(argv[4]);
//If condition satisfies
if (pagingMode == 0){
//Display message
printf("Page Size: %dkb Memory Size: %dkb Algorithm: FIFO Frames Allocated: %d ",pageSize,memSize,frameNumber);
}
//Otherwise
else{
//Display message
printf("Page Size: %dkb Memory Size: %dkb Algorithm: LRU Frames Allocated: %d ",pageSize,memSize,frameNumber);
}
//Declare variable
int prefs[100];
//Declare variable
int g = 0;
//Loop
while (g < 100){
//Assign value
prefs[g] = 0;
//Increment value
g++;
}
//Declare variable
int check = 0;
//Declare variable
char exit[8] = " ";
//Declare variable
int number;
//Display message
printf("Enter the addresses (eg: 0xFC68): ");
//Loop
while (fgets(exit, sizeof(exit), stdin)){
//Exit
exit[strlen(exit) - 1] = '';
//If condition satisfies
if (strcmp(exit, "") == 0)
//Break
break;
//Loop
int z=0;
for (z = 0; z < 8; z++){
//If condition satisfies
if (exit[z] == 'A' || exit[z] == 'a')
//Assign value
exit[z] = '3';
//If condition satisfies
else if(exit[z] == 'B' || exit[z] == 'b')
//Assign value
exit[z] = '5';
//If condition satisfies
else if(exit[z] == 'C' || exit[z] == 'c')
//Assign value
exit[z] = '7';
//If condition satisfies
else if(exit[z] == 'D' || exit[z] == 'd')
//Assign value
exit[z] = '9';
//If condition satisfies
else if(exit[z] == 'E' || exit[z] == 'e')
//Assign value
exit[z] = '0';
//If condition satisfies
else if(exit[z] == 'F' || exit[z] == 'f')
//Assign value
exit[z] = '1';
//If condition satisfies
else if(exit[z] == 'X' || exit[z] == 'x')
//Assign value
exit[z] = '4';
}
//Assign value
prefs[check] = atoi(exit);
//Increment
check++;
}
//If condition satisfies
if (pagingMode == 0){
//Display message
printf("Number of faults: %d ", fifo(prefs, check));
}
//Otherwise
else if (pagingMode == 1){
//Display message
printf("Number of faults: %d ", lru(prefs, check));
}
//Pause console window
system("pause");
//Return
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.