Global Vs Local Replacement - Learning Module

Loading content...

0/227

Local Replacement

Process-Isolated Memory Management

While global replacement treats physical memory as a shared pool, local replacement takes the opposite approach: each process receives a dedicated allocation of frames, and page replacement decisions are strictly confined to that allocation. When a process experiences a page fault and needs a victim, the operating system only considers frames already belonging to that process.

This isolation model provides predictability and protection at the potential cost of efficiency. A process cannot steal frames from others—but it also cannot benefit from unused memory that other processes aren't utilizing.

What You Will Learn

By the end of this page, you will understand how local replacement enforces process isolation, the mechanisms used to implement fixed-per-process allocation, the benefits of predictable performance, and the efficiency costs of memory partitioning. You will gain analytical skills to evaluate when local replacement offers superior guarantees.

Understanding Local Replacement

Local replacement means that when a process needs a frame, the page replacement algorithm examines only frames currently allocated to that process. Each process operates within its own memory partition, isolated from all others.

The fundamental principle:

Under local replacement, physical memory is conceptually divided into fixed (or dynamically-adjusted-but-isolated) partitions. Each process owns its partition. When process P experiences a page fault:

The replacement algorithm scans only P's frames
The victim page is guaranteed to belong to P
Other processes' frames are never considered as candidates
P's memory usage cannot increase at another process's expense

local_replacement_concept.c
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
/**
 * Local Page Replacement - Conceptual Model
 * 
 * Each process has its own frame allocation.
 * Replacement decisions are confined to that allocation.
 */
 
struct process_frame_allocation {
    pid_t    process_id;
    int      num_frames;             // Fixed allocation for this process
    int      *owned_frames;          // Array of frame numbers
    int      clock_hand;             // Local clock hand position
    list_t   local_lru_list;         // Process-local LRU list
};
 
struct frame {
    int      frame_number;
    pid_t    owner;                  // Owning process
    int      page_number;
    bool     reference_bit;
    bool     modified_bit;
};
 
/**
 * Local replacement victim selection
 * ONLY examines frames belonging to the faulting process
 */
int select_local_victim(struct process_frame_allocation *pfa,
                        struct frame *global_frames) {
    /* Key difference: we ONLY look at this process's frames */
    int best_victim_idx = -1;
    int best_score = INT_MIN;
    
    for (int i = 0; i < pfa->num_frames; i++) {
        int frame_num = pfa->owned_frames[i];
        struct frame *f = &global_frames[frame_num];
        
        /* Confirm this frame belongs to our process */
        assert(f->owner == pfa->process_id);
        
        int score = compute_replacement_score(f);
        if (score > best_score) {
            best_score = score;
            best_victim_idx = i;
        }
    }
    
    if (best_victim_idx >= 0) {
        int victim_frame = pfa->owned_frames[best_victim_idx];
        struct frame *victim = &global_frames[victim_frame];
        
        /* Handle dirty page write-back */
        if (victim->modified_bit) {
            schedule_page_write(victim);
        }
        
        /* The victim ALWAYS belongs to the faulting process */
        return victim_frame;
    }
    
    return -1;  // Should never happen if allocation > 0
}
 
/**
 * Example scenario:
 * 
 * Process A: owns frames [0, 3, 7, 12]   (4 frames)
 * Process B: owns frames [1, 2, 5, 8]    (4 frames)
 * Process C: owns frames [4, 6, 9, 10, 11] (5 frames)
 * 
 * If Process A page faults:
 *   - Algorithm scans ONLY frames 0, 3, 7, 12
 *   - Cannot select frames 1, 2, 4, 5, 6, 8, 9, 10, 11
 *   - Victim is guaranteed to be one of A's pages
 *   - Process B and C are completely unaffected
 */

Key characteristics of local replacement:

Partitioned memory pool: Each process has its own frame set
Self-contained selection: Victims come only from the faulting process
Zero interference: Other processes cannot lose frames due to your faults
Fixed guarantees: A process always retains its allocation (unless modified by policy)
Per-process optimization: Replacement optimizes for the individual process, not the system

How Local Replacement Works

The page fault handling sequence under local replacement is similar to global replacement—but with one critical constraint: the search for a victim is scoped to the faulting process only.

Step-by-step page fault handling with local replacement:

Local Replacement Page Fault Sequence

•Page Fault Trigger: Process P accesses virtual address V, and the page table shows valid = 0
•Hardware Trap: MMU raises page fault exception, transferring control to OS page fault handler
•Check Process P's Free Frames: Does P have any unused frames in its allocation? If yes, use one and skip to step 7
•Process P's Allocation Full: All of P's frames are in use; must select a victim
•Local Victim Selection: Scan ONLY P's frames using the replacement algorithm (e.g., local clock, local LRU)
•Page-Out if Dirty: If victim page was modified, write it to swap
•Update Page Table: Mark P's page table entry for victim page as invalid
•Page-In: Load the faulting page into the now-free frame
•Update Page Table: Mark P's page table entry for V as valid, pointing to the frame
•Resume Execution: Return from fault handler and re-execute the instruction

Converting Mermaid diagram...

The critical difference:

Notice that in step 5, the algorithm strictly scans only Process P's frames. Even if Process Q has pages that haven't been accessed in days, they are invisible to P's replacement algorithm. The isolation is absolute: P manages its own memory, Q manages its own memory, and they never interact through the paging system.

Implementing Local Replacement

Local replacement requires per-process data structures to track frame ownership and enable efficient scoped victim selection. The implementation is inherently more complex than global replacement because the OS must maintain separation between process memory domains.

Per-process frame tracking structures:

local_frame_management.c
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
/**
 * Local Replacement Data Structures
 * 
 * Each process maintains its own replacement state,
 * completely independent of other processes.
 */
 
/* Per-process memory management structure */
struct process_memory {
    pid_t       pid;
    
    /* Frame allocation */
    int         allocated_frames;     // Total frames given to process
    int         used_frames;          // Currently used frames
    bitset_t    frame_bitmap;         // Which frames belong to us
    
    /* Local replacement algorithm state */
    list_head_t local_active_list;    // Recently accessed pages
    list_head_t local_inactive_list;  // Candidates for eviction
    spinlock_t  local_lru_lock;
    
    /* Local clock algorithm state */
    int         local_clock_hand;      // Clock hand for this process only
    
    /* Performance tracking */
    uint64_t    page_faults;
    uint64_t    page_evictions;
    uint64_t    disk_reads;
    uint64_t    disk_writes;
};
 
/* Process control block extension for memory */
struct task_struct {
    /* ... other task fields ... */
    struct process_memory *mm_local;  // Local memory management
};
 
/**
 * Allocate frames to a new process (local replacement setup)
 */
int allocate_frames_to_process(struct process_memory *pm, 
                               int num_frames) {
    pm->allocated_frames = num_frames;
    pm->used_frames = 0;
    
    /* Find and reserve frames for this process */
    int allocated = 0;
    for (int f = 0; f < total_physical_frames && allocated < num_frames; f++) {
        if (is_frame_available(f)) {
            claim_frame_for_process(f, pm->pid);
            bitset_set(&pm->frame_bitmap, f);
            allocated++;
        }
    }
    
    if (allocated < num_frames) {
        /* Not enough frames available - process cannot start */
        release_claimed_frames(pm);
        return -ENOMEM;
    }
    
    /* Initialize local LRU lists (empty) */
    INIT_LIST_HEAD(&pm->local_active_list);
    INIT_LIST_HEAD(&pm->local_inactive_list);
    pm->local_clock_hand = 0;
    
    return 0;
}
 
/**
 * Local Clock Algorithm - Process-Scoped
 */
int local_clock_select_victim(struct process_memory *pm,
                              struct frame *global_frames) {
    spin_lock(&pm->local_lru_lock);
    
    int scanned = 0;
    int max_scan = pm->allocated_frames * 2;
    
    /* Find starting frame for this process */
    int frame_idx = find_nth_set_bit(&pm->frame_bitmap, 
                                      pm->local_clock_hand);
    
    while (scanned < max_scan) {
        struct frame *f = &global_frames[frame_idx];
        
        /* Verify this frame still belongs to us */
        if (f->owner != pm->pid) {
            /* Shouldn't happen, but defensive check */
            frame_idx = next_owned_frame(pm, frame_idx);
            continue;
        }
        
        if (f->reference_bit == 0 && !is_frame_locked(f)) {
            /* Found victim in OUR frames */
            pm->local_clock_hand = frame_idx;
            spin_unlock(&pm->local_lru_lock);
            
            pm->page_evictions++;
            return frame_idx;
        }
        
        /* Give second chance - clear reference bit */
        f->reference_bit = 0;
        
        /* Move to next frame WE OWN */
        frame_idx = next_owned_frame(pm, frame_idx);
        scanned++;
    }
    
    spin_unlock(&pm->local_lru_lock);
    
    /* All our frames are hot - must evict something anyway */
    return force_select_victim(pm);
}
 
/**
 * Helper: Get next frame owned by this process
 */
static int next_owned_frame(struct process_memory *pm, int current) {
    int next = (current + 1) % total_physical_frames;
    
    while (!bitset_test(&pm->frame_bitmap, next)) {
        next = (next + 1) % total_physical_frames;
        if (next == current) break;  // Wrapped around
    }
    
    return next;
}

Implementation Complexity

Local replacement requires significantly more bookkeeping than global replacement. Each process needs its own LRU lists, clock hands, and frame tracking bitmaps. The OS must ensure these structures remain synchronized with actual frame ownership, adding complexity to both page fault handling and process lifecycle management.

Frame Allocation Strategies

Local replacement requires a policy for determining how many frames each process receives. Unlike global replacement where allocation is implicit and dynamic, local replacement must explicitly partition memory among processes.

Common allocation strategies:

Frame Allocation Strategies for Local Replacement
Strategy	Description	Formula	Trade-offs
Equal Allocation	Every process gets the same number of frames	f = m / n (m frames, n processes)	Simple but ignores varying working sets
Proportional Allocation	Frames allocated based on process size	f_i = (s_i / S) × m	Better match to needs; complex tracking
Priority-Based	Higher priority processes get more frames	Weighted by priority factor	Supports QoS; may starve low priority
Working Set Based	Allocate frames matching observed working set	f_i = WSS_i	Most accurate; requires WSS tracking
Fixed Reservation	Administrator configures exact frame counts	Manual configuration	Full control; requires expertise

allocation_strategies.c
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
/**
 * Frame Allocation Strategies for Local Replacement
 */
 
/* System memory configuration */
#define TOTAL_FRAMES     1000
#define MIN_FRAMES       10    // Minimum per process
 
struct allocation_policy {
    int total_frames;
    int num_processes;
    int reserved_frames;  // For kernel, buffers, etc.
};
 
/**
 * Equal Allocation
 * Every process gets the same share
 */
int equal_allocation(struct allocation_policy *policy, 
                     struct process *proc) {
    int available = policy->total_frames - policy->reserved_frames;
    int per_process = available / policy->num_processes;
    
    return max(per_process, MIN_FRAMES);
}
 
/**
 * Proportional Allocation
 * Based on process virtual memory size
 */
int proportional_allocation(struct allocation_policy *policy,
                            struct process *proc,
                            struct process *all_procs[],
                            int num_procs) {
    /* Calculate total virtual memory across all processes */
    unsigned long total_vsize = 0;
    for (int i = 0; i < num_procs; i++) {
        total_vsize += all_procs[i]->virtual_size;
    }
    
    /* This process's proportion */
    unsigned long available = policy->total_frames - policy->reserved_frames;
    unsigned long share = (proc->virtual_size * available) / total_vsize;
    
    return max((int)share, MIN_FRAMES);
}
 
/**
 * Priority-Based Allocation
 * Higher priority = more frames
 */
int priority_allocation(struct allocation_policy *policy,
                        struct process *proc,
                        int total_priority_weight) {
    unsigned long available = policy->total_frames - policy->reserved_frames;
    
    /* Convert nice value to priority weight */
    int weight = priority_to_weight(proc->priority);
    
    /* Proportional to priority weight */
    int frames = (weight * available) / total_priority_weight;
    
    return max(frames, MIN_FRAMES);
}
 
/**
 * Example allocation scenario:
 * 
 * Total frames: 100
 * Reserved: 20 (kernel)
 * Available: 80
 * 
 * Process A: 200MB virtual, priority LOW
 * Process B: 400MB virtual, priority NORMAL
 * Process C: 600MB virtual, priority HIGH
 * 
 * Equal allocation:
 *   A = 26, B = 26, C = 26 (ignores differences)
 * 
 * Proportional (by size):
 *   A = 13, B = 27, C = 40 (matches memory needs)
 * 
 * Priority-weighted:
 *   A = 10, B = 20, C = 50 (high priority gets more)
 */

The Minimum Frames Constraint

Every process requires a minimum number of frames to make progress. This minimum depends on CPU architecture—specifically, the maximum number of pages a single instruction might reference (for operands, instruction fetch, and indirect addressing). If a process receives fewer frames than this minimum, it cannot complete even one instruction without faulting, leading to thrashing. Local replacement must respect these minimums or risk process starvation.

Advantages of Local Replacement

Local replacement offers distinct advantages that make it preferable in certain scenarios. Understanding these benefits reveals when process isolation should take precedence over system-wide optimization.

Primary advantages:

Key Benefits of Local Replacement

•Performance Isolation — A process's performance depends only on its own memory behavior, not on what other processes are doing. This enables predictable, reproducible performance.
•No Noisy Neighbors — Memory-hungry processes cannot degrade other processes' performance. Each processes lives within its allocation, period.
•Easier Debugging — When performance problems occur, they can be attributed to the process itself, not external interference. Diagnosis is straightforward.
•Guaranteed Frame Counts — A process knows exactly how many frames it has. This enables accurate capacity planning and resource provisioning.
•Fairness Enforcement — Resources are explicitly divided. A low-priority batch job cannot accidentally impact a high-priority service.
•Multi-Tenant Isolation — In shared environments (containers, VMs), local replacement prevents one tenant from affecting others.

Predictability Benefits

•Consistent page fault rates
•Reproducible benchmarks
•SLA compliance enabled
•Performance modeling possible

Isolation Benefits

•Security boundary for memory
•Denial of service prevention
•Resource guarantee enforcement
•Container/VM separation

Why Real-Time Systems Prefer Local Replacement

In real-time systems where latency bounds are critical, local replacement is often mandatory. A hard real-time task cannot tolerate variable page fault rates caused by unrelated processes. With local replacement, the task's page fault behavior is entirely deterministic based on its own access patterns—essential for meeting strict timing guarantees.

Disadvantages and Costs

Local replacement's isolation comes at a cost. The rigid partitioning of memory sacrifices flexibility and can lead to suboptimal overall system performance.

Primary costs and disadvantages:

Costs of Local Replacement

•Memory Underutilization — If one process doesn't need all its frames while another is thrashing, those unused frames sit idle. The system cannot redistribute.
•Inflexible to Workload Changes — A process stuck with too few frames cannot dynamically acquire more, even if memory is available elsewhere.
•Potential for Process Thrashing — A process with insufficient allocation will thrash within its own partition while other processes have excess frames.
•Complex Administration — Someone must decide how to partition memory. Poor decisions lead to inefficiency or process failure.
•Suboptimal System Throughput — By optimizing locally rather than globally, the total work completed by the system may be lower than under global replacement.
•Minimum Frame Constraints — Must ensure every process gets at least its minimum frames, which limits how many processes can run concurrently.

The Stranded Memory Problem

Consider Process A sleeping with 50 frames while Process B desperately needs more memory. Under local replacement, B cannot use A's frames. Those 50 frames are 'stranded'—allocated but not useful. Under global replacement, B would naturally acquire those frames. This stranded memory is the primary efficiency cost of local replacement.

stranded_memory_example.py
Python
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
"""
Stranded Memory Problem - Local Replacement Inefficiency
 
Demonstrates how local replacement can waste memory
when process demands are mismatched.
"""
 
# Scenario: 100 total frames, 3 processes, local replacement
 
class LocalReplacementSystem:
    def __init__(self):
        self.total_frames = 100
        
        # Fixed allocation under local replacement
        self.allocations = {
            "web_server": 40,  # Equal split
            "database": 40,    
            "logger": 20,
        }
        
    def simulate_workload_shift(self):
        """
        Workload changes over time - local replacement cannot adapt
        """
        
        # Initially: all processes active, allocation works
        initial_state = {
            "web_server": {"allocated": 40, "in_use": 38, "wasted": 2},
            "database": {"allocated": 40, "in_use": 40, "wasted": 0},
            "logger": {"allocated": 20, "in_use": 15, "wasted": 5},
        }
        
        # Later: database goes into maintenance (sleeping)
        # Web server gets traffic spike
        shifted_state = {
            "web_server": {
                "allocated": 40,
                "needs": 75,     # Traffic spike!
                "has": 40,       # Stuck at allocation
                "deficit": 35,   # THRASHING
                "page_faults_per_sec": 500,  # High due to thrashing
            },
            "database": {
                "allocated": 40,
                "needs": 5,      # Just connection handlers
                "has": 40,       # Still has full allocation
                "wasted": 35,    # 35 STRANDED FRAMES!
            },
            "logger": {
                "allocated": 20,
                "needs": 10,
                "has": 20,
                "wasted": 10,    # More stranded frames
            },
        }
        
        # Total stranded: 45 frames sitting unused
        # While web_server needs 35 more frames!
        
        # Under GLOBAL replacement:
        # - Database's 35 unused frames would flow to web_server
        # - Logger's 10 unused frames would flow to web_server  
        # - Web server would have 75+ frames, no thrashing
        
        print("Local Replacement: Stranded Memory Problem")
        print("-" * 50)
        print(f"Web server THRASHING: needs 75, has only 40")
        print(f"Database WASTING: using 5, holding 40 (35 stranded)")
        print(f"Logger WASTING: using 10, holding 20 (10 stranded)")
        print(f"\nTotal stranded frames: 45")
        print(f"Total system efficiency: {55}% of memory productive")
        print(f"\nWith global replacement:")
        print(f"  Memory would flow to web_server")
        print(f"  System efficiency: ~95%")
        
        return shifted_state
 
system = LocalReplacementSystem()
system.simulate_workload_shift()

When to Use Local Replacement

Despite its efficiency costs, local replacement is the right choice in specific scenarios where isolation and predictability outweigh throughput concerns.

Ideal scenarios for local replacement:

Scenarios Favoring Local Replacement
Scenario	Why Local Works Better	Example
Real-Time Systems	Predictable page fault timing required	Avionics, medical devices, industrial control
Multi-Tenant Cloud	Strict isolation between customers required	AWS, GCP, Azure compute instances
Security-Critical	Memory-based side-channel attack prevention	Cryptographic services, key management
Billing/Resource Accounting	Clear per-customer resource tracking needed	Metered services, shared clusters
SLA Compliance	Performance guarantees contractually required	Database hosting, financial systems
Reproducible Benchmarking	Need consistent, isolated measurements	Performance testing, research experiments

Questions to Determine if Local Replacement is Appropriate

•Do processes have strict performance SLAs that cannot tolerate interference?
•Is memory isolation a security requirement (preventing timing attacks, information leakage)?
•Must workload performance be reproducible across runs?
•Is the system running untrusted or multi-tenant code?
•Are processes relatively stable in their memory demands over time?
•Is there sufficient memory to give each process an adequate allocation?

Container Isolation in Practice

Modern container orchestration (Kubernetes, Docker) uses memory limits that effectively create local replacement boundaries. Each container receives a memory allocation it cannot exceed. This is local replacement with dynamic sizing—containers cannot steal from each other, but the orchestrator can adjust limits based on policy. This hybrid approach captures local replacement's isolation with some of global replacement's flexibility.

Real-World Applications

Local replacement principles appear in many practical systems, often combined with other mechanisms to balance isolation and efficiency.

Examples in production:

Linux Memory Cgroups (Local Replacement Boundaries)

•memory.max: Hard limit that creates a local replacement boundary—processes in this cgroup can only reclaim from each other
•memory.high: Soft limit that triggers aggressive reclaim within the cgroup before affecting others
•Hierarchical limits: Nested cgroups create hierarchical local replacement domains
•Container isolation: Docker/Kubernetes use cgroups to give each container its own memory partition

cgroup_local_replacement.sh
Bash
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
#!/bin/bash
# Setting up local replacement boundaries with cgroups v2
 
# Create cgroup for isolated application
sudo mkdir /sys/fs/cgroup/isolated_app
 
# Set hard memory limit - creates local replacement boundary
echo "1G" | sudo tee /sys/fs/cgroup/isolated_app/memory.max
 
# Processes in this cgroup cannot use more than 1GB
# When they hit the limit, they reclaim from EACH OTHER only
# Other system processes are protected (local replacement behavior)
 
# Move process into isolated cgroup
echo $$ | sudo tee /sys/fs/cgroup/isolated_app/cgroup.procs
 
# Now this shell and its children are subject to local replacement
# within their 1GB allocation
 
# Check current usage
cat /sys/fs/cgroup/isolated_app/memory.current
# Output: bytes used by this cgroup
 
# In this cgroup:
# - Page faults reclaim from other pages in the SAME cgroup
# - Cannot steal memory from processes outside the cgroup
# - Behaves as local replacement within the boundary
# - If allocation exhausted: OOM killer targets processes in cgroup

Windows Resource Management:

Windows Job Objects (Local Replacement Domains)

•Job Objects: Group of processes with shared resource limits—creates local replacement boundary
•Working Set Limits: Can set minimum and maximum working set per process, enforcing local behavior
•Process Memory Commit: Hard limit on committed virtual memory per process
•Foreground Priority: Interactive processes get protected working sets, preferring to trim background apps

Hybrid Reality

In practice, most production systems use neither pure global nor pure local replacement. They employ global replacement as the base but create local boundaries for isolation when needed. Linux cgroups, Windows Job Objects, and hypervisor memory management all implement this hybrid model—local replacement within boundaries, global replacement across the unconstrained system.

Summary: Local Replacement

We have thoroughly explored local page replacement—a memory management strategy that partitions physical memory into per-process allocations with strictly isolated replacement decisions.

Key Takeaways

•Definition — Local replacement constrains victim selection to frames owned by the faulting process only
•Implementation — Requires per-process frame tracking, local LRU lists, and allocation policies
•Primary benefit — Complete performance isolation; one process cannot impact another's memory behavior
•Primary cost — Memory underutilization when process demands are mismatched (stranded memory problem)
•Ideal scenarios — Real-time systems, multi-tenant environments, security-critical workloads, SLA-bound services
•Real-world forms — Linux cgroups, Windows Job Objects, container memory limits all implement local replacement boundaries

Next: Process Interference

In the next page, we examine the phenomenon of process interference in detail—how one process's memory behavior affects others under global replacement, and how local replacement prevents this interference at the cost of efficiency.

Page Complete

You now understand local replacement comprehensively—from its isolation principle to implementation complexity, advantages, costs, and real-world applications. This knowledge enables you to evaluate when process isolation should take precedence over system-wide efficiency in memory management design.