02. Scheduling in Batch Systems

Batch processing represents the foundational operational paradigm of mainframe computing and modern High-Performance Computing (HPC) clusters. In a batch environment, jobs are submitted non-interactively to a spooling queue. Because no human user sits at a terminal waiting for immediate keystroke feedback, the primary optimization objectives shift decisively:

Maximizing Throughput (X): Completing the maximum number of computational tasks per hour.
Minimizing Turnaround Time (T_turnaround): Delivering finished outputs as quickly as possible.
Maximizing CPU Utilization (U): Ensuring expensive silicon execution units remain saturated near 100% capacity.

1. First-Come, First-Served (FCFS)

The simplest and most intuitive scheduling discipline is First-Come, First-Served (FCFS). Tasks are assigned the processor strictly in the chronological order of their arrival in the Ready queue.

Mechanics & Implementation

The operating system manages the Ready list as a standard FIFO (First-In, First-Out) queue. When a job enters the Ready state, its Process Control Block (PCB) is linked to the tail of the queue. The dispatcher repeatedly pulls the task from the queue head, loads its register state, and allows it to run.

Non-Preemptive Invariant: FCFS is strictly non-preemptive. Once a process acquires a CPU core, it retains exclusive ownership until it voluntarily relinquishes control—either by terminating (exit()) or blocking on an I/O request (read(), write()).

Implementation Complexity: Trivially minimal. Enqueue and dequeue operations operate in O(1) time with zero algorithmic overhead.
Starvation Immunity: Because the arrival order is monotonic and immutable, every queued process will eventually reach the head of the queue. Starvation is impossible under finite job lengths.

The Convoy Effect

Despite its simplicity, FCFS suffers from a severe performance vulnerability known as the convoy effect.

Consider a workload containing one massive, compute-bound process (Process A requiring 24 ms of continuous CPU execution) followed by three lightweight, I/O-bound processes (Processes B, C, and D, each requiring only 3 ms of computation before issuing disk writes).

Figure 2.1: The Convoy Effect under First-Come, First-Served (FCFS)

A single compute-bound task monopolizes the CPU, forcing fast I/O tasks to queue and leaving hardware I/O devices idle.

Mathematical Turnaround and Waiting Time Analysis

Process	Burst Time	Completion Time	Turnaround Time (T_turnaround)	Waiting Time (T_wait)
Process A	24 ms	24 ms	24 − 0 = 24 ms	24 − 24 = 0 ms
Process B	3 ms	27 ms	27 − 0 = 27 ms	27 − 3 = 24 ms
Process C	3 ms	30 ms	30 − 0 = 30 ms	30 − 3 = 27 ms
Process D	3 ms	33 ms	33 − 0 = 33 ms	33 − 3 = 30 ms

FCFS Performance Summary:
Average Turnaround Time = (24 + 27 + 30 + 33) / 4 = 28.5 ms
Average Waiting Time = (0 + 24 + 27 + 30) / 4 = 20.25 ms
The Convoy Consequence: Processes B, C, and D suffer a penalty ratio (slowdown) of W = 27 / 3 = 9.0x to 33 / 3 = 11.0x simply because they were trapped behind a single compute hog. Meanwhile, the disk controller sat completely idle for 24 ms. When A finally finishes, all three short jobs rush through the CPU and issue disk requests simultaneously, leaving the CPU idle while disk queues overflow.

2. Shortest Job First (SJF)

To eliminate the convoy effect and minimize average waiting time, batch architectures turn to Shortest Job First (SJF). When the CPU becomes free, the scheduler inspects the Ready queue and selects the job with the smallest required CPU burst duration.

Mathematical Proof of SJF Turnaround Optimality

Theorem: When all jobs arrive simultaneously at time T = 0, non-preemptive Shortest Job First is provably optimal: it yields the minimum possible average waiting time and minimum average turnaround time among all non-preemptive algorithms.

Formal Proof:
Consider n jobs arriving at T = 0 with execution burst durations t₁, t₂, ..., t_n.
Suppose the scheduler executes these jobs in arbitrary permutation π = (π₁, π₂, ..., π_n).

The waiting time for the first job executed (π₁) is 0.
The waiting time for the second job (π₂) is t_π₁.
The waiting time for the third job (π₃) is t_π₁ + t_π₂.
In general, the waiting time for the k-th job is the sum of all preceding burst lengths:

T_wait(π_k) = ∑_j=1^k−1 t_{π_j}

Summing the waiting times across all n jobs yields the total system waiting time:

Total T_wait = (n − 1)t_π₁ + (n − 2)t_π₂ + (n − 3)t_π₃ + ... + 1·t_{π_n−1} + 0·t_{π_n}

Notice that the burst time of the first job (t_π₁) is added into the waiting time of all (n − 1) remaining jobs. The burst time of the second job is added into (n − 2) jobs, and so on.

To minimize this linear combination ∑_i=1ⁿ (n − i)t_{π_i}, coefficients (n − i) strictly decrease as i increases. By the Rearrangement Inequality, the sum is minimized if and only if the burst times are ordered in monotonically non-decreasing order:

t_π₁ ≤ t_π₂ ≤ t_π₃ ≤ ... ≤ t_{π_n}

Since Average Turnaround Time is simply Average Waiting Time plus the constant mean burst time, minimizing total waiting time simultaneously minimizes average turnaround time. Q.E.D.

Revisiting the Convoy Workload with SJF

Applying non-preemptive SJF to the earlier workload (Jobs B, C, D requiring 3 ms; Job A requiring 24 ms, all available at T = 0):

Execution Order: B → C → D → A
Waiting Times: T_wait(B) = 0 ms, T_wait(C) = 3 ms, T_wait(D) = 6 ms, T_wait(A) = 9 ms.
Average Waiting Time: (0 + 3 + 6 + 9) / 4 = 4.5 ms (vs. 20.25 ms under FCFS — a 78% reduction).
Average Turnaround Time: (3 + 6 + 9 + 33) / 4 = 12.75 ms (vs. 28.5 ms under FCFS — a 55% reduction).

The Arrival Timing Dilemma & Starvation

SJF's mathematical optimality holds strictly only when all candidate jobs arrive simultaneously.

Arrival Order Vulnerability: If Job A (24 ms) arrives at T = 0, and Jobs B, C, and D arrive at T = 1 ms, non-preemptive SJF cannot preempt Job A. The system degenerates into FCFS, and the convoy effect re-emerges.
Starvation (Indefinite Postponement): If short jobs arrive in a steady, continuous stream, a long-running compute job will sit in the Ready queue indefinitely, starved of CPU cycles.

3. Shortest Remaining Time Next (SRTN)

To prevent short jobs from being trapped when they arrive immediately after a long job begins running, operating systems introduce preemption. Shortest Remaining Time Next (SRTN) is the preemptive variant of Shortest Job First.

Preemptive Evaluation Logic

Whenever a new process enters the Ready queue, the scheduler does not wait for the currently executing process to finish. Instead, it compares the expected remaining execution time of the currently running task against the full burst duration of the newly arrived task:

If the newly arrived process requires less execution time than the current task has remaining, the running task is immediately preempted.
The preempted task's register state is preserved in its PCB/trap frame, its state is moved back to TASK_RUNNING (in the Ready list), and the dispatcher switches the CPU core to the new task.
If the new process requires more time than remains on the current task, the running process continues uninterrupted.

Interactive Stepper: FCFS Convoy Effect vs. SRTN Preemption

Timeline Marker T = 0 ms

Active Core Job Process A (Burst: 24 ms)

Ready Queue Depth Empty (No arrivals)

Average Wait Time 0.0 ms (Active)

Current Step Summary Process A arrives at T=0 with a 24ms burst requirement. The CPU starts executing Process A. The Ready queue is currently empty.

What Is Happening

Process A enters the CPU core at T=0. Because no other jobs exist, Process A is granted immediate execution.

Why The System Does This

The operating system maximizes hardware utilization by never letting an execution core sit idle when runnable work is present.

4. Predicting Future Bursts: Exponential Smoothing

The fatal practical limitation of both SJF and SRTN in general-purpose operating systems is obvious: the scheduler cannot know how long a process will execute before it runs. A process may loop three times, read a file, or loop ten million times depending on user input.

To approximate SJF/SRTN, the operating system estimates the next CPU burst duration based on the process's past measured behavior using an exponential moving average (exponential smoothing).

Mathematical Recurrence Formulation

Let t_n be the length of the n-th actual, measured CPU burst. Let τ_n be the predicted value for the n-th burst. The prediction for the upcoming (n + 1)-th burst is calculated recursively as:

τ_n+1 = αt_n + (1 − α)τ_n

where α (0 ≤ α ≤ 1) is a configurable smoothing parameter that controls the weighting:

α = 0 (τ_n+1 = τ_n): Recent history has zero influence. The prediction remains frozen at its initial baseline τ₀.
α = 1 (τ_n+1 = t_n): Past history has zero influence. The next burst is assumed to exactly equal the most recent single burst. Highly vulnerable to temporary anomalies.
α = 0.5 (Balanced Exponential Decay): Equal weight is assigned to the immediate past burst and the historical aggregate. This is the canonical default in production systems.

Expanding the Recurrence Relation

Expanding the formula reveals how historical burst observations decay geometrically over time:

τ_n+1 = αt_n + (1 − α)αt_n−1 + (1 − α)²αt_n−2 + ... + (1 − α)^jαt_n−j + ... + (1 − α)ⁿ⁺¹τ₀

Because (1 − α) < 1, the term (1 − α)^j shrinks exponentially as j increases. Older burst lengths rapidly lose their mathematical weight. If a process historically performed long 100 ms calculations but recently transitions into an interactive I/O phase (producing 2 ms bursts), τ adjusts downward within 3 to 4 scheduling cycles, dynamically reclassifying the task as short.

5. Comprehensive Batch Scheduling Comparison

Selecting or designing a batch scheduling discipline requires evaluating trade-offs across four foundational axes: average turnaround latency, algorithmic complexity, runtime estimation feasibility, and starvation resistance.

1. Bridging the Gap: Highest Response Ratio Next (HRRN)

Non-preemptive Shortest Job First (SJF) minimizes average turnaround time, but leaves long compute jobs vulnerable to indefinite starvation if short jobs arrive continuously. Preemptive Shortest Remaining Time Next (SRTN) eliminates this arrival vulnerability, but requires hardware timer preemption and incurs continuous context-switching overhead.

To resolve the starvation dilemma in strictly non-preemptive batch architectures without timer interrupts, Brinch Hansen developed Highest Response Ratio Next (HRRN).

The HRRN Priority Formula:
Whenever the CPU core becomes free, the scheduler calculates the Response Ratio (R) for every waiting process in the Ready queue and dispatches the task with the maximum ratio:

R = (w + s) / s = 1 + (w / s)

where:

w = Time spent waiting in the Ready queue so far.
s = Expected CPU service / burst time (estimated via τ).

Mechanisms of Built-In Aging:

Favors Short Jobs: When a new task arrives (w = 0), its ratio is R = 1.0. As soon as it waits, a small expected burst s in the denominator causes w / s to grow rapidly, giving short jobs quick escalation.
Prevents Starvation: A massive compute job with large s starts with a sluggish ratio. However, as it sits in the queue, its waiting time w accumulates monotonically in the numerator. Eventually, w becomes large enough that the long job's ratio surpasses newly arrived short jobs, guaranteeing execution without preemption.

2. Multi-Dimensional Batch Comparison Matrix

Algorithm	Selection Rule	Preemption	Turnaround Profile	Starvation Risk	Data Structure & Cost
FCFS	`MIN(Arrival)`	Non-Preemptive	Poor (Degraded by Convoy Effect)	Zero (Monotonic arrival order)	FIFO Queue: `O(1)` enqueue & dequeue.
SJF	`MIN(Burst τ)`	Non-Preemptive	Optimal for simultaneous arrivals	High (Continuous short jobs starve long jobs)	Min-Heap: `O(log n)` insert/extract.
SRTN	`MIN(Remaining τ)`	Preemptive	Optimal across dynamic arrivals	High (Long tasks can be repeatedly interrupted)	Min-Heap: `O(log n)` + context switch cost.
HRRN	`MAX((w+s)/s)`	Non-Preemptive	Near-Optimal (Balances short/long)	Zero (Waiting time w guarantees aging)	Linear scan: `O(n)` per dispatch.

3. Analytical Edge Cases & Theorems

The Identical-Burst Degeneracy Theorem: If all processes in a workload require identical CPU burst durations (s₁ = s₂ = ... = s_n = K), then SJF, SRTN, and HRRN all collapse into standard First-Come First-Served (FCFS). Under this condition, preemption in SRTN provides zero mathematical benefit and serves only to waste CPU cycles in pointless context switching.
The Starvation Threshold: Under SJF or SRTN, a long job requiring S seconds of CPU time will starve indefinitely if the arrival rate of short jobs λ_short and their mean service duration E[S_short] satisfy:
```
ρ_short = λ_short × E[S_short] ≥ 1.0
```
When the utilization generated solely by short tasks equals or exceeds 100% of CPU capacity, the ready queue never clears of short tasks, driving the waiting time of the long job to infinity:
```
T_wait(Long Job) → ∞
```

4. Production Batch Systems & HPC Scheduling

In modern High-Performance Computing (HPC) clusters and supercomputer workload managers (such as SLURM, PBS Pro, or HTCondor), CPU cores are scheduled across thousands of nodes executing multi-day scientific simulations.

Because general-purpose exponential smoothing (τ) cannot reliably predict whether a climate model will run for 10 minutes or 48 hours, production HPC systems bypass estimation entirely:

Mandatory Wall-Clock Declarations: Users submit jobs with an explicit declared execution ceiling (#SBATCH --time=04:00:00). If the job exceeds this duration, the kernel immediately terminates it via SIGKILL.
Reservation Scheduling & Backfilling: To prevent the convoy effect without killing long compute jobs, modern batch systems use Backfilling:
1. A massive 512-core simulation is queued and assigned an upcoming start reservation at T = 14:00.
2. Rather than leaving cores idle while waiting for earlier jobs to drain, the scheduler scans the queue for short jobs that can start immediately and finish before the 14:00 reservation.
3. These short jobs are "backfilled" into the execution gaps, achieving 95%+ CPU utilization across the cluster while honoring the reservation of the primary batch job.