Detection Methods

Throughout this module, we've examined the definition, causes, and symptoms of thrashing. Now we synthesize this knowledge into systematic detection methods—algorithms and approaches that can identify thrashing reliably, automatically, and early enough to take corrective action.

Effective thrashing detection is the bridge between understanding and action. A system that can detect thrashing can prevent it; a system that cannot detect it will inevitably suffer catastrophic performance collapse.

Thrashing detection faces a fundamental challenge: we need to detect the problem before it becomes catastrophic, but the clearest signals appear after significant degradation has occurred.

The Detection Spectrum:

Detection Requirements:

An effective thrashing detection system should:

1. Be non-intrusive — Detection overhead shouldn't cause the problem it detects
2. Minimize false positives — Unnecessary load shedding wastes capacity
3. Minimize false negatives — Missing actual thrashing causes outages
4. Provide early warning — Enough lead time for intervention
5. Distinguish workload phases — Don't alarm on startup spikes
6. Support automation — Enable programmatic response

The most theoretically sound approach to thrashing detection is working set analysis. If we can measure each process's working set and compare the sum to available memory, we can predict thrashing before it occurs.

Working Set Estimation Methods:

Reference Bit Sampling Algorithm:

Algorithm: Working Set Estimation via Reference Bits

Inputs:
  - Δ = working set window (e.g., 10 seconds)
  - τ = sampling interval (e.g., 1 second)
  - history[process][page] = number of intervals page was referenced

Every τ seconds:
  For each process P:
    For each page pg in P's page table:
      If reference_bit(pg) == 1:
        history[P][pg] = Δ/τ  # Reset to max age
        clear reference_bit(pg)
      Else:
        history[P][pg] -= 1  # Age the entry
        If history[P][pg] <= 0:
          Remove pg from working set estimate
    
    WSS[P] = count of pages with history > 0

Thrashing Detection:
  If ∑ WSS[P] > available_memory * threshold:
    ALERT: Thrashing likely

This algorithm approximates working sets by observing which pages are accessed during each sampling interval. Pages not accessed for Δ seconds are dropped from the working set estimate.

Page Fault Frequency (PFF) provides a simpler, more practical detection approach than full working set tracking. Instead of measuring working sets directly, we observe the symptom of inadequate allocation: elevated fault rates.

PFF Detection Algorithm:

Algorithm: PFF-Based Thrashing Detection

Parameters:
  - upper_threshold = maximum acceptable fault rate per process
  - lower_threshold = minimum useful fault rate
  - global_threshold = system-wide fault rate threshold
  - sample_interval = measurement period

Every sample_interval:
  total_faults = 0
  processes_over_limit = 0
  
  For each process P:
    fault_rate[P] = faults(P) / sample_interval
    total_faults += fault_rate[P]
    
    If fault_rate[P] > upper_threshold:
      processes_over_limit += 1
      mark P as "needs more frames"
    
    If fault_rate[P] < lower_threshold:
      mark P as "can release frames"
  
  # Global thrashing detection
  If total_faults > global_threshold:
    If all processes marked "needs more frames":
      ALERT: THRASHING - reduce multiprogramming
    Else:
      ACTION: Rebalance frames from "can release" to "needs more"

Modern operating systems expose memory pressure indicators that provide early warning of potential thrashing. These metrics aggregate multiple signals into actionable information.

The most robust thrashing detection combines multiple indicators into a composite score. This approach reduces false positives by requiring multiple metrics to agree before alerting.

The Composite Detection Framework:

Algorithm: Composite Thrashing Detection

Metrics (each normalized to 0-100 scale):
  M1 = Memory pressure (PSI full, or MemAvailable/MemTotal inverted)
  M2 = Page fault rate (relative to baseline)
  M3 = I/O wait percentage
  M4 = Load average divergence from CPU utilization
  M5 = Swap activity rate

Weights (tunable based on system):
  W1 = 0.25  (memory pressure is primary indicator)
  W2 = 0.25  (fault rate is strong signal)
  W3 = 0.20  (I/O wait is reliable)
  W4 = 0.15  (load divergence is confirming)
  W5 = 0.15  (swap activity is confirming)

Composite Score:
  S = W1*M1 + W2*M2 + W3*M3 + W4*M4 + W5*M5

Thresholds:
  S < 30:  NORMAL
  30 ≤ S < 50:  WARNING
  50 ≤ S < 70:  CRITICAL
  S ≥ 70:  THRASHING

Metric Normalization:

To combine different metrics, we normalize each to a 0-100 scale:

Normalization ensures each metric contributes proportionally to the composite score.

For complex systems with variable workloads, machine learning approaches can learn thrashing patterns from historical data and detect anomalies that rule-based systems might miss.

ML Approaches for Thrashing Detection:

Practical ML Implementation:

# Simplified thrashing prediction using Isolation Forest
from sklearn.ensemble import IsolationForest
import numpy as np

class ThrashingPredictor:
    def __init__(self, contamination=0.05):
        # Contamination = expected fraction of anomalies
        self.model = IsolationForest(
            contamination=contamination,
            random_state=42,
            n_estimators=100
        )
        self.trained = False
    
    def train(self, normal_operation_data: np.ndarray):
        """
        Train on data from normal operation.
        Data shape: (n_samples, n_features)
        Features: [cpu_user, cpu_wait, mem_pct, fault_rate, swap_rate]
        """
        self.model.fit(normal_operation_data)
        self.trained = True
    
    def detect(self, current_metrics: np.ndarray) -> dict:
        """
        Detect if current metrics indicate thrashing.
        Returns prediction and anomaly score.
        """
        if not self.trained:
            return {'error': 'Model not trained'}
        
        # -1 = anomaly (potential thrashing)
        # +1 = normal
        prediction = self.model.predict(current_metrics.reshape(1, -1))[0]
        score = self.model.score_samples(current_metrics.reshape(1, -1))[0]
        
        return {
            'is_anomaly': prediction == -1,
            'anomaly_score': -score,  # Higher = more anomalous
            'status': 'POTENTIAL_THRASHING' if prediction == -1 else 'NORMAL'
        }

Detection approaches fall into two categories: real-time (detecting current thrashing) and predictive (anticipating future thrashing). Each has distinct use cases.

Predictive Detection Example:

Algorithm: Trend-Based Thrashing Prediction

Inputs:
  - memory_usage[] = last 60 samples of memory utilization
  - fault_rate[] = last 60 samples of page fault rate
  - horizon = prediction time (e.g., 5 minutes)

Process:
  1. Fit linear regression to recent memory_usage
     trend_mem = slope of regression
  
  2. Fit linear regression to recent fault_rate
     trend_fault = slope of regression
  
  3. Project forward:
     projected_mem = current_mem + trend_mem × horizon
     projected_fault = current_fault + trend_fault × horizon
  
  4. Risk assessment:
     If projected_mem > 90% AND projected_fault > baseline × 5:
       ALERT: Thrashing predicted in ~{horizon} minutes
       Recommended action: Preemptive load reduction

This simple linear extrapolation provides early warning for gradual memory pressure buildup.