This project implements and compares Page Replacement Algorithms as part of an Operating Systems Problem-Based Learning (PBL) assignment. It demonstrates how different strategies handle memory management when pages are requested by a process but limited frames are available.

• Loads a reference string of page requests from user input
• Accepts the number of frames available in memory
• Simulates four algorithms step‑by‑step:
  • FIFO (First-In, First-Out) → replaces the oldest page in memory
  • LRU (Least Recently Used) → replaces the page unused for the longest time
  • Optimal → replaces the page not needed for the longest time in the future
  • LFU (Least Frequently Used) → replaces the page with the lowest usage frequency
• Prints a trace table showing frames after each request and whether it was a HIT or FAULT
• Summarizes total page faults for each algorithm
• Compares results side‑by‑side to highlight differences in efficiency
• Works seamlessly on Windows 11 (MinGW/MSYS2) and Linux (Arch/Ubuntu) using the provided Makefile

page-replacement-algorithms-analysis/
│
├── docs/                        # Documentation folder (reports, diagrams, extended notes)
│
├── src/                         # Source code folder
│   ├── algorithms.h             # Header file declaring prototypes for all algorithms
│   ├── fifo.c                   # FIFO algorithm implementation
│   ├── fifo.o                   # Compiled object file for FIFO
│   ├── lfu.c                    # LFU algorithm implementation
│   ├── lfu.o                    # Compiled object file for LFU
│   ├── lru.c                    # LRU algorithm implementation
│   ├── lru.o                    # Compiled object file for LRU
│   ├── optimal.c                # Optimal algorithm implementation
│   ├── optimal.o                # Compiled object file for Optimal
│   ├── utils.c                  # Utility functions (printing, helpers, frequency tracking)
│   ├── utils.h                  # Header file for utility functions
│   ├── utils.o                  # Compiled object file for utils
│   ├── main.c                   # Entry point: handles input, calls algorithms, prints results
│   ├── main.o                   # Compiled object file for main
│   ├── Makefile                 # Cross-platform build script (Windows + Linux)
│   ├── page_replacement         # Linux executable (built via `make`)
│   └── page_replacement.exe     # Windows executable (built via `mingw32-make`)
│
└── README.md                    # Project documentation (overview, usage, algorithms, contributors)

• src/ contains all source code and compiled artifacts.
• .c files → algorithm implementations and utilities.
• .h files → function prototypes and shared declarations.
• .o files → intermediate object files generated during compilation.
• Executables (page_replacement, page_replacement.exe) are generated depending on OS.
• docs/ can be used for reports, diagrams, or extended documentation.
• README.md provides usage instructions, algorithm explanations, and contributor credits.

To build and run this project successfully, ensure the following prerequisites are installed and configured:

• A working Git installation (for cloning and version control).
• Basic knowledge of C programming and Makefiles.

• GCC (GNU Compiler Collection)
  Install via package manager:

  sudo pacman -S gcc        # Arch Linux
  sudo apt-get install gcc  # Ubuntu/Debian

• Make (GNU Make)

  sudo pacman -S make       # Arch Linux
  sudo apt-get install make # Ubuntu/Debian

• MSYS2/MinGW-w64 environment
  Download and install from MSYS2.
• Update packages:

  pacman -Syu

• Install required toolchain:

  pacman -S mingw-w64-ucrt-x86_64-gcc mingw-w64-ucrt-x86_64-make

• Use PowerShell or MSYS2 terminal to run mingw32-make.

• VS Code or any IDE/editor for editing source files.
• GitHub Desktop or CLI for managing commits and pushes.
• Markdown previewer for viewing README.md formatting.

git clone https://github.com/Code-Crew-Nexus/page-replacement-algorithms-analysis.git
cd page-replacement-algorithms-analysis/src

This project uses a cross-platform Makefile that works on both Windows 11 (MinGW/MSYS2) and Linux (Arch, Ubuntu, etc.).

make clean
make
make run

mingw32-make clean
mingw32-make
mingw32-make run

The Makefile automatically detects the OS and builds the correct executable (page_replacement on Linux, page_replacement.exe on Windows).

The program simulates page replacement algorithms by:

1. Taking input:
   • Number of pages in the reference string
   • The reference string itself
   • Number of frames available
2. Iterating through each page request:
   • Checking if the page is already in memory (HIT).
   • If not, applying the chosen algorithm to decide which page to replace (FAULT).
3. Printing a step-by-step trace of frames and results.
4. Summarizing total page faults for each algorithm.

• Definition: Replace the oldest page in memory (the one loaded earliest).
• Formula: Replace page[i - frame_count] when a fault occurs.
• Example:
  Reference string: 1 2 3 4 1 2 5 with 3 frames → FIFO faults = 6.

• Definition: Replace the page that has not been used for the longest time.
• Formula: Replace the page with the minimum last-used timestamp.
• Example:
  Reference string: 1 2 3 4 1 2 5 with 3 frames → LRU faults = 5.

• Definition: Replace the page that will not be used for the longest time in the future.
• Formula: Replace the page with the maximum next-use distance.
• Example:
  Reference string: 1 2 3 4 1 2 5 with 3 frames → Optimal faults = 4.

• Definition: Replace the page with the lowest usage frequency.
• Formula: Replace the page with the minimum frequency count.
• Example:
  Reference string: 1 2 3 4 1 2 5 with 3 frames → LFU faults = 5.

Input:

Enter number of pages in reference string: 12
Enter the reference string (space-separated): 1 2 3 4 1 2 5 1 2 3 4 5
Enter number of frames: 3

Output:

---- FIFO Simulation ----
Page   Frames      Result
1      1  -  -     FAULT   
2      1  2  -     FAULT   
3      1  2  3     FAULT   
4      4  2  3     FAULT   
1      4  1  3     FAULT   
2      4  1  2     FAULT   
5      5  1  2     FAULT   
1      5  1  2     HIT     
2      5  1  2     HIT     
3      5  3  2     FAULT   
4      5  3  4     FAULT   
5      5  3  4     HIT     
Total Page Faults (FIFO): 9

----  LRU Simulation ----
Page   Frames      Result
1      1  -  -     FAULT   
2      1  2  -     FAULT   
3      1  2  3     FAULT   
4      4  2  3     FAULT   
1      4  1  3     FAULT   
2      4  1  2     FAULT   
5      5  1  2     FAULT   
1      5  1  2     HIT     
2      5  1  2     HIT     
3      3  1  2     FAULT   
4      3  4  2     FAULT   
5      3  4  5     FAULT   
Total Page Faults (LRU): 10

--- Optimal Simulation ---
Page   Frames      Result
1      1  -  -     FAULT   
2      1  2  -     FAULT   
3      1  2  3     FAULT   
4      1  2  4     FAULT   
1      1  2  4     HIT     
2      1  2  4     HIT     
5      1  2  5     FAULT   
1      1  2  5     HIT     
2      1  2  5     HIT     
3      3  2  5     FAULT   
4      4  2  5     FAULT   
5      4  2  5     HIT     
Total Page Faults (Optimal): 7

----  LFU Simulation ----
Page   Frames      Result
1      1  -  -     FAULT   
2      1  2  -     FAULT   
3      1  2  3     FAULT   
4      4  2  3     FAULT   
1      1  2  3     FAULT   
2      1  2  3     HIT     
5      5  2  3     FAULT   
1      1  2  3     FAULT   
2      1  2  3     HIT     
3      1  2  3     HIT     
4      4  2  3     FAULT   
5      5  2  3     FAULT   
Total Page Faults (LFU): 9

Output (summary):

=== Final Page Replacement Analysis ===
FIFO Page Faults   : 9
LRU Page Faults    : 10
Optimal Page Faults: 7
LFU Page Faults    : 9

This project provides a comprehensive analysis of Page Replacement Algorithms — FIFO, LRU, Optimal, and LFU — by simulating their behavior on given reference strings and comparing their performance. It demonstrates how different strategies handle page faults when memory frames are limited, highlighting the trade‑offs between simplicity, efficiency, and practicality in operating system design.

• FIFO is straightforward but often inefficient, as it may evict frequently used pages.
• LRU improves efficiency by tracking usage history, closely approximating optimal behavior.
• Optimal achieves the lowest possible faults but is theoretical, requiring future knowledge.
• LFU favors frequently used pages but can penalize recently important ones.

The project is designed with a cross‑platform Makefile, ensuring seamless compilation and execution on both Windows 11 (MinGW/MSYS2) and Linux (Arch/Ubuntu). With clear documentation, structured source code, and sample input/output demonstrations, this repository serves as both an academic resource and a practical tool for understanding memory management strategies in operating systems.

• M. Sai Krishna
• Md. Abdul Rayain
• Rishit Ghosh
• Y. Karthik

Future contributors welcome! Fork the repo, submit pull requests, and help improve the project.

• Optimal is theoretical and always gives the lowest page faults.
• FIFO is simplest but often inefficient.
• LRU and LFU approximate real-world scenarios better.
• This project demonstrates the trade-offs in memory management strategies.