Virtual memory systems rely on efficient page replacement policies to handle situations where physical memmory frames are exhausted. When a page fault occurs and no free frames exist, the operating system must select a victim page to swap out. This simulation examines two common strategies: Least Recently Used (LRU) and the Clock algorithm.

Least Recently Used (LRU) Strategy

The LRU algorithm evicts the page that has not been accessed for the longest period. To implement this, each page frame tracks a timestamp indicating its last access moment. During a replacement event, the system scans all ocucpied frames to identify the one with the smallest timestamp value.

Implementation Details

The following C implementation maintains an array of page frames. Each frame stores the page iedntifier and the tick count of its last usage. When a request arrives, the system checks for existence. If missing, it either fills an empty slot or replaces the frame with the oldest timestamp.

#include <stdio.h>
#include <stdlib.h>

#define CAPACITY 4
#define MAX_TICKS 1000000

typedef struct {
    int page_id;
    int last_access;
    int is_occupied;
} PageFrame;

int find_page(PageFrame *frames, int target, int count) {
    for (int i = 0; i < count; i++) {
        if (frames[i].page_id == target && frames[i].is_occupied) {
            return i;
        }
    }
    return -1;
}

int find_victim_lru(PageFrame *frames, int count) {
    int victim = 0;
    int min_time = MAX_TICKS;
    for (int i = 0; i < count; i++) {
        if (frames[i].is_occupied && frames[i].last_access < min_time) {
            min_time = frames[i].last_access;
            victim = i;
        }
    }
    return victim;
}

void display_frames(PageFrame *frames, int capacity, int occupied_count) {
    for (int i = 0; i < capacity; i++) {
        if (i < occupied_count && frames[i].is_occupied) {
            printf("%d ", frames[i].page_id);
        } else {
            printf("# ");
        }
    }
    printf("\n");
}

int main() {
    PageFrame memory[CAPACITY];
    int occupied_count = 0;
    int current_tick = 0;
    int page_faults = 0;
    int replacements = 0;
    int total_requests = 0;
    int request;

    for(int i=0; i<CAPACITY; i++) memory[i].is_occupied = 0;

    printf("Enter page request sequence (end with 0):\n");
    while (scanf("%d", &request) && request != 0) {
        current_tick++;
        total_requests++;
        int index = find_page(memory, request, occupied_count);

        if (index == -1) {
            page_faults++;
            if (occupied_count < CAPACITY) {
                index = occupied_count;
                occupied_count++;
            } else {
                index = find_victim_lru(memory, CAPACITY);
                replacements++;
            }
            memory[index].page_id = request;
            memory[index].is_occupied = 1;
        }
        memory[index].last_access = current_tick;
        display_frames(memory, CAPACITY, occupied_count);
    }

    printf("Page Faults: %d\nReplacements: %d\nFault Rate: %.1f%%\n", 
           page_faults, replacements, (float)page_faults / total_requests * 100);
    return 0;
}

Clock Page Replacement Strategy

The Clock algorithm approximates LRU behavior with lower overhead. It organizes memory frames into a circular buffer. Each frame includes a reference bit. When a page is accessed, its reference bit is set to 1. During replacement, the system checks the bit at the current hand position. If the bit is 0, the page is evicted. If it is 1, the bit is cleared to 0, and the hand moves to the next frame. This continues until a candidate with a 0 bit is found.

Implementation Details

This version uses a fixed-size array to represent the circular buffer, managed by a hand index. This avoids the pointer overhead of a linked list while maintaining the circular logic through modulo arithmetic.

#include <stdio.h>
#include <stdlib.h>

#define FRAME_COUNT 5

typedef struct {
    int page_id;
    int reference_bit;
    int is_valid;
} ClockFrame;

int search_clock(ClockFrame *frames, int target, int count) {
    for (int i = 0; i < count; i++) {
        if (frames[i].is_valid && frames[i].page_id == target) {
            return i;
        }
    }
    return -1;
}

int select_victim_clock(ClockFrame *frames, int *hand, int count) {
    while (1) {
        if (!frames[*hand].is_valid || frames[*hand].reference_bit == 0) {
            int victim = *hand;
            *hand = (*hand + 1) % count;
            return victim;
        }
        frames[*hand].reference_bit = 0;
        *hand = (*hand + 1) % count;
    }
}

void display_clock(ClockFrame *frames, int count) {
    for (int i = 0; i < count; i++) {
        if (frames[i].is_valid) {
            printf("%d ", frames[i].page_id);
        } else {
            printf("# ");
        }
    }
    printf("\n");
}

int main() {
    ClockFrame frames[FRAME_COUNT];
    int hand = 0;
    int valid_count = 0;
    int page_faults = 0;
    int replacements = 0;
    int total_requests = 0;
    int request;

    for(int i=0; i<FRAME_COUNT; i++) {
        frames[i].is_valid = 0;
        frames[i].reference_bit = 0;
    }

    printf("Enter page request sequence (end with 0):\n");
    while (scanf("%d", &request) && request != 0) {
        total_requests++;
        int found_index = search_clock(frames, request, FRAME_COUNT);
        int is_fault = 0;

        if (found_index != -1) {
            frames[found_index].reference_bit = 1;
        } else {
            is_fault = 1;
            page_faults++;
            int victim_index = select_victim_clock(frames, &hand, FRAME_COUNT);
            
            if (!frames[victim_index].is_valid) {
                valid_count++;
            } else {
                replacements++;
            }
            
            frames[victim_index].page_id = request;
            frames[victim_index].is_valid = 1;
            frames[victim_index].reference_bit = 1;
        }
        display_clock(frames, FRAME_COUNT);
    }

    printf("Page Faults: %d\nReplacements: %d\nFault Rate: %.1f%%\n", 
           page_faults, replacements, (float)page_faults / total_requests * 100);
    return 0;
}