Consider a batch system with four runnable jobs. One requires several seconds of CPU time, while the other three need only short bursts.

Which job should run first? Should the system process them in arrival order or prioritize the shortest job? And if a shorter job arrives while another is running, should it interrupt the current job?

These choices give rise to three classic scheduling algorithms:

These algorithms are intentionally simple, which makes their trade-offs easy to see. Even with the same workload and total CPU demand, the chosen policy can produce very different waiting, response, and turnaround times.

We will compare all three algorithms using one set of processes:

Assume:

The total CPU demand is:

Because P1 arrives at time 0 and some process is always runnable afterward, every schedule will keep the CPU busy from time 0 through time 15. All three algorithms therefore have the same 100% CPU utilization and the same makespan for this workload.

What changes is which process waits and when each process completes.

First-Come, First-Served (FCFS) selects runnable processes in the order they arrived.

The ready queue behaves like an ordinary FIFO queue:

FCFS is normally described as non-preemptive. Once a process receives the CPU, a newly arriving process does not take the CPU away from it. The running process continues until its current CPU burst ends, it blocks, or it exits.

Non-preemptive does not mean a process owns the CPU for its entire lifetime. If it blocks for input, it stops running. When it later becomes runnable, it joins the ready population again according to the system's queueing rules.

At time 0, only P1 has arrived, so P1 starts.

P2 arrives at time 1, P3 at time 2, and P4 at time 3. All three enter the ready queue, but none can preempt P1.

P1 completes at time 8. FCFS then removes processes from the front of the queue:

The first start and completion times are:

Because FCFS is non-preemptive and each process has one burst, response time and waiting time are equal:

The averages are:

P4 needs only one unit of CPU time, but it waits eleven units before running. FCFS never considers burst length, so a short job can wait behind every earlier long job.

The convoy effect occurs when a long CPU burst at the front of an FCFS queue delays many short bursts behind it.

The name evokes a line of fast vehicles forced to travel behind one slow vehicle on a road where overtaking is impossible:

The queue holds one long process followed by three short ones, and everyone behind P1 waits for it to finish.

In our example, P2, P3, and P4 have seven units of total CPU work, yet all of them wait until P1 completes its eight-unit burst.

The effect is particularly harmful when short, frequently blocking tasks sit behind a CPU-bound task. Once the long task finishes, the short tasks may run briefly and then all block for I/O. The CPU can alternate between one long period dominated by the CPU-bound task and another period in which little runnable work remains.

FCFS is not always poor. If jobs have similar burst lengths or arrive at well-spaced times, its simplicity may be valuable and the convoy effect may be small. The problem is that arrival order says nothing about how long the work will occupy the CPU.

FCFS has several practical strengths:

Its weaknesses follow from the same simplicity:

Consider the same three burst lengths arriving together:

FCFS order 2, 4, 10 gives waiting times:

FCFS order 10, 4, 2 gives:

The workload is identical. Only arrival order changed, yet average waiting time became three times larger.

Shortest Job First (SJF) selects the ready process with the smallest next CPU burst.

Like FCFS, classical SJF is non-preemptive. It makes a choice only when the CPU becomes available. Once selected, the process keeps the CPU until its burst finishes or it blocks.

Conceptually:

Among the ready processes, P2 needs 4 units, P3 needs 2, and P4 needs 1, so SJF chooses P4.

SJF uses information that FCFS ignores. Finishing a short burst first prevents many other processes from waiting behind a long one.

The word job can be misleading. The scheduler cares about the length of the next CPU burst, not necessarily the process's entire remaining lifetime. A process may execute a short burst, block for I/O, and later return with another burst.

At time 0, only P1 is available. SJF must choose P1 even though shorter processes will arrive later.

Because SJF is non-preemptive, the arrivals of P2, P3, and P4 do not interrupt P1:

At time 8, the ready processes have burst lengths 4, 2, and 1. SJF chooses P4, then P3, then P2:

The per-process metrics are:

The averages are:

SJF improves average waiting and turnaround over FCFS for this schedule, but P4 still waits five time units. The algorithm cannot act on P4's short burst until the non-preemptive P1 finishes.

Suppose two jobs are already available. Job X requires x units and job Y requires y units, where:

If X runs before Y, their waiting times are:

If their order is reversed:

Because y < x, putting the shorter job first reduces total waiting by:

Any schedule containing a longer available job immediately before a shorter one can be improved by swapping that pair. Repeating the swap eventually orders all available jobs from shortest to longest.

This exchange argument establishes an important result:

When all jobs are available together, burst lengths are known, switching has no cost, and the scheduler will not leave the CPU intentionally idle, SJF minimizes average waiting time among non-preemptive schedules.

The assumptions matter. With unknown future arrivals, a scheduler cannot know whether remaining idle briefly would allow a very short job to arrive. Real operating systems also do not know future CPU bursts exactly.

SJF's optimality is therefore a result for a defined model, not a promise that one simple rule solves every real workload.

A process normally cannot tell the kernel exactly how long its next CPU burst will be.

The burst depends on runtime data, branch decisions, cache behavior, interrupts, and when the process next requests an operation that blocks. A server might handle one request in 100 microseconds and another in 50 milliseconds using the same code path.

An operating system can estimate future behavior from past behavior. A common textbook estimator uses exponential averaging:

Using symbols:

where:

Suppose the previous estimate was 6 milliseconds, the most recent actual burst was 2 milliseconds, and α = 0.5:

A larger α reacts more strongly to recent behavior. A smaller α preserves more history and changes gradually.

Prediction makes mistakes inevitable. A task with a history of short bursts may suddenly perform a long computation, while a historically CPU-bound task may next execute only briefly.

SJF can indefinitely delay a long job if shorter jobs continue arriving.

Suppose L needs 20 CPU units. Every time the CPU becomes free, another one-unit job is already waiting:

At each decision point the ready set is L with 20 units left plus a fresh one-unit job, so the scheduler runs S1, then S2, then S3, and so on.

L remains runnable but is repeatedly bypassed. If the stream of short jobs never ends, L may never start.

This is starvation: a task is eligible to run but fails to make progress because the policy continually prefers other work.

SJF minimizes an average under its model, but a good average does not guarantee bounded waiting for every individual process. The long job's experience can be arbitrarily bad while many short jobs complete quickly.

Shortest Remaining Time First (SRTF) is the preemptive form of SJF.

At every scheduling decision, SRTF chooses the runnable process with the smallest amount of CPU work remaining in its current burst.

If a new process arrives with a shorter remaining time than the process currently running, the current process is preempted:

Before the arrival, P1 holds the CPU with 7 units remaining. P2 then arrives with a burst time of 4. Because 4 < 7, SRTF preempts P1 and runs P2.

The comparison uses remaining time, not original burst time. If P1 began with a burst of 8 but has already run for 6 units, its remaining time is 2.

SRTF continually applies the short-work-first idea rather than waiting for the current burst to finish.

At time 0, P1 is the only process, so it starts with eight units remaining.

Time 1: P2 arrives

P1 has executed for one unit and has seven remaining. P2 needs four:

Time 2: P3 arrives

P2 has executed for one unit and has three remaining. P3 needs two:

Time 3: P4 arrives

P3 has executed for one unit and has one remaining. P4 also needs one:

Our tie rule lets the current process continue, so P3 finishes at time 4. P4 then runs from 4 to 5.

The remaining ready processes are P2 with three units left and P1 with seven. P2 runs from 5 to 8, followed by P1 from 8 to 15:

The diagram combines P3's execution from time 2 through time 4 because the equal-time arrival at 3 does not preempt it.

Verify the executed CPU time:

P1 starts immediately but waits after being preempted:

P2 also starts immediately upon arrival, then waits from time 2 to time 5:

P3 arrives and runs immediately to completion:

P4 waits one unit because its burst ties P3's remaining time and the tie rule favors the current process:

The averages are:

SRTF substantially improves the average values for this workload. P1 pays the price: its turnaround grows from 8 under FCFS and SJF to 15 under SRTF.

Suppose two runnable processes have remaining times x and y, where x > y. Completing the y-unit process first removes one process from the system sooner. Running the longer process instead delays the short process without creating an earlier completion.

The same exchange idea can be reapplied whenever arrivals change the runnable population. This gives the classical result:

On one CPU, with known remaining times, zero switching cost, and freely allowed preemption, SRTF minimizes mean turnaround time among preemptive schedules.

In the single-burst model, total burst time is fixed for a given workload. Reducing total turnaround also reduces total waiting:

The theorem optimizes an average, not every individual completion. It does not prevent starvation, account for inaccurate burst predictions, or include the cost of frequent context switches. Those limitations explain why a mathematically optimal result inside a model is not automatically a complete general-purpose scheduling policy.

The same processes, arrivals, and burst times produce these results:

FCFS preserves arrival order. SJF improves the averages once the CPU becomes free, but it cannot interrupt P1. SRTF reacts to the later short arrivals immediately.

All three schedules perform exactly 15 units of application CPU work. Under the zero-cost-switch assumption, they also have identical utilization and throughput. The improvements come from changing completion order, not from reducing the total computation.

This example also shows why one average cannot describe every task. SRTF gives the best average turnaround, while P1 has its worst individual turnaround under SRTF.

An algorithm may leave several processes equally eligible.

Under FCFS, two processes can have the same arrival time. Under SJF, two ready processes can have equal burst estimates. Under SRTF, a new process can tie the current process's remaining time.

A complete scheduling problem needs a deterministic tie rule, such as:

In the worked SRTF example, choosing P4 at time 3 instead would produce:

P4 would have zero waiting while P3 would wait one unit. Their combined waiting would remain one unit, but their individual response and completion times would differ.

Never silently invent a tie rule halfway through a calculation. State it before drawing the timeline and apply it consistently.

The numerical examples assume that switching between processes takes zero time. Real context switches require kernel work and can disturb useful cache and translation state.

SRTF may switch more often than SJF or FCFS because each arrival can trigger a preemption. If bursts are extremely short, the overhead can consume a meaningful fraction of the time saved by reordering them.

Suppose switching tasks costs 0.2 time units. A schedule with five task changes spends approximately one unit in explicit switching overhead:

How that time affects the metrics depends on the problem's convention. A timeline that includes switch cost must show the overhead intervals and move later completion times accordingly.

Do not add an overhead value unless the problem supplies one. The standard classroom assumption is zero switch cost so the scheduling policy can be studied independently from machine-specific mechanism costs.

SRTF can starve long-running work for the same fundamental reason as SJF.

A long process may begin, but a stream of newly arriving short processes can repeatedly preempt it:

Long task L starts, S1 arrives and preempts it, then S2 runs before L, then S3 runs before L, and so on for as long as short work keeps arriving.

L may receive occasional CPU service, so its remaining time falls slowly, but there is no general guarantee that it completes if shorter work keeps arriving without bound.

SRTF's strong average performance and its starvation risk are not contradictory. Minimizing the sum of completion delays can favor completing many short jobs while imposing a very large delay on one long job.

FCFS asks:

Which runnable process arrived first?

SJF asks:

Of the processes ready now, which has the shortest predicted next CPU burst?

SRTF asks:

Of all runnable processes, including the current one, which has the least predicted CPU time remaining?

Their decision points differ:

Their information requirements differ as well. FCFS needs arrival order but no burst estimate. SJF and SRTF need some estimate of future CPU demand. SRTF must additionally track how much of the predicted burst remains.

Start by sorting processes by arrival time. Apply the stated tie rule to equal arrivals.

Move through the sorted list while tracking the current clock:

Taking the later value matters when the CPU becomes idle before the next process arrives.

For example:

The correct timeline contains an idle interval:

P2 starts at max(2, 5) = 5, not at time 2.

After drawing the timeline, derive response, turnaround, and waiting time from the timestamps. Do not try to infer all metrics mentally while constructing the order.

At each point when the CPU becomes free:

If no process is ready, move the clock to the next arrival and mark the gap as idle.

Do not sort the entire input by burst time once and assume that is the answer. A short process that arrives at time 10 cannot run at time 0.

For the main workload, sorting globally by burst would incorrectly place P4 first even though P4 does not exist in the ready population until time 3.

SRTF requires attention at every event that can change the best choice:

Track remaining time rather than repeatedly using original burst time.

For a process that runs from time a to time b:

At each arrival:

Event-by-event reasoning is safer than drawing one time unit at a time. A one-unit grid becomes tedious for large burst times and makes off-by-one errors more likely.

At the end, verify that every process's execution intervals add to its original burst.

The algorithms can be expressed without implementation-specific data structures.

FCFS:

Non-preemptive SJF:

SRTF:

A FIFO queue naturally supports FCFS. SJF and SRTF need a structure that can efficiently identify a minimum value, along with a deterministic way to handle ties.

These policies appear outside a kernel scheduler as well.

A basic worker queue often behaves like FCFS: requests or jobs are taken in enqueue order. This is predictable, but one expensive job at the front can delay many small jobs behind it.

A build system or data-processing service may approximate SJF when it has historical duration estimates. Completing small jobs first can reduce average queueing time, although inaccurate estimates and starvation still need consideration.

SRTF is harder to apply to application jobs because work must be safely pausable and its remaining duration must be estimated. Preempting a CPU thread is transparent at the operating-system level; pausing an application-level database migration or file transformation may require explicit checkpointing.

The general lesson carries across layers:

Reordering short work ahead of long work can improve average latency, but only if length can be estimated and long work is still guaranteed acceptable progress.

FCFS runs ready work in arrival order. It is simple and resistant to bypass by newer arrivals, but a long burst can create a convoy that delays every short process behind it.

SJF non-preemptively chooses the shortest available CPU burst and minimizes average waiting for a known set of simultaneously available jobs under the standard assumptions. Its central practical limitation is that future burst lengths must be predicted, and continual short arrivals can starve long work.

SRTF extends the short-job principle with preemption: whenever runnable work changes, it selects the process with the least predicted CPU time remaining. This often improves average response, waiting, and turnaround, but it can cause more switching and still provides no inherent protection against starvation.