LFU Page Replacement Algorithm in C

TheLazyBusyCoder's Blog

Welcome to my coding adventures! In this post, we'll explore a C program.

Optimal Page Replacement(OPT) in C

The page which has less frequency gets replaced

        
#include <stdio.h>
#include<stdbool.h>

typedef struct Frame {
	int p , f , t;
} Frame;

void display(Frame frame[] , int framesize , bool isHit) {
	int i;
	for(i = 0; i < framesize; i++) {
		printf("%2d | " , frame[i].p);
	}
	if(isHit == true) printf(" HIT\n");
	else printf(" *\n");
}

bool find(Frame frame[] , int framesize, int cur) {
	int i = 0;
	for(i = 0; i < framesize; i++) {
		if(frame[i].p == cur) return true;
	}
	return false;
}

int replace(Frame frame[] , int framesize) {
	int i;
	for(i = 0; i < framesize; i++) if(frame[i].p == -1) return i;

	int rep = 0;
	for(i = 1; i < framesize; i++) {
		if(frame[i].f < frame[rep].f) {
			rep = i;
		} else if(frame[i].f == frame[rep].f) {
			if(frame[i].t < frame[rep].t) rep = i;
		}
	}
	return rep;
}

void lfu(int arr[] , int n ,int framesize) {
	Frame frame[framesize];
	int i;
	int hit = 0 , pf = 0; 
	int j;

	for(i = 0; i < framesize; i++) frame[i].p = -1 , frame[i].f = 0 , frame[i].t = 0;
	int rep = 0;
	for(i = 0; i < n; i++) {
		int cur = arr[i];
		if(find(frame , framesize , cur) == false) {
			pf++;
			rep = replace(frame , framesize);
			frame[rep].p = cur;
			frame[rep].f = 0;
			frame[rep].t = i;
			display(frame , framesize , false);
		} else {
			hit++;
            int x = 0;
            for(; x < framesize; x++) 
              if(frame[x].p == cur) 
                rep = x;
            frame[rep].f++;
            frame[rep].t = i;
			display(frame , framesize , true);
		}
	}
}

int main() {
	int arr[] = {3,4,5,4,3,4,7,2,4,5,6,7,2,4,6};
	int n = 15;
	int framesize = 3;
	lfu(arr , n , framesize);
}