Fifo Algorithm - Learning Module

Loading content...

0/227

Simple Implementation

From Theory to Code

The elegance of FIFO lies not just in its concept, but in the simplicity of its realization. Transforming the principle "evict the oldest page" into working code reveals why FIFO has been a foundational teaching tool and why, despite its limitations, it remains valuable in contexts where simplicity and predictability outweigh peak performance.

In this page, we will build FIFO from the ground up. We'll examine the data structures that naturally represent FIFO ordering, the algorithms for page loading and eviction, and complete implementations with detailed walkthroughs. By the end, you'll be able to implement FIFO in any language and understand every aspect of its operation.

What You Will Learn

By the end of this page, you will be able to implement FIFO page replacement from scratch, understand why queues are the natural data structure for FIFO, trace through complete reference string examples, and analyze the time and space complexity of FIFO operations.

The Queue: FIFO's Natural Data Structure

The very name "First-In, First-Out" points directly to the data structure we need: a queue. A queue maintains insertion order and provides:

Enqueue: Add an element to the back (newest position)
Dequeue: Remove the element from the front (oldest position)
Front/Peek: Examine the front element without removing it

These operations map perfectly to FIFO page replacement:

FIFO Operation	Queue Operation	Description
Load new page	Enqueue	Add to back of queue
Select victim	Front/Peek	Identify oldest page
Evict victim	Dequeue	Remove from front
Check presence	Search	Is a page in the queue?

Implementation Options:

Several data structures can implement a queue efficiently:

1. Circular Array (Ring Buffer)

+---+---+---+---+---+---+---+---+
| A | B | C | D | E |   |   |   |
+---+---+---+---+---+---+---+---+
  ↑                   ↑
front                back

Pros: Cache-friendly, O(1) enqueue/dequeue, minimal overhead
Cons: Fixed capacity, requires knowing maximum frame count
Best for: Kernel implementations where frame count is fixed

2. Linked List

[Head/Front] → A → B → C → D → E → [Tail/Back]

Pros: Dynamic size, simple implementation
Cons: Memory overhead for pointers, cache-unfriendly
Best for: Flexible implementations, teaching contexts

3. Array with Dynamic Resizing

Pros: Familiar interface, reasonable performance
Cons: Occasional O(n) resize, less elegant than circular buffer
Best for: High-level language implementations

Converting Mermaid diagram...

Practical Recommendation

For kernel-level implementation, circular arrays are preferred due to their cache efficiency and lack of dynamic allocation. For simulation or teaching purposes, linked lists or standard library queues offer cleaner code. The algorithmic complexity is identical; the choice is about context.

The FIFO Algorithm Step by Step

Let's formalize the FIFO page replacement algorithm with precise pseudocode. The algorithm handles two cases: page hits (page already in memory) and page misses (page must be loaded).

State Variables:

frames[]: Array representing physical memory frames
queue: FIFO queue tracking page arrival order
page_to_frame: Mapping from page number to frame index (optional, for O(1) lookup)
num_frames: Total number of available frames

Core Algorithm:

fifo_page_replacement.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
FUNCTION handle_page_reference(page_number):
    // Phase 1: Check if page is already in memory (HIT)
    IF page_number IN frames THEN
        // Page HIT - no action needed for FIFO
        log("HIT: Page " + page_number + " already in memory")
        RETURN "HIT"
    END IF
    
    // Phase 2: Page MISS - must load the page
    log("MISS: Page " + page_number + " not in memory")
    page_fault_count += 1
    
    // Phase 2a: Check if there's a free frame
    IF queue.size() < num_frames THEN
        // Free frame available - just load
        free_frame = find_free_frame()
        frames[free_frame] = page_number
        queue.enqueue(page_number)
        log("Loaded page " + page_number + " into frame " + free_frame)
    ELSE
        // Phase 2b: No free frame - must evict
        victim_page = queue.dequeue()     // Remove oldest
        victim_frame = find_frame(victim_page)
        
        // Optional: Write back if dirty
        IF victim_page.is_dirty THEN
            write_to_disk(victim_page)
        END IF
        
        // Replace victim with new page
        frames[victim_frame] = page_number
        queue.enqueue(page_number)        // Add new page to back
        
        log("Evicted page " + victim_page + ", loaded page " + page_number)
    END IF
    
    RETURN "MISS"
END FUNCTION

Algorithm Analysis:

Let's analyze each phase:

Phase 1: Hit Detection

Check if the referenced page exists in frames
Naive approach: O(n) search through frames array
Optimized approach: O(1) lookup using hash map from page to frame
On hit: No action required — this is a key FIFO characteristic

Phase 2a: Load into Free Frame

When queue hasn't reached capacity, simply load
No eviction needed
O(1) operation

Phase 2b: Eviction Required

Dequeue identifies victim: O(1)
Find victim's frame: O(n) naive or O(1) with mapping
Optional dirty page writeback
Enqueue new page: O(1)

FIFO Operation Complexity
Operation	Naive Implementation	Optimized Implementation
Check if page in memory	O(n)	O(1) with hash set
Find free frame	O(n)	O(1) with free list
Select victim (dequeue)	O(1)	O(1)
Add new page (enqueue)	O(1)	O(1)
Find victim's frame	O(n)	O(1) with hash map
Overall page miss	O(n)	O(1)

Complete Implementation in Code

Let's build a complete, production-quality FIFO page replacement simulator. This implementation includes proper tracking, statistics, and clean interfaces.

fifo_implementation.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
 
#define MAX_FRAMES 100
#define MAX_PAGES 1000
 
// FIFO Page Replacement Implementation
typedef struct {
    int frames[MAX_FRAMES];          // Frame contents (-1 = empty)
    int queue[MAX_FRAMES];           // Circular queue for FIFO order
    int front;                       // Queue front index
    int rear;                        // Queue rear index
    int count;                       // Current number of pages in memory
    int num_frames;                  // Total frames available
    int page_faults;                 // Page fault counter
    int page_hits;                   // Page hit counter
} FIFOPager;
 
// Initialize the FIFO pager
void fifo_init(FIFOPager* pager, int num_frames) {
    pager->num_frames = num_frames;
    pager->front = 0;
    pager->rear = -1;
    pager->count = 0;
    pager->page_faults = 0;
    pager->page_hits = 0;
    
    // Initialize all frames as empty
    for (int i = 0; i < MAX_FRAMES; i++) {
        pager->frames[i] = -1;
        pager->queue[i] = -1;
    }
}
 
// Check if page is in memory
bool fifo_contains(FIFOPager* pager, int page) {
    for (int i = 0; i < pager->count; i++) {
        int idx = (pager->front + i) % pager->num_frames;
        if (pager->queue[idx] == page) {
            return true;
        }
    }
    return false;
}
 
// Find frame containing a page
int fifo_find_frame(FIFOPager* pager, int page) {
    for (int i = 0; i < pager->num_frames; i++) {
        if (pager->frames[i] == page) {
            return i;
        }
    }
    return -1;
}
 
// Process a page reference
bool fifo_reference(FIFOPager* pager, int page, int* evicted) {
    *evicted = -1;
    
    // Check for page hit
    if (fifo_contains(pager, page)) {
        pager->page_hits++;
        return false;  // No page fault
    }
    
    // Page fault occurred
    pager->page_faults++;
    
    if (pager->count < pager->num_frames) {
        // Free frame available - no eviction needed
        pager->rear = (pager->rear + 1) % pager->num_frames;
        pager->queue[pager->rear] = page;
        pager->frames[pager->count] = page;
        pager->count++;
    } else {
        // Must evict oldest page
        *evicted = pager->queue[pager->front];
        int victim_frame = fifo_find_frame(pager, *evicted);
        
        // Remove oldest from queue
        pager->front = (pager->front + 1) % pager->num_frames;
        
        // Add new page to queue
        pager->rear = (pager->rear + 1) % pager->num_frames;
        pager->queue[pager->rear] = page;
        
        // Update frame content
        pager->frames[victim_frame] = page;
    }
    
    return true;  // Page fault occurred
}
 
// Print current state
void fifo_print_state(FIFOPager* pager) {
    printf("Frames: [");
    for (int i = 0; i < pager->num_frames; i++) {
        if (pager->frames[i] == -1) {
            printf(" - ");
        } else {
            printf(" %d ", pager->frames[i]);
        }
    }
    printf("] Queue order (oldest→newest): ");
    for (int i = 0; i < pager->count; i++) {
        int idx = (pager->front + i) % pager->num_frames;
        printf("%d ", pager->queue[idx]);
    }
    printf("\n");
}
 
// Run simulation with reference string
void fifo_simulate(int* reference_string, int length, int num_frames) {
    FIFOPager pager;
    fifo_init(&pager, num_frames);
    
    printf("\nFIFO Simulation with %d frames:\n", num_frames);
    printf("Reference string: ");
    for (int i = 0; i < length; i++) {
        printf("%d ", reference_string[i]);
    }
    printf("\n\n");
    
    for (int i = 0; i < length; i++) {
        int page = reference_string[i];
        int evicted;
        bool fault = fifo_reference(&pager, page, &evicted);
        
        printf("Ref: %d -> ", page);
        if (!fault) {
            printf("HIT    ");
        } else if (evicted == -1) {
            printf("MISS   (loaded)     ");
        } else {
            printf("MISS   (evicted %d) ", evicted);
        }
        fifo_print_state(&pager);
    }
    
    printf("\n--- Statistics ---\n");
    printf("Total references: %d\n", length);
    printf("Page faults: %d\n", pager.page_faults);
    printf("Page hits: %d\n", pager.page_hits);
    printf("Hit ratio: %.2f%%\n", 
           (float)pager.page_hits / length * 100);
    printf("Fault ratio: %.2f%%\n", 
           (float)pager.page_faults / length * 100);
}

Implementation Details

The circular buffer approach uses modulo arithmetic to wrap around indices. This avoids the need to shift elements and provides true O(1) enqueue and dequeue operations. The 'front' index points to the oldest page (next to be evicted), while 'rear' points to the most recently added page.

Complete Worked Example

Let's trace through FIFO execution step by step with a complete example. This detailed walkthrough shows exactly how FIFO maintains state and makes decisions.

Problem Setup:

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Number of frames: 3

This is a classic operating systems textbook example that demonstrates FIFO behavior.

FIFO Execution Trace (3 Frames)
Step	Page Ref	Frame 0	Frame 1	Frame 2	Queue (oldest→newest)	Result	Evicted
1	7	7			7	MISS
2	0	7	0		7→0	MISS
3	1	7	0	1	7→0→1	MISS
4	2	2	0	1	0→1→2	MISS	7
5	0	2	0	1	0→1→2	HIT
6	3	2	3	1	1→2→3	MISS	0
7	0	2	3	0	2→3→0	MISS	1
8	4	4	3	0	3→0→4	MISS	2
9	2	4	2	0	0→4→2	MISS	3
10	3	4	2	3	4→2→3	MISS	0
11	0	0	2	3	2→3→0	MISS	4
12	3	0	2	3	2→3→0	HIT
13	2	0	2	3	2→3→0	HIT
14	1	0	1	3	3→0→1	MISS	2
15	2	0	1	2	0→1→2	MISS	3
16	0	0	1	2	0→1→2	HIT
17	1	0	1	2	0→1→2	HIT
18	7	7	1	2	1→2→7	MISS	0
19	0	7	0	2	2→7→0	MISS	1
20	1	7	0	1	7→0→1	MISS	2

Analysis of the Trace:

Metric	Value
Total references	20
Page faults	15
Page hits	5
Hit ratio	25%
Fault ratio	75%

Observations:

High fault rate: The 75% fault rate is substantial. Compare this to OPT which achieves only 9 faults (45%) on the same reference string.
Evicting useful pages: Notice steps 6-7: Page 0 is evicted at step 6, immediately needed at step 7, forcing another eviction. FIFO doesn't know page 0 is about to be used.
Queue rotation: The queue maintains strict FIFO order. Watch how pages rotate through the queue regardless of how often they're accessed.
Hit clustering: Hits tend to occur when the same pages are referenced closely together (steps 5, 12-13, 16-17).

The 0→evict→0 Pattern

The trace shows page 0 being evicted at step 6, then immediately needed at step 7. This pattern—evicting a page that's about to be used—is FIFO's fundamental weakness. LRU would recognize page 0 was recently used and protect it. FIFO cannot make this distinction.

Optimizing FIFO Implementation

While the basic FIFO implementation is simple, several optimizations can improve practical performance:

Optimization 1: O(1) Page Lookup with Hash Sets

Instead of scanning frames to check if a page is present, maintain a hash set of currently loaded pages:

// Add to structure:
HashSet* loaded_pages;

// Contains check becomes:
bool contains = hashset_contains(loaded_pages, page);  // O(1)

Optimization 2: Direct Frame Mapping

Maintain a hash map from page number to frame index:

// Add to structure:
HashMap* page_to_frame;  // page_number -> frame_index

// Finding victim's frame becomes:
int frame = hashmap_get(page_to_frame, victim_page);  // O(1)

Optimization 3: Memory-Aligned Structures

For kernel implementations, align data structures to cache lines:

typedef struct __attribute__((aligned(64))) {
    int frames[MAX_FRAMES];
    // ... other fields
} FIFOPager;

Optimization 4: Batch Processing

For simulation or analysis, process multiple references before updating statistics:

void fifo_batch_reference(FIFOPager* pager, int* pages, int count) {
    for (int i = 0; i < count; i++) {
        // Process without intermediate logging
        fifo_reference_silent(pager, pages[i]);
    }
    // Update statistics once
    update_statistics(pager);
}

Time Optimizations

•Hash-based page lookup: O(n) → O(1)
•Direct frame mapping: O(n) → O(1)
•Circular buffer: No element shifting
•Inline small functions
•Branch prediction hints

Space Optimizations

•Use bit arrays for presence flags
•Packed structures for metadata
•Avoid redundant frame/queue storage
•Pool allocation for nodes
•Memory-mapped structures for persistence

Integration with Operating System Components

In a real operating system, FIFO doesn't exist in isolation. It integrates with several other subsystems:

1. Memory Management Unit (MMU) Integration

The MMU notifies the OS of page faults via hardware interrupts. The FIFO algorithm runs inside the page fault handler:

Page Fault Interrupt
    ↓
OS Page Fault Handler
    ↓
FIFO Victim Selection (if no free frames)
    ↓
Disk I/O (load new page, optionally write victim)
    ↓
Update Page Table Entries
    ↓
Resume Faulted Process

2. Page Table Integration

FIFO must coordinate with page tables:

When loading a page: Set valid bit, update frame mapping
When evicting a page: Clear valid bit in victim's page table entry
Must handle multi-process environments where each process has its own page table

3. Disk I/O Subsystem

Page replacement involves substantial I/O:

Reading: Fetch the faulted page from disk (mandatory)
Writing: Write back dirty victim pages (conditional on dirty bit)
I/O time dominates page fault cost, dwarfing FIFO algorithm overhead

4. Process Scheduling Interaction

Page faults cause context switches:

The faulting process blocks waiting for I/O
Scheduler may run other processes
FIFO decisions affect which processes can run efficiently

Converting Mermaid diagram...

Algorithm Speed vs. I/O Dominance

The FIFO algorithm itself runs in microseconds. The disk I/O it triggers takes milliseconds (1000x+ slower). This means FIFO's O(1) victim selection is effectively "free" compared to the I/O cost. What matters for performance is the QUALITY of victim selection (minimizing future faults), not the SPEED of making the selection.

Testing and Verification

Implementing FIFO correctly requires careful testing. Here are the test cases every implementation should pass:

Test Category 1: Basic Functionality

fifo_tests.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// Test 1: Sequential loading with no eviction
// Reference: 1, 2, 3 with 3 frames
// Expected: 3 faults, 0 hits, pages 1,2,3 in memory
void test_sequential_load() {
    int refs[] = {1, 2, 3};
    FIFOPager p;
    fifo_init(&p, 3);
    
    for (int i = 0; i < 3; i++) {
        int evicted;
        fifo_reference(&p, refs[i], &evicted);
        assert(evicted == -1);  // No eviction yet
    }
    assert(p.page_faults == 3);
    assert(p.page_hits == 0);
}
 
// Test 2: Simple eviction
// Reference: 1, 2, 3, 4 with 3 frames
// Expected: Page 1 evicted when page 4 loads
void test_simple_eviction() {
    int refs[] = {1, 2, 3, 4};
    FIFOPager p;
    fifo_init(&p, 3);
    
    int evicted;
    for (int i = 0; i < 4; i++) {
        fifo_reference(&p, refs[i], &evicted);
    }
    assert(evicted == 1);  // Page 1 (oldest) was evicted
}
 
// Test 3: Page hit doesn't affect queue
// Reference: 1, 2, 3, 2, 4 with 3 frames
// Expected: Page 1 evicted (not 2, even though 2 was hit)
void test_hit_no_queue_change() {
    int refs[] = {1, 2, 3, 2, 4};
    FIFOPager p;
    fifo_init(&p, 3);
    
    int evicted;
    for (int i = 0; i < 5; i++) {
        fifo_reference(&p, refs[i], &evicted);
    }
    assert(evicted == 1);  // 1 is still oldest despite 2's hit
}
 
// Test 4: Verify FIFO order maintained
// Reference: 1, 2, 3, 4, 5, 6 with 3 frames
// Expected: Evictions in order 1, 2, 3
void test_fifo_order() {
    int refs[] = {1, 2, 3, 4, 5, 6};
    int expected_evictions[] = {-1, -1, -1, 1, 2, 3};
    FIFOPager p;
    fifo_init(&p, 3);
    
    for (int i = 0; i < 6; i++) {
        int evicted;
        fifo_reference(&p, refs[i], &evicted);
        assert(evicted == expected_evictions[i]);
    }
}

Critical Test Cases

•Empty start: First reference always faults and loads
•Fill without eviction: Loading up to frame count causes no evictions
•First eviction: n+1th unique page evicts the first page
•Hit behavior: Hits don't change queue order or cause eviction
•Cyclic references: Verify correct behavior with repeating patterns
•Single frame: Extreme case—every unique reference is a fault
•Large frame count: Many frames, few faults
•Edge case verification: Belady's anomaly test cases

Summary

We've now covered FIFO implementation comprehensively. Let's consolidate the key points:

Key Takeaways

•Queue is the natural data structure — FIFO maps directly to queue semantics: enqueue on load, dequeue on evict.
•Circular buffer is optimal for kernels — Fixed-size, cache-friendly, no dynamic allocation, O(1) operations.
•Hits require no action — Unlike LRU, FIFO doesn't update any state on page hits, giving it zero runtime overhead for memory accesses.
•O(1) victim selection — Dequeuing the oldest page is constant time, making FIFO algorithmically efficient even if not optimal.
•Hash-based lookups eliminate O(n) searches — Pages-in-memory set and page-to-frame mappings should use hash structures.
•Testing must verify FIFO order — The key invariant is that eviction order exactly matches loading order.

What's Next:

With implementation mastered, we turn to FIFO's most surprising property: Belady's Anomaly. In the next page, we'll discover that adding more frames can actually increase page faults—a counterintuitive result that reveals deep truths about the nature of page replacement algorithms.

Implementation Complete

You can now implement FIFO page replacement from scratch. You understand the data structures, algorithms, complexity, and integration points. Next, we explore Belady's Anomaly—the paradox that makes FIFO a fascinating subject beyond its practical applications.

Simple Implementation

From Theory to Code

What You Will Learn

The Queue: FIFO's Natural Data Structure

The very name "First-In, First-Out" points directly to the data structure we need: a queue. A queue maintains insertion order and provides:

Enqueue: Add an element to the back (newest position)
Dequeue: Remove the element from the front (oldest position)
Front/Peek: Examine the front element without removing it

These operations map perfectly to FIFO page replacement:

FIFO Operation	Queue Operation	Description
Load new page	Enqueue	Add to back of queue
Select victim	Front/Peek	Identify oldest page
Evict victim	Dequeue	Remove from front
Check presence	Search	Is a page in the queue?

Implementation Options:

Several data structures can implement a queue efficiently:

1. Circular Array (Ring Buffer)

+---+---+---+---+---+---+---+---+
| A | B | C | D | E |   |   |   |
+---+---+---+---+---+---+---+---+
  ↑                   ↑
front                back

Pros: Cache-friendly, O(1) enqueue/dequeue, minimal overhead
Cons: Fixed capacity, requires knowing maximum frame count
Best for: Kernel implementations where frame count is fixed

2. Linked List

[Head/Front] → A → B → C → D → E → [Tail/Back]

Pros: Dynamic size, simple implementation
Cons: Memory overhead for pointers, cache-unfriendly
Best for: Flexible implementations, teaching contexts

3. Array with Dynamic Resizing

Pros: Familiar interface, reasonable performance
Cons: Occasional O(n) resize, less elegant than circular buffer
Best for: High-level language implementations

Converting Mermaid diagram...

Practical Recommendation

The FIFO Algorithm Step by Step

Let's formalize the FIFO page replacement algorithm with precise pseudocode. The algorithm handles two cases: page hits (page already in memory) and page misses (page must be loaded).

State Variables:

frames[]: Array representing physical memory frames
queue: FIFO queue tracking page arrival order
page_to_frame: Mapping from page number to frame index (optional, for O(1) lookup)
num_frames: Total number of available frames

Core Algorithm:

fifo_page_replacement.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
FUNCTION handle_page_reference(page_number):
    // Phase 1: Check if page is already in memory (HIT)
    IF page_number IN frames THEN
        // Page HIT - no action needed for FIFO
        log("HIT: Page " + page_number + " already in memory")
        RETURN "HIT"
    END IF
    
    // Phase 2: Page MISS - must load the page
    log("MISS: Page " + page_number + " not in memory")
    page_fault_count += 1
    
    // Phase 2a: Check if there's a free frame
    IF queue.size() < num_frames THEN
        // Free frame available - just load
        free_frame = find_free_frame()
        frames[free_frame] = page_number
        queue.enqueue(page_number)
        log("Loaded page " + page_number + " into frame " + free_frame)
    ELSE
        // Phase 2b: No free frame - must evict
        victim_page = queue.dequeue()     // Remove oldest
        victim_frame = find_frame(victim_page)
        
        // Optional: Write back if dirty
        IF victim_page.is_dirty THEN
            write_to_disk(victim_page)
        END IF
        
        // Replace victim with new page
        frames[victim_frame] = page_number
        queue.enqueue(page_number)        // Add new page to back
        
        log("Evicted page " + victim_page + ", loaded page " + page_number)
    END IF
    
    RETURN "MISS"
END FUNCTION

Algorithm Analysis:

Let's analyze each phase:

Phase 1: Hit Detection

Check if the referenced page exists in frames
Naive approach: O(n) search through frames array
Optimized approach: O(1) lookup using hash map from page to frame
On hit: No action required — this is a key FIFO characteristic

Phase 2a: Load into Free Frame

When queue hasn't reached capacity, simply load
No eviction needed
O(1) operation

Phase 2b: Eviction Required

Dequeue identifies victim: O(1)
Find victim's frame: O(n) naive or O(1) with mapping
Optional dirty page writeback
Enqueue new page: O(1)

FIFO Operation Complexity
Operation	Naive Implementation	Optimized Implementation
Check if page in memory	O(n)	O(1) with hash set
Find free frame	O(n)	O(1) with free list
Select victim (dequeue)	O(1)	O(1)
Add new page (enqueue)	O(1)	O(1)
Find victim's frame	O(n)	O(1) with hash map
Overall page miss	O(n)	O(1)

Complete Implementation in Code

Let's build a complete, production-quality FIFO page replacement simulator. This implementation includes proper tracking, statistics, and clean interfaces.

fifo_implementation.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
 
#define MAX_FRAMES 100
#define MAX_PAGES 1000
 
// FIFO Page Replacement Implementation
typedef struct {
    int frames[MAX_FRAMES];          // Frame contents (-1 = empty)
    int queue[MAX_FRAMES];           // Circular queue for FIFO order
    int front;                       // Queue front index
    int rear;                        // Queue rear index
    int count;                       // Current number of pages in memory
    int num_frames;                  // Total frames available
    int page_faults;                 // Page fault counter
    int page_hits;                   // Page hit counter
} FIFOPager;
 
// Initialize the FIFO pager
void fifo_init(FIFOPager* pager, int num_frames) {
    pager->num_frames = num_frames;
    pager->front = 0;
    pager->rear = -1;
    pager->count = 0;
    pager->page_faults = 0;
    pager->page_hits = 0;
    
    // Initialize all frames as empty
    for (int i = 0; i < MAX_FRAMES; i++) {
        pager->frames[i] = -1;
        pager->queue[i] = -1;
    }
}
 
// Check if page is in memory
bool fifo_contains(FIFOPager* pager, int page) {
    for (int i = 0; i < pager->count; i++) {
        int idx = (pager->front + i) % pager->num_frames;
        if (pager->queue[idx] == page) {
            return true;
        }
    }
    return false;
}
 
// Find frame containing a page
int fifo_find_frame(FIFOPager* pager, int page) {
    for (int i = 0; i < pager->num_frames; i++) {
        if (pager->frames[i] == page) {
            return i;
        }
    }
    return -1;
}
 
// Process a page reference
bool fifo_reference(FIFOPager* pager, int page, int* evicted) {
    *evicted = -1;
    
    // Check for page hit
    if (fifo_contains(pager, page)) {
        pager->page_hits++;
        return false;  // No page fault
    }
    
    // Page fault occurred
    pager->page_faults++;
    
    if (pager->count < pager->num_frames) {
        // Free frame available - no eviction needed
        pager->rear = (pager->rear + 1) % pager->num_frames;
        pager->queue[pager->rear] = page;
        pager->frames[pager->count] = page;
        pager->count++;
    } else {
        // Must evict oldest page
        *evicted = pager->queue[pager->front];
        int victim_frame = fifo_find_frame(pager, *evicted);
        
        // Remove oldest from queue
        pager->front = (pager->front + 1) % pager->num_frames;
        
        // Add new page to queue
        pager->rear = (pager->rear + 1) % pager->num_frames;
        pager->queue[pager->rear] = page;
        
        // Update frame content
        pager->frames[victim_frame] = page;
    }
    
    return true;  // Page fault occurred
}
 
// Print current state
void fifo_print_state(FIFOPager* pager) {
    printf("Frames: [");
    for (int i = 0; i < pager->num_frames; i++) {
        if (pager->frames[i] == -1) {
            printf(" - ");
        } else {
            printf(" %d ", pager->frames[i]);
        }
    }
    printf("] Queue order (oldest→newest): ");
    for (int i = 0; i < pager->count; i++) {
        int idx = (pager->front + i) % pager->num_frames;
        printf("%d ", pager->queue[idx]);
    }
    printf("\n");
}
 
// Run simulation with reference string
void fifo_simulate(int* reference_string, int length, int num_frames) {
    FIFOPager pager;
    fifo_init(&pager, num_frames);
    
    printf("\nFIFO Simulation with %d frames:\n", num_frames);
    printf("Reference string: ");
    for (int i = 0; i < length; i++) {
        printf("%d ", reference_string[i]);
    }
    printf("\n\n");
    
    for (int i = 0; i < length; i++) {
        int page = reference_string[i];
        int evicted;
        bool fault = fifo_reference(&pager, page, &evicted);
        
        printf("Ref: %d -> ", page);
        if (!fault) {
            printf("HIT    ");
        } else if (evicted == -1) {
            printf("MISS   (loaded)     ");
        } else {
            printf("MISS   (evicted %d) ", evicted);
        }
        fifo_print_state(&pager);
    }
    
    printf("\n--- Statistics ---\n");
    printf("Total references: %d\n", length);
    printf("Page faults: %d\n", pager.page_faults);
    printf("Page hits: %d\n", pager.page_hits);
    printf("Hit ratio: %.2f%%\n", 
           (float)pager.page_hits / length * 100);
    printf("Fault ratio: %.2f%%\n", 
           (float)pager.page_faults / length * 100);
}

Implementation Details

Complete Worked Example

Let's trace through FIFO execution step by step with a complete example. This detailed walkthrough shows exactly how FIFO maintains state and makes decisions.

Problem Setup:

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Number of frames: 3

This is a classic operating systems textbook example that demonstrates FIFO behavior.

FIFO Execution Trace (3 Frames)
Step	Page Ref	Frame 0	Frame 1	Frame 2	Queue (oldest→newest)	Result	Evicted
1	7	7			7	MISS
2	0	7	0		7→0	MISS
3	1	7	0	1	7→0→1	MISS
4	2	2	0	1	0→1→2	MISS	7
5	0	2	0	1	0→1→2	HIT
6	3	2	3	1	1→2→3	MISS	0
7	0	2	3	0	2→3→0	MISS	1
8	4	4	3	0	3→0→4	MISS	2
9	2	4	2	0	0→4→2	MISS	3
10	3	4	2	3	4→2→3	MISS	0
11	0	0	2	3	2→3→0	MISS	4
12	3	0	2	3	2→3→0	HIT
13	2	0	2	3	2→3→0	HIT
14	1	0	1	3	3→0→1	MISS	2
15	2	0	1	2	0→1→2	MISS	3
16	0	0	1	2	0→1→2	HIT
17	1	0	1	2	0→1→2	HIT
18	7	7	1	2	1→2→7	MISS	0
19	0	7	0	2	2→7→0	MISS	1
20	1	7	0	1	7→0→1	MISS	2

Analysis of the Trace:

Metric	Value
Total references	20
Page faults	15
Page hits	5
Hit ratio	25%
Fault ratio	75%

Observations:

High fault rate: The 75% fault rate is substantial. Compare this to OPT which achieves only 9 faults (45%) on the same reference string.
Evicting useful pages: Notice steps 6-7: Page 0 is evicted at step 6, immediately needed at step 7, forcing another eviction. FIFO doesn't know page 0 is about to be used.
Queue rotation: The queue maintains strict FIFO order. Watch how pages rotate through the queue regardless of how often they're accessed.
Hit clustering: Hits tend to occur when the same pages are referenced closely together (steps 5, 12-13, 16-17).

The 0→evict→0 Pattern

Optimizing FIFO Implementation

While the basic FIFO implementation is simple, several optimizations can improve practical performance:

Optimization 1: O(1) Page Lookup with Hash Sets

Instead of scanning frames to check if a page is present, maintain a hash set of currently loaded pages:

// Add to structure:
HashSet* loaded_pages;

// Contains check becomes:
bool contains = hashset_contains(loaded_pages, page);  // O(1)

Optimization 2: Direct Frame Mapping

Maintain a hash map from page number to frame index:

// Add to structure:
HashMap* page_to_frame;  // page_number -> frame_index

// Finding victim's frame becomes:
int frame = hashmap_get(page_to_frame, victim_page);  // O(1)

Optimization 3: Memory-Aligned Structures

For kernel implementations, align data structures to cache lines:

typedef struct __attribute__((aligned(64))) {
    int frames[MAX_FRAMES];
    // ... other fields
} FIFOPager;

Optimization 4: Batch Processing

For simulation or analysis, process multiple references before updating statistics:

void fifo_batch_reference(FIFOPager* pager, int* pages, int count) {
    for (int i = 0; i < count; i++) {
        // Process without intermediate logging
        fifo_reference_silent(pager, pages[i]);
    }
    // Update statistics once
    update_statistics(pager);
}

Time Optimizations

•Hash-based page lookup: O(n) → O(1)
•Direct frame mapping: O(n) → O(1)
•Circular buffer: No element shifting
•Inline small functions
•Branch prediction hints

Space Optimizations

•Use bit arrays for presence flags
•Packed structures for metadata
•Avoid redundant frame/queue storage
•Pool allocation for nodes
•Memory-mapped structures for persistence

Integration with Operating System Components

In a real operating system, FIFO doesn't exist in isolation. It integrates with several other subsystems:

1. Memory Management Unit (MMU) Integration

The MMU notifies the OS of page faults via hardware interrupts. The FIFO algorithm runs inside the page fault handler:

Page Fault Interrupt
    ↓
OS Page Fault Handler
    ↓
FIFO Victim Selection (if no free frames)
    ↓
Disk I/O (load new page, optionally write victim)
    ↓
Update Page Table Entries
    ↓
Resume Faulted Process

2. Page Table Integration

FIFO must coordinate with page tables:

When loading a page: Set valid bit, update frame mapping
When evicting a page: Clear valid bit in victim's page table entry
Must handle multi-process environments where each process has its own page table

3. Disk I/O Subsystem

Page replacement involves substantial I/O:

Reading: Fetch the faulted page from disk (mandatory)
Writing: Write back dirty victim pages (conditional on dirty bit)
I/O time dominates page fault cost, dwarfing FIFO algorithm overhead

4. Process Scheduling Interaction

Page faults cause context switches:

The faulting process blocks waiting for I/O
Scheduler may run other processes
FIFO decisions affect which processes can run efficiently

Converting Mermaid diagram...

Algorithm Speed vs. I/O Dominance

Testing and Verification

Implementing FIFO correctly requires careful testing. Here are the test cases every implementation should pass:

Test Category 1: Basic Functionality

fifo_tests.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// Test 1: Sequential loading with no eviction
// Reference: 1, 2, 3 with 3 frames
// Expected: 3 faults, 0 hits, pages 1,2,3 in memory
void test_sequential_load() {
    int refs[] = {1, 2, 3};
    FIFOPager p;
    fifo_init(&p, 3);
    
    for (int i = 0; i < 3; i++) {
        int evicted;
        fifo_reference(&p, refs[i], &evicted);
        assert(evicted == -1);  // No eviction yet
    }
    assert(p.page_faults == 3);
    assert(p.page_hits == 0);
}
 
// Test 2: Simple eviction
// Reference: 1, 2, 3, 4 with 3 frames
// Expected: Page 1 evicted when page 4 loads
void test_simple_eviction() {
    int refs[] = {1, 2, 3, 4};
    FIFOPager p;
    fifo_init(&p, 3);
    
    int evicted;
    for (int i = 0; i < 4; i++) {
        fifo_reference(&p, refs[i], &evicted);
    }
    assert(evicted == 1);  // Page 1 (oldest) was evicted
}
 
// Test 3: Page hit doesn't affect queue
// Reference: 1, 2, 3, 2, 4 with 3 frames
// Expected: Page 1 evicted (not 2, even though 2 was hit)
void test_hit_no_queue_change() {
    int refs[] = {1, 2, 3, 2, 4};
    FIFOPager p;
    fifo_init(&p, 3);
    
    int evicted;
    for (int i = 0; i < 5; i++) {
        fifo_reference(&p, refs[i], &evicted);
    }
    assert(evicted == 1);  // 1 is still oldest despite 2's hit
}
 
// Test 4: Verify FIFO order maintained
// Reference: 1, 2, 3, 4, 5, 6 with 3 frames
// Expected: Evictions in order 1, 2, 3
void test_fifo_order() {
    int refs[] = {1, 2, 3, 4, 5, 6};
    int expected_evictions[] = {-1, -1, -1, 1, 2, 3};
    FIFOPager p;
    fifo_init(&p, 3);
    
    for (int i = 0; i < 6; i++) {
        int evicted;
        fifo_reference(&p, refs[i], &evicted);
        assert(evicted == expected_evictions[i]);
    }
}

Critical Test Cases

•Empty start: First reference always faults and loads
•Fill without eviction: Loading up to frame count causes no evictions
•First eviction: n+1th unique page evicts the first page
•Hit behavior: Hits don't change queue order or cause eviction
•Cyclic references: Verify correct behavior with repeating patterns
•Single frame: Extreme case—every unique reference is a fault
•Large frame count: Many frames, few faults
•Edge case verification: Belady's anomaly test cases

Summary

We've now covered FIFO implementation comprehensively. Let's consolidate the key points:

Key Takeaways

•Queue is the natural data structure — FIFO maps directly to queue semantics: enqueue on load, dequeue on evict.
•Circular buffer is optimal for kernels — Fixed-size, cache-friendly, no dynamic allocation, O(1) operations.
•Hits require no action — Unlike LRU, FIFO doesn't update any state on page hits, giving it zero runtime overhead for memory accesses.
•O(1) victim selection — Dequeuing the oldest page is constant time, making FIFO algorithmically efficient even if not optimal.
•Hash-based lookups eliminate O(n) searches — Pages-in-memory set and page-to-frame mappings should use hash structures.
•Testing must verify FIFO order — The key invariant is that eviction order exactly matches loading order.

What's Next:

Implementation Complete