Beyond Physical Memory: Policies

Treating RAM as a Cache for Disk

Once free frames are exhausted every page fault forces eviction of some resident page. RAM can be regarded as a small fast cache whose backing store is the slow disk. Disk latency is orders of magnitude higher than RAM, so even a one-percent miss probability makes average access time disk-dominated. A successful policy therefore tries to retain pages that will be referenced soon.

Optimal Replacement and Why It Cannot Be Used

Given complete knowledge of future references the best action is to evict the page whose next use lies farthest ahead. That choice produces the theoretical minimum number of misses. Because a live OS lacks such knowledge the algorithm is used only offline: comparing a candidate policy’s miss count against the optimal count shows how much room for improvement remains.

FIFO: Simple yet Potentially Blind

FIFO keeps a queue ordered by load time and always discards the page that has resided longest. Implementation cost is negligible—just a record of arrival order. The policy never looks at whether a page is still being used after it arrived, so a page that entered early yet remains hot can be evicted too soon, causing extra faults.

Pitfalls

• Treating the optimal algorithm as something that can run on-line
• Overlooking that a low miss rate still turns a program disk-bound
• Assuming extra frames always reduce FIFO faults (Belady’s anomaly)

Minimum C11 · complete program · Download .c

#include <stdio.h>

int main(void) {
    int frames = 3;
    int page_refs[] = {1, 2, 3, 4, 1, 2, 5, 1, 2};
    int num_refs = 9;
    int mem[3];
    int count = 0;
    int hit_count = 0;
    printf("Demonstrating FIFO page replacement\n");
    for (int i = 0; i < num_refs; ++i) {
        int pg = page_refs[i];
        int found = 0;
        for (int k = 0; k < count; ++k) {
            if (mem[k] == pg) {
                found = 1;
                break;
            }
        }
        if (found) {
            hit_count++;
            printf("page %d : hit, memory contains", pg);
        } else {
            printf("page %d : miss, memory contains", pg);
            if (count < frames) {
                mem[count] = pg;
                count++;
            } else {
                for (int k = 0; k < frames - 1; ++k) {
                    mem[k] = mem[k + 1];
                }
                mem[frames - 1] = pg;
            }
        }
        for (int k = 0; k < count; ++k) {
            printf(" %d", mem[k]);
        }
        printf("\n");
    }
    printf("Hits = %d out of %d\n", hit_count, num_refs);
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-22-swapping-policies.c -o example && ./example

Expected result

Demonstrating FIFO page replacement
page 1 : miss, memory contains 1
page 2 : miss, memory contains 1 2
page 3 : miss, memory contains 1 2 3
page 4 : miss, memory contains 2 3 4
page 1 : miss, memory contains 3 4 1
page 2 : miss, memory contains 4 1 2
page 5 : miss, memory contains 1 2 5
page 1 : hit, memory contains 1 2 5
page 2 : hit, memory contains 1 2 5
Hits = 2 out of 9

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

With 3 frames and the reference string 1,2,3,4,1,2,5,1,2 how many page faults occur under FIFO?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.