Operating SystemsFrame Allocation & Thrashing

Frame Allocation Problem

LevelIntermediate

Duration60 mins

TopicFrame Allocation & Thrashing

5 / 5

Fairness Considerations

The Fairness Dilemma

What does it mean to allocate frames fairly? The question seems simple, but it quickly reveals deep complexity.

Consider: Is it fair to give every process the same number of frames, regardless of their needs? Or is it fairer to give each process what it needs, even if some get much more than others? What about priority—should important processes receive preferential treatment? And over what timeframe should we measure fairness?

These questions have no universally correct answers. Different definitions of fairness lead to different allocation policies, and each has implications for system behavior, user experience, and overall system health. Understanding these tradeoffs is essential for designing or tuning memory management policies that align with the goals of the system and the expectations of its users.

What You Will Master

By the end of this page, you will understand multiple definitions of fairness, how they apply to frame allocation, mechanisms for achieving and measuring fairness, and how to handle the inevitable conflicts between fairness and other system goals.

Defining Fairness

Before we can achieve fairness, we must define it. Several competing definitions exist, each with different implications.

1. Equal Share Fairness (Egalitarian)

"Every process should receive the same number of frames."

Simple and intuitive
Ignores differences in process needs
Results in waste (over-allocation) and starvation (under-allocation) simultaneously
Used in some embedded and real-time systems for predictability

2. Proportional Fairness

"Every process should receive frames in proportion to some measure (size, weight, priority)."

Fairer than equal share when processes differ
Still may not match actual needs if the proportion metric is wrong
Weighted version allows expressing relative importance

3. Need-Based Fairness

"Every process should receive what it needs to operate efficiently."

Most efficient if needs can be accurately determined
Fairness becomes subjective—who decides need?
Processes may game the system by inflating apparent need

4. Max-Min Fairness

"Maximize the minimum allocation any process receives."

No process starves while others have excess
Sacrifices some efficiency for guaranteed floors
Common in network bandwidth allocation

Fairness Definitions Comparison
Definition	Principle	Advantage	Disadvantage
Equal Share	Same for everyone	Simple, predictable	Ignores actual needs
Proportional	Based on weight/size	Reflects differences	May not match needs
Need-Based	Based on working set	Efficient allocation	Hard to determine need
Max-Min	Raise the floor first	Prevents starvation	May limit high performers
Utilitarian	Maximize total utility	Best system throughput	May starve some processes

5. Utilitarian Fairness

"Allocate to maximize total system utility (e.g., total throughput)."

Optimizes system-wide metrics
May sacrifice individual processes for the good of the whole
Not "fair" by some definitions—some processes may starve
Often what systems actually optimize for in practice

Temporal dimension:

Fairness can be measured instantaneously or over time:

Instantaneous: Is the current allocation fair right now?
Short-term: Has each process received fair treatment over the last minute?
Long-term: Over the session, has each process been treated fairly?

A system might be instantaneously unfair (one process temporarily starved) but long-term fair (everyone gets their share over time).

No Universal Fairness

There is no single "correct" definition of fairness. Different systems, workloads, and user expectations call for different definitions. The key is to choose a definition that aligns with system goals and then consistently apply it.

Starvation and Its Prevention

The most serious fairness violation is starvation—when a process cannot make progress because it consistently receives insufficient frames.

Causes of starvation:

Priority inversion: Low-priority processes never get frames when high-priority processes are present
Greedy processes: Processes that request more frames than they need, depriving others
Workload imbalance: When new processes arrive faster than old ones complete
Memory pressure: System-wide scarcity forces some processes to suffer
Poor allocation policy: Equal allocation starving large processes; proportional allocation starving small ones

Starvation vs thrashing:

Starvation and thrashing are related but distinct:

Thrashing: Process has frames but not enough, causing constant page faults
Starvation: Process cannot get frames at all (or gets below minimum)

Both result in poor performance, but starvation is the more severe condition—the process makes no progress at all.

starvation_detection.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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/*
 * Starvation Detection and Prevention
 *
 * Mechanisms for detecting when processes are being starved
 * and taking corrective action.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
 
#define MAX_PROCESSES 64
#define STARVATION_THRESHOLD_SEC 30   // Starved if waiting this long
#define PROGRESS_THRESHOLD_PAGES 10    // Must gain at least this many
 
typedef struct {
    int pid;
    int allocated_frames;
    int minimum_needed;
    int requested_frames;
    
    // Starvation tracking
    time_t last_allocation_time;    // When we last got frames
    time_t last_progress_time;      // When we last made forward progress
    int frames_since_last_check;    // Frames gained since check
    bool marked_starving;
} ProcessStarvation;
 
typedef struct {
    ProcessStarvation processes[MAX_PROCESSES];
    int count;
    time_t current_time;
} StarvationMonitor;
 
/*
 * Detect if a process is starving
 */
bool is_starving(StarvationMonitor *mon, ProcessStarvation *p) {
    // Condition 1: Below minimum for extended period
    if (p->allocated_frames < p->minimum_needed) {
        time_t duration = mon->current_time - p->last_progress_time;
        if (duration > STARVATION_THRESHOLD_SEC / 2) {
            return true;
        }
    }
    
    // Condition 2: Significantly below request with no progress
    if (p->allocated_frames < p->requested_frames * 0.5) {
        time_t wait_time = mon->current_time - p->last_allocation_time;
        if (wait_time > STARVATION_THRESHOLD_SEC) {
            return true;
        }
    }
    
    // Condition 3: No frame gains while repeatedly requesting
    if (p->frames_since_last_check < PROGRESS_THRESHOLD_PAGES &&
        p->allocated_frames < p->requested_frames) {
        time_t stall_time = mon->current_time - p->last_progress_time;
        if (stall_time > STARVATION_THRESHOLD_SEC) {
            return true;
        }
    }
    
    return false;
}
 
/*
 * Scan all processes for starvation
 */
void detect_starvation(StarvationMonitor *mon) {
    printf("Starvation Detection Scan\n");
    printf("=========================\n");
    printf("Current time: %ld\n\n", mon->current_time);
    
    int starving_count = 0;
    
    for (int i = 0; i < mon->count; i++) {
        ProcessStarvation *p = &mon->processes[i];
        
        bool starving = is_starving(mon, p);
        p->marked_starving = starving;
        
        if (starving) {
            starving_count++;
            printf("STARVING: PID %d\n", p->pid);
            printf("  Allocated: %d, Minimum: %d, Requested: %d\n",
                   p->allocated_frames, p->minimum_needed, 
                   p->requested_frames);
            printf("  Last allocation: %ld seconds ago\n",
                   mon->current_time - p->last_allocation_time);
            printf("  Last progress: %ld seconds ago\n\n",
                   mon->current_time - p->last_progress_time);
        }
    }
    
    printf("Summary: %d of %d processes starving\n\n",
           starving_count, mon->count);
}
 
/*
 * Aging-based priority boost
 *
 * Processes that have waited longer get temporary priority boost,
 * helping them escape starvation.
 */
typedef struct {
    int pid;
    int base_priority;
    int effective_priority;
    time_t last_frame_granted;
    int wait_boost;           // Additional priority from waiting
} AgingProcess;
 
void apply_aging(AgingProcess procs[], int n, time_t now) {
    printf("\nApplying Aging Boost\n");
    printf("====================\n\n");
    
    for (int i = 0; i < n; i++) {
        AgingProcess *p = &procs[i];
        
        // Calculate wait time
        time_t wait = now - p->last_frame_granted;
        
        // Aging boost: +1 priority for every 5 seconds waiting
        p->wait_boost = wait / 5;
        if (p->wait_boost > 10) p->wait_boost = 10;  // Cap
        
        p->effective_priority = p->base_priority + p->wait_boost;
        
        printf("PID %d: base=%d, wait_boost=%d, effective=%d\n",
               p->pid, p->base_priority, p->wait_boost, 
               p->effective_priority);
    }
    
    printf("\nProcesses with higher effective priority will\n");
    printf("receive frames before those with lower priority.\n");
}
 
/*
 * Key insight: Starvation prevention mechanisms
 *
 * 1. Aging: Boost priority/allocation for waiting processes
 * 2. Minimum guarantees: Always give at least the minimum
 * 3. Round-robin grants: Distribute new frames cyclically
 * 4. Reservation: Reserve some frames for starving processes
 * 5. Monitoring: Detect starvation and trigger corrective action
 */

Starvation is Subtle

Starvation can be hard to detect because the starving process is still "running" (technically). It's consuming CPU in page fault handlers, showing activity, but making no forward progress. Metrics like "page faults per useful instruction" can reveal starvation that raw resource usage hides.

Fair Share Scheduling

Fair Share Scheduling is a comprehensive approach that extends fairness beyond frame allocation to the entire resource set.

The fair share principle:

Resources (CPU, memory, I/O) are divided into shares. Each process (or process group) is assigned a share, and the system ensures that over time, each entity receives resource access proportional to its share.

Application to frames:

In fair share memory allocation:

Each process group is assigned a share (e.g., 25%, 10%, etc.)
Frames are allocated to match these shares
If a group uses less than its share, excess may be borrowed by others
When the owner needs frames back, they are returned

Benefits:

Predictable resource allocation per group
Protection between groups (one group can't starve another)
Flexibility within groups (processes can share their group's allocation)
Useful for multi-tenant environments (cloud, shared servers)

fair_share.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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
/*
 * Fair Share Memory Allocation
 *
 * Allocates frames to process groups based on assigned shares,
 * with borrowing and reclamation mechanisms.
 */
 
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_GROUPS 16
#define MAX_PROCS_PER_GROUP 32
 
typedef struct {
    int pid;
    int allocated_frames;
    int working_set_size;
} GroupProcess;
 
typedef struct {
    int group_id;
    const char *name;
    int share_percent;        // Assigned share (e.g., 25%)
    int entitled_frames;      // share_percent * total_frames
    int allocated_frames;     // Actually allocated to this group
    int borrowed_frames;      // Extra frames borrowed from others
    int lent_frames;          // Frames lent to other groups
    
    GroupProcess processes[MAX_PROCS_PER_GROUP];
    int process_count;
} FairShareGroup;
 
typedef struct {
    int total_frames;
    FairShareGroup groups[MAX_GROUPS];
    int group_count;
} FairShareManager;
 
/*
 * Calculate entitled frames for each group
 */
void calculate_entitlements(FairShareManager *fsm) {
    printf("Calculating Group Entitlements\n");
    printf("==============================\n\n");
    
    // Verify shares sum to 100 (or close)
    int total_share = 0;
    for (int i = 0; i < fsm->group_count; i++) {
        total_share += fsm->groups[i].share_percent;
    }
    
    printf("Total shares: %d%% (should be ~100%%)\n\n", total_share);
    
    // Calculate entitled frames
    for (int i = 0; i < fsm->group_count; i++) {
        FairShareGroup *g = &fsm->groups[i];
        g->entitled_frames = (fsm->total_frames * g->share_percent) / 100;
        printf("Group '%s': %d%% share = %d frames\n",
               g->name, g->share_percent, g->entitled_frames);
    }
    printf("\n");
}
 
/*
 * Calculate actual need within a group
 */
int group_need(FairShareGroup *g) {
    int total_wss = 0;
    for (int i = 0; i < g->process_count; i++) {
        total_wss += g->processes[i].working_set_size;
    }
    return total_wss;
}
 
/*
 * Allocate with borrowing
 *
 * Groups using less than their entitlement can lend to others.
 * When a group needs its frames back, borrowers must return them.
 */
void allocate_with_borrowing(FairShareManager *fsm) {
    printf("Fair Share Allocation with Borrowing\n");
    printf("====================================\n\n");
    
    // First pass: give each group its entitled frames (or need, if less)
    int unallocated = fsm->total_frames;
    int total_excess = 0;
    int total_deficit = 0;
    
    for (int i = 0; i < fsm->group_count; i++) {
        FairShareGroup *g = &fsm->groups[i];
        int need = group_need(g);
        
        if (need <= g->entitled_frames) {
            // Group needs less than its share - will lend
            g->allocated_frames = need;
            g->lent_frames = g->entitled_frames - need;
            total_excess += g->lent_frames;
            printf("Group '%s': needs %d, entitled %d, lending %d\n",
                   g->name, need, g->entitled_frames, g->lent_frames);
        } else {
            // Group needs more than its share - wants to borrow
            g->allocated_frames = g->entitled_frames;
            g->borrowed_frames = 0;  // Will try to borrow below
            total_deficit += need - g->entitled_frames;
            printf("Group '%s': needs %d, entitled %d, deficit %d\n",
                   g->name, need, g->entitled_frames, 
                   need - g->entitled_frames);
        }
        unallocated -= g->allocated_frames;
    }
    
    printf("\nTotal lendable: %d frames\n", total_excess);
    printf("Total deficit: %d frames\n\n", total_deficit);
    
    // Second pass: distribute excess to groups with deficits
    if (total_excess > 0 && total_deficit > 0) {
        printf("Distributing borrowed frames:\n");
        
        int to_distribute = (total_excess < total_deficit) ? 
                            total_excess : total_deficit;
        
        for (int i = 0; i < fsm->group_count && to_distribute > 0; i++) {
            FairShareGroup *g = &fsm->groups[i];
            int need = group_need(g);
            int current_deficit = need - g->allocated_frames;
            
            if (current_deficit > 0) {
                int borrow = (current_deficit < to_distribute) ? 
                             current_deficit : to_distribute;
                g->borrowed_frames = borrow;
                g->allocated_frames += borrow;
                to_distribute -= borrow;
                
                printf("  Group '%s' borrows %d frames\n",
                       g->name, borrow);
            }
        }
    }
    
    printf("\nFinal Allocations:\n");
    for (int i = 0; i < fsm->group_count; i++) {
        FairShareGroup *g = &fsm->groups[i];
        printf("  %-12s: %4d frames (entitled %4d, borrowed %d, lent %d)\n",
               g->name, g->allocated_frames, g->entitled_frames,
               g->borrowed_frames, g->lent_frames);
    }
}
 
/*
 * Reclaim borrowed frames when owner needs them
 */
void reclaim_borrowed(FairShareManager *fsm, int owner_group_id, 
                      int frames_needed) {
    FairShareGroup *owner = &fsm->groups[owner_group_id];
    
    printf("\nGroup '%s' reclaiming %d borrowed frames\n",
           owner->name, frames_needed);
    
    int reclaimed = 0;
    
    // Find groups that borrowed from us
    for (int i = 0; i < fsm->group_count && reclaimed < frames_needed; i++) {
        if (i == owner_group_id) continue;
        
        FairShareGroup *borrower = &fsm->groups[i];
        if (borrower->borrowed_frames > 0) {
            int take = (borrower->borrowed_frames < frames_needed - reclaimed) ?
                       borrower->borrowed_frames : frames_needed - reclaimed;
            
            borrower->borrowed_frames -= take;
            borrower->allocated_frames -= take;
            reclaimed += take;
            
            printf("  Reclaimed %d from '%s'\n", take, borrower->name);
        }
    }
    
    owner->lent_frames -= reclaimed;
    owner->allocated_frames += reclaimed;
    
    if (reclaimed < frames_needed) {
        printf("  Only reclaimed %d of %d needed\n", 
               reclaimed, frames_needed);
    }
}

cgroups in Linux

Linux cgroups (control groups) implement a form of fair share scheduling. Each cgroup can be assigned memory limits and shares. Processes within a cgroup compete with each other but not with other groups beyond their fair share. This is fundamental to container orchestration (Docker, Kubernetes).

Fairness Metrics

To measure and optimize for fairness, we need quantitative metrics.

1. Jain's Fairness Index

A standard metric for measuring fairness in resource allocation:

J(x₁, x₂, ..., xₙ) = (Σxᵢ)² / (n × Σxᵢ²)

Where xᵢ is the allocation to process i.

J = 1: Perfect fairness (all equal)
J = 1/n: Minimum fairness (one gets all)
Higher is more fair

2. Coefficient of Variation

Measures spread in allocations:

CV = σ / μ

Where σ is standard deviation and μ is mean allocation.

CV = 0: All allocations equal
Higher CV: More inequality

3. Deficit Ratio

Measures how close each process is to its need:

Deficit_i = max(0, need_i - allocation_i) / need_i
Average_Deficit = Σ Deficit_i / n

4. Starvation Rate

Fraction of processes below minimum or with excessive fault rates.

fairness_metrics.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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/*
 * Fairness Metrics Implementation
 *
 * Quantitative measures of allocation fairness.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
typedef struct {
    int pid;
    int allocated;
    int needed;       // Working set size or request
    int minimum;
} ProcessAlloc;
 
/*
 * Jain's Fairness Index
 *
 * Ranges from 1/n (worst) to 1 (best/equal).
 */
double jains_fairness_index(ProcessAlloc procs[], int n) {
    if (n == 0) return 1.0;
    
    double sum = 0;
    double sum_sq = 0;
    
    for (int i = 0; i < n; i++) {
        double alloc = procs[i].allocated;
        sum += alloc;
        sum_sq += alloc * alloc;
    }
    
    if (sum_sq == 0) return 1.0;  // All zero, technically equal
    
    return (sum * sum) / (n * sum_sq);
}
 
/*
 * Coefficient of Variation
 *
 * 0 means equal, higher means more inequality.
 */
double coefficient_of_variation(ProcessAlloc procs[], int n) {
    if (n <= 1) return 0.0;
    
    // Calculate mean
    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += procs[i].allocated;
    }
    double mean = sum / n;
    
    if (mean == 0) return 0.0;
    
    // Calculate variance
    double variance = 0;
    for (int i = 0; i < n; i++) {
        double diff = procs[i].allocated - mean;
        variance += diff * diff;
    }
    variance /= n;
    
    double std_dev = sqrt(variance);
    return std_dev / mean;
}
 
/*
 * Need Satisfaction Ratio
 *
 * 1.0 means all needs fully met, lower means under-allocation.
 */
double need_satisfaction_ratio(ProcessAlloc procs[], int n) {
    if (n == 0) return 1.0;
    
    double total_satisfaction = 0;
    
    for (int i = 0; i < n; i++) {
        if (procs[i].needed == 0) {
            total_satisfaction += 1.0;  // No need = fully satisfied
        } else {
            double ratio = (double)procs[i].allocated / procs[i].needed;
            total_satisfaction += (ratio > 1.0) ? 1.0 : ratio;
        }
    }
    
    return total_satisfaction / n;
}
 
/*
 * Starvation Rate
 *
 * Fraction of processes below minimum allocation.
 */
double starvation_rate(ProcessAlloc procs[], int n) {
    if (n == 0) return 0.0;
    
    int starving = 0;
    for (int i = 0; i < n; i++) {
        if (procs[i].allocated < procs[i].minimum) {
            starving++;
        }
    }
    
    return (double)starving / n;
}
 
/*
 * Combined fairness report
 */
void fairness_report(ProcessAlloc procs[], int n) {
    printf("Fairness Metrics Report\n");
    printf("=======================\n\n");
    
    // Display allocations
    printf("%-5s %-10s %-10s %-10s %-10s\n",
           "PID", "Allocated", "Needed", "Minimum", "Satisfied");
    printf("-----------------------------------------------\n");
    
    for (int i = 0; i < n; i++) {
        double sat = (procs[i].needed > 0) ?
                     (double)procs[i].allocated / procs[i].needed : 1.0;
        printf("%-5d %-10d %-10d %-10d %.2f%%\n",
               procs[i].pid, procs[i].allocated, procs[i].needed,
               procs[i].minimum, sat * 100);
    }
    
    printf("\nMetrics:\n");
    printf("  Jain's Fairness Index:     %.4f (1.0 = perfect)\n",
           jains_fairness_index(procs, n));
    printf("  Coefficient of Variation:  %.4f (0.0 = equal)\n",
           coefficient_of_variation(procs, n));
    printf("  Need Satisfaction Ratio:   %.2f%% (100%% = all needs met)\n",
           need_satisfaction_ratio(procs, n) * 100);
    printf("  Starvation Rate:           %.2f%% (0%% = no starvation)\n",
           starvation_rate(procs, n) * 100);
    
    printf("\nInterpretation:\n");
    double jfi = jains_fairness_index(procs, n);
    if (jfi > 0.95) {
        printf("  Allocation equality: EXCELLENT\n");
    } else if (jfi > 0.8) {
        printf("  Allocation equality: GOOD\n");
    } else if (jfi > 0.5) {
        printf("  Allocation equality: FAIR\n");
    } else {
        printf("  Allocation equality: POOR - significant inequality\n");
    }
    
    double sr = starvation_rate(procs, n);
    if (sr == 0) {
        printf("  Starvation: NONE\n");
    } else if (sr < 0.1) {
        printf("  Starvation: MINOR (%.0f%% of processes)\n", sr * 100);
    } else {
        printf("  Starvation: CRITICAL (%.0f%% of processes)\n", sr * 100);
    }
}

Jain's Index Interpretation

Jain's Fairness Index is widely used because it's independent of scale and population size. A value of 1.0 means perfect equality (everyone gets the same). A value of 0.5 means roughly that half the resources are distributed unfairly. Values below 0.5 indicate serious inequality concerns.

Fairness vs Efficiency

One of the fundamental tensions in system design is between fairness and efficiency. Often, the most efficient allocation is not the most fair, and vice versa.

The conflict:

Consider a system with 100 frames and two processes:

Process A: WSS = 80, contribution to throughput when fully allocated = 100
Process B: WSS = 80, contribution to throughput when fully allocated = 100

If we allocate fairly (50-50):

Both processes thrash, maybe 20% efficiency each
Total throughput: 40

If we allocate efficiently (100-0):

One process runs at full speed, one doesn't run at all
Total throughput: 100

Resolving the tension:

Time-sharing: Alternate which process gets enough frames
- Fairness over time, efficiency at each instant
- Both processes complete eventually
Swapping: Run one fully, swap out, run the other
- Similar to time-sharing but at process granularity
- Higher overhead for the swap
Accept inefficiency: Give both some frames, accept thrashing
- Fair but inefficient
- May be appropriate if both processes are interactive

Efficiency-First Approach

•Give each process enough or none
•Maximize throughput at expense of latency
•Swap/suspend under-allocated processes
•Best for batch workloads
•May hurt interactive response

Fairness-First Approach

•Everyone gets something
•Accept lower total throughput
•Everyone makes some progress
•Best for interactive workloads
•May cause system-wide slowdown

The Pareto frontier:

In practice, systems operate somewhere along a tradeoff curve. At one extreme is maximum efficiency (possibly unfair). At the other is strict fairness (possibly inefficient). Most systems choose a point along this curve based on their goals:

Servers: Lean toward efficiency (maximize requests served)
Desktops: Lean toward fairness (keep applications responsive)
Real-time: May have strict fairness requirements for safety
Cloud multi-tenant: Strong fairness required for billing and SLA

The key insight is that fairness and efficiency are both valid goals, and choosing between them is a policy decision, not a technical one.

Global Thrashing is Lose-Lose

The worst outcome is the "fair" allocation that gives every process too few frames, causing system-wide thrashing. No one makes progress, throughput collapses, and the system is neither fair nor efficient. This is why admission control and process suspension are sometimes necessary—it's better to run fewer processes well than many processes badly.

Multi-User Fairness

In multi-user systems (shared servers, cloud environments), fairness operates at multiple levels:

User-level fairness:

Each user should receive fair treatment, regardless of how many processes they run. A user running 100 processes shouldn't get 100x the resources of a user running 1 process.

Solution: Per-user quotas

Allocate frames per user, not per process
A user's processes share their user's allocation
This is the fair share approach at the user level

Tenant-level fairness:

In cloud environments, each tenant (customer) expects their share:

Enforced through cgroups, VMs, or containers
Each tenant's workload isolated from others
Oversubscription requires careful management

Priority among users:

Not all users may be equal:

Paying customers vs free tier
Premium vs standard service levels
Administrative vs regular users

Priority-weighted fair sharing addresses this.

Multi-Level Fairness Hierarchy
Level	Unit	Mechanism	Typical Policy
System	Total frames	Hardware	Fixed by RAM installed
Tenant	Tenant pool	VM/cgroup limits	SLA-based allocation
User	User quota	Per-user cgroups	Fair share within tenant
Process Group	Group share	cgroup hierarchy	Job-based allocation
Process	Individual	Demand paging	Dynamic within group

multi_level_fairness.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
/*
 * Multi-Level Fairness
 *
 * Demonstrates hierarchical fair share allocation
 * for multi-tenant environments.
 */
 
#include <stdio.h>
 
#define MAX_TENANTS 4
#define MAX_USERS_PER_TENANT 8
#define MAX_PROCS_PER_USER 16
 
typedef struct {
    int pid;
    int allocated;
} Process;
 
typedef struct {
    const char *name;
    int quota;              // Frames allocated to this user
    int actual_use;         // Currently using
    Process processes[MAX_PROCS_PER_USER];
    int process_count;
} User;
 
typedef struct {
    const char *name;
    int sla_percent;        // Percent of system guaranteed
    int entitled_frames;
    int allocated_frames;
    User users[MAX_USERS_PER_TENANT];
    int user_count;
} Tenant;
 
typedef struct {
    int total_frames;
    Tenant tenants[MAX_TENANTS];
    int tenant_count;
} MultiTenantSystem;
 
void hierarchical_allocation(MultiTenantSystem *mts) {
    printf("Hierarchical Fair Share Allocation\n");
    printf("===================================\n\n");
    
    // Level 1: Allocate to tenants based on SLA
    printf("Level 1: Tenant Allocation (SLA-based)\n");
    for (int t = 0; t < mts->tenant_count; t++) {
        Tenant *tenant = &mts->tenants[t];
        tenant->entitled_frames = 
            (mts->total_frames * tenant->sla_percent) / 100;
        tenant->allocated_frames = tenant->entitled_frames;
        
        printf("  Tenant '%s': %d%% SLA = %d frames\n",
               tenant->name, tenant->sla_percent, 
               tenant->entitled_frames);
    }
    printf("\n");
    
    // Level 2: Within each tenant, allocate to users
    printf("Level 2: User Allocation (Equal within tenant)\n");
    for (int t = 0; t < mts->tenant_count; t++) {
        Tenant *tenant = &mts->tenants[t];
        
        if (tenant->user_count == 0) continue;
        
        int per_user = tenant->allocated_frames / tenant->user_count;
        
        printf("  Tenant '%s' (%d users, %d frames each):\n",
               tenant->name, tenant->user_count, per_user);
        
        for (int u = 0; u < tenant->user_count; u++) {
            User *user = &tenant->users[u];
            user->quota = per_user;
            printf("    User '%s': %d frames\n", user->name, per_user);
        }
    }
    printf("\n");
    
    // Level 3: Within each user, allocate to processes
    printf("Level 3: Process Allocation (Within user quota)\n");
    for (int t = 0; t < mts->tenant_count; t++) {
        Tenant *tenant = &mts->tenants[t];
        
        for (int u = 0; u < tenant->user_count; u++) {
            User *user = &tenant->users[u];
            
            if (user->process_count == 0) continue;
            
            int per_proc = user->quota / user->process_count;
            
            printf("  %s/%s (%d procs, %d frames each)\n",
                   tenant->name, user->name, 
                   user->process_count, per_proc);
            
            for (int p = 0; p < user->process_count; p++) {
                user->processes[p].allocated = per_proc;
            }
        }
    }
}
 
/*
 * Key insight: Hierarchical fairness
 *
 * - Tenants isolated from each other (can't exceed SLA)
 * - Users within tenant compete fairly
 * - Processes within user share user's quota
 *
 * A misbehaving process affects only its user.
 * A misbehaving user affects only their tenant.
 * Tenant isolation protects the system.
 *
 * This is how cloud environments maintain fairness
 * in multi-tenant systems.
 */

The Noisy Neighbor Problem

In cloud environments, a "noisy neighbor" is a tenant that consumes excessive resources, impacting others. Hierarchical fair sharing with strict tenant isolation prevents noisy neighbors from affecting other tenants. This is why memory limits in containers and VMs are strictly enforced.

Adaptive Fairness Policies

The best fairness policies adapt to conditions rather than applying rigid rules.

Condition-based adaptation:

Under low pressure: Be generous, allow borrowing, prioritize efficiency
- All processes can exceed their base allocation
- No need for strict enforcement
- System runs smoothly
Under moderate pressure: Start enforcing shares
- Borrowed frames may be reclaimed
- Processes limited to their fair share
- Background processes deprioritized
Under high pressure: Strict quotas and possible suspension
- No borrowing allowed
- Processes that can't fit are suspended/swapped
- Essential services protected

Feedback-driven policies:

Monitor process behavior and adjust allocations:

Processes making good progress deserve their allocation
Processes thrashing need more frames or should yield
Processes idle can lend their frames temporarily

Adaptive Fairness Principles

•Monitor continuously — Track memory pressure, fault rates, and progress metrics
•Respond proportionally — Match enforcement strictness to pressure level
•Protect minimums always — Never violate architectural minimums regardless of pressure
•Favor active processes — Processes actively computing deserve frames more than idle ones
•Age priority claims — Long-waiting processes get priority boost
•Communicate limits — Processes should be able to query their allocation for self-regulation

Self-regulating processes:

Some environments allow processes to participate in fairness:

Memory pressure notifications (Linux prctl, Windows WNF)
Applications can release caches when notified
Cooperative garbage collection scheduling
Application-level memory limits (JVM heap, browser tab limits)

This cooperation improves system-wide fairness because:

Applications know which of their memory is truly important
OS can't distinguish essential vs expendable pages
Voluntary reduction is smoother than forced eviction

iOS Memory Warnings

iOS sends memory pressure notifications to apps, expecting them to release non-essential memory. Apps that respond promptly are less likely to be killed when memory is tight. This cooperative model achieves fairness through communication rather than coercion.

Summary: Balancing Competing Interests

We've explored the multifaceted nature of fairness in frame allocation—from defining what fairness means to measuring it, achieving it, and balancing it against other goals. Fairness is not a simple checkbox; it's a spectrum of choices that reflect system values and user expectations.

Key Takeaways

•Multiple fairness definitions exist — Equal share, proportional, need-based, max-min, and utilitarian approaches all have merit
•Starvation is the critical fairness violation — Prevention through aging, guarantees, and monitoring is essential
•Fair share scheduling provides structure — Groups receive guaranteed shares with borrowing mechanisms
•Quantitative metrics enable measurement — Jain's index, CV, and satisfaction ratios quantify fairness
•Fairness vs efficiency is a tradeoff — Systems must choose their position on this spectrum
•Multi-level fairness serves multi-user systems — Hierarchies of tenant, user, and process fairness provide isolation
•Adaptive policies work best — Respond to conditions rather than applying rigid rules

Module complete:

This completes our exploration of the Frame Allocation Problem. We've covered the fundamental constraint of limited frames, process requirements and working sets, minimum frame guarantees, allocation strategies, and fairness considerations.

The next module explores Allocation Strategies in greater depth, examining global vs local replacement and the interplay between allocation and replacement decisions.

Module 1 Complete

You now have a comprehensive understanding of the frame allocation problem—from the fundamental scarcity of frames through minimum requirements, allocation strategies, and fairness considerations. This foundation is essential for understanding thrashing, its causes, and its solutions in subsequent modules.

5 / 5

Loading learning content...

Operating SystemsFrame Allocation & Thrashing

Frame Allocation Problem

LevelIntermediate

Duration60 mins

TopicFrame Allocation & Thrashing

5 / 5

Fairness Considerations

The Fairness Dilemma

What does it mean to allocate frames fairly? The question seems simple, but it quickly reveals deep complexity.

What You Will Master

Defining Fairness

Before we can achieve fairness, we must define it. Several competing definitions exist, each with different implications.

1. Equal Share Fairness (Egalitarian)

"Every process should receive the same number of frames."

Simple and intuitive
Ignores differences in process needs
Results in waste (over-allocation) and starvation (under-allocation) simultaneously
Used in some embedded and real-time systems for predictability

2. Proportional Fairness

"Every process should receive frames in proportion to some measure (size, weight, priority)."

Fairer than equal share when processes differ
Still may not match actual needs if the proportion metric is wrong
Weighted version allows expressing relative importance

3. Need-Based Fairness

"Every process should receive what it needs to operate efficiently."

Most efficient if needs can be accurately determined
Fairness becomes subjective—who decides need?
Processes may game the system by inflating apparent need

4. Max-Min Fairness

"Maximize the minimum allocation any process receives."

No process starves while others have excess
Sacrifices some efficiency for guaranteed floors
Common in network bandwidth allocation

Fairness Definitions Comparison
Definition	Principle	Advantage	Disadvantage
Equal Share	Same for everyone	Simple, predictable	Ignores actual needs
Proportional	Based on weight/size	Reflects differences	May not match needs
Need-Based	Based on working set	Efficient allocation	Hard to determine need
Max-Min	Raise the floor first	Prevents starvation	May limit high performers
Utilitarian	Maximize total utility	Best system throughput	May starve some processes

5. Utilitarian Fairness

"Allocate to maximize total system utility (e.g., total throughput)."

Optimizes system-wide metrics
May sacrifice individual processes for the good of the whole
Not "fair" by some definitions—some processes may starve
Often what systems actually optimize for in practice

Temporal dimension:

Fairness can be measured instantaneously or over time:

Instantaneous: Is the current allocation fair right now?
Short-term: Has each process received fair treatment over the last minute?
Long-term: Over the session, has each process been treated fairly?

A system might be instantaneously unfair (one process temporarily starved) but long-term fair (everyone gets their share over time).

No Universal Fairness

Starvation and Its Prevention

The most serious fairness violation is starvation—when a process cannot make progress because it consistently receives insufficient frames.

Causes of starvation:

Priority inversion: Low-priority processes never get frames when high-priority processes are present
Greedy processes: Processes that request more frames than they need, depriving others
Workload imbalance: When new processes arrive faster than old ones complete
Memory pressure: System-wide scarcity forces some processes to suffer
Poor allocation policy: Equal allocation starving large processes; proportional allocation starving small ones

Starvation vs thrashing:

Starvation and thrashing are related but distinct:

Thrashing: Process has frames but not enough, causing constant page faults
Starvation: Process cannot get frames at all (or gets below minimum)

Both result in poor performance, but starvation is the more severe condition—the process makes no progress at all.

starvation_detection.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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/*
 * Starvation Detection and Prevention
 *
 * Mechanisms for detecting when processes are being starved
 * and taking corrective action.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
 
#define MAX_PROCESSES 64
#define STARVATION_THRESHOLD_SEC 30   // Starved if waiting this long
#define PROGRESS_THRESHOLD_PAGES 10    // Must gain at least this many
 
typedef struct {
    int pid;
    int allocated_frames;
    int minimum_needed;
    int requested_frames;
    
    // Starvation tracking
    time_t last_allocation_time;    // When we last got frames
    time_t last_progress_time;      // When we last made forward progress
    int frames_since_last_check;    // Frames gained since check
    bool marked_starving;
} ProcessStarvation;
 
typedef struct {
    ProcessStarvation processes[MAX_PROCESSES];
    int count;
    time_t current_time;
} StarvationMonitor;
 
/*
 * Detect if a process is starving
 */
bool is_starving(StarvationMonitor *mon, ProcessStarvation *p) {
    // Condition 1: Below minimum for extended period
    if (p->allocated_frames < p->minimum_needed) {
        time_t duration = mon->current_time - p->last_progress_time;
        if (duration > STARVATION_THRESHOLD_SEC / 2) {
            return true;
        }
    }
    
    // Condition 2: Significantly below request with no progress
    if (p->allocated_frames < p->requested_frames * 0.5) {
        time_t wait_time = mon->current_time - p->last_allocation_time;
        if (wait_time > STARVATION_THRESHOLD_SEC) {
            return true;
        }
    }
    
    // Condition 3: No frame gains while repeatedly requesting
    if (p->frames_since_last_check < PROGRESS_THRESHOLD_PAGES &&
        p->allocated_frames < p->requested_frames) {
        time_t stall_time = mon->current_time - p->last_progress_time;
        if (stall_time > STARVATION_THRESHOLD_SEC) {
            return true;
        }
    }
    
    return false;
}
 
/*
 * Scan all processes for starvation
 */
void detect_starvation(StarvationMonitor *mon) {
    printf("Starvation Detection Scan\n");
    printf("=========================\n");
    printf("Current time: %ld\n\n", mon->current_time);
    
    int starving_count = 0;
    
    for (int i = 0; i < mon->count; i++) {
        ProcessStarvation *p = &mon->processes[i];
        
        bool starving = is_starving(mon, p);
        p->marked_starving = starving;
        
        if (starving) {
            starving_count++;
            printf("STARVING: PID %d\n", p->pid);
            printf("  Allocated: %d, Minimum: %d, Requested: %d\n",
                   p->allocated_frames, p->minimum_needed, 
                   p->requested_frames);
            printf("  Last allocation: %ld seconds ago\n",
                   mon->current_time - p->last_allocation_time);
            printf("  Last progress: %ld seconds ago\n\n",
                   mon->current_time - p->last_progress_time);
        }
    }
    
    printf("Summary: %d of %d processes starving\n\n",
           starving_count, mon->count);
}
 
/*
 * Aging-based priority boost
 *
 * Processes that have waited longer get temporary priority boost,
 * helping them escape starvation.
 */
typedef struct {
    int pid;
    int base_priority;
    int effective_priority;
    time_t last_frame_granted;
    int wait_boost;           // Additional priority from waiting
} AgingProcess;
 
void apply_aging(AgingProcess procs[], int n, time_t now) {
    printf("\nApplying Aging Boost\n");
    printf("====================\n\n");
    
    for (int i = 0; i < n; i++) {
        AgingProcess *p = &procs[i];
        
        // Calculate wait time
        time_t wait = now - p->last_frame_granted;
        
        // Aging boost: +1 priority for every 5 seconds waiting
        p->wait_boost = wait / 5;
        if (p->wait_boost > 10) p->wait_boost = 10;  // Cap
        
        p->effective_priority = p->base_priority + p->wait_boost;
        
        printf("PID %d: base=%d, wait_boost=%d, effective=%d\n",
               p->pid, p->base_priority, p->wait_boost, 
               p->effective_priority);
    }
    
    printf("\nProcesses with higher effective priority will\n");
    printf("receive frames before those with lower priority.\n");
}
 
/*
 * Key insight: Starvation prevention mechanisms
 *
 * 1. Aging: Boost priority/allocation for waiting processes
 * 2. Minimum guarantees: Always give at least the minimum
 * 3. Round-robin grants: Distribute new frames cyclically
 * 4. Reservation: Reserve some frames for starving processes
 * 5. Monitoring: Detect starvation and trigger corrective action
 */

Starvation is Subtle

Fair Share Scheduling

Fair Share Scheduling is a comprehensive approach that extends fairness beyond frame allocation to the entire resource set.

The fair share principle:

Application to frames:

In fair share memory allocation:

Each process group is assigned a share (e.g., 25%, 10%, etc.)
Frames are allocated to match these shares
If a group uses less than its share, excess may be borrowed by others
When the owner needs frames back, they are returned

Benefits:

Predictable resource allocation per group
Protection between groups (one group can't starve another)
Flexibility within groups (processes can share their group's allocation)
Useful for multi-tenant environments (cloud, shared servers)

fair_share.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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
/*
 * Fair Share Memory Allocation
 *
 * Allocates frames to process groups based on assigned shares,
 * with borrowing and reclamation mechanisms.
 */
 
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_GROUPS 16
#define MAX_PROCS_PER_GROUP 32
 
typedef struct {
    int pid;
    int allocated_frames;
    int working_set_size;
} GroupProcess;
 
typedef struct {
    int group_id;
    const char *name;
    int share_percent;        // Assigned share (e.g., 25%)
    int entitled_frames;      // share_percent * total_frames
    int allocated_frames;     // Actually allocated to this group
    int borrowed_frames;      // Extra frames borrowed from others
    int lent_frames;          // Frames lent to other groups
    
    GroupProcess processes[MAX_PROCS_PER_GROUP];
    int process_count;
} FairShareGroup;
 
typedef struct {
    int total_frames;
    FairShareGroup groups[MAX_GROUPS];
    int group_count;
} FairShareManager;
 
/*
 * Calculate entitled frames for each group
 */
void calculate_entitlements(FairShareManager *fsm) {
    printf("Calculating Group Entitlements\n");
    printf("==============================\n\n");
    
    // Verify shares sum to 100 (or close)
    int total_share = 0;
    for (int i = 0; i < fsm->group_count; i++) {
        total_share += fsm->groups[i].share_percent;
    }
    
    printf("Total shares: %d%% (should be ~100%%)\n\n", total_share);
    
    // Calculate entitled frames
    for (int i = 0; i < fsm->group_count; i++) {
        FairShareGroup *g = &fsm->groups[i];
        g->entitled_frames = (fsm->total_frames * g->share_percent) / 100;
        printf("Group '%s': %d%% share = %d frames\n",
               g->name, g->share_percent, g->entitled_frames);
    }
    printf("\n");
}
 
/*
 * Calculate actual need within a group
 */
int group_need(FairShareGroup *g) {
    int total_wss = 0;
    for (int i = 0; i < g->process_count; i++) {
        total_wss += g->processes[i].working_set_size;
    }
    return total_wss;
}
 
/*
 * Allocate with borrowing
 *
 * Groups using less than their entitlement can lend to others.
 * When a group needs its frames back, borrowers must return them.
 */
void allocate_with_borrowing(FairShareManager *fsm) {
    printf("Fair Share Allocation with Borrowing\n");
    printf("====================================\n\n");
    
    // First pass: give each group its entitled frames (or need, if less)
    int unallocated = fsm->total_frames;
    int total_excess = 0;
    int total_deficit = 0;
    
    for (int i = 0; i < fsm->group_count; i++) {
        FairShareGroup *g = &fsm->groups[i];
        int need = group_need(g);
        
        if (need <= g->entitled_frames) {
            // Group needs less than its share - will lend
            g->allocated_frames = need;
            g->lent_frames = g->entitled_frames - need;
            total_excess += g->lent_frames;
            printf("Group '%s': needs %d, entitled %d, lending %d\n",
                   g->name, need, g->entitled_frames, g->lent_frames);
        } else {
            // Group needs more than its share - wants to borrow
            g->allocated_frames = g->entitled_frames;
            g->borrowed_frames = 0;  // Will try to borrow below
            total_deficit += need - g->entitled_frames;
            printf("Group '%s': needs %d, entitled %d, deficit %d\n",
                   g->name, need, g->entitled_frames, 
                   need - g->entitled_frames);
        }
        unallocated -= g->allocated_frames;
    }
    
    printf("\nTotal lendable: %d frames\n", total_excess);
    printf("Total deficit: %d frames\n\n", total_deficit);
    
    // Second pass: distribute excess to groups with deficits
    if (total_excess > 0 && total_deficit > 0) {
        printf("Distributing borrowed frames:\n");
        
        int to_distribute = (total_excess < total_deficit) ? 
                            total_excess : total_deficit;
        
        for (int i = 0; i < fsm->group_count && to_distribute > 0; i++) {
            FairShareGroup *g = &fsm->groups[i];
            int need = group_need(g);
            int current_deficit = need - g->allocated_frames;
            
            if (current_deficit > 0) {
                int borrow = (current_deficit < to_distribute) ? 
                             current_deficit : to_distribute;
                g->borrowed_frames = borrow;
                g->allocated_frames += borrow;
                to_distribute -= borrow;
                
                printf("  Group '%s' borrows %d frames\n",
                       g->name, borrow);
            }
        }
    }
    
    printf("\nFinal Allocations:\n");
    for (int i = 0; i < fsm->group_count; i++) {
        FairShareGroup *g = &fsm->groups[i];
        printf("  %-12s: %4d frames (entitled %4d, borrowed %d, lent %d)\n",
               g->name, g->allocated_frames, g->entitled_frames,
               g->borrowed_frames, g->lent_frames);
    }
}
 
/*
 * Reclaim borrowed frames when owner needs them
 */
void reclaim_borrowed(FairShareManager *fsm, int owner_group_id, 
                      int frames_needed) {
    FairShareGroup *owner = &fsm->groups[owner_group_id];
    
    printf("\nGroup '%s' reclaiming %d borrowed frames\n",
           owner->name, frames_needed);
    
    int reclaimed = 0;
    
    // Find groups that borrowed from us
    for (int i = 0; i < fsm->group_count && reclaimed < frames_needed; i++) {
        if (i == owner_group_id) continue;
        
        FairShareGroup *borrower = &fsm->groups[i];
        if (borrower->borrowed_frames > 0) {
            int take = (borrower->borrowed_frames < frames_needed - reclaimed) ?
                       borrower->borrowed_frames : frames_needed - reclaimed;
            
            borrower->borrowed_frames -= take;
            borrower->allocated_frames -= take;
            reclaimed += take;
            
            printf("  Reclaimed %d from '%s'\n", take, borrower->name);
        }
    }
    
    owner->lent_frames -= reclaimed;
    owner->allocated_frames += reclaimed;
    
    if (reclaimed < frames_needed) {
        printf("  Only reclaimed %d of %d needed\n", 
               reclaimed, frames_needed);
    }
}

cgroups in Linux

Fairness Metrics

To measure and optimize for fairness, we need quantitative metrics.

1. Jain's Fairness Index

A standard metric for measuring fairness in resource allocation:

J(x₁, x₂, ..., xₙ) = (Σxᵢ)² / (n × Σxᵢ²)

Where xᵢ is the allocation to process i.

J = 1: Perfect fairness (all equal)
J = 1/n: Minimum fairness (one gets all)
Higher is more fair

2. Coefficient of Variation

Measures spread in allocations:

CV = σ / μ

Where σ is standard deviation and μ is mean allocation.

CV = 0: All allocations equal
Higher CV: More inequality

3. Deficit Ratio

Measures how close each process is to its need:

Deficit_i = max(0, need_i - allocation_i) / need_i
Average_Deficit = Σ Deficit_i / n

4. Starvation Rate

Fraction of processes below minimum or with excessive fault rates.

fairness_metrics.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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/*
 * Fairness Metrics Implementation
 *
 * Quantitative measures of allocation fairness.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
typedef struct {
    int pid;
    int allocated;
    int needed;       // Working set size or request
    int minimum;
} ProcessAlloc;
 
/*
 * Jain's Fairness Index
 *
 * Ranges from 1/n (worst) to 1 (best/equal).
 */
double jains_fairness_index(ProcessAlloc procs[], int n) {
    if (n == 0) return 1.0;
    
    double sum = 0;
    double sum_sq = 0;
    
    for (int i = 0; i < n; i++) {
        double alloc = procs[i].allocated;
        sum += alloc;
        sum_sq += alloc * alloc;
    }
    
    if (sum_sq == 0) return 1.0;  // All zero, technically equal
    
    return (sum * sum) / (n * sum_sq);
}
 
/*
 * Coefficient of Variation
 *
 * 0 means equal, higher means more inequality.
 */
double coefficient_of_variation(ProcessAlloc procs[], int n) {
    if (n <= 1) return 0.0;
    
    // Calculate mean
    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += procs[i].allocated;
    }
    double mean = sum / n;
    
    if (mean == 0) return 0.0;
    
    // Calculate variance
    double variance = 0;
    for (int i = 0; i < n; i++) {
        double diff = procs[i].allocated - mean;
        variance += diff * diff;
    }
    variance /= n;
    
    double std_dev = sqrt(variance);
    return std_dev / mean;
}
 
/*
 * Need Satisfaction Ratio
 *
 * 1.0 means all needs fully met, lower means under-allocation.
 */
double need_satisfaction_ratio(ProcessAlloc procs[], int n) {
    if (n == 0) return 1.0;
    
    double total_satisfaction = 0;
    
    for (int i = 0; i < n; i++) {
        if (procs[i].needed == 0) {
            total_satisfaction += 1.0;  // No need = fully satisfied
        } else {
            double ratio = (double)procs[i].allocated / procs[i].needed;
            total_satisfaction += (ratio > 1.0) ? 1.0 : ratio;
        }
    }
    
    return total_satisfaction / n;
}
 
/*
 * Starvation Rate
 *
 * Fraction of processes below minimum allocation.
 */
double starvation_rate(ProcessAlloc procs[], int n) {
    if (n == 0) return 0.0;
    
    int starving = 0;
    for (int i = 0; i < n; i++) {
        if (procs[i].allocated < procs[i].minimum) {
            starving++;
        }
    }
    
    return (double)starving / n;
}
 
/*
 * Combined fairness report
 */
void fairness_report(ProcessAlloc procs[], int n) {
    printf("Fairness Metrics Report\n");
    printf("=======================\n\n");
    
    // Display allocations
    printf("%-5s %-10s %-10s %-10s %-10s\n",
           "PID", "Allocated", "Needed", "Minimum", "Satisfied");
    printf("-----------------------------------------------\n");
    
    for (int i = 0; i < n; i++) {
        double sat = (procs[i].needed > 0) ?
                     (double)procs[i].allocated / procs[i].needed : 1.0;
        printf("%-5d %-10d %-10d %-10d %.2f%%\n",
               procs[i].pid, procs[i].allocated, procs[i].needed,
               procs[i].minimum, sat * 100);
    }
    
    printf("\nMetrics:\n");
    printf("  Jain's Fairness Index:     %.4f (1.0 = perfect)\n",
           jains_fairness_index(procs, n));
    printf("  Coefficient of Variation:  %.4f (0.0 = equal)\n",
           coefficient_of_variation(procs, n));
    printf("  Need Satisfaction Ratio:   %.2f%% (100%% = all needs met)\n",
           need_satisfaction_ratio(procs, n) * 100);
    printf("  Starvation Rate:           %.2f%% (0%% = no starvation)\n",
           starvation_rate(procs, n) * 100);
    
    printf("\nInterpretation:\n");
    double jfi = jains_fairness_index(procs, n);
    if (jfi > 0.95) {
        printf("  Allocation equality: EXCELLENT\n");
    } else if (jfi > 0.8) {
        printf("  Allocation equality: GOOD\n");
    } else if (jfi > 0.5) {
        printf("  Allocation equality: FAIR\n");
    } else {
        printf("  Allocation equality: POOR - significant inequality\n");
    }
    
    double sr = starvation_rate(procs, n);
    if (sr == 0) {
        printf("  Starvation: NONE\n");
    } else if (sr < 0.1) {
        printf("  Starvation: MINOR (%.0f%% of processes)\n", sr * 100);
    } else {
        printf("  Starvation: CRITICAL (%.0f%% of processes)\n", sr * 100);
    }
}

Jain's Index Interpretation

Fairness vs Efficiency

One of the fundamental tensions in system design is between fairness and efficiency. Often, the most efficient allocation is not the most fair, and vice versa.

The conflict:

Consider a system with 100 frames and two processes:

Process A: WSS = 80, contribution to throughput when fully allocated = 100
Process B: WSS = 80, contribution to throughput when fully allocated = 100

If we allocate fairly (50-50):

Both processes thrash, maybe 20% efficiency each
Total throughput: 40

If we allocate efficiently (100-0):

One process runs at full speed, one doesn't run at all
Total throughput: 100

Resolving the tension:

Time-sharing: Alternate which process gets enough frames
- Fairness over time, efficiency at each instant
- Both processes complete eventually
Swapping: Run one fully, swap out, run the other
- Similar to time-sharing but at process granularity
- Higher overhead for the swap
Accept inefficiency: Give both some frames, accept thrashing
- Fair but inefficient
- May be appropriate if both processes are interactive

Efficiency-First Approach

•Give each process enough or none
•Maximize throughput at expense of latency
•Swap/suspend under-allocated processes
•Best for batch workloads
•May hurt interactive response

Fairness-First Approach

•Everyone gets something
•Accept lower total throughput
•Everyone makes some progress
•Best for interactive workloads
•May cause system-wide slowdown

The Pareto frontier:

Servers: Lean toward efficiency (maximize requests served)
Desktops: Lean toward fairness (keep applications responsive)
Real-time: May have strict fairness requirements for safety
Cloud multi-tenant: Strong fairness required for billing and SLA

The key insight is that fairness and efficiency are both valid goals, and choosing between them is a policy decision, not a technical one.

Global Thrashing is Lose-Lose

Multi-User Fairness

In multi-user systems (shared servers, cloud environments), fairness operates at multiple levels:

User-level fairness:

Each user should receive fair treatment, regardless of how many processes they run. A user running 100 processes shouldn't get 100x the resources of a user running 1 process.

Solution: Per-user quotas

Allocate frames per user, not per process
A user's processes share their user's allocation
This is the fair share approach at the user level

Tenant-level fairness:

In cloud environments, each tenant (customer) expects their share:

Enforced through cgroups, VMs, or containers
Each tenant's workload isolated from others
Oversubscription requires careful management

Priority among users:

Not all users may be equal:

Paying customers vs free tier
Premium vs standard service levels
Administrative vs regular users

Priority-weighted fair sharing addresses this.

Multi-Level Fairness Hierarchy
Level	Unit	Mechanism	Typical Policy
System	Total frames	Hardware	Fixed by RAM installed
Tenant	Tenant pool	VM/cgroup limits	SLA-based allocation
User	User quota	Per-user cgroups	Fair share within tenant
Process Group	Group share	cgroup hierarchy	Job-based allocation
Process	Individual	Demand paging	Dynamic within group

multi_level_fairness.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
/*
 * Multi-Level Fairness
 *
 * Demonstrates hierarchical fair share allocation
 * for multi-tenant environments.
 */
 
#include <stdio.h>
 
#define MAX_TENANTS 4
#define MAX_USERS_PER_TENANT 8
#define MAX_PROCS_PER_USER 16
 
typedef struct {
    int pid;
    int allocated;
} Process;
 
typedef struct {
    const char *name;
    int quota;              // Frames allocated to this user
    int actual_use;         // Currently using
    Process processes[MAX_PROCS_PER_USER];
    int process_count;
} User;
 
typedef struct {
    const char *name;
    int sla_percent;        // Percent of system guaranteed
    int entitled_frames;
    int allocated_frames;
    User users[MAX_USERS_PER_TENANT];
    int user_count;
} Tenant;
 
typedef struct {
    int total_frames;
    Tenant tenants[MAX_TENANTS];
    int tenant_count;
} MultiTenantSystem;
 
void hierarchical_allocation(MultiTenantSystem *mts) {
    printf("Hierarchical Fair Share Allocation\n");
    printf("===================================\n\n");
    
    // Level 1: Allocate to tenants based on SLA
    printf("Level 1: Tenant Allocation (SLA-based)\n");
    for (int t = 0; t < mts->tenant_count; t++) {
        Tenant *tenant = &mts->tenants[t];
        tenant->entitled_frames = 
            (mts->total_frames * tenant->sla_percent) / 100;
        tenant->allocated_frames = tenant->entitled_frames;
        
        printf("  Tenant '%s': %d%% SLA = %d frames\n",
               tenant->name, tenant->sla_percent, 
               tenant->entitled_frames);
    }
    printf("\n");
    
    // Level 2: Within each tenant, allocate to users
    printf("Level 2: User Allocation (Equal within tenant)\n");
    for (int t = 0; t < mts->tenant_count; t++) {
        Tenant *tenant = &mts->tenants[t];
        
        if (tenant->user_count == 0) continue;
        
        int per_user = tenant->allocated_frames / tenant->user_count;
        
        printf("  Tenant '%s' (%d users, %d frames each):\n",
               tenant->name, tenant->user_count, per_user);
        
        for (int u = 0; u < tenant->user_count; u++) {
            User *user = &tenant->users[u];
            user->quota = per_user;
            printf("    User '%s': %d frames\n", user->name, per_user);
        }
    }
    printf("\n");
    
    // Level 3: Within each user, allocate to processes
    printf("Level 3: Process Allocation (Within user quota)\n");
    for (int t = 0; t < mts->tenant_count; t++) {
        Tenant *tenant = &mts->tenants[t];
        
        for (int u = 0; u < tenant->user_count; u++) {
            User *user = &tenant->users[u];
            
            if (user->process_count == 0) continue;
            
            int per_proc = user->quota / user->process_count;
            
            printf("  %s/%s (%d procs, %d frames each)\n",
                   tenant->name, user->name, 
                   user->process_count, per_proc);
            
            for (int p = 0; p < user->process_count; p++) {
                user->processes[p].allocated = per_proc;
            }
        }
    }
}
 
/*
 * Key insight: Hierarchical fairness
 *
 * - Tenants isolated from each other (can't exceed SLA)
 * - Users within tenant compete fairly
 * - Processes within user share user's quota
 *
 * A misbehaving process affects only its user.
 * A misbehaving user affects only their tenant.
 * Tenant isolation protects the system.
 *
 * This is how cloud environments maintain fairness
 * in multi-tenant systems.
 */

The Noisy Neighbor Problem

Adaptive Fairness Policies

The best fairness policies adapt to conditions rather than applying rigid rules.

Condition-based adaptation:

Under low pressure: Be generous, allow borrowing, prioritize efficiency
- All processes can exceed their base allocation
- No need for strict enforcement
- System runs smoothly
Under moderate pressure: Start enforcing shares
- Borrowed frames may be reclaimed
- Processes limited to their fair share
- Background processes deprioritized
Under high pressure: Strict quotas and possible suspension
- No borrowing allowed
- Processes that can't fit are suspended/swapped
- Essential services protected

Feedback-driven policies:

Monitor process behavior and adjust allocations:

Processes making good progress deserve their allocation
Processes thrashing need more frames or should yield
Processes idle can lend their frames temporarily

Adaptive Fairness Principles

•Monitor continuously — Track memory pressure, fault rates, and progress metrics
•Respond proportionally — Match enforcement strictness to pressure level
•Protect minimums always — Never violate architectural minimums regardless of pressure
•Favor active processes — Processes actively computing deserve frames more than idle ones
•Age priority claims — Long-waiting processes get priority boost
•Communicate limits — Processes should be able to query their allocation for self-regulation

Self-regulating processes:

Some environments allow processes to participate in fairness:

Memory pressure notifications (Linux prctl, Windows WNF)
Applications can release caches when notified
Cooperative garbage collection scheduling
Application-level memory limits (JVM heap, browser tab limits)

This cooperation improves system-wide fairness because:

Applications know which of their memory is truly important
OS can't distinguish essential vs expendable pages
Voluntary reduction is smoother than forced eviction

iOS Memory Warnings

Summary: Balancing Competing Interests

Key Takeaways

•Multiple fairness definitions exist — Equal share, proportional, need-based, max-min, and utilitarian approaches all have merit
•Starvation is the critical fairness violation — Prevention through aging, guarantees, and monitoring is essential
•Fair share scheduling provides structure — Groups receive guaranteed shares with borrowing mechanisms
•Quantitative metrics enable measurement — Jain's index, CV, and satisfaction ratios quantify fairness
•Fairness vs efficiency is a tradeoff — Systems must choose their position on this spectrum
•Multi-level fairness serves multi-user systems — Hierarchies of tenant, user, and process fairness provide isolation
•Adaptive policies work best — Respond to conditions rather than applying rigid rules

Module complete:

The next module explores Allocation Strategies in greater depth, examining global vs local replacement and the interplay between allocation and replacement decisions.

Module 1 Complete

5 / 5