Paging Algorithms

/*
This program demonstrates page faults with 3 paging algorithms

    First-In First-Out
    Optimal
    Least Recently Used

Inputs are the number of frames, number of page references and actual page references,
which must be given as numbers, preferably using a set of consecutive numbers

Eg:-
Number of frames     = 3
Number of references = 6
Actual references    = 1 2 3 2 3 1

The program does not use any classes.
*/
using namespace std;
#include <iostream>
#include <stdlib.h>

const int MAX_FRAMES = 10, MAX_PAGEREF = 50, INFINITY = 1000;

int frames, pageref, frame_array[MAX_FRAMES], pageref_array[MAX_PAGEREF];

void    fifo_algo(void);
void optimal_algo(void);
void     lru_algo(void);
void print_frames(void);
int fault_occured(int );
void  fatal_error(int );

int main(int argc, char *argv[])
{
    cout << "Enter the number of frames: ";
    cin >> frames;

    cout << "Enter the number of page references: ";
    cin >> pageref;

    cout << "Enter the page references: ";
    for (int i = 0; i < pageref; i++) {
        cin >> pageref_array[i];
        }

    fifo_algo(); //Prints First-In, First-Out Algorithm
    
    optimal_algo(); //Prints Optimal Algorithm
    
    lru_algo(); //Print Least Recently Used Algorithm

    return 0;
}

void fifo_algo()
{
    int pagefault = 0, new_frame = 0;

    cout << "---***---FIRST IN FIRST OUT ALGORITHM---***---" << endl;
    for (int frame_index = 0; frame_index < frames; frame_index++) {
        frame_array[frame_index] = 0;
    }
    print_frames();
    
    for (int i = 0; i < pageref; i++) {
        cout << "New page referenced is " << pageref_array[i];
        if (fault_occured(pageref_array[i])) {
            pagefault++;
            if (new_frame == frames) {
                new_frame = 0;
            }
            frame_array[new_frame++] = pageref_array[i];
        }
        print_frames();
    }
    cout << endl << "NUMBER OF PAGE FAULTS IS " << pagefault << endl << endl;
}

void optimal_algo()
{
    int pagefault = 0, pages_in_frame = 0, largest_future_time, victim_frame;
  
    cout << "---***---OPTIMAL ALGORITHM---***---" << endl;
    for (int frame_index = 0; frame_index < frames; frame_index++) {
        frame_array[frame_index] = 0;
    }
    print_frames();
    
    for (int i = 0; i < pageref; i++) {
        cout << "New page referenced is " << pageref_array[i];
        if (fault_occured(pageref_array[i])) {
            pagefault ++;
            if (pages_in_frame != frames) {
                frame_array[pages_in_frame++] = pageref_array[i];
            }
            else {
                largest_future_time = 0;
                for (int j = 0; j < frames; j++) {
                    int k;
                    for (k = i + 1; k < pageref; k++) {
                        if (frame_array[j] == pageref_array[k]) {
                            break;
                        }
                    }
                    if (k > largest_future_time) {
                        largest_future_time = k;
                        victim_frame = j;
                    }
                }
                frame_array[victim_frame] = pageref_array[i];
            }
        }
        print_frames();
    }
    cout << endl << "NUMBER OF PAGE FAULTS IS " << pagefault << endl << endl;
}

void lru_algo()
{
    int pagefault = 0, pages_in_frame = 0, largest_past_time, victim_frame;

    cout << "---***---LEAST RECENTLY USED ALGORITHM---***---" << endl;
    for (int frame_index = 0; frame_index < frames; frame_index++) {
        frame_array[frame_index] = 0;
    }
    print_frames();
    
    for (int i = 0; i < pageref; i++) {
        cout << "New page referenced is " << pageref_array[i];
        if (fault_occured(pageref_array[i])) {
            pagefault ++;
            if (pages_in_frame != frames) {
                frame_array[pages_in_frame++] = pageref_array[i];
            }
            else {
                largest_past_time = INFINITY;
                for (int j = 0; j < frames; j++) {
                    int k;
                    for (k = i - 1; k >= 0; k--) {
                        if (frame_array[j] == pageref_array[k]) {
                            break;
                        }
                    }
                    if (k < largest_past_time) {
                        largest_past_time = k;
                        victim_frame = j;
                    }
                }
                frame_array[victim_frame] = pageref_array[i];
            }
        }
        print_frames();
    }
    cout << endl << "NUMBER OF PAGE FAULTS IS " << pagefault << endl << endl;
}

void print_frames()
{
    for (int i = 0; i < frames; i++) cout << " " << frame_array[i] << " " ;
}

int fault_occured(int faulted_page)
{
    for (int i = 0; i < frames; i++) {
        if (frame_array[i] == faulted_page) {
            cout << "  ++++++++NO PAGE FAULT++++++++" << endl;
            return 0;
        }
    }
    cout << "  *****PAGE FAULT*****" << endl;
    return 1;
}