Least Recently Used (LRU) page algorithm in c

TheLazyBusyCoder's Blog

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

Least Recently Used page algo in C

Watch this video for explanation

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

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

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

int replace(int arr[] , int n , int frame[] , int framesize , int start) {
    int i;
    for(i = 0; i < framesize; i++) {
        if(frame[i] == -1) return i;
    }
    int j;
    int max = 999;
    int rep = 0;
    for(i = 0; i < framesize; i++) {
        int cur = frame[i];
        for(j = start; j >= 0; j--) {
            if(cur == arr[j]) break;
        }
        if(j < max) {
            max = j;
            rep = i;
        }
    }
    return rep;
}

void lru(int arr[] , int n , int framesize) {
    int frame[framesize];
    int i;
    int hit = 0;
    int pf = 0;
    for(i = 0; i < framesize; i++) frame[i] = -1;

    for(i = 0; i < n; i++) {
        int cur = arr[i];
        if(find(frame , framesize , cur) == false) {
            pf++;
            int rep = replace(arr , n , frame , framesize , i - 1);
            frame[rep] = cur;
            display(frame , framesize , false);
        } else {
            hit++;
            display(frame , framesize , true);
        }
    }
    printf("\n\nTotal HIT's: %d\nTotal PageFault: %d\n" , hit , pf);
}

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