LRU (Least Recently Used) Page Replacement

HARDWARE LRU COUNTER DESIGN
===========================
 
Component 1: Global Logical Clock Register
- N-bit counter (N typically 32 or 64)
- Increments automatically on every memory reference
- Must be accessible from all cores (coherent)
 
Component 2: Extended Page Table Entry
- Standard PTE fields (52 bits for address, 12 bits for flags)
- Added: N-bit timestamp field
- On EVERY memory access, hardware writes current clock to timestamp field
 
   63                                           12 11         0
  +-----------------------------------------------+------------+
  |     Physical Frame Number + Timestamp        |   Flags    |
  +-----------------------------------------------+------------+
                                    ^
                                    |
                            Must accommodate 32-64 bit timestamp
 
Component 3: Minimum Finder
- When eviction needed, hardware or software scans all PTEs
- Finds entry with minimum timestamp
- That page is the LRU victim

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

// TRAP-BASED COUNTER LRU (Hypothetical - NOT practical)
 
// Global shared state
uint64_t logical_clock = 0;
uint64_t page_timestamp[MAX_PAGES];  // Timestamp per page
spinlock_t lru_lock;
 
// Called on EVERY memory access (would require hardware trap)
void memory_access_trap_handler(int page_number) {
    // This runs BILLIONS of times per second!
    
    acquire_spinlock(&lru_lock);
    
    logical_clock++;
    page_timestamp[page_number] = logical_clock;
    
    release_spinlock(&lru_lock);
}
 
// COST ANALYSIS:
// - Trap overhead: ~500-1000 cycles minimum
// - Lock acquisition: ~50-200 cycles  
// - Memory updates: ~10-50 cycles
// - Total: ~600-1300 cycles per memory reference
//
// With 10 billion memory references/second:
//   = 6-13 trillion additional cycles/second
//   = CPU would need to be 2000-4000 GHz to keep up
//
// CONCLUSION: Completely impossible

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

// PAGE FAULT TIME COUNTER (Feasible but NOT true LRU)
 
uint64_t fault_clock = 0;
uint64_t page_fault_time[MAX_PAGES];
 
void page_fault_handler(int page_number) {
    // Only runs on page faults (thousands/second, not billions)
    
    fault_clock++;
    page_fault_time[page_number] = fault_clock;
    
    // Load page from disk...
    // Update page tables...
}
 
int find_lru_victim() {
    // Find page with minimum fault time
    uint64_t min_time = UINT64_MAX;
    int victim = -1;
    
    for (int i = 0; i < num_resident_pages; i++) {
        if (page_fault_time[resident_pages[i]] < min_time) {
            min_time = page_fault_time[resident_pages[i]];
            victim = resident_pages[i];
        }
    }
    return victim;
}
 
// PROBLEM: This is FIFO for resident pages, not LRU!
//
// Example:
//   Page A faults at t=1, loaded
//   Page B faults at t=2, loaded
//   ... A is accessed 1 million times, B never touched ...
//   Need to evict at t=3: Algorithm says "evict A" (fault_time=1)
//   But A is HOT! B should be evicted.
//
// We never learn about accesses between faults.

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

// Counter normalization to prevent overflow
 
void normalize_counters() {
    // Find minimum counter value
    uint64_t min_val = UINT64_MAX;
    for (int i = 0; i < num_pages; i++) {
        if (page_timestamp[i] < min_val) {
            min_val = page_timestamp[i];
        }
    }
    
    // Subtract minimum from all counters
    for (int i = 0; i < num_pages; i++) {
        page_timestamp[i] -= min_val;
    }
    
    // Reset global clock to highest page value
    logical_clock = 0;
    for (int i = 0; i < num_pages; i++) {
        if (page_timestamp[i] > logical_clock) {
            logical_clock = page_timestamp[i];
        }
    }
}
 
// COST: O(n) scan of ALL pages
// With 1 million pages: ~1-10 milliseconds
// During normalization: no memory accesses can be tracked
// Must acquire global lock, blocking all cores
//
// If we normalize every second: 1-10ms of stall per second = 0.1-1% overhead
// But with 32-bit counters, we'd normalize 2x/second = unacceptable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int find_lru_victim_naive() {
    uint64_t min_time = UINT64_MAX;
    int victim = -1;
    
    // Scan ALL resident pages
    for (int i = 0; i < num_resident_pages; i++) {
        if (page_timestamp[resident_pages[i]] < min_time) {
            min_time = page_timestamp[resident_pages[i]];
            victim = resident_pages[i];
        }
    }
    
    return victim;
}
 
// With 1 million pages:
//   - 1 million comparisons
//   - ~1 million memory reads (8 bytes each = 8 MB data)
//   - Cache misses galore
//   - Total time: 1-10 milliseconds
//
// Page faults typically occur thousands of times per second.
// 1000 faults × 10ms each = 10 seconds of scanning per second
// IMPOSSIBLE.

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

// Min-heap based LRU (better but still problematic)
 
typedef struct {
    int page_number;
    uint64_t timestamp;
} HeapEntry;
 
HeapEntry lru_heap[MAX_PAGES];
int heap_size;
HashMap page_to_heap_position;  // For O(1) position lookup
 
// Find LRU victim: O(1) - just return heap root
int find_lru_victim() {
    return lru_heap[0].page_number;  // Root is minimum
}
 
// Problem: UPDATE on access is expensive
void update_timestamp_on_access(int page_number) {
    // 1. Find page's position in heap: O(1) with hash map
    int pos = hashmap_get(page_to_heap_position, page_number);
    
    // 2. Update timestamp (increases value)
    lru_heap[pos].timestamp = ++logical_clock;
    
    // 3. Re-heapify: timestamp increased, so bubble DOWN
    //    O(log n) operations
    heapify_down(pos);
}
 
// The heap "fix" operation is O(log n) per access
// With n=1M pages: log(1M) ≈ 20 heap operations per access
// With 10 billion accesses/second: 200 billion heap ops/second
// Still impossible in software!

REGISTER-BASED LRU
==================
 
For N frames, maintain N hardware registers (8 bits each for simplicity):
 
     Frame 0 Reg    Frame 1 Reg    Frame 2 Reg    Frame 3 Reg
    +-----------+  +-----------+  +-----------+  +-----------+
    | 10010011  |  | 01001001  |  | 11000001  |  | 00100100  |
    +-----------+  +-----------+  +-----------+  +-----------+
         147           73            193            36
 
On each memory access to frame F:
1. Right-shift all registers by 1 (divide by 2, losing LSB)
2. Set MSB of frame F's register to 1
 
Example: Access to Frame 2
 
Before: [147, 73, 193, 36]
After shift: [73, 36, 96, 18]   (all values halved, rounded down)
Set MSB of Frame 2: [73, 36, 224, 18]   (96 + 128 = 224)
 
Interpretation:
- Higher values = more recent accesses
- Find minimum = LRU victim
- MSB = accessed this period, LSB = accessed long ago

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

// THE AGING ALGORITHM
// Periodic sampling combines reference bits with counters
 
// Each page has an 8-bit aging counter
uint8_t age_counter[MAX_PAGES];
 
// Every T milliseconds (e.g., T=100ms), the OS runs:
void aging_timer_interrupt() {
    for (int page = 0; page < num_resident_pages; page++) {
        // Right-shift counter (age the value)
        age_counter[page] >>= 1;
        
        // If reference bit is set, add 128 (set MSB)
        if (get_reference_bit(page)) {
            age_counter[page] |= 0x80;  // 0b10000000
        }
        
        // Clear reference bit for next period
        clear_reference_bit(page);
    }
}
 
// To find LRU victim: find page with minimum age_counter
int find_lru_victim() {
    uint8_t min_age = 0xFF;
    int victim = -1;
    
    for (int page = 0; page < num_resident_pages; page++) {
        if (age_counter[page] < min_age) {
            min_age = age_counter[page];
            victim = page;
        }
    }
    return victim;
}

LINUX MGLRU (Multi-Generation LRU)
===================================
 
Instead of per-page counters, pages are placed in GENERATIONS:
 
    Gen 0 (oldest)    Gen 1         Gen 2        Gen 3 (newest)
    +-----------+  +-----------+  +-----------+  +-----------+
    | Page list |  | Page list |  | Page list |  | Page list |
    +-----------+  +-----------+  +-----------+  +-----------+
    Evict first    ...           ...           Most protected
 
Promotion: When page is accessed, move to higher generation
Demotion: Periodically, pages age down generations
Eviction: Select victims from generation 0
 
Benefits:
- No per-page counter storage
- Constant-time generation membership check
- Batch aging (move whole generations down)
- Configurable number of generations (typically 4)
 
This is counter-like behavior with practical overhead.