CPU & I/O Scheduling

A scheduler exists because there are more runnable executions than processors, and something must decide which one runs next.

The organising fact is that every scheduling algorithm is a different answer to a single question, and each answer optimises one metric at the cost of another. There is no best algorithm, only an algorithm best matched to a workload and a goal.

Shortest job first minimises average waiting time and starves long jobs. Round robin bounds response time and worsens average turnaround. First come first served is trivially fair and permits the convoy effect.

The second organising fact is that the exam grades your bookkeeping, not your opinions. Almost every scheduling question is a Gantt chart followed by an arithmetic mean, and marks are lost to arrival times and tie-breaking, not to conceptual confusion.

The third is that disk scheduling is the same problem with a different cost function. The CPU scheduler minimises time; the disk scheduler minimises head movement, because seek time dominates everything else on a rotating disk.

1. What the Scheduler Decides

The long-term scheduler admits new processes into the system, controlling the degree of multiprogramming. It runs rarely, in seconds or minutes, and is absent from most interactive systems.

The short-term scheduler picks which ready process runs next. It runs every few milliseconds and must therefore be fast, since its own cost is pure overhead.

The medium-term scheduler swaps processes out to disk and back, reducing memory pressure by temporarily removing a process from the ready set.

A dispatcher is not a scheduler. The scheduler decides; the dispatcher performs the context switch, loads the new register set and jumps to the resumption point. The time it takes is called dispatch latency.

2. Criteria and Metrics

Five quantities are defined for each process, and getting the definitions exactly right is worth more marks than knowing every algorithm.

Waiting time counts all the time a process spends in the ready queue, whether it was preempted or had not yet started. Deriving it as turnaround minus burst handles both cases automatically and is safer than adding up gaps by eye.

Response time and turnaround time diverge sharply under round robin, which is precisely the point of that algorithm: a process gets on the CPU quickly even though it finishes late.

Throughput and average waiting time can conflict. A policy that admits more short jobs raises throughput while a long job's waiting time grows without bound.

3. Preemptive and Non-preemptive Scheduling

Non-preemptive scheduling lets a running process keep the CPU until it blocks or exits. Scheduling decisions occur only at those two points.

Preemptive scheduling can take the CPU away, at a timer interrupt, or when a higher-priority process becomes ready.

Preemption is what makes interactive systems responsive, and also what makes shared data hazardous, because a process can be interrupted between any two instructions.

Preemption costs context switches, so a scheduler that preempts too eagerly spends its gains on overhead.

4. The Classical Algorithms

First come first served runs processes in arrival order and is non-preemptive. It is simple and fair in the queueing sense, but suffers the convoy effect: one long CPU-bound process at the head makes every short process behind it wait, and average waiting time can be arbitrarily bad.

Shortest job first picks the ready process with the smallest next CPU burst. It provably minimises average waiting time among non-preemptive policies. Its defect is that the next burst length is not known, so it must be estimated, usually by exponential averaging of past bursts.

Shortest remaining time first is the preemptive form of shortest job first. When a new process arrives with a burst shorter than the remaining time of the running one, it preempts. It gives the lowest average waiting time of the classical set and starves long jobs most severely.

Priority scheduling picks the highest priority ready process and exists in both preemptive and non-preemptive forms. Shortest job first is exactly priority scheduling with priority equal to the inverse of the next burst.

Its defect is indefinite blocking, where a low-priority process never runs because higher-priority arrivals keep coming. Aging fixes it by raising a process's priority the longer it waits, guaranteeing it eventually reaches the top.

Round robin gives each process a time quantum and cycles through the ready queue. It is the responsiveness algorithm: with $n$ processes and quantum $q$, no process waits more than $(n-1)q$ time units for its first turn, ignoring switch overhead.

Quantum selection is the whole design question for round robin. Too large and it degenerates into first come first served. Too small and context switch overhead dominates. The usual guidance is that around 80 percent of bursts should be shorter than the quantum.

5. Multilevel Queues and Feedback

A multilevel queue partitions the ready set permanently, typically into a foreground interactive queue and a background batch queue, each with its own algorithm, plus a policy for scheduling between queues.

A multilevel feedback queue lets processes move between levels, which is what real systems use.

The standard configuration has several queues of decreasing priority and increasing quantum. A new process enters the highest-priority queue. If it uses its entire quantum without blocking, it is demoted; if it blocks early, it stays or is promoted.

This approximates shortest job first without needing to know burst lengths. A process that keeps yielding early is behaving like a short interactive job and is rewarded with high priority; one that consumes full quanta is behaving like a batch job and is demoted.

Aging is layered on top so that a demoted process cannot starve forever.

6. Disk Scheduling

On a rotating disk, access time has three components, and only one is worth optimising.

Seek time moves the arm to the right cylinder and is the largest, on the order of milliseconds.

Rotational latency waits for the sector to arrive under the head and averages half a rotation.

Transfer time moves the bytes and is comparatively negligible.

Because seek dominates, disk scheduling algorithms are judged by total head movement.

First come first served serves requests in arrival order and can swing the arm wildly across the disk.

Shortest seek time first always serves the closest pending request. It reduces total movement substantially but can starve requests at the edges while a cluster of nearby requests keeps arriving.

SCAN, the elevator algorithm, moves the head in one direction serving everything on the way, reaches the end of the disk, reverses, and serves everything on the way back. No request waits more than one full sweep.

C-SCAN serves requests in one direction only, then jumps back to the start without serving anything on the return. It gives a more uniform waiting time than SCAN, because under SCAN a cylinder just behind the head is served twice in quick succession at the turn.

LOOK and C-LOOK are the practical variants: they reverse at the last pending request rather than at the physical end of the disk, saving the useless travel to cylinder zero or the last cylinder.

Solid state drives change the analysis completely. There is no arm and no seek, so these algorithms give no benefit and simple queue ordering with write coalescing is used instead.

7. Worked Examples

Example 1. Four processes arrive at time 0 in the order P1, P2, P3, P4 with bursts 8, 4, 9, 5. Compute average waiting time under first come first served and under shortest job first.

Under first come first served the order is P1, P2, P3, P4.

Average waiting time is $(0+8+12+21)/4=41/4=10.25$.

Under shortest job first the order is P2, P4, P1, P3.

Average waiting time is $(0+4+9+17)/4=30/4=7.5$.

Note what did not change. Total completion time is 26 in both cases, because the same total work is done with no idle time. Shortest job first improves the average by moving the waiting onto the longest job, not by reducing total waiting.

Example 2. Processes arrive as follows: P1 at 0 with burst 7, P2 at 2 with burst 4, P3 at 4 with burst 1, P4 at 5 with burst 4. Schedule under shortest remaining time first.

Evaluate at each arrival and each completion.

At time 0 only P1 is present, so P1 runs.

At time 2 P2 arrives with burst 4. P1 has 5 remaining. Since 4 is less than 5, P2 preempts.

At time 4 P3 arrives with burst 1. P2 has 2 remaining. Since 1 is less than 2, P3 preempts.

At time 5 P3 finishes. Ready are P1 with 5 remaining, P2 with 2, and P4 with 4, which just arrived. P2 has the smallest remaining time and runs.

At time 7 P2 finishes. Ready are P1 with 5 and P4 with 4, so P4 runs.

At time 11 P4 finishes and P1 runs its remaining 5, completing at 16.

Average waiting time is $(9+1+0+2)/4=3$.

Example 3. Three processes arrive at time 0 with bursts 24, 3, 3. Compute average waiting time and average response time under round robin with quantum 4, then state what changes at quantum 1.

With quantum 4 the sequence is P1 for 4, P2 for 3, P3 for 3, then P1 for the remaining 20.

P1 first runs at 0 and completes at 30. P2 runs from 4 to 7. P3 runs from 7 to 10.

Average waiting time is $(6+4+7)/3\approx 5.67$ and average response time is $(0+4+7)/3\approx 3.67$.

At quantum 1 the response times improve, since P2 first runs at time 1 and P3 at time 2, giving an average response of 1.

But the number of context switches rises sharply. With quantum 4 there are 3 switches; with quantum 1 there are 29. If each switch costs even 0.1 time units, quantum 1 adds 2.9 units of pure overhead against 0.3.

This is the round robin trade-off in one example: the quantum buys response time and pays in overhead.

Example 4. A priority scheduler has a low-priority process that has waited 100 time units while higher-priority arrivals keep coming. Explain the failure and how aging repairs it, with a concrete rule.

The failure is indefinite blocking, often called starvation. The scheduler always picks the highest-priority ready process, and as long as such arrivals keep coming, the low-priority process is never chosen.

Nothing in the algorithm bounds the wait, because priority is a static property of the process and time in the queue does not enter the decision.

Aging makes waiting time part of the priority. A concrete rule: increase the priority of every waiting process by one level for each 10 time units it spends in the ready queue.

Under that rule a process starting at priority 20, where 0 is highest, reaches priority 0 after 200 time units of waiting, at which point no arrival can outrank it.

The guarantee is now a bound rather than a hope. Every process reaches the top priority in finite time, so every process eventually runs, regardless of the arrival pattern.

The cost is that aging weakens the priority scheme it protects, since a sufficiently patient low-priority job will eventually preempt genuinely urgent work. Real-time systems therefore do not age their highest band.

Example 5. A disk has 200 cylinders numbered 0 to 199. The head is at cylinder 53 and the pending queue is 98, 183, 37, 122, 14, 124, 65, 67. Compute total head movement under shortest seek time first, SCAN moving toward higher cylinders, and C-SCAN.

Under shortest seek time first, always take the nearest pending request.

From 53 the nearest is 65, then 67, then 37, then 14, then 98, then 122, then 124, then 183.

Movement is $12+2+30+23+84+24+2+59=236$ cylinders.

Under SCAN toward higher cylinders, serve 65, 67, 98, 122, 124, 183, continue to 199, reverse, then serve 37 and 14.

Movement is $(199-53)+(199-14)=146+185=331$ cylinders.

Under C-SCAN, serve 65, 67, 98, 122, 124, 183, continue to 199, jump to 0, then serve 14 and 37.

Movement is $(199-53)+(199-0)+37=146+199+37=382$ cylinders.

Shortest seek time first wins on total movement here, as it usually does, but it is the only one of the three that can starve a request. A stream of requests near cylinder 60 would keep the head there while 183 waits indefinitely.

Under LOOK the wasted travel disappears: reverse at 183 rather than 199, giving $(183-53)+(183-14)=130+169=299$.

Example 6. Prove informally that shortest job first minimises average waiting time when all processes arrive together.

Consider any schedule and suppose two adjacent jobs run in the order long then short, with bursts $a$ and $b$ where $a>b$.

Let the pair start at time $t$. In this order, the first waits $t$ and the second waits $t+a$, so their combined waiting is $2t+a$.

Swap them. Now the short one waits $t$ and the long one waits $t+b$, so their combined waiting is $2t+b$.

Since $b<a$, the swap strictly reduces total waiting.

No other process is affected, because the pair occupies the same interval either way and every later job still starts at $t+a+b$.

Therefore any schedule containing an out-of-order adjacent pair can be improved, so an optimal schedule has no such pair, which means it is sorted by increasing burst. That is exactly shortest job first.

The argument needs the equal-arrival assumption. With staggered arrivals the swap may not be available, because the shorter job might not have arrived yet, which is why the preemptive variant is needed to recover optimality.

Summary

Every scheduling algorithm answers one question and each optimises a different metric, so the comparison is always about workload and goal rather than a single best choice.

Turnaround is completion minus arrival, waiting is turnaround minus burst, and response is first CPU time minus arrival. Deriving waiting from turnaround avoids errors with preempted processes.

First come first served is non-preemptive and permits the convoy effect. Shortest job first minimises average waiting time but needs an unknown quantity, so bursts are estimated by exponential averaging. Shortest remaining time first is its preemptive form and starves long jobs.

Priority scheduling generalises shortest job first and suffers indefinite blocking, which aging repairs by making waiting time raise priority.

Round robin bounds first-turn waiting at $(n-1)q$ and trades response time against context switch overhead. The quantum should exceed about 80 percent of bursts.

Multilevel feedback queues approximate shortest job first without knowing burst lengths, demoting processes that consume full quanta and rewarding those that block early.

Disk scheduling minimises head movement because seek time dominates. Shortest seek time first is efficient but can starve edge requests. SCAN sweeps and reverses at the disk end; C-SCAN returns without serving, giving more uniform waits; LOOK and C-LOOK reverse at the last pending request. None of this applies to solid state drives, which have no seek.