Paging Simulator - Complete Documentation

Table of Contents

1. Project Overview

2. System Architecture

3. Project Structure

4. Installation & Setup

5. Core Components

6. Paging Algorithms

7. Usage Guide

8. API Reference

9. Testing

10. Performance Analysis

11. Contributing

12. License

---

Project Overview

Purpose

The Paging Simulator is an educational tool designed to demonstrate and compare various page replacement algorithms used in operating systems for virtual memory management. It simulates demand paging and helps understand how different algorithms affect system performance.

Key Features

• Multiple Page Replacement Algorithms: Implements Basic, LRU (Least Recently Used), and Predictive paging strategies

• Performance Metrics: Tracks page faults, hit rates, and memory utilization

• Configurable Simulation: Adjustable parameters for memory size, page count, and process behavior

• Visual Analysis: Tools for visualizing simulation results and algorithm performance

• Educational Value: Clear code structure for learning operating systems concepts

Technical Specifications

• Language: C

• Build System: GNU Make

• Memory Model: Virtual memory with demand paging

• Page Size: Configurable (typically 4KB)

• Process Support: Multi-process simulation

• Physical Memory: Limited shared physical pages

---

System Architecture

High-Level Design

┌─────────────────────────────────────────────┐
│         User Interface / Test Harness        │
└──────────────────┬──────────────────────────┘
                   │
┌──────────────────▼──────────────────────────┐
│         Simulator Core (simulator.c)         │
│  - Process Management                        │
│  - Memory Management                         │
│  - Page Table Management                     │
│  - Statistics Collection                     │
└──────────────────┬──────────────────────────┘
                   │
┌──────────────────▼──────────────────────────┐
│      Paging Algorithm Interface (pageit)     │
└──────────────────┬──────────────────────────┘
                   │
      ┌────────────┼────────────┐
      │            │            │
┌─────▼─────┐ ┌───▼────┐ ┌────▼─────┐
│   Basic   │ │  LRU   │ │ Predict  │
│  Pager    │ │ Pager  │ │  Pager   │
└───────────┘ └────────┘ └──────────┘

Component Interaction Flow

1. Simulator initializes processes and memory

2. Programs execute and request pages

3. Paging Algorithm decides which pages to load/evict

4. Simulator performs page in/out operations

5. Statistics are collected and reported

---

Project Structure

paging-simulator/
├── Makefile                  # Build configuration
├── README.md                 # Project documentation
│
├── src/                      # Source files
│   ├── simulator.c           # Core simulator implementation
│   ├── simulator.h           # Simulator API and data structures
│   ├── programs.c            # Test program definitions
│   ├── pager-basic.c         # Basic paging algorithm
│   ├── pager-lru.c           # LRU paging algorithm
│   ├── pager-predict.c       # Predictive paging algorithm
│   └── api-test.c            # API testing implementation
│
├── include/                  # Header files
│   └── simulator.h           # Public API declarations
│
├── test/                     # Test programs
│   ├── test-basic            # Basic algorithm tests
│   ├── test-lru              # LRU algorithm tests
│   └── test-predict          # Predictive algorithm tests
│
├── scripts/                  # Utility scripts
│   ├── see.R                 # Visualization script
│   └── run_tests.sh          # Automated testing script
│
├── docs/                     # Documentation
│   ├── ARCHITECTURE.md       # System architecture
│   ├── API.md                # API reference
│   ├── ALGORITHMS.md         # Algorithm descriptions
│   └── PERFORMANCE.md        # Performance analysis
│
└── pseudo/                   # Pseudo code files
    ├── pgm1.pseudo           # Test program 1 pseudo code
    ├── pgm2.pseudo           # Test program 2 pseudo code
    └── pgm3.pseudo           # Test program 3 pseudo code

Directory Descriptions

/src - Source Code

Contains all core implementation files including the simulator engine and paging algorithms.

/include - Public Headers

Header files that define the public API for the simulator.

/test - Test Executables

Compiled test programs for each paging algorithm implementation.

/scripts - Utility Scripts

Helper scripts for visualization and automated testing.

/docs - Documentation

Detailed documentation covering architecture, APIs, and algorithms.

/pseudo - Pseudo Code

Human-readable pseudo code for test programs.

---

Installation & Setup

Prerequisites

# Required tools
- GCC compiler (version 7.0+)
- GNU Make (version 4.0+)
- Git

# Optional (for visualization)
- R (version 3.0+)
- R packages: ggplot2, gridExtra

Build Instructions

Clone Repository

git clone https://github.com/Mido191020/paging-simulator.git
cd paging-simulator

Compile All Components

make

Compile Specific Target

make test-basic    # Build basic pager
make test-lru      # Build LRU pager
make test-predict  # Build predictive pager
make test-api      # Build API test

Clean Build

make clean         # Remove all compiled files

Verification

# Run basic test
./test-basic

# Check if executables exist
ls -l test-*

---

Core Components

1. Simulator Core (simulator.c)

Purpose

The simulator core manages the virtual memory system, process execution, and page fault handling.

Key Responsibilities

• Process Management: Creates and manages simulated processes

• Memory Management: Maintains physical memory frames and page tables

• Page Fault Handling: Detects and processes page faults

• Statistics Tracking: Collects performance metrics

• Time Management: Simulates CPU ticks and execution time

Main Functions

// Initialize the simulator
void simulator_init(int physical_pages);

// Run simulation for specified ticks
void simulator_run(int ticks);

// Get current statistics
stats_t simulator_get_stats(void);

// Reset simulation state
void simulator_reset(void);

Data Structures

typedef struct {
    int pid;                    // Process ID
    int pc;                     // Program counter
    int pages[MAXPROCPAGES];    // Page table
    int active;                 // Active status
} Process;

typedef struct {
    int frame_number;
    int process_id;
    int page_number;
    int referenced;
    int modified;
} PageFrame;

2. Paging Algorithm Interface

The pageit() Function

The core interface that all paging algorithms must implement:

void pageit(Pentry q[MAXPROCESSES]);

Parameters:

• q[]: Array of process entries containing current state

Called: Every simulation tick

Purpose: Decides which pages to swap in/out

Process Entry Structure

typedef struct {
    int active;                 // Is process running?
    int pc;                     // Program counter
    int npages;                 // Number of pages
    int pages[MAXPROCPAGES];    // Page table (0=out, 1=in)
} Pentry;

3. Page Management Functions

pagein()

int pagein(int process, int page);

Purpose: Request to load a page into physical memory

Returns:

• 1: Page successfully loaded

• 0: Page load initiated (takes time)

• -1: Error or page already in memory

Usage:

if (q[proc].pages[page] == 0) {
    pagein(proc, page);
}

pageout()

int pageout(int process, int page);

Purpose: Remove a page from physical memory

Returns:

• 1: Page successfully removed

• 0: Page removal initiated

• -1: Error or page not in memory

Usage:

if (q[proc].pages[page] == 1) {
    pageout(proc, page);
}

---

Paging Algorithms

1. Basic Pager (pager-basic.c)

Algorithm Description

The simplest paging strategy that runs only one process at a time. It loads all pages for the current process and doesn't swap until the process completes.

Strategy

1. Select first active process

2. Load all pages for that process

3. Wait for process completion

4. Move to next process

Characteristics

• Advantages: Simple, predictable, no complex logic

• Disadvantages: Poor memory utilization, high latency

• Use Case: Baseline for performance comparison

Implementation Highlights

void pageit(Pentry q[MAXPROCESSES]) {
    static int current_proc = 0;

    // Find next active process
    while (!q[current_proc].active) {
        current_proc = (current_proc + 1) % MAXPROCESSES;
    }

    // Load all pages for current process
    for (int page = 0; page < q[current_proc].npages; page++) {
        if (q[current_proc].pages[page] == 0) {
            pagein(current_proc, page);
        }
    }
}

Performance Metrics

• Page Faults: High (loads all pages sequentially)

• Memory Utilization: Low (only one process at a time)

• Throughput: Poor (serialized execution)

2. LRU Pager (pager-lru.c)

Algorithm Description

Implements the Least Recently Used algorithm, which evicts the page that hasn't been accessed for the longest time when memory is full.

Strategy

1. Track last access time for each page

2. When page fault occurs and memory is full

3. Find least recently used page

4. Evict that page and load new one

Data Structures

typedef struct {
    int timestamp;      // Last access time
    int process;        // Owner process
    int page;           // Page number
} PageInfo;

static PageInfo page_history[MAXPROCESSES][MAXPROCPAGES];
static int current_time = 0;

Implementation Highlights

void pageit(Pentry q[MAXPROCESSES]) {
    current_time++;

    for (int proc = 0; proc < MAXPROCESSES; proc++) {
        if (!q[proc].active) continue;

        int pc_page = q[proc].pc / PAGESIZE;

        // Update timestamp for current page
        if (q[proc].pages[pc_page]) {
            page_history[proc][pc_page].timestamp = current_time;
        } else {
            // Page fault - need to load
            if (memory_full()) {
                // Find LRU page
                int victim = find_lru_page();
                pageout(victim.proc, victim.page);
            }
            pagein(proc, pc_page);
        }
    }
}

Characteristics

• Advantages: Good approximation of optimal, reasonable performance

• Disadvantages: Requires tracking access history, overhead

• Time Complexity: O(n) for finding LRU page

• Space Complexity: O(processes × pages)

Performance Metrics

• Page Faults: Medium (better than basic)

• Memory Utilization: Good (efficient use of frames)

• Throughput: Good (multiple processes concurrent)

3. Predictive Pager (pager-predict.c)

Algorithm Description

Advanced algorithm that predicts future page accesses based on observed patterns and preemptively loads pages.

Strategy

1. Pattern Detection: Analyze program execution patterns

2. Prediction: Forecast which pages will be needed

3. Preloading: Load predicted pages before needed

4. Adaptive: Adjust predictions based on accuracy

Pattern Recognition

The algorithm identifies common patterns:

• Sequential Access: Pages accessed in order

• Loop Behavior: Repeated access to same pages

• Working Set: Set of pages actively used

Data Structures

typedef struct {
    int pattern[MAX_PATTERN];   // Observed access pattern
    int pattern_length;         // Pattern size
    int confidence;             // Prediction confidence
} PatternInfo;

typedef struct {
    int needed_now[MAXPROCPAGES];    // Pages needed immediately
    int needed_soon[MAXPROCPAGES];   // Pages predicted for near future
    int can_evict[MAXPROCPAGES];     // Safe to remove
} PagePriority;

Implementation Highlights

void pageit(Pentry q[MAXPROCESSES]) {
    for (int proc = 0; proc < MAXPROCESSES; proc++) {
        if (!q[proc].active) continue;

        // Detect pattern
        update_pattern(proc, q[proc].pc);

        // Predict future pages
        PagePriority priority = predict_pages(proc, q);

        // Load immediate needs
        for (int i = 0; i < priority.needed_now_count; i++) {
            int page = priority.needed_now[i];
            if (!q[proc].pages[page]) {
                if (memory_full()) {
                    evict_safe_page(priority.can_evict);
                }
                pagein(proc, page);
            }
        }

        // Preload predicted pages
        prefetch_pages(proc, priority.needed_soon, q);
    }
}

Prediction Logic

PagePriority predict_pages(int proc, Pentry q[]) {
    PagePriority priority = {0};
    int pc_page = q[proc].pc / PAGESIZE;

    // Current page is needed now
    priority.needed_now[0] = pc_page;
    priority.needed_now_count = 1;

    // Predict based on pattern
    if (is_sequential_pattern(proc)) {
        // Predict next sequential pages
        for (int i = 1; i <= LOOKAHEAD; i++) {
            if (pc_page + i < q[proc].npages) {
                priority.needed_soon[i-1] = pc_page + i;
            }
        }
    } else if (is_loop_pattern(proc)) {
        // Load all pages in loop working set
        copy_loop_pages(proc, priority.needed_soon);
    }

    // Mark safe eviction candidates
    mark_evictable_pages(proc, q, &priority);

    return priority;
}

Characteristics

• Advantages: Lowest page faults, highest throughput

• Disadvantages: Complex, requires learning phase

• Time Complexity: O(n × m) for pattern matching

• Space Complexity: O(processes × pattern_length)

Performance Metrics

• Page Faults: Lowest (predictive loading)

• Memory Utilization: Excellent (intelligent prefetch)

• Throughput: Highest (minimal blocking)

• Adaptation Time: Requires initial learning period

---

Usage Guide

Running Simulations

Basic Usage

# Run with default settings
./test-basic
./test-lru
./test-predict

Command Line Options

# Display help
./test-basic -help

# Set number of simulation ticks
./test-basic -ticks 10000

# Enable verbose output
./test-basic -verbose

# Generate CSV output for analysis
./test-basic -csv

# Set random seed for reproducibility
./test-basic -seed 12345

# Limit physical pages
./test-basic -pages 100

Example Commands

# Run LRU with 5000 ticks and CSV output
./test-lru -ticks 5000 -csv

# Compare algorithms with same seed
./test-basic -seed 42 -ticks 10000
./test-lru -seed 42 -ticks 10000
./test-predict -seed 42 -ticks 10000

# Long simulation with verbose output
./test-predict -ticks 100000 -verbose > output.log

Interpreting Results

Standard Output

Simulation Results:
------------------
Total Ticks:        10000
Total Page Faults:  1234
Page Fault Rate:    12.34%
Memory Utilization: 87.5%
Throughput:         8.5 processes/sec

Per-Process Stats:
Process 0: 234 faults, 45.2% hit rate
Process 1: 189 faults, 52.1% hit rate
Process 2: 301 faults, 38.9% hit rate
...

Key Metrics

Page Faults: Number of times a requested page wasn't in memory

• Lower is better

• Indicates algorithm efficiency

Page Fault Rate: Percentage of memory accesses that fault

• Formula: (faults / total_accesses) × 100

• Target: < 5% for good performance

Memory Utilization: Percentage of physical pages in use

• Higher is better (to a point)

• Shows memory efficiency

Throughput: Processes completed per time unit

• Higher is better

• Measures overall system performance

Visualization

Generate Trace Data

./test-predict -csv -ticks 10000

This creates CSV files:

• page_trace.csv: Page access patterns

• memory_trace.csv: Memory state over time

• fault_trace.csv: Page fault occurrences

Run Visualization

# Launch R
R

# In R console
> setwd("/path/to/paging-simulator")
> source("scripts/see.R")

The visualization shows:

• Process execution timeline

• Page fault locations

• Memory allocation over time

• Algorithm behavior patterns

---

API Reference

Simulator Functions

simulator_init()

void simulator_init(int physical_pages);

Description: Initializes the simulator with specified memory size

Parameters:

• physical_pages: Number of physical memory frames

Example:

simulator_init(100);  // 100 physical pages

simulator_run()

void simulator_run(int ticks);

Description: Runs simulation for specified number of clock ticks

Parameters:

• ticks: Number of simulation steps to execute

Example:

simulator_run(10000);

simulator_get_stats()

stats_t simulator_get_stats(void);

Description: Retrieves current simulation statistics

Returns: Structure containing performance metrics

Example:

stats_t stats = simulator_get_stats();
printf("Page faults: %d\n", stats.page_faults);

Paging Functions

pagein()

int pagein(int process, int page);

Description: Loads a page into physical memory

Parameters:

• process: Process ID (0 to MAXPROCESSES-1)

• page: Page number (0 to MAXPROCPAGES-1)

Returns:

• 1: Page loaded successfully

• 0: Load initiated (in progress)

• -1: Error condition

Error Conditions:

• Invalid process ID

• Invalid page number

• Page already in memory

• No free frames available

Example:

if (q[proc].pages[page] == 0) {
    int result = pagein(proc, page);
    if (result == -1) {
        // Handle error
    }
}

pageout()

int pageout(int process, int page);

Description: Removes a page from physical memory

Parameters:

• process: Process ID

• page: Page number

Returns:

• 1: Page removed successfully

• 0: Removal initiated (in progress)

• -1: Error condition

Error Conditions:

• Invalid process ID

• Invalid page number

• Page not in memory

• Page currently being accessed

Example:

if (q[proc].pages[page] == 1) {
    pageout(proc, page);
}

Data Structures

Pentry Structure

typedef struct {
    int active;                 // Process status (1=active, 0=terminated)
    int pc;                     // Program counter
    int npages;                 // Total pages in process
    int pages[MAXPROCPAGES];    // Page table (0=not loaded, 1=loaded)
} Pentry;

Fields:

• active: Whether process is currently running

• pc: Current instruction address

• npages: Size of process in pages

• pages[]: Current page table state

stats_t Structure

typedef struct {
    int total_ticks;
    int page_faults;
    int page_hits;
    double fault_rate;
    double memory_utilization;
    int processes_completed;
} stats_t;

Constants

#define MAXPROCESSES    20      // Maximum simultaneous processes
#define MAXPROCPAGES    20      // Maximum pages per process
#define PAGESIZE        128     // Size of each page in bytes
#define PHYSICALPAGES   100     // Default physical memory frames

---

Testing

Test Programs

The simulator includes several test programs with different memory access patterns:

Program 1: Sequential Access

for i = 0 to n:
    access page[i]

Tests sequential page access patterns.

Program 2: Random Access

for i = 0 to n:
    page = random(0, npages)
    access page

Tests random access patterns and algorithm adaptability.

Program 3: Loop with Working Set

while true:
    for i = 0 to k:
        access page[i]

Tests algorithms with locality of reference.

Running Tests

Individual Algorithm Test

./test-lru -ticks 10000 -verbose

Comparative Testing

# Test script
#!/bin/bash
echo "Testing all algorithms..."

for algo in basic lru predict; do
    echo "Running test-$algo"
    ./test-$algo -ticks 10000 -seed 42 > results_$algo.txt
done

echo "Tests complete"

Automated Test Suite

./scripts/run_tests.sh

This runs all algorithms with various configurations and generates comparison reports.

API Testing

./test-api

Tests simulator state changes and API behavior. Useful for:

• Verifying simulator correctness

• Debugging paging algorithms

• Understanding API semantics

---

Performance Analysis

Benchmark Results

Test Configuration

• Physical Pages: 100

• Processes: 4

• Simulation Ticks: 10,000

• Random Seed: 42

Results Table

Analysis

Basic Pager:

• High fault rate due to sequential process execution

• Poor memory utilization (only one process active)

• Suitable only for very simple scenarios

LRU Pager:

• 60% reduction in page faults vs. Basic

• Good memory utilization

• Reasonable performance for general workloads

Predictive Pager:

• 84% reduction in page faults vs. Basic

• Excellent memory utilization

• Best overall performance

• Requires learning period (first 100-200 ticks)

Optimization Tips

For Basic Pager

• Increase memory allocation

• Reduce number of processes

• Use smaller processes

For LRU Pager

• Tune history tracking window

• Optimize LRU search algorithm

• Consider clock-based approximation

For Predictive Pager

• Adjust lookahead distance

• Fine-tune pattern detection thresholds

• Balance prefetching aggressiveness

---

Contributing

Development Setup

# Fork and clone
git clone https://github.com/yourusername/paging-simulator.git
cd paging-simulator

# Create feature branch
git checkout -b feature/new-algorithm

# Build and test
make clean && make
./test-api

Code Style

• Follow K&R C style

• Use meaningful variable names

• Comment complex logic

• Keep functions under 50 lines

• Use consistent indentation (4 spaces)

Adding New Algorithms

1. Create new file: pager-newalgo.c

2. Implement pageit() function

3. Add build target to Makefile

4. Create test program

5. Document algorithm behavior

6. Submit pull request

Testing Requirements

• All algorithms must pass API tests

• Include performance benchmarks

• Test with multiple random seeds

• Document expected behavior

---

License

MIT License - See LICENSE file for details

---

Contact & Support

• Author: Mido191020

• Repository: https://github.com/Mido191020/paging-simulator

• Issues: Submit via GitHub Issues

• Discussions: Use GitHub Discussions for questions

---

Acknowledgments

• Based on operating systems coursework

• Inspired by classical page replacement algorithms

• Thanks to the open-source community

---

Appendix

Glossary

Page: Fixed-size block of virtual memory

Frame: Fixed-size block of physical memory

Page Fault: Occurs when requested page not in physical memory

Page Replacement: Process of swapping pages between memory and disk

Working Set: Set of pages a process actively uses

Thrashing: Excessive paging that degrades performance

References

Operating Systems: Three Easy Pieces

---

Last Updated: December 2025 Version: 1.0.0