In this problem, we will compare the performance of the two algorithms that you implemented in Problem
Question:
In this problem, we will compare the performance of the two algorithms that you implemented in Problem 1 and Problem 2, respectively. In comparing the performance, we will vary the number of frames from 1 to 7.
For each number of frames (i.e., from 1 to 7), execute the LRU and OPT algorithms with the input of 1,000 reference strings. Each string should consist of 10 randomly selected integers between 0 and 20. In other words, for each number of frames, run both algorithms 1,000 times with those randomly generated 1,000 reference strings and record the number of page faults, and calculate the average number of page faults for both algorithms.
Display the results using a graph that may look something like this.
Problem 1 code:
#include
#include
int LRU(int time[], int n){
int i;
int min = time[0];
int min_index = 0;
for(i = 1; i < n; ++i){
if(time[i] < min){
min = time[i];
min_index = i;
}
}
return min_index;
}
int main(){
int no_of_frames = 4;
int no_of_pages = 10;
int frames[4];
int reference_str[10];
int i,j;
int faults = 0;
printf("Enter reference string: ");
for(i = 0; i < no_of_pages; ++i){
scanf("%d", &reference_str[i]);
}
for(i = 0; i < no_of_frames; ++i){
frames[i] = -1;
}
int ctr = 0;
int time[4];
for(i = 0; i < no_of_pages; ++i){
int flag1 = 0;
int flag2 = 0;
for(j = 0; j < no_of_frames; ++j){
if(frames[j] == reference_str[i]){
ctr++;
time[j] = ctr;
flag1 = flag2 = 1;
break;
}
}
if(flag1 == 0){
for(j = 0; j < no_of_frames; ++j){
if(frames[j] == -1){
ctr++;
faults++;
frames[j] = reference_str[i];
time[j] = ctr;
flag2 = 1;
break;
}
}
}
if(flag2 == 0){
int min_index = LRU(time, no_of_frames);
ctr++;
faults++;
frames[min_index] = reference_str[i];
time[min_index] = ctr;
}
printf("Displaying the 4 frames contents after each reference:");
printf("After refernce of %d ",reference_str[i]);
for(j = 0; j < no_of_frames; ++j){
printf("%dt", frames[j]);
}
printf("");
}
printf("%d Page Faults occurred ", faults);
return 0;
}
Problem 2 code:
#include
int main(){
int numberOfFrames=4, numberOfPages=10, framesArray[4], pagesArray[10], tempArray[10], f1, f2, f3, i, j, k, position, maximum, numberOfFaults = 0;
printf("Enter the reference string: ");
for(i = 0; i < numberOfPages; ++i){
do{
scanf("%d", &pagesArray[i]);
}
while(pagesArray[i]<0||pagesArray[i]>20);
}
for(i = 0; i < numberOfFrames; ++i){
framesArray[i] = -1;
}
for(i = 0; i < numberOfPages; ++i){
f1 = f2 = 0;
for(j = 0; j < numberOfFrames; ++j){
if(framesArray[j] == pagesArray[i]){
f1 = f2 = 1;
break;
}
}
if(f1 == 0){
for(j = 0; j < numberOfFrames; ++j){
if(framesArray[j] == -1){
numberOfFaults++;
framesArray[j] = pagesArray[i];
f2 = 1;
break;
}
}
}
if(f2 == 0){
f3 =0;
for(j = 0; j < numberOfFrames; ++j){
tempArray[j] = -1;
for(k = i + 1; k < numberOfPages; ++k){
if(framesArray[j] == pagesArray[k]){
tempArray[j] = k;
break;
}
}
}
for(j = 0; j < numberOfFrames; ++j){
if(tempArray[j] == -1){
position = j;
f3 = 1;
break;
}
}
if(f3 ==0){
maximum = tempArray[0];
position = 0;
for(j = 1; j < numberOfFrames; ++j){
if(tempArray[j] > maximum){
maximum = tempArray[j];
position = j;
}
}
}
framesArray[position] = pagesArray[i];
numberOfFaults++;
}
printf("");
for(j = 0; j < numberOfFrames; ++j){
printf("%dt", framesArray[j]);
}
}
printf("%d page faults occurred!", numberOfFaults);
return 0;
}
Probability and Statistics
ISBN: 978-0321500465
4th edition
Authors: Morris H. DeGroot, Mark J. Schervish