Memory Page Replacement Strategies for learning

PageReplacement.c

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define FRAMES 4
#define	ITERATIONS 10

// Check if the page is already in the frame
int hasPageInFrame(int *a,int request){
	int i;
	for(i = 0; i < FRAMES; i++)
		if(a[i] == request)
			return i+1;
	return 0;
}

// Find the page whose counter value is lowest
int findVictim(int* counter){
	int minIndex = 0,i;
	for(i = 0; i < FRAMES; i++)
		if(counter[i] < counter[minIndex])
			minIndex = i;
	return minIndex;
}

// Find the frame which is not going to be used for the longest time
int findFurthest(int *a,int *requests, int index){
	int frame,i,victim = 0,maxDistance = 0;
	for(frame = 0; frame < FRAMES; frame++){	
		int distance = 0;
		// If a frame is empty, select it
		if(a[frame] == -1) return frame;
		for(i = index; i < ITERATIONS; i++){
			if(a[frame] == requests[i]){
				distance = i;
				break;
			}								
		}
		// If a frame is not going to be used again, select it
		if(i == ITERATIONS) return frame;
		if(distance > maxDistance){
			maxDistance = distance;
			victim = frame;
		}
	}
	return victim;
}

void print(int *a){
	int i;
	for(i = 0; i < FRAMES; i++) printf("%d\t",a[i]);
	printf("\n");
}

// First in First out
void FIFO(int* requests){
	int i,ptr = 0,faults = 0;
	int a[FRAMES];
	for(i = 0; i < FRAMES; i++) a[i] = -1;
	for(i = 0; i < ITERATIONS; i++){
		int request = requests[i];
		if(hasPageInFrame(a,request)){
			printf("HIT:  (%d)\n",request);
		} else {
			printf("MISS: (%d)\n",request);
			a[ptr++%FRAMES] = request;			
			faults++;
		}
		print(a);
	}
	printf("Faults: %d\n",faults);
}

// Least recently used
void LRU(int* requests){
	int a[FRAMES],counter[FRAMES];
	int i,faults = 0;
	for(i = 0; i < FRAMES; i++) a[i] = -1;
	for(i = 0; i < FRAMES; i++) counter[i] = -1;
	for(i = 0; i < ITERATIONS; i++){
		int request = requests[i];
		int index = hasPageInFrame(a,request);
		if(index){
			counter[index-1] = i;
			printf("HIT:  (%d)\n",request);
		} else {
			printf("MISS: (%d)\n",request);
			int victim = findVictim(counter);
			a[victim] = request;
			counter[victim] = i;
			faults++;
		}
		print(a);
		print(counter);
	}
	printf("Faults: %d\n",faults);
}

// Optimal page replacement strategy
void optimal(int *requests){
	int a[FRAMES],i,faults = 0;
	for(i = 0; i < FRAMES; i++) a[i] = -1;
	for(i = 0; i < ITERATIONS; i++){
		int request = requests[i];
		int index = hasPageInFrame(a,request);
		if(index){
			printf("HIT:  (%d)\n",request);
		} else {
			printf("MISS: (%d)\n",request);
			int victim = findFurthest(a,requests,i+1);
			a[victim] = request;	
			faults++;
		}		
		print(a);
	}
	printf("Faults: %d\n",faults);
}

int main(){
	srand(time(NULL));
	int n = rand()%10,i; // Random number of total pages
	
	int requests[ITERATIONS];
	for(i = 0; i < ITERATIONS; i++)
		requests[i] = rand()%n; // Random requests
	
	printf("\nFIFO\n");
	FIFO(requests);
	
	printf("\nLRU\n");
	LRU(requests);
	
	printf("\nOptimal\n");
	optimal(requests);
	
	return 0;
}