Global vs Local Replacement

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

/**
 * Process Interference Types - Illustration
 * 
 * Different interference patterns and their effects
 */
 
/* Scenario 1: Direct Frame Stealing */
void direct_stealing_example() {
    /*
     * Initial State:
     *   Process A: frames [0,1,2,3]
     *   Process B: frames [4,5,6,7]
     *   Process C: frames [8,9,10,11]
     *   Free frames: 0
     *
     * Event: Process A accesses new page, causes fault
     * 
     * Action: Global LRU selects frame 5 (Process B's)
     *         Process B's page evicted
     *         Frame 5 now belongs to Process A
     *
     * Result: Process A benefits; Process B degraded
     */
}
 
/* Scenario 2: Cascading Eviction */
void cascading_eviction_example() {
    /*
     * Time T0: Process A faults, evicts Process B's page
     * Time T1: Process B runs, faults on evicted page
     *          Evicts Process C's page to recover
     * Time T2: Process C runs, faults on evicted page
     *          Evicts Process D's page to recover
     * Time T3: Process D runs, faults...
     *
     * Result: A single page fault in A eventually impacts
     *         multiple processes (B, C, D) in cascade
     *
     * This is particularly severe because:
     * - Each fault adds disk I/O latency (5-10ms each)
     * - System throughput drops dramatically
     * - CPU utilization plummets (processes waiting on I/O)
     */
}
 
/* Scenario 3: Working Set Collapse */
void working_set_collapse_example() {
    /*
     * Process "Database": Working Set Size = 50 frames
     * Currently allocated: 55 frames (comfortable margin)
     *
     * Memory hog starts: steals 30 frames over 2 seconds
     * Database now has: 25 frames (below WSS!)
     *
     * Result: Database enters thrashing:
     *   - Every query causes multiple page faults
     *   - Query latency jumps from 5ms to 500ms
     *   - Throughput drops 100x
     *   - But memory hog is "working fine"!
     *
     * The collapse is non-linear:
     *   55 frames: normal operation
     *   50 frames: slight degradation
     *   45 frames: moderate degradation
     *   40 frames: significant faulting
     *   25 frames: CATASTROPHIC (below WSS cliff)
     */
}
 
/* Scenario 4: Priority Inversion */
void priority_inversion_example() {
    /*
     * Process "interactive_ui": HIGH priority, needs fast response
     * Process "batch_job":      LOW priority, crunches data
     *
     * Expectation: batch_job yields resources to interactive_ui
     *
     * Reality with global replacement:
     *   - batch_job touches huge data set
     *   - LRU doesn't consider priority
     *   - batch_job evicts interactive_ui's pages
     *   - User experiences lag in UI
     *
     * This is priority inversion via memory:
     *   Low-priority process degrades high-priority process
     */
}

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
130
131
132
133
134
135

"""
Process Interference Detection and Measurement
 
Tools and techniques for identifying interference in running systems.
"""
 
import subprocess
import time
from collections import defaultdict
 
class InterferenceDetector:
    """
    Monitors system for signs of process interference
    """
    
    def __init__(self):
        self.baseline_faults = {}
        self.current_faults = {}
        self.interference_events = []
    
    def capture_baseline(self, process_pid):
        """
        Record baseline page fault behavior for a process.
        Should be captured when system is under normal load.
        """
        stats = self._read_proc_stat(process_pid)
        self.baseline_faults[process_pid] = {
            'minor_faults': stats['minflt'],
            'major_faults': stats['majflt'],
            'timestamp': time.time(),
            'rss_pages': stats['rss'],
        }
    
    def detect_interference(self, process_pid):
        """
        Compare current behavior to baseline.
        Returns interference score (0 = none, 1.0+ = significant)
        """
        current = self._read_proc_stat(process_pid)
        baseline = self.baseline_faults.get(process_pid)
        
        if not baseline:
            return 0.0  # No baseline for comparison
        
        time_delta = time.time() - baseline['timestamp']
        
        # Calculate fault rate changes
        baseline_major_rate = baseline['major_faults'] / time_delta
        current_major_rate = current['majflt'] / time_delta
        
        # Major fault increase is primary interference signal
        if baseline_major_rate > 0:
            fault_increase_ratio = current_major_rate / baseline_major_rate
        else:
            fault_increase_ratio = current_major_rate * 100  # Any faults are new
        
        # RSS shrinkage indicates memory being stolen
        rss_shrinkage = (baseline['rss_pages'] - current['rss']) / baseline['rss_pages']
        
        # Composite interference score
        interference_score = (fault_increase_ratio * 0.7) + (max(0, rss_shrinkage) * 30)
        
        if interference_score > 1.5:
            self.interference_events.append({
                'victim_pid': process_pid,
                'score': interference_score,
                'fault_increase': fault_increase_ratio,
                'rss_lost_pct': rss_shrinkage * 100,
                'timestamp': time.time(),
            })
        
        return interference_score
    
    def find_aggressor(self, victim_pid):
        """
        Identify process most likely causing interference.
        Look for processes with rapidly growing RSS during victim's degradation.
        """
        all_processes = self._list_all_processes()
        
        suspects = []
        for pid in all_processes:
            if pid == victim_pid:
                continue
            
            stats = self._read_proc_stat(pid)
            if pid in self.baseline_faults:
                baseline = self.baseline_faults[pid]
                rss_growth = stats['rss'] - baseline['rss_pages']
                
                if rss_growth > 0:
                    suspects.append({
                        'pid': pid,
                        'rss_growth': rss_growth,
                        'fault_rate': stats['majflt'],
                    })
        
        # Sort by RSS growth - biggest grower is prime suspect
        suspects.sort(key=lambda x: x['rss_growth'], reverse=True)
        
        return suspects[:3]  # Return top 3 suspects
    
    def print_interference_report(self):
        """Generate human-readable interference analysis"""
        print("\n" + "="*60)
        print("PROCESS INTERFERENCE REPORT")
        print("="*60)
        
        for event in self.interference_events:
            print(f"\nVictim PID: {event['victim_pid']}")
            print(f"  Interference Score: {event['score']:.2f}")
            print(f"  Page Fault Increase: {event['fault_increase']:.1f}x baseline")
            print(f"  RSS Lost: {event['rss_lost_pct']:.1f}%")
            
            aggressors = self.find_aggressor(event['victim_pid'])
            if aggressors:
                print(f"  Likely Aggressors:")
                for a in aggressors:
                    print(f"    PID {a['pid']}: grew {a['rss_growth']} pages")
    
    def _read_proc_stat(self, pid):
        """Read process statistics from /proc"""
        with open(f'/proc/{pid}/stat', 'r') as f:
            fields = f.read().split()
            return {
                'minflt': int(fields[9]),
                'majflt': int(fields[11]),
                'rss': int(fields[23]),
            }
    
    def _list_all_processes(self):
        """Get list of all running process PIDs"""
        result = subprocess.run(['pgrep', '-x', '.*'], 
                                capture_output=True, text=True)
        return [int(pid) for pid in result.stdout.strip().split()]

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

/**
 * Demonstration of Interference Impact on Performance
 * 
 * This illustrates the domino effect of memory interference.
 */
 
#include <stdio.h>
#include <time.h>
 
/* Simulated database query function */
double execute_query(int query_id, int useful_pages_in_memory) {
    /* 
     * Query needs to access 20 pages of data
     * If those pages are in memory: fast (< 1ms)
     * If evicted due to interference: slow (10ms per page fault)
     */
    const int pages_needed = 20;
    const double disk_latency_ms = 10.0;
    const double memory_latency_ms = 0.001;
    
    int pages_in_memory = (useful_pages_in_memory > pages_needed) 
                           ? pages_needed 
                           : useful_pages_in_memory;
    int pages_on_disk = pages_needed - pages_in_memory;
    
    double total_latency = (pages_in_memory * memory_latency_ms) +
                           (pages_on_disk * disk_latency_ms);
    
    return total_latency;
}
 
void demonstrate_interference_impact() {
    printf("=== Interference Impact Demonstration ===
 
");
    
    /* Scenario 1: No interference - database has adequate memory */
    printf("SCENARIO 1: Normal Operation (no interference)
");
    printf("  Database has 100 frames, needs ~80 for working set
");
    
    double normal_latency = execute_query(1, 100);
    printf("  Query latency: %.2f ms
", normal_latency);
    printf("  Queries per second: %.0f
 
", 1000.0 / normal_latency);
    
    /* Scenario 2: Mild interference - lost 30% of frames */
    printf("SCENARIO 2: Mild Interference
");
    printf("  Memory hog stole 30 frames, database has 70
");
    
    double mild_latency = execute_query(1, 70);
    printf("  Query latency: %.2f ms
", mild_latency);
    printf("  Queries per second: %.0f
", 1000.0 / mild_latency);
    printf("  Degradation: %.1fx slower
 
", mild_latency / normal_latency);
    
    /* Scenario 3: Severe interference - lost 60% of frames */
    printf("SCENARIO 3: Severe Interference
");
    printf("  Memory hog stole 60 frames, database has 40
");
    
    double severe_latency = execute_query(1, 40);
    printf("  Query latency: %.2f ms
", severe_latency);
    printf("  Queries per second: %.0f
", 1000.0 / severe_latency);
    printf("  Degradation: %.1fx slower
 
", severe_latency / normal_latency);
    
    /* Scenario 4: Catastrophic - below working set */
    printf("SCENARIO 4: Catastrophic (Below Working Set)
");
    printf("  Memory hog stole 90 frames, database has only 10
");
    
    double catastrophic_latency = execute_query(1, 10);
    printf("  Query latency: %.2f ms
", catastrophic_latency);
    printf("  Queries per second: %.0f
", 1000.0 / catastrophic_latency);
    printf("  Degradation: %.1fx slower
", catastrophic_latency / normal_latency);
    printf("  Status: DATABASE ESSENTIALLY UNUSABLE
");
}
 
/* Output:
 *
 * === Interference Impact Demonstration ===
 * 
 * SCENARIO 1: Normal Operation (no interference)
 *   Database has 100 frames, needs ~80 for working set
 *   Query latency: 0.02 ms
 *   Queries per second: 50000
 * 
 * SCENARIO 2: Mild Interference
 *   Memory hog stole 30 frames, database has 70
 *   Query latency: 0.02 ms
 *   Queries per second: 50000
 *   Degradation: 1.0x slower
 * 
 * SCENARIO 3: Severe Interference
 *   Memory hog stole 60 frames, database has 40
 *   Query latency: 0.04 ms
 *   Queries per second: 25000
 *   Degradation: 2.0x slower
 * 
 * SCENARIO 4: Catastrophic (Below Working Set)
 *   Memory hog stole 90 frames, database has only 10
 *   Query latency: 100.01 ms
 *   Queries per second: 10
 *   Degradation: 5000.0x slower
 *   Status: DATABASE ESSENTIALLY UNUSABLE
 */

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

#!/bin/bash
# Interference Prevention Configurations
 
# ============================================
# 1. Hard Memory Limits (cgroups v2)
# ============================================
 
# Create isolated cgroup for untrusted workload
mkdir -p /sys/fs/cgroup/untrusted
echo "2G" > /sys/fs/cgroup/untrusted/memory.max
# Cannot exceed 2GB regardless of system memory
 
# Critical service gets guaranteed memory
mkdir -p /sys/fs/cgroup/database
echo "4G" > /sys/fs/cgroup/database/memory.min  # GUARANTEED minimum
echo "8G" > /sys/fs/cgroup/database/memory.max   # Maximum cap
 
# ============================================
# 2. OOM Killer Tuning
# ============================================
 
# Make the database process very resistant to OOM killing
echo -1000 > /proc/$(pgrep postgres)/oom_score_adj
# -1000 = never kill this process (except as last resort)
 
# Make batch jobs expendable
echo 1000 > /proc/$(pgrep batch_job)/oom_score_adj
# 1000 = kill this first when memory exhausted
 
# ============================================
# 3. Memory Locking for Critical Pages
# ============================================
 
# In the critical application, lock working set:
# mlockall(MCL_CURRENT | MCL_FUTURE);
# These pages CANNOT be evicted by any other process
 
# Check locked memory for a process:
grep VmLck /proc/$(pgrep critical_app)/status
# VmLck: 52428 kB  <- 50MB locked
 
# ============================================
# 4. Systemd Service Memory Configuration
# ============================================
 
# In /etc/systemd/system/database.service:
cat << 'EOF'
[Service]
MemoryMin=2G           # Guaranteed minimum - protected from interference
MemoryHigh=6G          # Reclaim aggressively above this
MemoryMax=8G           # Hard limit
MemorySwapMax=0        # No swapping for this service
OOMScoreAdjust=-500    # Resistant to OOM killer
EOF
 
# ============================================
# 5. Docker Container Memory Isolation
# ============================================
 
# Run container with explicit memory limits
docker run -d     --memory=4g     --memory-reservation=2g     --oom-kill-disable=false     --oom-score-adj=-500     my_critical_app
 
# This container:
# - Gets 4GB max (hard limit)
# - Gets 2GB minimum (soft reservation)
# - Can be OOM killed if necessary (but with low priority)
 
# ============================================
# 6. Kubernetes Pod Resource Guarantees
# ============================================
 
cat << 'EOF' > critical-pod.yaml
apiVersion: v1
kind: Pod
metadata:
  name: critical-database
spec:
  containers:
  - name: postgres
    resources:
      requests:
        memory: "4Gi"   # Guaranteed minimum (affects scheduling)
      limits:
        memory: "8Gi"   # Maximum allowed
EOF
# Kubernetes scheduler ensures node has 4Gi available
# Container killed if it exceeds 8Gi

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

"""
Automated Interference Detection and Response System
 
Monitors for interference and takes corrective action.
"""
 
import time
import subprocess
import logging
 
logging.basicConfig(level=logging.INFO)
log = logging.getLogger('interference_responder')
 
class InterferenceResponder:
    """
    Monitors memory metrics and responds to interference events
    """
    
    def __init__(self, protected_cgroup, expendable_cgroups):
        self.protected = protected_cgroup
        self.expendable = expendable_cgroups
        
        # Thresholds
        self.pressure_threshold = 0.8     # 80% memory pressure = action
        self.fault_rate_threshold = 100   # >100 faults/sec = concerning
        self.refault_threshold = 0.5      # >50% refaults = thrashing
        
    def monitor_loop(self):
        """Continuous monitoring with automatic response"""
        while True:
            protection_needed = self._check_protected_process()
            
            if protection_needed:
                log.warning("Protected process interference detected!")
                self._take_protective_action()
            
            time.sleep(5)  # Check every 5 seconds
    
    def _check_protected_process(self):
        """Check if protected cgroup is experiencing interference"""
        
        # Read memory.pressure from cgroup
        pressure = self._read_pressure(self.protected)
        
        # Read page fault statistics
        stats = self._read_memory_stats(self.protected)
        refault_ratio = stats.get('workingset_refault_anon', 0) / max(stats.get('pgfault', 1), 1)
        
        log.debug(f"Protected cgroup: pressure={pressure:.2f}, refault_ratio={refault_ratio:.2f}")
        
        # Interference detected if:
        # - High memory pressure (pages being reclaimed)
        # - AND high refault ratio (those pages immediately needed again)
        return pressure > self.pressure_threshold and refault_ratio > self.refault_threshold
    
    def _take_protective_action(self):
        """Reduce memory pressure on protected process"""
        
        log.info("Taking protective action")
        
        # Strategy 1: Force low-priority cgroups to release memory
        for cgroup in self.expendable:
            current_high = self._read_memory_high(cgroup)
            
            # Reduce their memory.high to force reclamation
            reduced = int(current_high * 0.75)  # Reduce by 25%
            self._write_memory_high(cgroup, reduced)
            
            log.info(f"Reduced {cgroup} memory.high to {reduced / 1e9:.2f}GB")
        
        # Wait for reclamation to take effect
        time.sleep(2)
        
        # Strategy 2: If still under pressure, use memory.reclaim
        if self._check_protected_process():
            log.warning("Still under pressure, forcing reclamation")
            
            for cgroup in self.expendable:
                self._force_reclaim(cgroup, amount_bytes=512 * 1024 * 1024)
                log.info(f"Force-reclaimed 512MB from {cgroup}")
        
        # Strategy 3: If critical, throttle CPU of aggressors
        if self._check_protected_process():
            log.error("Critical interference - throttling aggressors")
            
            for cgroup in self.expendable:
                self._apply_cpu_throttle(cgroup, limit_percent=25)
                log.info(f"Throttled {cgroup} to 25% CPU")
    
    def _read_pressure(self, cgroup_path):
        """Read memory pressure (some avg 10)"""
        try:
            with open(f'{cgroup_path}/memory.pressure', 'r') as f:
                # Line format: some avg10=0.00 avg60=0.00 avg300=0.00 total=0
                for line in f:
                    if line.startswith('some'):
                        parts = line.split()
                        avg10 = float(parts[1].split('=')[1])
                        return avg10 / 100.0  # Convert to 0-1 scale
        except:
            pass
        return 0.0
    
    def _force_reclaim(self, cgroup_path, amount_bytes):
        """Use memory.reclaim to force page eviction"""
        try:
            with open(f'{cgroup_path}/memory.reclaim', 'w') as f:
                f.write(str(amount_bytes))
        except PermissionError:
            log.error(f"Cannot force reclaim from {cgroup_path}")
 
# Example usage:
# responder = InterferenceResponder(
#     protected_cgroup='/sys/fs/cgroup/production/database',
#     expendable_cgroups=[
#         '/sys/fs/cgroup/batch',
#         '/sys/fs/cgroup/development',
#     ]
# )
# responder.monitor_loop()