Loading learning content...
When a running process demands a new page and physical memory is exhausted, the operating system faces a pivotal decision: from which pool of frames should the victim page be selected? This seemingly simple question has profound implications for system behavior, performance isolation, and overall memory utilization.
Global replacement represents one of the two fundamental approaches to this problem—an approach where the operating system treats all of physical memory as a single, shared resource. When any process needs a frame, the replacement algorithm considers every frame in memory, regardless of which process currently owns it.
By the end of this page, you will understand how global replacement works, why operating systems favor it for throughput optimization, its impact on process behavior, and the sophisticated mechanisms required to implement it effectively. You will gain the analytical skills to evaluate when global replacement excels and when its characteristics may prove problematic.
At its core, global replacement means that when a page fault occurs and no free frames are available, the page replacement algorithm examines all frames in physical memory to select the optimal victim—regardless of which process those frames belong to.
The fundamental principle:
In a global replacement scheme, physical memory is conceptualized as a unified resource pool shared among all processes. The operating system maintains complete authority over frame allocation, dynamically redistributing memory based on observed demand patterns. A process experiencing heavy page faults may effectively 'steal' frames from processes with lower memory pressure.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
/** * Global Page Replacement - Conceptual Model * * When a page fault occurs, the victim selection algorithm * examines frames across ALL processes in the system. */ struct frame { int frame_number; pid_t owning_process; // Process that owns this frame int page_number; // Page mapped in this frame bool reference_bit; // For LRU approximation bool modified_bit; // Dirty bit time_t last_access_time; // For true LRU (if tracked)}; struct global_frame_table { struct frame *frames; int total_frames; int free_frame_count; list_head_t free_list; // Free frames list_head_t active_list; // All frames in use}; /** * Global replacement victim selection * Examines ALL frames in the system, not just the faulting process */int select_global_victim(struct global_frame_table *gft, pid_t faulting_process) { struct frame *best_victim = NULL; int best_score = INT_MIN; /* Iterate over ALL frames in the system */ list_for_each_entry(frame, &gft->active_list, list) { int score = compute_replacement_score(frame); /* Note: We consider frames from ANY process, * not just 'faulting_process' */ if (score > best_score) { best_score = score; best_victim = frame; } } if (best_victim != NULL) { /* The victim might belong to process A while * the fault occurred in process B - this is the * essence of global replacement */ pid_t victim_owner = best_victim->owning_process; /* Update the victim process's page table */ invalidate_pte(victim_owner, best_victim->page_number); /* Handle dirty page if necessary */ if (best_victim->modified_bit) { schedule_page_write(best_victim); } return best_victim->frame_number; } return -1; // No frames available (shouldn't happen)}Key characteristics of global replacement:
To truly understand global replacement, we must trace through the complete lifecycle of a page fault under this policy. The mechanics reveal both the elegance and complexity of treating memory as a shared resource.
Step-by-step page fault handling with global replacement:
The critical observation:
Notice how in step 5, the victim frame can belong to any process in the system. If Process A causes a page fault but the LRU page in memory belongs to Process B, Process B loses a frame to satisfy Process A's demand. This is the defining characteristic of global replacement—and the source of both its power and its complications.
Implementing global replacement requires sophisticated data structures that track frame status across the entire system. The operating system must maintain a global view of all physical memory, enabling efficient victim selection under heavy load.
Core data structures for global replacement:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102
/** * Global Frame Management Infrastructure * * These structures enable system-wide frame tracking * and efficient global victim selection. */ /* Core frame descriptor - one per physical frame */struct page_frame { int frame_id; atomic_t ref_count; // Reference count for sharing unsigned long flags; // PG_locked, PG_dirty, etc. struct list_head lru_list; // Position in LRU list struct address_space *mapping; // File mapping (if any) pgoff_t index; // Page index in mapping struct mem_cgroup *mem_cg; // Memory control group void *virtual_address; // Kernel virtual address}; /* Page frame flags */#define PG_locked (1 << 0) // Frame is locked in memory#define PG_referenced (1 << 1) // Reference bit (accessed recently)#define PG_dirty (1 << 2) // Page modified#define PG_active (1 << 3) // On active list#define PG_swapcache (1 << 4) // In swap cache#define PG_unevictable (1 << 5) // Cannot be evicted (mlock'd) /* Global LRU lists - the heart of global replacement */struct lruvec { struct list_head lists[NR_LRU_LISTS]; unsigned long anon_cost; // Anonymous page costs unsigned long file_cost; // File-backed page costs atomic_long_t nonresident_age; // Non-resident tracking unsigned long refaults; // Refault tracking spinlock_t lru_lock; // Protect list operations}; /* LRU list types */enum lru_list { LRU_INACTIVE_ANON, // Cold anonymous pages LRU_ACTIVE_ANON, // Hot anonymous pages LRU_INACTIVE_FILE, // Cold file-backed pages LRU_ACTIVE_FILE, // Hot file-backed pages LRU_UNEVICTABLE, // Locked pages NR_LRU_LISTS}; /** * Move a page between LRU lists (global operation) * This affects the page's priority for eviction system-wide */void lru_cache_add(struct page_frame *page) { struct lruvec *lruvec = mem_cgroup_page_lruvec(page); enum lru_list lru = page_lru(page); spin_lock(&lruvec->lru_lock); /* Add to global LRU list - visible to all processes */ list_add(&page->lru_list, &lruvec->lists[lru]); update_lru_sizes(lruvec, lru, 1); spin_unlock(&lruvec->lru_lock);} /** * Shrink LRU list - global victim selection * Called when system memory pressure is high */unsigned long shrink_lru_list(struct lruvec *lruvec, unsigned long nr_to_scan, struct scan_control *sc) { struct list_head *lru_list; struct page_frame *page; unsigned long nr_reclaimed = 0; lru_list = &lruvec->lists[active_lru(sc)]; /* Scan pages from ANY process */ while (!list_empty(lru_list) && nr_to_scan > 0) { page = list_entry(lru_list->prev, struct page_frame, lru_list); /* Check if page can be reclaimed */ if (page_evictable(page) && !PageLocked(page)) { /* Try to reclaim - may affect any process */ if (try_to_unmap(page)) { if (PageDirty(page)) pageout(page); // Write back free_page_frame(page); nr_reclaimed++; } } list_move(&page->lru_list, &lruvec->lists[inactive_lru(sc)]); nr_to_scan--; } return nr_reclaimed;}Linux implements global replacement through a multi-tier LRU system. Pages move between 'active' and 'inactive' lists based on access patterns. When memory pressure occurs, the kernel's kswapd daemon scans the inactive lists across all zones to find reclaimable pages, regardless of owning process. This is a sophisticated implementation of global replacement with additional heuristics for distinguishing file-backed and anonymous pages.
The Clock algorithm—a practical LRU approximation—demonstrates clearly how global replacement operates across process boundaries. When implemented globally, the clock hand sweeps across frames belonging to all processes, treating physical memory as a circular buffer.
Global Clock algorithm characteristics:
| Property | Global Behavior | Significance |
|---|---|---|
| Clock Hand Position | Single hand for entire physical memory | Unified traversal across all process frames |
| Reference Bit Checking | Examines reference bits of all frames | Finds least recently used page system-wide |
| Victim Selection | First frame with reference bit = 0 | May belong to any process |
| Second Chance | Applied equally to all processes | Recently accessed pages protected regardless of owner |
| Fairness | Based on access patterns, not process identity | Active processes gain frames; idle processes lose them |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
/** * Global Clock Algorithm Implementation * * A single clock hand sweeps across ALL physical frames, * providing LRU approximation across all processes. */ struct global_clock { struct frame *frames; // All physical frames int total_frames; int hand; // Current clock hand position spinlock_t lock;}; static struct global_clock gclock; /** * Initialize global clock structure * Called during system boot */void init_global_clock(int num_frames) { gclock.frames = kmalloc(sizeof(struct frame) * num_frames); gclock.total_frames = num_frames; gclock.hand = 0; spin_lock_init(&gclock.lock); for (int i = 0; i < num_frames; i++) { gclock.frames[i].frame_number = i; gclock.frames[i].owning_process = -1; // Free gclock.frames[i].reference_bit = 0; gclock.frames[i].modified_bit = 0; }} /** * Select victim using global clock algorithm * Returns frame number of selected victim */int global_clock_select_victim(pid_t requesting_process) { spin_lock(&gclock.lock); int frames_scanned = 0; /* Sweep through ALL frames, regardless of owner */ while (frames_scanned < gclock.total_frames * 2) { struct frame *current = &gclock.frames[gclock.hand]; /* Skip frames that cannot be evicted */ if (is_frame_locked(current) || is_frame_pinned(current)) { advance_hand(); frames_scanned++; continue; } /* Check reference bit */ if (current->reference_bit == 0) { /* VICTIM FOUND - could be from ANY process! */ pid_t victim_owner = current->owning_process; /* This is the key: we don't care if victim_owner * equals requesting_process or not */ /* Prepare for eviction */ struct victim_info victim = { .frame_number = current->frame_number, .owning_process = victim_owner, .page_number = current->page_number, .is_dirty = current->modified_bit }; advance_hand(); spin_unlock(&gclock.lock); return victim.frame_number; } /* Give second chance: clear reference bit */ current->reference_bit = 0; advance_hand(); frames_scanned++; } spin_unlock(&gclock.lock); /* No victim found - extremely high memory pressure */ return -1; // Trigger OOM or wait} static void advance_hand(void) { gclock.hand = (gclock.hand + 1) % gclock.total_frames;} /** * Example: Global clock in action * * System state: * Frame 0: Process A, Page 5, ref=1 * Frame 1: Process B, Page 2, ref=0 <- Victim selected * Frame 2: Process A, Page 8, ref=1 * Frame 3: Process C, Page 1, ref=1 * Frame 4: Process B, Page 7, ref=0 * * If Process C causes a page fault: * - Clock hand might be at Frame 0 * - Skips Frame 0 (ref=1, clears to ref=0) * - Selects Frame 1 (ref=0) as victim * - Process B loses its page 2! * - Process C gets Frame 1 for its new page */The power of global clock:
In the example above, Process C needed a frame and Process B was the 'victim'—not because Process B was doing anything wrong, but simply because its Page 2 hadn't been accessed recently. The global clock algorithm automatically shifts memory toward active processes and away from idle ones.
Global replacement offers compelling benefits that explain why it remains the dominant strategy in modern operating systems. Understanding these advantages illuminates the design philosophies underlying memory management.
Primary advantages:
Server environments particularly benefit from global replacement. Consider a web server where thousands of connections experience varying load patterns throughout the day. Global replacement automatically dedicates more memory to peak-load processes while reclaiming frames from idle connection handlers. This dynamic adaptation is far more efficient than any static allocation could be.
While global replacement offers significant performance benefits, it introduces risks that system designers must carefully consider. The shared memory pool model creates potential failure modes absent in isolated allocation schemes.
Primary risks and disadvantages:
In cloud computing, global replacement within a host can create 'noisy neighbors'—virtual machines that consume disproportionate memory at the expense of co-located VMs. This is why cloud providers often use memory isolation mechanisms (like cgroups in Linux) to limit each tenant's access to the global frame pool, partially overriding pure global replacement to achieve fairness guarantees.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
"""Noisy Neighbor Problem Demonstration This example shows how one process can degrade others through global replacement frame stealing.""" import timeimport threading # Shared system state (simulated)TOTAL_FRAMES = 100frames_per_process = {} def memory_hog(): """Process that touches huge amounts of memory""" process_id = "hog" # Initially, system gives this process just 33 frames frames_per_process[process_id] = 33 print(f"Memory hog starting with {frames_per_process[process_id]} frames") # Now allocate massive working set # With global replacement, it STEALS from others for i in range(10): # Each iteration causes page faults # Global replacement gives more frames to satisfy demand frames_per_process[process_id] += 5 # These frames come FROM other processes! for other in frames_per_process: if other != process_id and frames_per_process[other] > 10: frames_per_process[other] -= 2 print_frame_distribution() time.sleep(1) def database_process(): """Critical database process - needs consistent memory""" process_id = "database" frames_per_process[process_id] = 33 while True: current_frames = frames_per_process.get(process_id, 0) if current_frames < 20: print(f"⚠️ DATABASE DEGRADED: Only {current_frames} frames!") print(" Query latency will spike dramatically") time.sleep(1) def web_server(): """Web server process - loses frames to the hog""" process_id = "webserver" frames_per_process[process_id] = 34 while True: current_frames = frames_per_process.get(process_id, 0) if current_frames < 25: print(f"⚠️ WEB SERVER SLOW: {current_frames} frames insufficient") time.sleep(1) def print_frame_distribution(): total = sum(frames_per_process.values()) print(f"\nFrame distribution (total: {total}/{TOTAL_FRAMES}):") for proc, frames in frames_per_process.items(): bar = '█' * (frames // 2) print(f" {proc:12}: {bar} ({frames})") # Output after several iterations:## Frame distribution (total: 100/100):# hog : ████████████████████████████████ (78)# database : ██████ (12) # BELOW WORKING SET!# webserver : █████ (10) # SEVERELY STARVED!## Result: Memory hog causes database and web server to thrashModern operating systems employ several techniques to retain global replacement's benefits while limiting its downsides. These mechanisms add constraints to the pure global model, creating hybrid approaches.
Key mitigation strategies:
| Technique | How It Works | Protection Level |
|---|---|---|
| Memory Cgroups | Limit maximum memory consumption per process group | Strong isolation between control groups |
| OOM Killer | Terminate runaway processes before system-wide collapse | Last resort protection; kills rather than constrains |
| Memory Soft Limits | Allow burst above limit but reclaim aggressively when others need memory | Moderate; allows flexibility with eventual constraints |
| Working Set Estimation | Monitor process working sets; resist allocation below estimated WSS | Moderate; prevents catastrophic undersizing |
| Priority-Based Scanning | Scan low-priority processes first during reclamation | Protects important processes from frame stealing |
| mlock() System Call | Allow processes to lock critical pages in memory | Strong for specific pages; limited capacity |
12345678910111213141516171819202122232425262728
#!/bin/bash# Using Linux cgroups to constrain global replacement scope # Create a memory cgroup for potentially hungry processessudo cgcreate -g memory:/memory_limited # Set maximum memory limit to 1GB# This process cannot steal frames beyond this limitsudo cgset -r memory.max=1073741824 memory_limited # Set high-water mark for reclamation priority (soft limit)sudo cgset -r memory.high=536870912 memory_limited # Run the memory-intensive process in this cgroupsudo cgexec -g memory:memory_limited ./memory_hog_process # Effect: Even with global replacement, this process# is constrained to steal frames only up to the limit.# Other processes are protected from this "noisy neighbor." # Check current memory usagecat /sys/fs/cgroup/memory_limited/memory.current# Output: bytes currently used # Check page fault statisticscat /sys/fs/cgroup/memory_limited/memory.stat# pgfault: total page faults# pgmajfault: major page faults (from disk)Production systems typically combine multiple mitigation strategies. A robust configuration might use cgroups for hard limits, soft limits for flexible burst handling, priority-based scanning for QoS differentiation, and the OOM killer as an emergency backstop. This layered approach preserves global replacement's efficiency while providing isolation when needed.
Major operating systems implement global replacement with varying degrees of sophistication. Understanding these implementations reveals how theory translates to practice.
Linux implementation:
Windows implementation:
Both Linux and Windows technically use global replacement but augment it with per-process tracking (working sets) and constraints (cgroups/job objects). This hybrid model captures most of global replacement's efficiency benefits while providing tools for administrators to enforce isolation when required. Pure global replacement—with absolutely no per-process consideration—is rare in production systems.
We have thoroughly explored global page replacement—a memory management strategy that treats all frames as a shared, system-wide resource.
Next: Local Replacement
In the next page, we examine the contrasting approach—local replacement—where page replacement decisions are constrained to each process's own frame allocation. We will explore how this isolation model protects processes from each other while potentially sacrificing overall system efficiency.
You now understand global replacement in depth—from its fundamental principle of shared memory pools to implementation details, advantages, risks, and real-world mitigations. This knowledge prepares you to evaluate memory management policies and understand why modern operating systems favor global replacement with carefully designed safeguards.