Page Replacement โญโญโญโญ
Page Replacement โญโญโญโญ¶
Overview¶
Page replacement algorithms determine which page to evict when physical memory is insufficient. Learn about major algorithms including FIFO, Optimal, LRU, Belady's Anomaly, and thrashing.
Table of Contents¶
- Need for Page Replacement
- FIFO Algorithm
- Optimal Algorithm
- LRU Algorithm
- LRU Approximation Algorithms
- Belady's Anomaly
- Thrashing and Working Set
- Practice Problems
1. Need for Page Replacement¶
1.1 Over-allocation¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Memory Over-allocation โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Physical Memory: 8GB (2,097,152 frames @ 4KB) โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Process 1: 2GB virtual address space โ โ
โ โ Process 2: 4GB virtual address space โ โ
โ โ Process 3: 3GB virtual address space โ โ
โ โ Process 4: 2GB virtual address space โ โ
โ โ ... โ โ
โ โ Total virtual address space: 20GB โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ 20GB > 8GB โ Cannot hold all pages in memory! โ
โ โ
โ Solution: Demand paging + Page replacement โ
โ - Only actively used pages in memory โ
โ - Rest in disk swap space โ
โ - Replace when needed โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
1.2 Page Replacement Process¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Page Replacement Process โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ 1. Page fault occurs (needed page not in memory) โ
โ โ โ
โ โผ โ
โ 2. Find free frame โ
โ โโโ If available: use that frame โ
โ โโโ If not: page replacement needed โ
โ โ โ
โ โผ โ
โ 3. Select victim page (using page replacement algorithm) โ
โ โ โ
โ โผ โ
โ 4. Handle victim page โ
โ โโโ Modified (Dirty): write to disk โ
โ โโโ Not modified: discard โ
โ โ โ
โ โผ โ
โ 5. Load new page โ
โ - Read from disk to frame โ
โ โ โ
โ โผ โ
โ 6. Update tables โ
โ - Victim page: valid=0 โ
โ - New page: valid=1, record frame number โ
โ โ โ
โ โผ โ
โ 7. Restart instruction โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
1.3 Dirty Bit¶
// Using Dirty Bit in page replacement
void replace_page(int victim_frame) {
PageTableEntry* victim_pte = get_pte_for_frame(victim_frame);
if (victim_pte->dirty) {
// Modified page - must write to disk
write_to_swap(victim_frame, victim_pte->swap_slot);
// 2 I/Os: read + write
} else {
// Not modified - disk copy is valid
// Just discard, no disk write needed
// 1 I/O: read only
}
// Load new page
read_from_swap(victim_frame, new_page_swap_slot);
}
2. FIFO Algorithm¶
2.1 Concept¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ FIFO (First-In, First-Out) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Rule: Replace the oldest page โ
โ โ
โ Implementation: Use queue โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ โ
โ โ Page load order: A โ B โ C โ D โ ... โ โ
โ โ โ โ
โ โ Memory (3 frames): โ โ
โ โ โโโโโฌโโโโฌโโโโ โ โ
โ โ โ A โ B โ C โ โ Oldest: A โ โ
โ โ โโโฌโโดโโโโดโโโโ โ โ
โ โ โ โ โ
โ โ โผ On D access โ โ
โ โ โโโโโฌโโโโฌโโโโ โ โ
โ โ โ D โ B โ C โ โ A replaced โ โ
โ โ โโโโโดโโฌโโดโโโโ โ โ
โ โ โ โ โ
โ โ โผ On E access โ โ
โ โ โโโโโฌโโโโฌโโโโ โ โ
โ โ โ D โ E โ C โ โ B replaced (now C is oldest) โ โ
โ โ โโโโโดโโโโดโโโโ โ โ
โ โ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ Advantages: Simple implementation โ
โ Disadvantages: May replace frequently used pages โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
2.2 FIFO Implementation¶
#include <stdio.h>
#include <stdbool.h>
#define MAX_FRAMES 10
typedef struct {
int pages[MAX_FRAMES];
int front;
int rear;
int count;
int capacity;
} FIFOQueue;
void fifo_init(FIFOQueue* q, int capacity) {
q->front = 0;
q->rear = 0;
q->count = 0;
q->capacity = capacity;
}
bool fifo_contains(FIFOQueue* q, int page) {
for (int i = 0; i < q->count; i++) {
int idx = (q->front + i) % q->capacity;
if (q->pages[idx] == page) return true;
}
return false;
}
int fifo_access(FIFOQueue* q, int page) {
// Hit if page already exists
if (fifo_contains(q, page)) {
printf("Page %d: hit\n", page);
return 0; // No page fault
}
// Page fault
printf("Page %d: fault", page);
if (q->count < q->capacity) {
// Free frame available
q->pages[q->rear] = page;
q->rear = (q->rear + 1) % q->capacity;
q->count++;
printf(" (using free frame)\n");
} else {
// Replace oldest page
int victim = q->pages[q->front];
q->pages[q->front] = page;
q->front = (q->front + 1) % q->capacity;
printf(" (replaced page %d)\n", victim);
}
return 1; // Page fault
}
void fifo_print(FIFOQueue* q) {
printf("Memory: [");
for (int i = 0; i < q->count; i++) {
int idx = (q->front + i) % q->capacity;
printf("%d", q->pages[idx]);
if (i < q->count - 1) printf(", ");
}
printf("]\n\n");
}
int main() {
FIFOQueue q;
fifo_init(&q, 3);
int reference_string[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2};
int n = sizeof(reference_string) / sizeof(reference_string[0]);
int page_faults = 0;
for (int i = 0; i < n; i++) {
page_faults += fifo_access(&q, reference_string[i]);
fifo_print(&q);
}
printf("Total page faults: %d\n", page_faults);
return 0;
}
2.3 Example¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ FIFO Example (3 frames) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2 โ
โ โ
โ Access Frame 0 Frame 1 Frame 2 Fault? โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ 7 7 - - fault โ
โ 0 7 0 - fault โ
โ 1 7 0 1 fault โ
โ 2 2 0 1 fault (replaced 7) โ
โ 0 2 0 1 hit โ
โ 3 2 3 1 fault (replaced 0) โ
โ 0 2 3 0 fault (replaced 1) โ
โ 4 4 3 0 fault (replaced 2) โ
โ 2 4 2 0 fault (replaced 3) โ
โ 3 4 2 3 fault (replaced 0) โ
โ 0 0 2 3 fault (replaced 4) โ
โ 3 0 2 3 hit โ
โ 2 0 2 3 hit โ
โ 1 0 1 3 fault (replaced 2) โ
โ 2 0 1 2 fault (replaced 3) โ
โ โ
โ Total page faults: 12 โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
3. Optimal Algorithm¶
3.1 Concept¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Optimal (OPT) Algorithm โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Rule: Replace the page that will be unused for the longest time โ
โ (Requires future knowledge - ideal algorithm) โ
โ โ
โ Example: โ
โ Future reference: ... D, E, F, A, B, C, A ... โ
โ โ โ
โ Current position โ
โ โ
โ Memory: [A, B, C] โ
โ Need to access D, which to replace? โ
โ โ
โ - A: used 4 accesses later โ
โ - B: used 5 accesses later โ
โ - C: used 6 accesses later โ Used latest โ
โ โ
โ โ Replacing C is optimal โ
โ โ
โ Advantages: Guarantees minimum page faults (comparison baseline) โ
โ Disadvantages: Cannot predict future โ Impossible to implement โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
3.2 Optimal Implementation¶
#include <stdio.h>
#include <stdbool.h>
#define MAX_FRAMES 10
#define MAX_REFS 100
int frames[MAX_FRAMES];
int frame_count = 0;
int capacity;
int reference_string[MAX_REFS];
int ref_length;
// Check if page is in memory
int find_page(int page) {
for (int i = 0; i < frame_count; i++) {
if (frames[i] == page) return i;
}
return -1;
}
// Find page that will be used latest in the future
int find_victim(int current_index) {
int victim = 0;
int farthest = -1;
for (int i = 0; i < frame_count; i++) {
int page = frames[i];
int next_use = ref_length; // Max value if not used
// Find when this page is used in future references
for (int j = current_index + 1; j < ref_length; j++) {
if (reference_string[j] == page) {
next_use = j;
break;
}
}
if (next_use > farthest) {
farthest = next_use;
victim = i;
}
}
return victim;
}
int optimal_access(int page, int current_index) {
int idx = find_page(page);
if (idx != -1) {
printf("Page %d: hit\n", page);
return 0;
}
printf("Page %d: fault", page);
if (frame_count < capacity) {
frames[frame_count++] = page;
printf(" (using free frame)\n");
} else {
int victim_idx = find_victim(current_index);
printf(" (replaced page %d)\n", frames[victim_idx]);
frames[victim_idx] = page;
}
return 1;
}
int main() {
capacity = 3;
int refs[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2};
ref_length = sizeof(refs) / sizeof(refs[0]);
for (int i = 0; i < ref_length; i++) {
reference_string[i] = refs[i];
}
int page_faults = 0;
for (int i = 0; i < ref_length; i++) {
page_faults += optimal_access(reference_string[i], i);
}
printf("\nTotal page faults: %d\n", page_faults);
return 0;
}
3.3 Example¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Optimal Example (3 frames) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2 โ
โ โ
โ Access Frame 0 Frame 1 Frame 2 Fault? Reason โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ 7 7 - - fault โ
โ 0 7 0 - fault โ
โ 1 7 0 1 fault โ
โ 2 2 0 1 fault 7: not used โ
โ 0 2 0 1 hit โ
โ 3 2 0 3 fault 1: used latest โ
โ 0 2 0 3 hit โ
โ 4 2 4 3 fault 0: used latest โ
โ 2 2 4 3 hit โ
โ 3 2 4 3 hit โ
โ 0 0 4 3 fault 2: used latest โ
โ 3 0 4 3 hit โ
โ 2 0 2 3 fault 4: not used โ
โ 1 0 2 1 fault 3: not used โ
โ 2 0 2 1 hit โ
โ โ
โ Total page faults: 9 (3 fewer than FIFO!) โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
4. LRU Algorithm¶
4.1 Concept¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ LRU (Least Recently Used) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Rule: Replace the page that has not been used for the longest time โ
โ (Recent use = likely to be used in near future) โ
โ โ
โ Comparison with Optimal: โ
โ - Optimal: Looks at future (will be unused longest) โ
โ - LRU: Looks at past (unused longest so far) โ
โ โ
โ Utilizes Temporal Locality: โ
โ "Recently used data is likely to be used again in near future" โ
โ โ
โ Advantages: โ
โ - Performance close to Optimal โ
โ - Actually implementable โ
โ โ
โ Disadvantages: โ
โ - Complex implementation (need to track all access times) โ
โ - High overhead without hardware support โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
4.2 LRU Implementation Methods¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ LRU Implementation Methods โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ 1. Counter-based โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Store timestamp for each page โ โ
โ โ โ โ
โ โ On page access: โ โ
โ โ page.last_used = ++global_counter; โ โ
โ โ โ โ
โ โ On replacement: select page with smallest counter value โ โ
โ โ โ โ
โ โ Disadvantage: O(n) table search, overflow handling needed โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ 2. Stack-based โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Manage pages with doubly linked list โ โ
โ โ โ โ
โ โ On page access: move that page to stack top โ โ
โ โ On replacement: remove page at stack bottom โ โ
โ โ โ โ
โ โ Top โ โ
โ โ โ โ โ
โ โ โโโโโ โ โ
โ โ โ A โ โ Most recently used โ โ
โ โ โโโโโค โ โ
โ โ โ C โ โ โ
โ โ โโโโโค โ โ
โ โ โ B โ โ Least recently used (replacement target) โ โ
โ โ โโโโโ โ โ
โ โ Bottom โ โ
โ โ โ โ
โ โ Advantage: O(1) replacement โ โ
โ โ Disadvantage: Pointer updates needed on move โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
4.3 LRU Stack Implementation¶
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
int page;
struct Node* prev;
struct Node* next;
} Node;
typedef struct {
Node* head; // Most recently used
Node* tail; // Least recently used
int count;
int capacity;
} LRUCache;
LRUCache* lru_create(int capacity) {
LRUCache* cache = malloc(sizeof(LRUCache));
cache->head = NULL;
cache->tail = NULL;
cache->count = 0;
cache->capacity = capacity;
return cache;
}
// Find page
Node* lru_find(LRUCache* cache, int page) {
Node* current = cache->head;
while (current) {
if (current->page == page) return current;
current = current->next;
}
return NULL;
}
// Move node to front
void move_to_front(LRUCache* cache, Node* node) {
if (node == cache->head) return; // Already at front
// Remove from list
if (node->prev) node->prev->next = node->next;
if (node->next) node->next->prev = node->prev;
if (node == cache->tail) cache->tail = node->prev;
// Insert at front
node->prev = NULL;
node->next = cache->head;
if (cache->head) cache->head->prev = node;
cache->head = node;
if (!cache->tail) cache->tail = node;
}
// Insert new node at front
void insert_front(LRUCache* cache, int page) {
Node* node = malloc(sizeof(Node));
node->page = page;
node->prev = NULL;
node->next = cache->head;
if (cache->head) cache->head->prev = node;
cache->head = node;
if (!cache->tail) cache->tail = node;
cache->count++;
}
// Remove tail node
int remove_tail(LRUCache* cache) {
if (!cache->tail) return -1;
Node* victim = cache->tail;
int page = victim->page;
cache->tail = victim->prev;
if (cache->tail) cache->tail->next = NULL;
else cache->head = NULL;
free(victim);
cache->count--;
return page;
}
int lru_access(LRUCache* cache, int page) {
Node* node = lru_find(cache, page);
if (node) {
// Hit: move to front
printf("Page %d: hit\n", page);
move_to_front(cache, node);
return 0;
}
// Fault
printf("Page %d: fault", page);
if (cache->count >= cache->capacity) {
// Replace least recently used page
int victim = remove_tail(cache);
printf(" (replaced page %d)", victim);
}
insert_front(cache, page);
printf("\n");
return 1;
}
void lru_print(LRUCache* cache) {
printf("Memory (MRUโLRU): [");
Node* current = cache->head;
while (current) {
printf("%d", current->page);
if (current->next) printf(", ");
current = current->next;
}
printf("]\n\n");
}
int main() {
LRUCache* cache = lru_create(3);
int refs[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2};
int n = sizeof(refs) / sizeof(refs[0]);
int page_faults = 0;
for (int i = 0; i < n; i++) {
page_faults += lru_access(cache, refs[i]);
lru_print(cache);
}
printf("Total page faults: %d\n", page_faults);
return 0;
}
4.4 Example¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ LRU Example (3 frames) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2 โ
โ โ
โ Access Stack (MRUโLRU) Fault? โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ 7 [7] fault โ
โ 0 [0, 7] fault โ
โ 1 [1, 0, 7] fault โ
โ 2 [2, 1, 0] fault (replaced 7 - LRU) โ
โ 0 [0, 2, 1] hit (moved 0 to MRU) โ
โ 3 [3, 0, 2] fault (replaced 1 - LRU) โ
โ 0 [0, 3, 2] hit (moved 0 to MRU) โ
โ 4 [4, 0, 3] fault (replaced 2 - LRU) โ
โ 2 [2, 4, 0] fault (replaced 3 - LRU) โ
โ 3 [3, 2, 4] fault (replaced 0 - LRU) โ
โ 0 [0, 3, 2] fault (replaced 4 - LRU) โ
โ 3 [3, 0, 2] hit (moved 3 to MRU) โ
โ 2 [2, 3, 0] hit (moved 2 to MRU) โ
โ 1 [1, 2, 3] fault (replaced 0 - LRU) โ
โ 2 [2, 1, 3] hit (moved 2 to MRU) โ
โ โ
โ Total page faults: 10 (FIFO: 12, OPT: 9) โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
5. LRU Approximation Algorithms¶
5.1 Second-Chance (Clock) Algorithm¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Second-Chance Algorithm โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Uses reference bit: โ
โ - On page access: reference bit = 1 โ
โ - On replacement: select page with reference bit = 0 โ
โ โ
โ Implemented as circular queue (clock algorithm): โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ โ
โ โผ โ โ
โ โโโโโโโโโโโ โโโโโโโโโโโ โ โโโโโโโโโโโ โ
โ โPage A โโโโโPage B โโโโผโโโPage C โโโโโโโ โ
โ โRef: 1 โ โRef: 0 โ โ โRef: 1 โ โ โ
โ โโโโโโโโโโโ โโโโโโโโโโโ โ โโโโโโโโโโโ โ โ
โ โฒ โ โ โ
โ โ โโโโโโโโโโโโโ โ โ
โ โ โ โ โ
โ โ โโโโโโโโโโโ โโโโโโโโโโโ โโโโโโโโโโโ โ
โ โโโโโโโโPage F โโโโโPage E โโโโโPage D โ โ
โ โRef: 0 โ โRef: 1 โ โRef: 0 โ โ
โ โโโโโโโโโโโ โโโโโโโโโโโ โโโโโโโโโโโ โ
โ โ โ
โ Pointer โ
โ โ
โ Replacement process: โ
โ 1. Examine page pointed to โ
โ 2. If Ref=1: set Ref=0, move to next (second chance) โ
โ 3. If Ref=0: replace this page โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
5.2 Enhanced Second-Chance¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Enhanced Second-Chance Algorithm โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Uses reference bit + modify bit โ
โ โ
โ Priority by (Ref, Mod) combination: โ
โ โโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโ โ
โ โ (Ref, Mod) โ Description โ Priority โ โ
โ โโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโค โ
โ โ (0, 0) โ Not recently used, not modified โ 1 (Best) โ โ
โ โ (0, 1) โ Not recently used, modified โ 2 โ โ
โ โ (1, 0) โ Recently used, not modified โ 3 โ โ
โ โ (1, 1) โ Recently used, modified โ 4 (Worst)โ โ
โ โโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโ โ
โ โ
โ Replacement algorithm: โ
โ 1. Search for (0,0) page โ replace if found โ
โ 2. Search for (0,1) page, set Ref=0 while passing โ
โ 3. Start over, search for (0,0) โ
โ 4. Search for (0,1) โ replace if found โ
โ โ
โ Advantage: Minimize dirty page replacement โ Reduce I/O โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
5.3 Clock Algorithm Implementation¶
#include <stdio.h>
#include <stdbool.h>
#define MAX_FRAMES 10
typedef struct {
int page;
bool reference_bit;
bool valid;
} Frame;
Frame frames[MAX_FRAMES];
int clock_hand = 0;
int capacity;
int count = 0;
void clock_init(int cap) {
capacity = cap;
for (int i = 0; i < MAX_FRAMES; i++) {
frames[i].valid = false;
}
}
int find_page(int page) {
for (int i = 0; i < capacity; i++) {
if (frames[i].valid && frames[i].page == page) {
return i;
}
}
return -1;
}
int find_empty() {
for (int i = 0; i < capacity; i++) {
if (!frames[i].valid) return i;
}
return -1;
}
int clock_access(int page) {
int idx = find_page(page);
if (idx != -1) {
// Hit: set reference bit
printf("Page %d: hit\n", page);
frames[idx].reference_bit = true;
return 0;
}
// Fault
printf("Page %d: fault", page);
int empty = find_empty();
if (empty != -1) {
// Use free frame
frames[empty].page = page;
frames[empty].reference_bit = true;
frames[empty].valid = true;
count++;
printf(" (using free frame %d)\n", empty);
return 1;
}
// Select victim with clock algorithm
while (true) {
if (!frames[clock_hand].reference_bit) {
// Replace if reference bit is 0
printf(" (replaced page %d in frame %d)\n",
frames[clock_hand].page, clock_hand);
frames[clock_hand].page = page;
frames[clock_hand].reference_bit = true;
clock_hand = (clock_hand + 1) % capacity;
return 1;
}
// If reference bit is 1, set to 0 and move to next
frames[clock_hand].reference_bit = false;
clock_hand = (clock_hand + 1) % capacity;
}
}
void clock_print() {
printf("Memory: [");
for (int i = 0; i < capacity; i++) {
if (frames[i].valid) {
printf("%d(R:%d)", frames[i].page,
frames[i].reference_bit ? 1 : 0);
} else {
printf("-");
}
if (i < capacity - 1) printf(", ");
}
printf("] Pointer: %d\n\n", clock_hand);
}
int main() {
clock_init(3);
int refs[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3};
int n = sizeof(refs) / sizeof(refs[0]);
int page_faults = 0;
for (int i = 0; i < n; i++) {
page_faults += clock_access(refs[i]);
clock_print();
}
printf("Total page faults: %d\n", page_faults);
return 0;
}
6. Belady's Anomaly¶
6.1 Phenomenon¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Belady's Anomaly โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Intuition: More frames should mean fewer page faults. โ
โ Belady's Anomaly: With FIFO, increasing frames can increase faults! โ
โ โ
โ Example: Reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 โ
โ โ
โ 3 frames: โ
โ 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 9 faults โ
โ โ
โ 4 frames: โ
โ 1 [1, -, -, -] fault โ
โ 2 [1, 2, -, -] fault โ
โ 3 [1, 2, 3, -] fault โ
โ 4 [1, 2, 3, 4] fault โ
โ 1 [1, 2, 3, 4] hit โ
โ 2 [1, 2, 3, 4] hit โ
โ 5 [5, 2, 3, 4] fault โ
โ 1 [5, 1, 3, 4] fault โ
โ 2 [5, 1, 2, 4] fault โ
โ 3 [5, 1, 2, 3] fault โ
โ 4 [4, 1, 2, 3] fault โ
โ 5 [4, 5, 2, 3] fault โ Total 10 faults โ
โ โ
โ 3 frames: 9 faults < 4 frames: 10 faults โ Anomaly! โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
6.2 Stack Algorithms¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Stack Algorithm โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Definition: Page set for n frames is always subset of n+1 frames โ
โ M(n) โ M(n+1) โ
โ โ
โ Stack Algorithm = No Belady's Anomaly โ
โ โ
โ Example: LRU โ
โ 3 frames: Memory = {A, B, C} โ
โ 4 frames: Memory = {A, B, C, D} โ
โ โ {A, B, C} โ {A, B, C, D} always holds โ
โ โ
โ FIFO is not a stack algorithm: โ
โ At time t, 3 frames: {1, 2, 3} โ
โ At time t, 4 frames: {2, 3, 4} โ
โ โ {1, 2, 3} โ {2, 3, 4} possible โ
โ โ
โ Stack algorithm examples: LRU, Optimal, LFU โ
โ Non-stack algorithm: FIFO โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
7. Thrashing and Working Set¶
7.1 Thrashing¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Thrashing โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Definition: Process spends more time on page replacement than executionโ
โ โ
โ CPU Utilization โ
โ โ โ
โ โ โฑโโโฒ โ
โ โ โฑ โฒ โ
โ โ โฑ โฒ โ
โ โ โฑ โฒ โ
โ โ โฑ โฒ โ
โ โ โฑ โฒ Thrashing โ
โ โ โฑ โฒ threshold โ
โ โ โฑ โฒ โ
โ โโฑ โฒ__________ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโถ Degree of multiprogramming โ
โ โ
โ Thrashing occurrence: โ
โ 1. Low CPU utilization โ OS runs more processes โ
โ 2. More processes โ fewer frames per process โ
โ 3. More page faults โ more I/O waiting โ
โ 4. CPU utilization decreases โ OS runs more processes... (vicious cycle)โ
โ โ
โ Result: System nearly stops working โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
7.2 Working Set Model¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Working Set Model โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Working Set: Set of pages referenced during time window (ฮ) โ
โ โ
โ Time window ฮ = 10 โ
โ โ
โ Reference sequence: ... 1 2 3 4 5 1 2 3 1 2 | 7 8 9 0 7 8 9 0 7 8 โ
โ โ Current time โ
โ โ
โ Working Set(ฮ=10) = {1, 2, 3, 4, 5} โ
โ โ
โ Working Set size change: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ โ
โ โ WSS โ โ
โ โ โ โญโโโฎ โญโโโฎ โ โ
โ โ โ โฑ โฒ โฑ โฒ Locality transition โ โ
โ โ โโโโโโฑ โฒโโฑ โฒโโโโ โ โ
โ โ โ Stable Stable Stable โ โ
โ โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโถ Time โ โ
โ โ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ Principle: โ
โ - WSS(i) = Process i's Working Set size โ
โ - D = ฮฃ WSS(i) = Total frame demand โ
โ - D > Total frames โ Thrashing occurs โ
โ โ
โ Solution: If D > m, suspend one process โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
7.3 Page Fault Frequency (PFF)¶
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Page Fault Frequency Method โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Concept: Adjust frame allocation based on page fault frequency โ
โ โ
โ Page fault rate โ
โ โ โ
โ โ โโโโโโโโโโ Upper threshold โ
โ โ โ โ
โ โ โ Allocate more frames โ
โ โ โ โ
โ โ โ โ โ โ โ โ Target range โ
โ โ โ โ
โ โ โ Reclaim frames โ
โ โ โ โ
โ โ โโโโโโโโโโ Lower threshold โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโถ Allocated frames โ
โ โ
โ Operation: โ
โ - Fault rate > upper: allocate more frames โ
โ - Fault rate < lower: reclaim some frames โ
โ - Insufficient frames: swap out some processes โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
7.4 Preventing Thrashing in Linux¶
# Check swap usage
$ free -h
total used free shared buff/cache available
Mem: 15Gi 10Gi 500Mi 100Mi 5.0Gi 4.5Gi
Swap: 8.0Gi 2.0Gi 6.0Gi โ Swap in use
# Check swappiness (0-100, higher = more aggressive swap)
$ cat /proc/sys/vm/swappiness
60
# Adjust swappiness (lower to prevent thrashing)
$ sudo sysctl vm.swappiness=10
# Check OOM Killer logs
$ dmesg | grep -i "out of memory"
# Memory usage by process
$ ps aux --sort=-%mem | head -10
# Limit memory with cgroups (containers)
$ cat /sys/fs/cgroup/memory/memory.limit_in_bytes
Practice Problems¶
Problem 1: Algorithm Comparison¶
Calculate page faults for reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with 3 frames using FIFO, LRU, and Optimal.
Show Answer
FIFO:
1: [1,-,-] fault 5: [5,2,3] fault 4: [4,5,2] fault
2: [1,2,-] fault 1: [5,1,3] fault 5: [4,5,2] hit
3: [1,2,3] fault 2: [5,1,2] fault
4: [4,2,3] fault 3: [3,1,2] fault
1: [4,1,3] fault
2: [4,1,2] fault
Total: 9 faults
LRU:
1: [1] fault 5: [5,1,2] fault 4: [4,3,2] fault
2: [2,1] fault 1: [1,5,2] hit 5: [5,4,3] fault
3: [3,2,1] fault 2: [2,1,5] hit
4: [4,3,2] fault 3: [3,2,1] fault
1: [1,4,3] fault
2: [2,1,4] fault
Total: 10 faults
Optimal:
1: [1,-,-] fault 5: [5,1,2] fault 4: [4,1,2] fault
2: [1,2,-] fault 1: [5,1,2] hit 5: [5,1,2] fault
3: [1,2,3] fault 2: [5,1,2] hit
4: [4,2,3] fault 3: [3,1,2] fault
1: [4,1,3] fault
2: [4,1,2] fault
Total: 7 faults
Problem 2: Second-Chance¶
With 4 frames in the following state, which page gets replaced when inserting page E?
Pointer โ [A, R=1] โ [B, R=0] โ [C, R=1] โ [D, R=0]
Show Answer
1. Pointer at A, R=1
โ Set R=0, move to next
2. Pointer at B, R=0
โ B gets replaced!
Result: [A, R=0] โ [E, R=1] โ [C, R=1] โ [D, R=0]
โ New page
Pointer now points to C
Problem 3: Working Set¶
Calculate Working Set at time t=10 with ฮ = 5.
Time: 1 2 3 4 5 6 7 8 9 10
Page: 1 2 3 1 2 1 3 4 5 2
Show Answer
References within ฮ=5 before t=10:
t=6: Page 1
t=7: Page 3
t=8: Page 4
t=9: Page 5
t=10: Page 2
Working Set(t=10, ฮ=5) = {1, 2, 3, 4, 5}
WSS = 5
This process needs at least 5 frames
Problem 4: Belady's Anomaly Proof¶
Calculate page faults for FIFO with 3 frames and 4 frames to verify Belady's Anomaly.
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Show Answer
3 frames (FIFO):
1: [1,-,-] F 1: [4,1,3] F 3: [3,1,2] F
2: [1,2,-] F 2: [4,1,2] F 4: [3,4,2] F
3: [1,2,3] F 5: [5,1,2] F 5: [3,4,5] F
4: [4,2,3] F 1: [5,1,2] H
2: [5,1,2] H
Total: 9 faults
4 frames (FIFO):
1: [1,-,-,-] F 5: [5,2,3,4] F 4: [4,1,2,3] F
2: [1,2,-,-] F 1: [5,1,3,4] F 5: [4,5,2,3] F
3: [1,2,3,-] F 2: [5,1,2,4] F
4: [1,2,3,4] F 3: [5,1,2,3] F
1: [1,2,3,4] H
2: [1,2,3,4] H
Total: 10 faults
Belady's Anomaly confirmed:
3 frames: 9 faults
4 frames: 10 faults
โ More frames but more faults!
Problem 5: Thrashing Solution¶
The following symptoms are observed in the system. Analyze the cause and propose solutions.
- CPU utilization: 5%
- Disk I/O: 95%
- Memory: Nearly full
- Many processes waiting
Show Answer
Cause Analysis:
- Classic thrashing state
- Too many processes competing for insufficient memory
- Most time spent on page fault handling (disk I/O)
Solutions:
1. Immediate fix:
- Suspend some processes
- Swap out to free frames for other processes
2. System configuration:
- Lower swappiness (vm.swappiness=10)
- Limit memory overcommit (vm.overcommit_memory=2)
3. Long-term solutions:
- Add physical memory
- Implement Working Set-based scheduling
- Monitor PFF (Page Fault Frequency)
- Limit per-process memory with cgroups
4. Application level:
- Check for memory leaks
- Adjust cache sizes
- Terminate unnecessary processes
Monitoring commands:
$ vmstat 1 # Check si/so (swap in/out)
$ sar -B 1 # Check pgpgin/pgpgout
Next Steps¶
Continue to 16_File_System_Basics.md to learn file system basics!
References¶
- Silberschatz, "Operating System Concepts" Chapter 10
- Tanenbaum, "Modern Operating Systems" Chapter 3
- Linux kernel source:
mm/vmscan.c,mm/workingset.c - Belady, L.A. "A study of replacement algorithms for virtual-storage computer"