Lrtf And Hrrn - Learning Module

Loading content...

0/240

Response Ratio Formula: Mathematical Foundations

The Mathematics Behind Fair Scheduling

In the previous section, we introduced the response ratio formula as HRRN's core priority metric:

R = (W + S) / S = 1 + W/S

This deceptively simple formula encapsulates profound mathematical properties that make HRRN work. In this section, we'll dissect the formula rigorously—examining its algebraic structure, asymptotic behavior, sensitivity analysis, and the conditions under which it achieves various performance guarantees.

Understanding these mathematical foundations isn't merely academic. It enables:

Predicting HRRN behavior on novel workloads without simulation
Designing variants tailored to specific system requirements
Proving properties about scheduling outcomes
Optimizing implementations based on formula characteristics

What You Will Master

By the end of this page, you will understand the algebraic derivation of the response ratio, analyze its behavior as waiting time and burst time vary, prove key theorems about HRRN properties, and develop intuition for when HRRN performs well versus poorly.

Derivation and Alternative Interpretations

The response ratio can be derived from first principles by asking: "What is the expected turnaround time if we schedule this process now?"

Derivation:

Let:

W = Time already waited (from arrival to current time)
S = Service time required (burst time)
T = Turnaround time = W + S (total time in system if scheduled now)

The response ratio is defined as:

R = T / S = (W + S) / S

This can be rewritten as:

R = 1 + W/S

Interpretations:

Multiple Interpretations of Response Ratio
Formula Form	Interpretation	Insight
R = (W + S) / S	Turnaround time normalized by service time	Measures 'how long in system relative to work done'
R = 1 + W/S	Base priority (1) plus waiting penalty	Waiting adds priority; shorter jobs amplify waiting
R = T / S	Response time per unit of service	Higher ratio = less efficient system use for this job
R = 1 + (delay × rate)	Where delay=W, rate=1/S	Delay accumulates faster for short jobs

Why This Formula Works:

The genius of the response ratio is the division by S. This normalization ensures:

Short jobs get priority for equal wait: If two jobs have waited the same time, the shorter one has higher ratio (divide by smaller S).
Long waits compensate for long bursts: A job with burst 100 must wait 100 times longer than a job with burst 1 to achieve the same ratio increase.
Ratio grows unboundedly: As W → ∞, R → ∞, guaranteeing eventual selection.
Initial fairness: All jobs start with R = 1, providing a level playing field.

Normalization Insight

The response ratio is dimensionless—it has no time units. This makes it a pure priority ranking that doesn't depend on the time scale of the system. Whether jobs take milliseconds or hours, the relative rankings based on R remain consistent.

Behavior Under Parameter Variation

Let's analyze how the response ratio behaves as its parameters change.

Partial Derivatives:

To understand sensitivity, we compute partial derivatives:

∂R/∂W = 1/S (rate of change with respect to waiting time) ∂R/∂S = -W/S² (rate of change with respect to burst time)

Implications:

Sensitivity Analysis

•∂R/∂W = 1/S > 0: Response ratio always increases with waiting time. The rate of increase is inversely proportional to burst time—short jobs' ratios grow faster.
•∂R/∂S = -W/S² < 0 (when W > 0): Response ratio decreases as burst time increases. Longer jobs have lower priority for the same wait.
•Short jobs are more responsive: A job with S=1 gains 1 unit of ratio per time unit waited. A job with S=100 gains only 0.01 per time unit.
•Ratio is linear in W but hyperbolic in S: Waiting has linear effect; burst time has diminishing-returns effect on reducing ratio.

Graphical Analysis:

Consider how R changes over time for processes with different burst times:

Time (W)	S=2	S=5	S=10	S=20	S=50
0	1.0	1.0	1.0	1.0	1.0
5	3.5	2.0	1.5	1.25	1.1
10	6.0	3.0	2.0	1.5	1.2
20	11.0	5.0	3.0	2.0	1.4
50	26.0	11.0	6.0	3.5	2.0
100	51.0	21.0	11.0	6.0	3.0

Observations:

Short jobs (S=2) quickly achieve very high ratios
Long jobs (S=50) need substantial wait to exceed short jobs' ratios
All jobs eventually reach any target ratio given enough time

ratio_analysis.py
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
"""
Response Ratio Behavior Analysis
 
Visualize how response ratios evolve over time for different burst times.
"""
 
import numpy as np
import matplotlib.pyplot as plt
 
def response_ratio(waiting_time, burst_time):
    """Compute response ratio."""
    return 1 + (waiting_time / burst_time)
 
def analyze_ratio_growth():
    """Analyze ratio growth patterns for different burst times."""
    burst_times = [2, 5, 10, 20, 50]
    wait_range = np.linspace(0, 100, 200)
    
    results = {}
    for S in burst_times:
        ratios = [response_ratio(W, S) for W in wait_range]
        results[S] = ratios
        
        # Find time to reach ratio of 5
        time_to_5 = (5 - 1) * S  # From R = 1 + W/S, W = (R-1)*S
        print(f"Burst={S}: Time to reach R=5: W={time_to_5}")
    
    return results
 
def critical_crossover_time(S1, S2, initial_W1, initial_W2):
    """
    Find when process with burst S2 overtakes process with burst S1.
    
    Both start at time t=0. Process 1 arrived at -initial_W1,
    Process 2 arrived at -initial_W2.
    
    Find t where R1(t) = R2(t).
    
    R1 = 1 + (t + initial_W1) / S1
    R2 = 1 + (t + initial_W2) / S2
    
    Setting equal:
    (t + initial_W1) / S1 = (t + initial_W2) / S2
    S2 * (t + initial_W1) = S1 * (t + initial_W2)
    t * (S2 - S1) = S1 * initial_W2 - S2 * initial_W1
    t = (S1 * initial_W2 - S2 * initial_W1) / (S2 - S1)
    """
    if S1 == S2:
        return float('inf') if initial_W1 == initial_W2 else None
    
    t = (S1 * initial_W2 - S2 * initial_W1) / (S2 - S1)
    return t if t > 0 else None
 
# Example: When does a long job (S=50) overtake a short job (S=5)?
# If short job just arrived (W=0) and long job has waited W=30:
crossover = critical_crossover_time(5, 50, 0, 30)
print(f"Long job (S=50, W=30) overtakes short job (S=5, W=0) at t={crossover}")

Critical Crossover Analysis

A key question in HRRN analysis: "When does a longer-burst process overtake a shorter-burst process in priority?"

Setting Up the Crossover Equation:

Consider two processes:

Process A: Burst = S_A, has waited W_A
Process B: Burst = S_B, has waited W_B

Assume S_A < S_B (A is shorter)

Their response ratios are:

R_A = 1 + W_A/S_A
R_B = 1 + W_B/S_B

Crossover occurs when R_A = R_B:

1 + W_A/S_A = 1 + W_B/S_B

W_A/S_A = W_B/S_B

W_B = W_A × (S_B/S_A)

Interpretation: The longer job must wait (S_B/S_A) times as long as the shorter job to have equal priority.

Crossover Waiting Times
Short Job (S_A)	Long Job (S_B)	Ratio S_B/S_A	If W_A = 10, W_B must be
5	10	2.0	20
5	25	5.0	50
5	50	10.0	100
2	100	50.0	500
1	1000	1000.0	10,000

Key Insight: Proportional Fairness

The crossover condition W_B = W_A × (S_B/S_A) reveals that HRRN implements a form of proportional fairness:

Jobs should wait proportionally to their size
A 10× longer job gets priority after waiting 10× longer
This is arguably "fair" since longer jobs consume more CPU resources

Dynamic Crossover During Execution:

As time progresses (and both jobs wait longer), their relative priority can shift:

At t=0: Both arrive with W=0, R=1. Equal priority (FCFS breaks tie)
If short job runs, long job's wait increases; ratio grows by 1/S_B per unit time
If long job keeps being skipped, its ratio eventually exceeds any newly arriving short job

This dynamic behavior is what prevents starvation—no matter how many short jobs arrive, the long job's ratio keeps growing.

Starvation Bound

For a long job with burst S competing against a stream of short jobs with burst s arriving continuously, the long job will be selected when its ratio exceeds all others. The maximum wait is bounded by the arrival rate and burst size of competing jobs—HRRN provides implicit bounds on starvation.

Theoretical Properties and Proofs

Let's formalize the key theoretical properties of the response ratio and HRRN scheduling.

Theorem 1: Starvation Freedom

Statement: Under HRRN scheduling, every process that arrives will eventually be scheduled, regardless of the arrival pattern of other processes.

Proof:

Let P be any process with burst time S > 0, arriving at time a.

At any time t > a, P's response ratio is:

R_P(t) = 1 + (t - a)/S

For any newly arriving process Q at time t with burst S_Q:

R_Q(t) = 1 + 0/S_Q = 1

As t → ∞, R_P(t) → ∞ while R_Q(t) = 1 for all new arrivals.

Let M be the maximum ratio of any process currently in the system (excluding P). M is finite since the number of processes is finite and each has finite wait.

Choose t such that R_P(t) > M:

1 + (t - a)/S > M
t > a + S(M - 1)

At this time, P has the highest ratio and will be selected.

Since scheduling decisions occur at finite intervals (process completions), P will be scheduled after at most finitely many decisions. ∎

Proof Significance

This proof is constructive—it not only shows starvation cannot happen but provides a bound on maximum wait time in terms of system parameters. This makes HRRN's behavior predictable and analyzable.

Theorem 2: Short Job Bias

Statement: Given two processes with equal waiting times, HRRN always schedules the shorter one first.

Proof:

Let P₁ have burst S₁ and P₂ have burst S₂, where S₁ < S₂. Let both have wait time W.

R₁ = 1 + W/S₁ R₂ = 1 + W/S₂

Since S₁ < S₂ and W ≥ 0:

W/S₁ > W/S₂ (for W > 0)
1 + W/S₁ > 1 + W/S₂
R₁ > R₂

Therefore P₁ is selected before P₂. ∎

Corollary: When all processes arrive simultaneously (W = 0 for all), HRRN reduces to pure SJF (all ratios equal 1, ties broken by arrival order which equals shortest job if we sort appropriately).

Theorem 3: Monotonic Priority

Statement: A process's response ratio never decreases (while waiting).

Proof:

R(t) = 1 + (t - a)/S where a is arrival time and S is burst time.

dR/dt = 1/S > 0 for all S > 0.

R is strictly increasing in t. ∎

Implication: Priority inversion cannot occur purely from waiting—a process's priority can only increase while in the ready queue.

Performance Bounds and Approximation Quality

How close does HRRN come to optimal (SJF) performance? Let's analyze bounds.

Setup:

Let:

OPT = Average waiting time under optimal (SJF) scheduling
HRRN_WT = Average waiting time under HRRN
n = Number of processes
S_max = Maximum burst time
S_min = Minimum burst time

Bound Analysis:

Observation 1: HRRN never performs worse than FCFS.

In the worst case, HRRN could schedule processes in arrival order (if all arrive simultaneously with equal burst times). FCFS is non-adaptive, so HRRN is at least as good.

Observation 2: When arrivals are spread out, HRRN approaches SJF.

If there's always at most one process in the ready queue (low load), HRRN degenerates to FCFS—but so does SJF. Both are optimal in this case.

Observation 3: Burst time variance affects the gap.

With high variance (mixture of very short and very long jobs), the gap between HRRN and SJF widens because HRRN allows long jobs to "age" into priority.

Empirical HRRN vs SJF Performance
Workload Type	HRRN Avg WT	SJF Avg WT	Ratio (HRRN/SJF)
Uniform burst times	~1.0x optimal	Optimal	≈1.0
Moderate variance	~1.05-1.15x	Optimal	≈1.1
High variance (exponential)	~1.10-1.25x	Optimal	≈1.2
Bimodal (short + long)	~1.15-1.30x	Optimal	≈1.2
All same burst time	=FCFS	=FCFS	1.0

Competitive Ratio Analysis:

In competitive analysis, we compare an online algorithm to an optimal offline algorithm.

For HRRN:

It's an online algorithm (decisions made without future knowledge)
SJF is the offline optimal (assuming known burst times)

The competitive ratio ρ = sup(HRRN_WT / SJF_WT) over all inputs.

Theorem (informal): HRRN has competitive ratio O(log(S_max/S_min)).

Intuition: The ratio grows logarithmically with the range of burst times. With bounded burst time ratios, HRRN's performance is within a constant factor of optimal.

Practical Impact

In most real systems, HRRN achieves 90-95% of SJF's efficiency while completely eliminating starvation. This small efficiency cost is often an excellent tradeoff for guaranteed service.

Formula Variants and Generalizations

The response ratio formula can be generalized to accommodate various scheduling requirements.

Generalized Response Ratio:

R = α + β × (W/S)^γ

Where:

α = Base priority (typically 1)
β = Scaling factor for wait contribution
γ = Exponent controlling wait sensitivity

Default HRRN: α=1, β=1, γ=1

Generalized Formula Variants
Variant	Formula	Behavior	Use Case
Standard HRRN	1 + W/S	Linear aging	General purpose
Aggressive aging	1 + 2(W/S)	Faster priority increase	Reduce max wait time
Conservative aging	1 + 0.5(W/S)	Slower priority increase	Prioritize short jobs more
Quadratic aging	1 + (W/S)²	Accelerating priority	Strong anti-starvation
Square root aging	1 + √(W/S)	Decelerating priority	Strong short-job bias

generalized_ratio.py
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
"""
Generalized Response Ratio Framework
 
Allows experimentation with different ratio formulas
to balance efficiency and fairness.
"""
 
from typing import Callable
import math
 
# Type alias for ratio functions
RatioFunction = Callable[[float, float], float]
 
def standard_hrrn(waiting_time: float, burst_time: float) -> float:
    """Standard HRRN: R = 1 + W/S"""
    return 1 + (waiting_time / burst_time)
 
def aggressive_hrrn(waiting_time: float, burst_time: float) -> float:
    """Aggressive aging: R = 1 + 2(W/S)"""
    return 1 + 2 * (waiting_time / burst_time)
 
def quadratic_hrrn(waiting_time: float, burst_time: float) -> float:
    """Quadratic aging: R = 1 + (W/S)²"""
    ratio = waiting_time / burst_time
    return 1 + (ratio ** 2)
 
def sqrt_hrrn(waiting_time: float, burst_time: float) -> float:
    """Square root aging: R = 1 + sqrt(W/S)"""
    ratio = waiting_time / burst_time
    return 1 + math.sqrt(ratio)
 
def weighted_hrrn(weight: float) -> RatioFunction:
    """Factory for weighted HRRN: R = w × (1 + W/S)"""
    def ratio_fn(waiting_time: float, burst_time: float) -> float:
        return weight * (1 + waiting_time / burst_time)
    return ratio_fn
 
def parameterized_hrrn(alpha: float, beta: float, gamma: float) -> RatioFunction:
    """Factory for generalized formula: R = α + β × (W/S)^γ"""
    def ratio_fn(waiting_time: float, burst_time: float) -> float:
        ratio = waiting_time / burst_time
        return alpha + beta * (ratio ** gamma)
    return ratio_fn
 
# Example usage
def compare_formulas():
    """Compare different ratio formulas for same wait/burst."""
    W, S = 20, 5  # Waiting 20 units, burst 5 units
    
    formulas = [
        ("Standard", standard_hrrn),
        ("Aggressive", aggressive_hrrn),
        ("Quadratic", quadratic_hrrn),
        ("Square Root", sqrt_hrrn),
        ("Weighted (w=1.5)", weighted_hrrn(1.5)),
    ]
    
    print(f"W={W}, S={S}")
    for name, fn in formulas:
        ratio = fn(W, S)
        print(f"  {name}: R = {ratio:.3f}")
 
# Output:
# W=20, S=5
#   Standard: R = 5.000
#   Aggressive: R = 9.000
#   Quadratic: R = 17.000
#   Square Root: R = 3.000
#   Weighted (w=1.5): R = 7.500

Choosing the Right Variant

Standard HRRN works well for most cases. Use aggressive aging when maximum wait time bounds matter more than average. Use conservative aging when minimizing average waiting time is paramount. The choice depends on system requirements.

Edge Cases and Numerical Issues

Implementing the response ratio formula correctly requires handling several edge cases.

Implementation Pitfalls

•Zero burst time: If S = 0 (instantaneous processes), the ratio is undefined (division by zero). Handle by either rejecting S=0 processes or assigning infinite priority.
•Negative waiting time: If current_time < arrival_time due to timing errors, W becomes negative. Always clamp W ≥ 0.
•Integer overflow: For large W and small S, W/S can overflow integer types. Use floating-point or carefully check bounds.
•Floating-point precision: When ratios are very close (differ by < 1e-9), floating-point comparison may be unreliable. Consider epsilon-based comparison or deterministic tiebreakers.
•Simultaneous arrivals: When multiple processes arrive at exactly the same time with identical burst times, all have R = 1. Use secondary ordering (arrival order, PID) for consistency.

robust_ratio.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
/**
 * Robust response ratio computation with edge case handling.
 */
 
#include <float.h>
#include <math.h>
 
typedef struct {
    int pid;
    double arrival_time;
    double burst_time;
} Process;
 
/**
 * Compute response ratio with robust edge case handling.
 * 
 * @param p Process to compute ratio for
 * @param current_time Current system time
 * @return Response ratio (guaranteed >= 1.0)
 */
double robust_response_ratio(const Process* p, double current_time) {
    // Edge case 1: Negative or zero burst time
    if (p->burst_time <= 0) {
        // Treat as instantaneous - highest priority
        return DBL_MAX;
    }
    
    // Edge case 2: Process hasn't arrived yet
    if (current_time < p->arrival_time) {
        return 0.0;  // Not eligible for scheduling
    }
    
    // Compute waiting time with safeguard
    double waiting_time = current_time - p->arrival_time;
    if (waiting_time < 0) {
        waiting_time = 0;  // Clamp to non-negative
    }
    
    // Compute ratio
    double ratio = 1.0 + (waiting_time / p->burst_time);
    
    // Edge case 3: Numerical overflow check
    if (!isfinite(ratio)) {
        return DBL_MAX;
    }
    
    return ratio;
}
 
/**
 * Compare two processes by response ratio with tiebreaking.
 * Returns negative if p1 should run first, positive if p2, 0 if tie.
 */
int compare_by_ratio(const Process* p1, const Process* p2, 
                     double current_time) {
    double r1 = robust_response_ratio(p1, current_time);
    double r2 = robust_response_ratio(p2, current_time);
    
    // Use epsilon for floating-point comparison
    const double EPSILON = 1e-9;
    double diff = r2 - r1;  // Higher ratio = higher priority
    
    if (fabs(diff) < EPSILON) {
        // Tie: use arrival time (earlier = higher priority)
        if (fabs(p1->arrival_time - p2->arrival_time) < EPSILON) {
            // Still tie: use PID (lower = higher priority)
            return p1->pid - p2->pid;
        }
        return (p1->arrival_time < p2->arrival_time) ? -1 : 1;
    }
    
    return (diff > 0) ? -1 : 1;  // Higher ratio wins
}

Summary and Key Insights

We've deeply analyzed the mathematical foundations of the response ratio, understanding not just how to compute it but why it works.

Key Takeaways

•R = 1 + W/S normalizes by service time: This makes the formula dimensionless and ensures short jobs are naturally prioritized.
•∂R/∂W = 1/S reveals growth rate: Short jobs' ratios grow faster, but all jobs' ratios grow unboundedly.
•Crossover requires W_B = W_A × (S_B/S_A): Long jobs must wait proportionally longer to match short jobs' priority.
•Starvation freedom is provable: R → ∞ as W → ∞ guarantees eventual selection.
•HRRN achieves ~90-95% of SJF efficiency: The fairness guarantee costs only 5-10% in average waiting time.
•Generalized formulas enable customization: α + β(W/S)^γ allows tuning the efficiency-fairness tradeoff.

What's Next:

The response ratio embodies a broader principle called aging—the systematic increase of priority for waiting processes. The next section explores aging as a general technique applicable to many scheduling algorithms, not just HRRN. Understanding aging opens doors to designing custom schedulers for specific requirements.

Section Complete

You now have a rigorous mathematical understanding of the response ratio. You can derive its properties, prove theorems about HRRN behavior, analyze performance bounds, and implement robust ratio computation. Next, we'll explore aging as a general scheduling principle.

Response Ratio Formula: Mathematical Foundations

The Mathematics Behind Fair Scheduling

In the previous section, we introduced the response ratio formula as HRRN's core priority metric:

R = (W + S) / S = 1 + W/S

Understanding these mathematical foundations isn't merely academic. It enables:

Predicting HRRN behavior on novel workloads without simulation
Designing variants tailored to specific system requirements
Proving properties about scheduling outcomes
Optimizing implementations based on formula characteristics

What You Will Master

Derivation and Alternative Interpretations

The response ratio can be derived from first principles by asking: "What is the expected turnaround time if we schedule this process now?"

Derivation:

Let:

W = Time already waited (from arrival to current time)
S = Service time required (burst time)
T = Turnaround time = W + S (total time in system if scheduled now)

The response ratio is defined as:

R = T / S = (W + S) / S

This can be rewritten as:

R = 1 + W/S

Interpretations:

Multiple Interpretations of Response Ratio
Formula Form	Interpretation	Insight
R = (W + S) / S	Turnaround time normalized by service time	Measures 'how long in system relative to work done'
R = 1 + W/S	Base priority (1) plus waiting penalty	Waiting adds priority; shorter jobs amplify waiting
R = T / S	Response time per unit of service	Higher ratio = less efficient system use for this job
R = 1 + (delay × rate)	Where delay=W, rate=1/S	Delay accumulates faster for short jobs

Why This Formula Works:

The genius of the response ratio is the division by S. This normalization ensures:

Short jobs get priority for equal wait: If two jobs have waited the same time, the shorter one has higher ratio (divide by smaller S).
Long waits compensate for long bursts: A job with burst 100 must wait 100 times longer than a job with burst 1 to achieve the same ratio increase.
Ratio grows unboundedly: As W → ∞, R → ∞, guaranteeing eventual selection.
Initial fairness: All jobs start with R = 1, providing a level playing field.

Normalization Insight

Behavior Under Parameter Variation

Let's analyze how the response ratio behaves as its parameters change.

Partial Derivatives:

To understand sensitivity, we compute partial derivatives:

∂R/∂W = 1/S (rate of change with respect to waiting time) ∂R/∂S = -W/S² (rate of change with respect to burst time)

Implications:

Sensitivity Analysis

•∂R/∂W = 1/S > 0: Response ratio always increases with waiting time. The rate of increase is inversely proportional to burst time—short jobs' ratios grow faster.
•∂R/∂S = -W/S² < 0 (when W > 0): Response ratio decreases as burst time increases. Longer jobs have lower priority for the same wait.
•Short jobs are more responsive: A job with S=1 gains 1 unit of ratio per time unit waited. A job with S=100 gains only 0.01 per time unit.
•Ratio is linear in W but hyperbolic in S: Waiting has linear effect; burst time has diminishing-returns effect on reducing ratio.

Graphical Analysis:

Consider how R changes over time for processes with different burst times:

Time (W)	S=2	S=5	S=10	S=20	S=50
0	1.0	1.0	1.0	1.0	1.0
5	3.5	2.0	1.5	1.25	1.1
10	6.0	3.0	2.0	1.5	1.2
20	11.0	5.0	3.0	2.0	1.4
50	26.0	11.0	6.0	3.5	2.0
100	51.0	21.0	11.0	6.0	3.0

Observations:

Short jobs (S=2) quickly achieve very high ratios
Long jobs (S=50) need substantial wait to exceed short jobs' ratios
All jobs eventually reach any target ratio given enough time

ratio_analysis.py
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
"""
Response Ratio Behavior Analysis
 
Visualize how response ratios evolve over time for different burst times.
"""
 
import numpy as np
import matplotlib.pyplot as plt
 
def response_ratio(waiting_time, burst_time):
    """Compute response ratio."""
    return 1 + (waiting_time / burst_time)
 
def analyze_ratio_growth():
    """Analyze ratio growth patterns for different burst times."""
    burst_times = [2, 5, 10, 20, 50]
    wait_range = np.linspace(0, 100, 200)
    
    results = {}
    for S in burst_times:
        ratios = [response_ratio(W, S) for W in wait_range]
        results[S] = ratios
        
        # Find time to reach ratio of 5
        time_to_5 = (5 - 1) * S  # From R = 1 + W/S, W = (R-1)*S
        print(f"Burst={S}: Time to reach R=5: W={time_to_5}")
    
    return results
 
def critical_crossover_time(S1, S2, initial_W1, initial_W2):
    """
    Find when process with burst S2 overtakes process with burst S1.
    
    Both start at time t=0. Process 1 arrived at -initial_W1,
    Process 2 arrived at -initial_W2.
    
    Find t where R1(t) = R2(t).
    
    R1 = 1 + (t + initial_W1) / S1
    R2 = 1 + (t + initial_W2) / S2
    
    Setting equal:
    (t + initial_W1) / S1 = (t + initial_W2) / S2
    S2 * (t + initial_W1) = S1 * (t + initial_W2)
    t * (S2 - S1) = S1 * initial_W2 - S2 * initial_W1
    t = (S1 * initial_W2 - S2 * initial_W1) / (S2 - S1)
    """
    if S1 == S2:
        return float('inf') if initial_W1 == initial_W2 else None
    
    t = (S1 * initial_W2 - S2 * initial_W1) / (S2 - S1)
    return t if t > 0 else None
 
# Example: When does a long job (S=50) overtake a short job (S=5)?
# If short job just arrived (W=0) and long job has waited W=30:
crossover = critical_crossover_time(5, 50, 0, 30)
print(f"Long job (S=50, W=30) overtakes short job (S=5, W=0) at t={crossover}")

Critical Crossover Analysis

A key question in HRRN analysis: "When does a longer-burst process overtake a shorter-burst process in priority?"

Setting Up the Crossover Equation:

Consider two processes:

Process A: Burst = S_A, has waited W_A
Process B: Burst = S_B, has waited W_B

Assume S_A < S_B (A is shorter)

Their response ratios are:

R_A = 1 + W_A/S_A
R_B = 1 + W_B/S_B

Crossover occurs when R_A = R_B:

1 + W_A/S_A = 1 + W_B/S_B

W_A/S_A = W_B/S_B

W_B = W_A × (S_B/S_A)

Interpretation: The longer job must wait (S_B/S_A) times as long as the shorter job to have equal priority.

Crossover Waiting Times
Short Job (S_A)	Long Job (S_B)	Ratio S_B/S_A	If W_A = 10, W_B must be
5	10	2.0	20
5	25	5.0	50
5	50	10.0	100
2	100	50.0	500
1	1000	1000.0	10,000

Key Insight: Proportional Fairness

The crossover condition W_B = W_A × (S_B/S_A) reveals that HRRN implements a form of proportional fairness:

Jobs should wait proportionally to their size
A 10× longer job gets priority after waiting 10× longer
This is arguably "fair" since longer jobs consume more CPU resources

Dynamic Crossover During Execution:

As time progresses (and both jobs wait longer), their relative priority can shift:

At t=0: Both arrive with W=0, R=1. Equal priority (FCFS breaks tie)
If short job runs, long job's wait increases; ratio grows by 1/S_B per unit time
If long job keeps being skipped, its ratio eventually exceeds any newly arriving short job

This dynamic behavior is what prevents starvation—no matter how many short jobs arrive, the long job's ratio keeps growing.

Starvation Bound

Theoretical Properties and Proofs

Let's formalize the key theoretical properties of the response ratio and HRRN scheduling.

Theorem 1: Starvation Freedom

Statement: Under HRRN scheduling, every process that arrives will eventually be scheduled, regardless of the arrival pattern of other processes.

Proof:

Let P be any process with burst time S > 0, arriving at time a.

At any time t > a, P's response ratio is:

R_P(t) = 1 + (t - a)/S

For any newly arriving process Q at time t with burst S_Q:

R_Q(t) = 1 + 0/S_Q = 1

As t → ∞, R_P(t) → ∞ while R_Q(t) = 1 for all new arrivals.

Let M be the maximum ratio of any process currently in the system (excluding P). M is finite since the number of processes is finite and each has finite wait.

Choose t such that R_P(t) > M:

1 + (t - a)/S > M
t > a + S(M - 1)

At this time, P has the highest ratio and will be selected.

Since scheduling decisions occur at finite intervals (process completions), P will be scheduled after at most finitely many decisions. ∎

Proof Significance

This proof is constructive—it not only shows starvation cannot happen but provides a bound on maximum wait time in terms of system parameters. This makes HRRN's behavior predictable and analyzable.

Theorem 2: Short Job Bias

Statement: Given two processes with equal waiting times, HRRN always schedules the shorter one first.

Proof:

Let P₁ have burst S₁ and P₂ have burst S₂, where S₁ < S₂. Let both have wait time W.

R₁ = 1 + W/S₁ R₂ = 1 + W/S₂

Since S₁ < S₂ and W ≥ 0:

W/S₁ > W/S₂ (for W > 0)
1 + W/S₁ > 1 + W/S₂
R₁ > R₂

Therefore P₁ is selected before P₂. ∎

Corollary: When all processes arrive simultaneously (W = 0 for all), HRRN reduces to pure SJF (all ratios equal 1, ties broken by arrival order which equals shortest job if we sort appropriately).

Theorem 3: Monotonic Priority

Statement: A process's response ratio never decreases (while waiting).

Proof:

R(t) = 1 + (t - a)/S where a is arrival time and S is burst time.

dR/dt = 1/S > 0 for all S > 0.

R is strictly increasing in t. ∎

Implication: Priority inversion cannot occur purely from waiting—a process's priority can only increase while in the ready queue.

Performance Bounds and Approximation Quality

How close does HRRN come to optimal (SJF) performance? Let's analyze bounds.

Setup:

Let:

OPT = Average waiting time under optimal (SJF) scheduling
HRRN_WT = Average waiting time under HRRN
n = Number of processes
S_max = Maximum burst time
S_min = Minimum burst time

Bound Analysis:

Observation 1: HRRN never performs worse than FCFS.

In the worst case, HRRN could schedule processes in arrival order (if all arrive simultaneously with equal burst times). FCFS is non-adaptive, so HRRN is at least as good.

Observation 2: When arrivals are spread out, HRRN approaches SJF.

If there's always at most one process in the ready queue (low load), HRRN degenerates to FCFS—but so does SJF. Both are optimal in this case.

Observation 3: Burst time variance affects the gap.

With high variance (mixture of very short and very long jobs), the gap between HRRN and SJF widens because HRRN allows long jobs to "age" into priority.

Empirical HRRN vs SJF Performance
Workload Type	HRRN Avg WT	SJF Avg WT	Ratio (HRRN/SJF)
Uniform burst times	~1.0x optimal	Optimal	≈1.0
Moderate variance	~1.05-1.15x	Optimal	≈1.1
High variance (exponential)	~1.10-1.25x	Optimal	≈1.2
Bimodal (short + long)	~1.15-1.30x	Optimal	≈1.2
All same burst time	=FCFS	=FCFS	1.0

Competitive Ratio Analysis:

In competitive analysis, we compare an online algorithm to an optimal offline algorithm.

For HRRN:

It's an online algorithm (decisions made without future knowledge)
SJF is the offline optimal (assuming known burst times)

The competitive ratio ρ = sup(HRRN_WT / SJF_WT) over all inputs.

Theorem (informal): HRRN has competitive ratio O(log(S_max/S_min)).

Intuition: The ratio grows logarithmically with the range of burst times. With bounded burst time ratios, HRRN's performance is within a constant factor of optimal.

Practical Impact

In most real systems, HRRN achieves 90-95% of SJF's efficiency while completely eliminating starvation. This small efficiency cost is often an excellent tradeoff for guaranteed service.

Formula Variants and Generalizations

The response ratio formula can be generalized to accommodate various scheduling requirements.

Generalized Response Ratio:

R = α + β × (W/S)^γ

Where:

α = Base priority (typically 1)
β = Scaling factor for wait contribution
γ = Exponent controlling wait sensitivity

Default HRRN: α=1, β=1, γ=1

Generalized Formula Variants
Variant	Formula	Behavior	Use Case
Standard HRRN	1 + W/S	Linear aging	General purpose
Aggressive aging	1 + 2(W/S)	Faster priority increase	Reduce max wait time
Conservative aging	1 + 0.5(W/S)	Slower priority increase	Prioritize short jobs more
Quadratic aging	1 + (W/S)²	Accelerating priority	Strong anti-starvation
Square root aging	1 + √(W/S)	Decelerating priority	Strong short-job bias

generalized_ratio.py
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
"""
Generalized Response Ratio Framework
 
Allows experimentation with different ratio formulas
to balance efficiency and fairness.
"""
 
from typing import Callable
import math
 
# Type alias for ratio functions
RatioFunction = Callable[[float, float], float]
 
def standard_hrrn(waiting_time: float, burst_time: float) -> float:
    """Standard HRRN: R = 1 + W/S"""
    return 1 + (waiting_time / burst_time)
 
def aggressive_hrrn(waiting_time: float, burst_time: float) -> float:
    """Aggressive aging: R = 1 + 2(W/S)"""
    return 1 + 2 * (waiting_time / burst_time)
 
def quadratic_hrrn(waiting_time: float, burst_time: float) -> float:
    """Quadratic aging: R = 1 + (W/S)²"""
    ratio = waiting_time / burst_time
    return 1 + (ratio ** 2)
 
def sqrt_hrrn(waiting_time: float, burst_time: float) -> float:
    """Square root aging: R = 1 + sqrt(W/S)"""
    ratio = waiting_time / burst_time
    return 1 + math.sqrt(ratio)
 
def weighted_hrrn(weight: float) -> RatioFunction:
    """Factory for weighted HRRN: R = w × (1 + W/S)"""
    def ratio_fn(waiting_time: float, burst_time: float) -> float:
        return weight * (1 + waiting_time / burst_time)
    return ratio_fn
 
def parameterized_hrrn(alpha: float, beta: float, gamma: float) -> RatioFunction:
    """Factory for generalized formula: R = α + β × (W/S)^γ"""
    def ratio_fn(waiting_time: float, burst_time: float) -> float:
        ratio = waiting_time / burst_time
        return alpha + beta * (ratio ** gamma)
    return ratio_fn
 
# Example usage
def compare_formulas():
    """Compare different ratio formulas for same wait/burst."""
    W, S = 20, 5  # Waiting 20 units, burst 5 units
    
    formulas = [
        ("Standard", standard_hrrn),
        ("Aggressive", aggressive_hrrn),
        ("Quadratic", quadratic_hrrn),
        ("Square Root", sqrt_hrrn),
        ("Weighted (w=1.5)", weighted_hrrn(1.5)),
    ]
    
    print(f"W={W}, S={S}")
    for name, fn in formulas:
        ratio = fn(W, S)
        print(f"  {name}: R = {ratio:.3f}")
 
# Output:
# W=20, S=5
#   Standard: R = 5.000
#   Aggressive: R = 9.000
#   Quadratic: R = 17.000
#   Square Root: R = 3.000
#   Weighted (w=1.5): R = 7.500

Choosing the Right Variant

Edge Cases and Numerical Issues

Implementing the response ratio formula correctly requires handling several edge cases.

Implementation Pitfalls

•Zero burst time: If S = 0 (instantaneous processes), the ratio is undefined (division by zero). Handle by either rejecting S=0 processes or assigning infinite priority.
•Negative waiting time: If current_time < arrival_time due to timing errors, W becomes negative. Always clamp W ≥ 0.
•Integer overflow: For large W and small S, W/S can overflow integer types. Use floating-point or carefully check bounds.
•Floating-point precision: When ratios are very close (differ by < 1e-9), floating-point comparison may be unreliable. Consider epsilon-based comparison or deterministic tiebreakers.
•Simultaneous arrivals: When multiple processes arrive at exactly the same time with identical burst times, all have R = 1. Use secondary ordering (arrival order, PID) for consistency.

robust_ratio.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
/**
 * Robust response ratio computation with edge case handling.
 */
 
#include <float.h>
#include <math.h>
 
typedef struct {
    int pid;
    double arrival_time;
    double burst_time;
} Process;
 
/**
 * Compute response ratio with robust edge case handling.
 * 
 * @param p Process to compute ratio for
 * @param current_time Current system time
 * @return Response ratio (guaranteed >= 1.0)
 */
double robust_response_ratio(const Process* p, double current_time) {
    // Edge case 1: Negative or zero burst time
    if (p->burst_time <= 0) {
        // Treat as instantaneous - highest priority
        return DBL_MAX;
    }
    
    // Edge case 2: Process hasn't arrived yet
    if (current_time < p->arrival_time) {
        return 0.0;  // Not eligible for scheduling
    }
    
    // Compute waiting time with safeguard
    double waiting_time = current_time - p->arrival_time;
    if (waiting_time < 0) {
        waiting_time = 0;  // Clamp to non-negative
    }
    
    // Compute ratio
    double ratio = 1.0 + (waiting_time / p->burst_time);
    
    // Edge case 3: Numerical overflow check
    if (!isfinite(ratio)) {
        return DBL_MAX;
    }
    
    return ratio;
}
 
/**
 * Compare two processes by response ratio with tiebreaking.
 * Returns negative if p1 should run first, positive if p2, 0 if tie.
 */
int compare_by_ratio(const Process* p1, const Process* p2, 
                     double current_time) {
    double r1 = robust_response_ratio(p1, current_time);
    double r2 = robust_response_ratio(p2, current_time);
    
    // Use epsilon for floating-point comparison
    const double EPSILON = 1e-9;
    double diff = r2 - r1;  // Higher ratio = higher priority
    
    if (fabs(diff) < EPSILON) {
        // Tie: use arrival time (earlier = higher priority)
        if (fabs(p1->arrival_time - p2->arrival_time) < EPSILON) {
            // Still tie: use PID (lower = higher priority)
            return p1->pid - p2->pid;
        }
        return (p1->arrival_time < p2->arrival_time) ? -1 : 1;
    }
    
    return (diff > 0) ? -1 : 1;  // Higher ratio wins
}

Summary and Key Insights

We've deeply analyzed the mathematical foundations of the response ratio, understanding not just how to compute it but why it works.

Key Takeaways

•R = 1 + W/S normalizes by service time: This makes the formula dimensionless and ensures short jobs are naturally prioritized.
•∂R/∂W = 1/S reveals growth rate: Short jobs' ratios grow faster, but all jobs' ratios grow unboundedly.
•Crossover requires W_B = W_A × (S_B/S_A): Long jobs must wait proportionally longer to match short jobs' priority.
•Starvation freedom is provable: R → ∞ as W → ∞ guarantees eventual selection.
•HRRN achieves ~90-95% of SJF efficiency: The fairness guarantee costs only 5-10% in average waiting time.
•Generalized formulas enable customization: α + β(W/S)^γ allows tuning the efficiency-fairness tradeoff.

What's Next:

Section Complete