In this post, we implement the FIFO (First In, First Out) Page Replacement Algorithm in C++. When the OS needs to load a new page into memory but all frames are occupied, FIFO evicts the page that has been in memory the longest — the one that arrived first. It is one of the simplest page replacement strategies and serves as a baseline for comparing more sophisticated algorithms.

What is FIFO Page Replacement?

Physical memory is divided into frames. When a process references a page not currently in a frame (a page fault), it must be loaded. If all frames are full, an existing page must be evicted. FIFO chooses the oldest resident page for eviction, regardless of how frequently it has been used.

• Page Hit — Referenced page is already in a frame. No disk I/O needed.
• Page Fault (Miss) — Referenced page is not in any frame. Must load from disk.
• FIFO Queue — Tracks the order in which pages were loaded. Front = oldest; back = newest.

A notable weakness of FIFO is Bélady’s Anomaly — adding more frames can sometimes cause more page faults, counter-intuitively.

In this post, we implement the Banker’s Algorithm in C++ — a classic deadlock avoidance mechanism in operating systems proposed by Edsger Dijkstra. The algorithm is named after the analogy of a bank that never lends money in a way that could prevent it from satisfying all customers’ future needs.

What is the Banker’s Algorithm?

Before granting any resource request, the OS runs the Banker’s Algorithm to check whether doing so keeps the system in a safe state. A safe state is one where a safe sequence exists — an ordering of all processes such that each can eventually complete using currently available resources plus the resources released by earlier processes in the sequence.

If no safe sequence exists, the state is unsafe, meaning deadlock is possible. The OS denies the request in that case.

Three data structures are needed:

• Available[] — Current free units of each resource type.
• Allocated[][] — Resources currently held by each process.
• Maximum[][] — The maximum resources each process may ever request.
• Need[][] — Remaining resources a process may still request: Need[i][j] = Maximum[i][j] - Allocated[i][j]

In this post, we implement the Shortest Job First (SJF) CPU scheduling algorithm in C++. SJF always selects the process with the smallest burst time from the ready queue and executes it next. This greedy approach provably minimizes the average waiting time, making SJF theoretically optimal among all non-preemptive algorithms when all jobs are available simultaneously.

What is SJF Scheduling?

In SJF, the scheduler sorts all ready processes by their burst (execution) time in ascending order and then runs them in that sequence. The shortest job finishes earliest, releasing the CPU quickly for others and keeping the average wait low.

It is non-preemptive — once started, a process runs to completion. The preemptive variant is called Shortest Remaining Time First (SRTF).

• Waiting Time (WT): WT[i] = WT[i-1] + BurstTime[i-1] - (ArrivalTime[i] - ArrivalTime[i-1])
• Turnaround Time (TT): TT[i] = WT[i] + BurstTime[i]

The key risk with SJF is starvation: if short jobs keep arriving, long jobs may never execute.