Operating Systems

CPU Scheduling

Published: 2026-08-15

Level: postgraduate

Audience: Postgraduate students studying Operating Systems

5.1 Multiprogramming and the CPU Burst Cycle

5.1.1 What Multiprogramming Means

The earlier material on processes and threads, including how threads get scheduled, is behind us. From here on the focus is process scheduling and, later, process synchronization. Everything in this topic hangs on one goal: an operating system exists to maximize CPU utilization. The CPU should never sit idle; it should always have some job to do. An idle CPU is wasted time, so multiprogramming exists to keep it busy.

Why should the CPU never sit idle? A processor that is not executing anything is a machine doing zero useful work while still consuming power and occupying rack space. In a single-processor system only one process can run at a time; any others must wait until the CPU is free and can be rescheduled. The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization.

Multiprogramming means more than one program is loaded into memory at the same time, all waiting for execution. While one program runs, another is also present in memory, ready to take over the moment the running one cannot. The classic sequence: the CPU executes a program for a while; the program needs input/output (I/O); the program waits for the I/O to finish; during that wait the CPU moves on to another program. That is how one CPU keeps several programs moving forward.

Everyday analogy — one chef, many ovens. Think of a single chef (the CPU) in a busy kitchen with several dishes (programs) at different stages. While one dish is inside the oven — which takes time and needs no chef — the chef starts chopping vegetables for another dish. If the chef insisted on standing still next to the oven until each dish finished baking, the kitchen would produce almost nothing. The oven is the I/O device: slow, external, and free to run while the chef works elsewhere. Multiprogramming is exactly this: instead of letting the CPU wait for a slow I/O operation, the operating system hands the CPU to a different program that is ready to compute. The analogy breaks where the chef is human — a chef works on one task at a time by choice, while the CPU must be switched by the operating system, and the switch itself costs time (the context switch we meet later).

5.1.2 The CPU and I/O Burst Cycle

Each stretch of execution has a name: we call a burst the execution time, whether it is CPU execution or I/O execution. A process does not run continuously; its life is an alternating cycle: CPU execution, then I/O, then CPU again, then I/O again, and so on. Eventually, the final CPU burst ends with a system request to terminate execution. The scheduling problem starts here, because the distribution of CPU bursts has to be balanced — a process that is mostly I/O with tiny CPU bursts looks very different from one that hogs the CPU. That balance is the main concern, and the basis, of scheduling.

The burst cycle, formally. Process execution is a cycle of CPU execution and I/O wait:

A process begins with a CPU burst — a stretch of pure computation.
The burst is followed by an I/O burst — a wait for an input/output device.
Then another CPU burst, another I/O burst, and so on.
The process ends when its final CPU burst issues a terminate request.

Two labels capture the extremes of this spectrum:

An I/O-bound program (one that spends most of its time waiting for devices) typically has many short CPU bursts — it computes a little, then goes back to waiting for I/O.
A CPU-bound program (one that does heavy computation) might have a few long CPU bursts — it grabs the CPU and keeps it for long stretches.

An I/O-bound process finishing a CPU burst and moving back to an I/O device is exactly the moment when the CPU can be reassigned to somebody else. This is why the mix of both kinds matters: if the system is full of long CPU-bound bursts, the CPU is busy but I/O devices idle; if it is full of short bursts, the CPU is frequently free but devices are busy. Scheduling tries to keep both sides busy.

A histogram of CPU-burst lengths shows the pattern: a large number of very short CPU bursts and a small number of long ones. The frequency on the vertical axis shows how many bursts last a given length, and the peak sits at the short end. The practical point of view: the CPU is not always there waiting for work, and we have to maximize its utilization. The distribution tells us that most processes use the CPU briefly, so with many programs in memory there is almost always a short burst ready to run — which is exactly what keeps the CPU busy.

Reading the histogram. Picture the chart from the lecture: the horizontal axis is CPU-burst duration in some time unit, growing longer to the right; the vertical axis is the frequency — how many bursts have that duration. The curve starts high at the left edge (a large number of very short bursts), then falls steeply, with a long thin tail of rare long bursts. Textbooks describe this curve as exponential or hyperexponential in shape. Two landmarks to notice: the peak at the short end tells you that most processes are brief visitors to the CPU; the long tail tells you that a few processes hold the CPU for a long time. The one-sentence takeaway: because most bursts are short, a ready queue holding several processes almost always contains a short burst that can be run next — the CPU can stay busy by rotating through the pool.

Scope and limits of the burst-cycle picture. The alternating-cycle model assumes a process can be cleanly divided into CPU stretches and I/O stretches, which is true of most real programs but not of every situation. A process that never performs I/O (a tight compute loop) has one huge CPU burst and no cycle at all; a process that is always waiting has almost nothing to run. The model also abstracts away the cost of switching between processes: in reality the switch itself consumes CPU time, so the benefit of multiprogramming only materializes when bursts are large compared with the switch cost.

Recap and bridge. Multiprogramming keeps several programs in memory so the CPU is never idle; a process's life alternates between CPU bursts and I/O bursts, most bursts are short, and that is the raw material the scheduler works with. Handoff: the burst cycle poses the question — which of the ready processes should the CPU pick next? — and the next topic answers it with the scheduler, the scheduling decisions, and the dispatcher.

Multiprogramming is not a theoretical curiosity — it is the reason the rest of this lecture exists. Every interactive system you use relies on it: when you type in a terminal or tap on a phone, the operating system is filling the gaps between your keystrokes and screen updates with other processes' bursts. Server farms do the same at scale: a web server is mostly I/O-bound (network waits), and a database's analytics engine is mostly CPU-bound; schedulers on those machines juggle both so that neither the processors nor the network links sit idle. Even inside a single chip, the idea repeats: multi-core and simultaneous multithreading (SMT) designs, such as Intel Hyper-Threading, are hardware attempts to fill otherwise idle execution units with a second thread's work — the same "never leave the CPU idle" principle, moved into silicon.

5.2 The Scheduler, Scheduling Decisions, and the Dispatcher

5.2.1 The Schedulers

Scheduling needs decisions, and the earlier material already named the decision makers: the long term scheduler, the short term scheduler, and the medium term scheduler. The short term scheduler is the one at the center of this topic. Its work happens very often — it runs many processes, but the time required for each of its decisions is very small. It selects the process sitting in the ready queue and allocates it to the CPU for execution. That is the usual picture. The ready queue can be ordered in any way we choose; the choice of that order is exactly what the scheduling algorithms decide.

Where the short term scheduler sits. In a single-processor system, only one process can run at a time; any others must wait until the CPU is free and can be rescheduled. Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed — and that selection is carried out by the short term scheduler (also called the CPU scheduler). Quick recap of the three schedulers, from the earlier process material:

Long term scheduler (job scheduler): decides which jobs are admitted into memory, from a pool of submitted jobs. It runs rarely — once per new job.
Medium term scheduler: handles swapping — moving processes between memory and disk to control the degree of multiprogramming. It runs occasionally.
Short term scheduler: selects the next process from the ready queue, on every CPU switch. It runs constantly — every few milliseconds — so its decision must be very fast.

Note that the ready queue is not necessarily a first-in, first-out queue. It is a concept: the set of processes in memory that are ready to execute. The queue can be implemented as a FIFO queue, a priority queue, a tree, or simply an unordered linked list; the scheduling algorithms decide which order is used, and the records in the queues are generally the process control blocks (PCBs) of the processes.

5.2.2 The Four Situations That Trigger Scheduling Decisions

A scheduling decision happens in four situations. Imagine a process currently executing on the CPU:

The process needs I/O, or an interrupt arrives, and the process switches from the running state to the waiting state. Here a decision is made.
The CPU switches the process from the running state to the ready state — its allowed execution time has run out, and it goes back to the ready queue. Here again a decision is made.
The process switches from the waiting state to the ready state. It was waiting for an I/O operation; the I/O completes, so the process returns to the ready state, ready for execution. Decision made.
The process completes its CPU execution and moves to the terminated state. Decision made.

In any one of these four situations, a scheduling decision is taken about which process runs next. The first and the fourth situations are non-preemptive: nothing forces the process to leave the CPU early. The process leaves only when it finishes by itself — there is no compulsion, no forced relinquishing of the CPU. The second and third situations are preemptive: the running process is taken out of the CPU so another process can execute.

Choice versus no choice. Situations 1 and 4 leave the scheduler with no real choice: the process is gone from the CPU, so if any process sits in the ready queue, one of them must be selected. The interesting scheduling freedom appears in situations 2 and 3: the running process could continue, but the scheduler may decide to replace it with another one. It is precisely this optionality that makes a scheduling scheme preemptive — and that makes the algorithm matter.

5.2.3 Preemptive vs Non-preemptive Scheduling

Preemption means we voluntarily take a process out of the CPU and bring the next process in for execution. That sounds simple, but when a process is taken out mid-execution, complications can arise. The process may be accessing shared data; the kernel may be in kernel mode; interrupts can occur while an important activity is being performed. Any of these can happen in situations two and three. So when scheduling is preemptive, the scheduler must consider all of these situations before it pulls a process out of the CPU. Non-preemptive scheduling avoids this complexity: the running process always runs to completion or until it blocks on its own, and only then does the next process get its chance.

What can go wrong during preemption (the professor's warning). Taking a process off the CPU mid-execution is not a neutral act. The scheduler must consider, before pulling a process out:

Shared data: two processes may share data; if one is updating it and is preempted, the next process can read data in an inconsistent, half-updated state. Coordinating such access needs new mechanisms (the synchronization topic that follows this lecture).
Kernel mode: during a system call, the kernel may be busy changing important kernel data, for instance the I/O queues. If the process is preempted in the middle of those changes, another process or the device driver may read or modify the same structure — chaos ensues. Many UNIX versions avoid this by waiting for the system call to complete or for an I/O block before doing a context switch.
Interrupts: by definition, interrupts can occur at any time, and they cannot always be ignored — otherwise input might be lost or output overwritten. Code sections affected by interrupts must be guarded (for example by disabling interrupts at entry and re-enabling at exit), but such sections are few and short.

Because of these complications, the scheduler must weigh all these situations before deciding to pull a process out of the CPU.

Dimension	Non-preemptive (cooperative)	Preemptive
When a process leaves the CPU	Only on its own: it terminates or blocks for I/O	It may be forced out at any moment by the scheduler
Scheduling decisions	Only situations 1 and 4	All four situations, especially 2 and 3
Shared-data risk	Low — nobody is yanked mid-update	High — a process can be preempted while updating shared data
Hardware required	None special	Needs a timer interrupt so the scheduler can reclaim the CPU
Fairness / interactivity	A runaway process starves everyone	The scheduler can give each process a slice
Example systems	Windows 3.x, early Mac OS (cooperative)	Windows 95 onward, modern Mac OS X, Linux, UNIX

The trade-off in one line: non-preemptive is simple and safe but can be unfair; preemptive is responsive and fair but must guard shared data and kernel structures. Real general-purpose operating systems use preemptive scheduling — Linux, Windows, and macOS all do. Cooperative scheduling survives mainly on limited hardware platforms that lack the timer hardware that preemption requires.

5.2.4 The Dispatcher and Dispatch Latency

The scheduler chooses the next process; the dispatcher carries the choice out. The dispatcher's job is to bring the selected process to the CPU for execution. It must perform context switching: save the state of the previous process, then load the state of the next process that comes for execution. It switches from kernel mode to user mode, then sends the process to the proper location in memory where its execution resumes. The time the dispatcher takes to stop one process and start another is called the dispatch latency. The short term scheduling function is performed with the help of the dispatcher module: the short term scheduler picks the process, and the dispatcher makes the switch happen.

The dispatcher's three actions. The dispatcher is the module that gives control of the CPU to the process selected by the short term scheduler. Its job has three parts:

Switch context: save the state (registers, program counter, stack pointer) of the outgoing process into its PCB, and load the saved state of the incoming process from its PCB.
Switch to user mode: the CPU is running kernel code; the dispatcher returns it to user mode so the process can run its own instructions.
Jump to the proper location in the user program to restart that program — resuming at the exact instruction where it was stopped.

Since the dispatcher is invoked during every process switch, it should be as fast as possible: the faster the switch, the less CPU time is eaten by bookkeeping. The total time to stop one process and start another is the dispatch latency — every millisecond of it is pure overhead added to each process switch.

Why dispatch latency matters — a quick sense of scale. Suppose a time-sharing system switches processes every 5 milliseconds and dispatch latency is 0.5 milliseconds. Each switch then spends 10% of its time just doing the switch. With one process of 10 time units total work, a time quantum of 6 means two quanta and one context switch; shrinking the quantum to 1 means ten quanta and nine context switches — the process runs more slowly even though it does the same work, because more of its time is consumed by switching. This is why real systems keep time quanta large relative to context-switch time.

Common beginner mistakes about the scheduler.

Confusing the scheduler with the dispatcher: the scheduler decides (which process), the dispatcher does (performs the switch). Both are needed.
Believing the ready queue is always FIFO: it is a logical queue; the algorithm decides the order, and the implementation may be a list, tree, or priority queue of PCBs.
Thinking preemption is free: every forced switch risks inconsistent shared data and kernel structures, and pays dispatch latency.
Assuming all four scheduling situations are choices: in situations 1 and 4 the CPU is already free, so a decision is forced; real choice exists only in situations 2 and 3.

Recap and bridge. The short term scheduler picks the next process from the ready queue whenever one of four situations occurs; situations 2 and 3 make scheduling preemptive, which buys responsiveness at the price of shared-data and kernel-safety complications; the dispatcher then executes the switch, and its dispatch latency is overhead on every switch. Handoff: we know when to schedule — the next question is on what basis to choose, which the scheduling criteria answer.

In the real world this machinery runs billions of times per second across data centers. On a typical Linux server, the Completely Fair Scheduler (CFS) makes a scheduling decision and invokes the dispatcher on every timer tick — thousands of times per second per core. Real-time systems such as automotive ECUs or industrial controllers set hard deadlines: an airbag controller must receive its sensor data within a few milliseconds of the crash, so its kernel is engineered to minimize dispatch latency (some versions keep the kernel fully preemptible specifically to reduce it). In contrast, cooperative scheduling survives in small embedded microcontrollers where one program is trusted to finish before the next starts — the trade-off made in section 5.2.3, chosen by real products.

5.3 Scheduling Criteria

5.3.1 CPU Utilization

When several processes sit in the ready queue, on what basis do we order them? The scheduling criteria answer that question. The first criterion, and the main aim of the whole exercise, is CPU utilization: keep the CPU as busy as possible, never idle. Real-world systems put concrete numbers on this. In interactive systems and real-time systems, the CPU should be at least 40% busy doing real work; non-interactive systems run at far lower levels. Whatever the system, the criterion stays the same — maximize CPU utilization.

Hook. With several processes waiting in the ready queue, who goes first? The answer depends on what we want the system to achieve — and the five criteria below are the yardsticks. The surprising part comes at the end: no single algorithm can win on all of them, so every real scheduler is a compromise.

CPU utilization is conceptually the fraction of time the CPU is busy, ranging from 0 to 100%. In a real system, a reasonable figure is 40% for a lightly loaded system and up to 90% for a heavily used one. The professor's rule of thumb — at least 40% busy in interactive and real-time systems — is the practical floor: below that, the machine is not earning its keep, and interactive users will feel the sluggishness as their commands queue behind nothing at all.

5.3.2 Throughput

The second criterion is throughput: how many processes get completed per unit time. Suppose 10 processes exist, and 4 of them have finished execution. The ratio of those two numbers is the throughput. More generally:

$Throughput = \frac{number of processes completed}{total time taken for all processes to complete}$

Symbols and units. The numerator is a pure count of completed processes, the denominator is elapsed time, so throughput carries units of processes per unit time — for example, 4 processes completed in 10 time units gives $\frac{4}{10} = 0.4$ processes per time unit. Throughput is a measure of how much work the system is actually finishing, not how much it is attempting. For long jobs the rate may be one process per hour; for short transactions it may be ten processes per second.

5.3.3 Turnaround Time

The third criterion is turnaround time: the total time it takes to execute a particular process. Everything counts here — the time the process arrives into the ready queue, the time it spends waiting to get the CPU, the time it executes, and the time until it completes and exits the CPU. It is the span from arrival to completion:

$T T = C T - A T$

where $T T$ is the turnaround time, $C T$ is the completion time, and $A T$ is the arrival time. Both $C T$ and $A T$ are measured in time units.

Why the formula captures everything. The definition of turnaround time is the interval from submission of a process to its completion — from the point of view of a particular process, how long it took to execute. $C T$ and $A T$ are both wall-clock times, so their difference is the full span a user waits from submitting a job until it finishes: waiting in memory, waiting in the ready queue, executing on the CPU, and doing I/O, all included. Because it includes I/O time, turnaround is not purely controlled by the scheduler — but the ready-queue portion of it is.

5.3.4 Waiting Time

The fourth criterion is waiting time: how long the process waits in the ready queue for its turn at the CPU. A convenient formula connects it to turnaround time: the burst time (the execution time) is the part of the turnaround spent actually running, so the rest is waiting.

$W T = T T - B T$

where $W T$ is the waiting time, $T T$ is the turnaround time, and $B T$ is the burst time.

Scope of the waiting-time formula. $W T = T T - B T$ holds exactly when the span from arrival to completion contains exactly one CPU burst and no I/O in between — which is the setup of every worked example in this lecture. In general, the waiting time is the sum of the periods the process spends waiting in the ready queue: under preemptive scheduling a process may be pulled out of the CPU and put back several times, and each stretch spent in the ready queue counts. Also note the scheduler does not control execution time or I/O time — it only shapes how much time a process spends waiting in the ready queue, which is exactly why waiting time is the fairest measure of a scheduling algorithm's quality.

5.3.5 Response Time

The fifth criterion is response time: the time from when the request is submitted until the first response arrives — the first moment the process gets into the CPU. This matters because a process does not necessarily run to completion once it enters. Under preemptive scheduling it can be pulled out and put back repeatedly; what counts for response time is only the first entry. Suppose P0 arrives at time 0, P1 at time 1, and P2 at time 2. Even though P1 arrived at time 1, it cannot jump into the CPU the instant it arrives. If P1 gets its first chance at the CPU at time 4 — and it may not run to completion from there — the response time is:

$R T = (time of first CPU access) - A T$

where $R T$ is the response time and $A T$ is the arrival time.

Worked micro-example. P0 arrives at 0, P1 at 1, P2 at 2. Say P0 runs 0 to 3, then P1 gets its first CPU access at time 3 — not 4; the exact numbers in the lecture were illustrative. Then $R T (P 1) = 3 - 1 = 2$ time units. If P1 is then preempted after 1 unit and only finishes at time 10, its turnaround time is $10 - 1 = 9$ , but its response time stays 2. The response time records only the first touch of the CPU; everything after that is irrelevant to it. Sense-check: a user typing in a terminal cares about when the first character of output appears — measured by response time — not when the whole request completes, so response time is the criterion of interactive systems.

5.3.6 The Optimization Goals

The criteria split into two groups. Out of all of them, two must be maximized: CPU utilization and throughput. The other three — turnaround time, waiting time, and response time — must be minimized. The optimization of scheduling is exactly this: maximize the first pair, minimize the second triple. One useful check applies to non-preemptive scheduling: the waiting time and the response time coincide, since a process that finally gets the CPU also gets its first response at that same moment. Only preemptive scheduling can separate the two numbers.

The professor's rule to remember. The CPU should never sit idle. Scheduling optimization means maximizing the pair (CPU utilization, throughput) and minimizing the triple (turnaround time, waiting time, response time). When asked "what does scheduling optimize?", answer with both groups, not one.

Why "maximize two, minimize three" is a compromise, not a free lunch. The criteria are interdependent and cannot all be optimized simultaneously. Improving response time, for example, usually means switching between processes frequently — which adds scheduling overhead and lowers throughput. The book makes the same point: providing good response time may require an algorithm that switches often, and every switch eats CPU time. In most cases we optimize the average measure, but some systems prefer minimizing the maximum response time to guarantee every user good service. Interactive systems care more about a predictable (low-variance) response time than a fast average one.

Waiting versus response under preemption. The professor's check: under non-preemptive scheduling, waiting time equals response time, because the moment a process finally enters the CPU is also the moment it receives its first response. Preemptive scheduling is the only case where the two diverge — a process can enter the CPU quickly (good response) but be yanked out and made to wait repeatedly (bad waiting time), or the reverse. When you see the two columns of a scheduling table show the same values, you know the scheme was non-preemptive; when they differ, a process was preempted at least once.

5.3.7 Student Questions and Answers

Q: Can you restate the throughput formula? I did not catch it at the end.

A: Throughput is the total number of processes completed divided by the total time taken for all the processes to complete. With five processes finished in 19 time units, the throughput comes out to $5/19$ , about 0.26 processes per time unit.

Exam note. The formulas are exam staples: turnaround time is completion minus arrival $(T T = C T - A T)$ ; waiting time is turnaround minus burst $(W T = T T - B T)$ ; response time is first CPU access minus arrival; throughput is completed processes divided by total time. Practice reading all four off a Gantt chart, because the next sections derive every table entry from exactly these definitions.

Recap and bridge. The five criteria give the scheduler its goals: keep the CPU busy (utilization), finish work (throughput), and serve processes quickly (turnaround, waiting, response) — with the first two maximized and the last three minimized. Handoff: criteria alone do not say how to order the queue; the scheduling algorithms do, and the next section previews the four core ones.

These criteria are the language of capacity planning in industry. Cloud providers meter throughput (requests per second) and utilization (percentage of allocated CPU) for billing and autoscaling: a Kubernetes cluster scales out when CPU utilization crosses a threshold and scales in when it drops. Database administrators watch response time percentiles (p99) because an average response time hides the users who wait longest. Real-time systems such as aircraft flight-control software treat response time as a hard guarantee: worst-case response must be provably bounded, not merely minimized on average. In all of these, the five criteria from this lecture are the measurement backbone.

5.4 The Scheduling Algorithms at a Glance

5.4.1 The Four Core Algorithms

The criteria tell us what to optimize, but not how. Different scheduling algorithms make different ordering choices, and we look at each one with examples. Four are the important ones: First Come, First Served (FCFS); Shortest Job First (SJF); Priority Scheduling; and Round Robin. A couple of other algorithms exist beyond these four, but these are the frequently used ones, and they are the ones to study in depth.

The map before the journey. Here is where each algorithm stands, one line each — the details and worked examples come in the next sections.

First Come, First Served (FCFS): serve the ready queue strictly in arrival order. Non-preemptive. Simplest, but long first jobs make everyone else wait (the convoy effect).
Shortest Job First (SJF): run the process with the shortest next CPU burst first. Provably optimal on average waiting time — but the burst length must be known or predicted.
Priority Scheduling: every process carries an integer priority; the smallest number runs first. SJF turns out to be a special case of it. Risk: low-priority starvation, cured by aging.
Round Robin: FCFS with a time quantum — each process gets at most one quantum before the CPU rotates to the next. Preemptive; the backbone of interactive and time-sharing systems.

How to compare them. Each algorithm is a different answer to the same ordering question, so the natural comparison is by the criteria of the previous section: average waiting time, turnaround time, response time, and whether the scheme is preemptive. In the worked examples ahead, the same four numbers — completion, turnaround, waiting, response — are computed for every algorithm, which is what makes the trade-offs visible. A preview of the division: FCFS is the baseline everyone beats, SJF is the optimal-but-impractical ideal, priority scheduling is the general framework that contains SJF, and round robin is the fairness mechanism that preemptive systems actually use.

Recap and bridge. The four core algorithms are FCFS, SJF, priority scheduling, and round robin — each a different ordering rule for the ready queue, each studied with the same metrics. Handoff: FCFS first, because it is the simplest and its weaknesses motivate everything that follows.

In practice, real operating systems rarely use one of these four in pure form — but every modern scheduler is built from their ideas. Linux's Completely Fair Scheduler spreads CPU time fairly like round robin, but weighted like priority scheduling; real-time threads in Linux and Windows use strict priority scheduling with aging-like boosts; and batch systems (HPC schedulers such as SLURM) still apply FCFS with SJF-style backfilling — letting a short job jump ahead when it fits a gap, which is exactly the SJF instinct dressed in production clothes.

5.5 First Come, First Served (FCFS)

5.5.1 The Algorithm

The name says it all: the process that comes first gets executed first. FCFS is a non-preemptive algorithm — the process currently in execution must complete before the next one starts, even if other processes are waiting in the queue. A process cannot be voluntarily taken out of the CPU; once it runs, it runs to the end. The ready queue is simply served in the order the processes arrived.

Formal picture. The implementation of FCFS is easily managed with a FIFO (first-in, first-out) queue: when a process enters the ready queue, its PCB is linked onto the tail of the queue; when the CPU is free, it is allocated to the process at the head of the queue, and that process is removed. The code for FCFS is simple to write and understand. The price of that simplicity: the average waiting time under FCFS is often quite long, and it can vary wildly with the order in which processes happen to arrive.

Hook. Imagine standing in a line at a bank where one customer at the front is processing a mortgage while everyone behind waits — and no one is allowed to switch counters. That is FCFS: simple, fair in the "nobody jumps the queue" sense, but utterly at the mercy of the first customer's size.

Exam note: the fixed working method. Whenever a scheduling problem is asked, the working method is fixed. First draw the Gantt chart — a timeline showing which process occupies the CPU at every time unit. Then draw a table showing the completion time, turnaround time, waiting time, and response time for every process, and finally the averages. The Gantt chart comes first because every other value is read off it — if the chart is wrong, every value derived from it is wrong.

5.5.2 Worked Example 1 — Three Processes, No Arrival Times

The first example is the one in the book. Three processes, P1, P2, and P3, with burst times 24, 3, and 3 time units. No arrival times are given. When the problem does not specify arrival times, assume all processes arrived at the same time. The order of arrival is P1, then P2, then P3.

The Gantt chart:

0–24	24–27	27–30
P1	P2	P3

P1 runs for 24 time units, P2 then runs for 3, P3 for 3. The total time is $24 + 3 + 3 = 30$ time units. This example mainly fixes the picture: completion at 24 for P1, at 27 for P2, at 30 for P3, and the same calculation steps that follow apply to every example.

Full table. Because no arrival times are given, every process is treated as arriving at time 0. The completion times are read directly off the Gantt chart: 24, 27, 30.

Turnaround times (completion minus arrival): $24 - 0 = 24$ , $27 - 0 = 27$ , $30 - 0 = 30$ .
Waiting times (turnaround minus burst): $24 - 24 = 0$ , $27 - 3 = 24$ , $30 - 3 = 27$ .
Response times (first CPU access minus arrival): P1 enters at 0, so $0 - 0 = 0$ ; P2 enters at 24, so $24 - 0 = 24$ ; P3 enters at 27, so $27 - 0 = 27$ .

Process	Burst	Completion	Turnaround	Waiting	Response
P1	24	24	24	0	0
P2	3	27	27	24	24
P3	3	30	30	27	27

Averages: turnaround $(24 + 27 + 30) /3 = 81/3 = 27$ time units; waiting $(0 + 24 + 27) /3 = 51/3 = 17$ time units; throughput $3/30 = 0.1$ processes per time unit. Sense-check: P2 and P3 each run for only 3 units, yet they each wait about as long as a whole day's work at 24+ units — the short jobs are punished by the long one, which is exactly the convoy pattern this section warns about.

5.5.3 Worked Example 2 — Arrival Times and an Idle CPU

The second example introduces arrival times: P1 arrives at 0 with burst time 2, P2 arrives at 3 with burst time 1, P3 arrives at 5 with burst time 6.

The Gantt chart:

0–2	2–3	3–4	4–5	5–11
P1	idle	P2	idle	P3

P1 arrived at time 0, so under FCFS it gets the CPU first and takes 2 time units, completing at time 2. Between time 2 and time 3 the CPU has nothing to do: P2 has not arrived yet. The shaded idle region marks this wasted span — no work is done. At time 3, P2 arrives and goes straight into the CPU, executing for 1 time unit until time 4. Again the CPU idles from 4 to 5, because no process is available. At time 5, P3 arrives and runs for 6 time units, completing at 11.

Full table. Completion times: P1 completes at 2, P2 at 4, P3 at 11. Turnaround times (completion minus arrival): $2 - 0 = 2$ , $4 - 3 = 1$ , $11 - 5 = 6$ . Waiting times (turnaround minus burst): $2 - 2 = 0$ , $1 - 1 = 0$ , $6 - 6 = 0$ . Response times: P1 arrived at 0 and entered the CPU at 0, so $0 - 0 = 0$ ; P2 arrived at 3 and entered at 3, so $0$ ; P3 arrived at 5 and entered at 5, so $0$ .

Process	Arrival	Burst	Completion	Turnaround
P1	0	2	2	2
P2	3	1	4	1
P3	5	6	11	6

Averages: turnaround $(2 + 1 + 6) /3 = 9/3 = 3$ time units (milliseconds, in this problem); waiting $0/3 = 0$ ; throughput $3/11 \approx 0.27$ processes per time unit. Sense-check: every process enters the CPU the instant it arrives, so nobody waits and every response time is zero — this is the friendliest possible case for FCFS, and it still wastes 2 idle time units (times 2–3 and 4–5) simply because nothing had arrived yet.

Why idle regions appear. An idle slot in a FCFS Gantt chart is not a scheduling failure of the algorithm — it is the mark of an empty ready queue: the CPU has no one to run. In this example the queue is empty at times 2 and 4 because the next arrival has not happened yet. The lesson: when the problem includes arrival times, always check after each completion whether the next process has actually arrived; the CPU sits idle in the gap if it has not.

5.5.4 Worked Example 3 — Four Processes in Arrival Order

A second FCFS problem makes the method stick. Four processes with arrival and burst times: P1 arrives at 0 with burst 7; P2 arrives at 8 with burst 3; P3 arrives at 3 with burst 4; P4 arrives at 5 with burst 6. The ready queue, in arrival order, is P1, P3, P4, P2.

The Gantt chart:

0–7	7–11	11–17	17–20
P1	P3	P4	P2

P1 came first, so it executes first and takes 7 time units, completing at time 7. By then P3 and P4 are already waiting, so the next in the queue, P3, runs 4 time units, completing at 11. P4 is next, with burst 6, completing at 17. Finally P2, with burst 3, completes at 20. Here the CPU never idles — by the time each process finishes, the next one has already arrived.

Full table. Completion times: P1 = 7, P2 = 20, P3 = 11, P4 = 17. Turnaround times: $7 - 0 = 7$ , $20 - 8 = 12$ , $11 - 3 = 8$ , $17 - 5 = 12$ . Waiting times: $7 - 7 = 0$ , $12 - 3 = 9$ , $8 - 4 = 4$ , $12 - 6 = 6$ . Response times: P1 enters the CPU at 0, response 0; P3 arrived at 3 but enters only at 7, so $7 - 3 = 4$ ; P4 arrived at 5 but enters at 11, so $11 - 5 = 6$ ; P2 arrived at 8 but enters at 17, so $17 - 8 = 9$ .

Process	Arrival	Burst	Completion	Turnaround	Waiting	Response
P1	0	7	7	7	0	0
P2	8	3	20	12	9	9
P3	3	4	11	8	4	4
P4	5	6	17	12	6	6

Averages: turnaround $(7 + 12 + 8 + 12) /4 = 39/4 = 9.75$ time units; waiting $(0 + 9 + 4 + 6) /4 = 19/4 = 4.75$ time units; throughput $4/20 = 0.2$ processes per time unit. Sense-check: the professor's stated totals — 39 for turnaround and 19 for waiting — match the table exactly, confirming the Gantt-chart reading. Note how waiting time and response time match in this non-preemptive algorithm; the values separate only under preemptive scheduling.

Exam note: order changes everything. The average waiting time depends on the arrival order — the same processes arriving in a different order produce a different (usually worse) average, because a process that arrived earlier can still enter the CPU much later. The book's classic illustration: the three processes from Example 1 (bursts 24, 3, 3) arriving in the order P1, P2, P3 give an average waiting time of 17; arriving in the order P2, P3, P1, the same processes give only $(6 + 0 + 3) /3 = 3$ . FCFS is not a strategy — it is a lottery ticket drawn from the arrival order.

5.5.5 The Convoy Effect

The previous example shows the weakness of FCFS. P2 has the shortest burst time of all — only 3 units — yet it arrives last and must wait for longer processes to complete; it enters the CPU only at time 17. That is the convoy effect: short processes queue behind long ones, because the algorithm insists on the first-come order and never lets a short process jump ahead. Waiting time is not reduced, and the CPU can sit idle while I/O-bound processes wait for their long CPU-bound predecessor.

The professor's picture. Imagine one CPU-bound process and many I/O-bound processes in the system. The CPU-bound process grabs the CPU and keeps it. While it runs, all the other processes finish their I/O and move into the ready queue, waiting for the CPU — and while they wait in the ready queue, the I/O devices sit idle. Eventually the CPU-bound process finishes its CPU burst and moves to an I/O device. Now the I/O-bound processes, whose CPU bursts are short, execute quickly and move straight back to the I/O queues. At this point the CPU sits idle — because the only long job is busy doing I/O. The CPU-bound process then returns, grabs the CPU again, and the whole cycle repeats: the I/O processes convoy behind it, and both the CPU and the devices starve in turns.

Pitfalls and scope of FCFS.

Long-average trap: FCFS's average waiting time is often long and highly variable — it depends on the arrival order, not on any property of the jobs themselves.
Convoy effect: one long CPU-bound process forces all short I/O-bound processes to queue behind it, lowering both CPU and device utilization.
Useless for time-sharing: FCFS is non-preemptive, so one long process can hold the CPU for an extended period; it would be disastrous for interactive systems, where each user needs a share of the CPU at regular intervals.
When FCFS is fine: for batch work where jobs are similar in size, the convoy effect is mild, and FCFS's simplicity and starvation-freedom make it a reasonable choice.

Recap and bridge. FCFS serves the queue strictly in arrival order: simple, non-preemptive, and easy to implement — but the convoy effect shows why it is abandoned: short processes wait behind long ones, and the CPU and I/O devices can idle in turns. Handoff: the next algorithm — Shortest Job First — exists precisely to avoid this situation, at the price of needing to know each process's burst length in advance.

The convoy effect is a real production failure mode, not a textbook curiosity. On batch supercomputers and HPC clusters, job schedulers (SLURM, PBS) actively guard against it: a single long simulation job placed at the front of a queue would stall dozens of short science jobs behind it, so these systems use backfilling — allowing short jobs to run in gaps while the big job waits for its reserved resources. The same principle shows up in everyday life: supermarket express lanes exist precisely because letting a one-item customer queue behind a full cart is the FCFS convoy effect, and every store chooses to break the first-come rule to shorten the average wait.

5.6 Shortest Job First (SJF)

5.6.1 The Algorithm and Its Central Difficulty

SJF associates with each process the length of its next CPU burst — the execution time it will need — and uses those lengths to schedule. Whichever process has the shortest burst time gets the next chance at the CPU. In its pure form the algorithm is optimal: it provably gives the minimum average waiting time among non-preemptive approaches. But it has a central difficulty: which process is the shortest? The CPU does not know in advance the burst length of a process that has not run yet. If that length were known in advance, picking the shortest job would be easy; since it is not, one practical solution is to ask the user. This unknown-next-burst problem follows SJF everywhere, and we return to it after the examples.

Hook. What if the scheduler could see into the future and always run the job that needs the least time? The answer is a provable optimum: no other non-preemptive scheme gives a smaller average waiting time. The catch is that the future is invisible — which is why this lecture ends with prediction, the honest substitute for clairvoyance.

The algorithm and why it is optimal. When the CPU is available, it is assigned to the process with the smallest next CPU burst; ties are broken with FCFS. A more accurate name would be shortest-next-CPU-burst scheduling, because the decision uses the next burst, not the process's total life span. The optimality has a simple exchange argument: moving a short process before a long one decreases the waiting time of the short process by the long process's whole burst, while increasing the long process's waiting only by the short one's burst — and since the short process is shorter, the total waiting time goes down. Repeating the swap leads to the minimum average waiting time. The reference text states this as: SJF is provably optimal in that it gives the minimum average waiting time for a given set of processes.

Scope — where the future is unknowable. The central difficulty: at short-term scheduling level there is no way to know the length of the next CPU burst of a process that has not run yet. Three practical responses exist:

Ask the user. For long-term (job) scheduling in a batch system, users submit the process time limit themselves. Users are motivated to estimate accurately: a lower estimate may mean faster response, but an estimate too low causes a time-limit-exceeded error and resubmission. SJF is used frequently in long-term scheduling for this reason.
Predict it. From past bursts of the same process, using the averaging technique developed in 5.6.5.
Use another measure as a stand-in for burst length — which is exactly what priority scheduling does in section 5.7.

The prediction route is the one the lecture develops, because at short-term level there is no user to ask on every switch.

5.6.2 Non-preemptive SJF — Worked Example

Four processes with arrival and burst times: P1 arrives at 0 with burst 8; P2 at 1 with burst 4; P3 at 2 with burst 9; P4 at 3 with burst 5. The version we solve first is non-preemptive: once a process enters the CPU, it must finish, even if a shorter job arrived meanwhile.

The Gantt chart:

0–8	8–12	12–17	17–26
P1	P2	P4	P3

P1 arrives first and, because the scheduling is non-preemptive, runs its full 8 time units. By time 8, P2, P3, and P4 have all arrived, and now we can compare their lengths: P2 is shortest (4), so it runs 8 to 12. Next shortest is P4 (5), running 12 to 17. The longest job, P3 (9), goes last, completing at 26. Note what happened: even though shorter jobs arrived while P1 was running, they could not get the CPU until P1 completed.

Full table. Completion times: P1 = 8, P2 = 12, P3 = 26, P4 = 17. Turnaround times: $8 - 0 = 8$ , $12 - 1 = 11$ , $26 - 2 = 24$ , $17 - 3 = 14$ . Waiting times: $8 - 8 = 0$ , $11 - 4 = 7$ , $24 - 9 = 15$ , $14 - 5 = 9$ . Response times: P1 enters at 0 (response 0); P2 arrived at 1 but enters at 8, so $8 - 1 = 7$ ; P3 arrived at 2 but enters at 17, so $17 - 2 = 15$ ; P4 arrived at 3 but enters at 12, so $12 - 3 = 9$ .

Process	Arrival	Burst	Completion	Turnaround	Waiting	Response
P1	0	8	8	8	0	0
P2	1	4	12	11	7	7
P3	2	9	26	24	15	15
P4	3	5	17	14	9	9

Averages: turnaround $(8 + 11 + 24 + 14) /4 = 57/4 = 14.25$ time units (stated as about 14.2); waiting $(0 + 7 + 15 + 9) /4 = 31/4 = 7.75$ time units; throughput $4/26 \approx 0.154$ processes per time unit. Sense-check: as in all non-preemptive schemes, waiting and response coincide column by column; and the shortest job available at each decision moment (P2 then P4) runs before the long one (P3), which is exactly the SJF rule.

5.6.3 Preemptive SJF (Shortest Remaining Time First) — Worked Example

The preemptive version of SJF is usually called Shortest Remaining Time First (SRTF). The rule changes: if a shorter job arrives while a process is mid-execution, the running process is taken out of the CPU and the shorter job runs. We solve the same problem as before with the same arrival and burst times, so the comparison is fair.

The Gantt chart:

0–1	1–5	5–10	10–17	17–26
P1	P2	P4	P1	P3

At time 0 only P1 exists, so it runs. At time 1, P2 arrives with burst 4; P1 still needs 7 time units, and $4 < 7$ , so P1 is pulled out of the CPU and placed back in the ready queue, and P2 takes over. While P2 runs, P3 arrives at time 2 with burst 9 — longer than P2's remaining time, so P2 continues. At time 3, P4 arrives with burst 5 — again longer than P2's remaining 2 time units, so P2 continues and completes at time 5. Now P1 (7 remaining), P3 (9), and P4 (5) are in the queue. P4 has the least remaining work, so it runs 5 to 10. Between P1 (7) and P3 (9), P1 is shorter, so P1 runs 10 to 17 and completes. P3 runs last, 17 to 26.

Full table. Completion times: P1 = 17, P2 = 5, P3 = 26, P4 = 10. The completion time of a preempted process is its last moment on the CPU, not its first — P2 may have entered and left the ready queue in between, but for the table only the final completion matters. Turnaround times: $17 - 0 = 17$ , $5 - 1 = 4$ , $26 - 2 = 24$ , $10 - 3 = 7$ . Waiting times: $17 - 8 = 9$ , $4 - 4 = 0$ , $24 - 9 = 15$ , $7 - 5 = 2$ . Response times: P1 enters at 0 (0); P2 arrives at 1 and enters at 1, so 0; P3 arrives at 2 and enters at 17, so $17 - 2 = 15$ ; P4 arrives at 3 and enters at 5, so $5 - 3 = 2$ .

Process	Arrival	Burst	Completion	Turnaround	Waiting	Response
P1	0	8	17	17	9	0
P2	1	4	5	4	0	0
P3	2	9	26	24	15	15
P4	3	5	10	7	2	2

Averages: turnaround $(17 + 4 + 24 + 7) /4 = 52/4 = 13$ time units — down from 14.25 in the non-preemptive version; waiting $(9 + 0 + 15 + 2) /4 = 26/4 = 6.5$ time units — also reduced. The reference text confirms this exact example: an average waiting time of 6.5 under preemptive SJF versus 7.75 under non-preemptive SJF. Throughput stays the same: all processes still complete by time 26, so $4/26 \approx 0.154$ , exactly as in the non-preemptive version — throughput depends on the total makespan, which preemption does not change. Sense-check: notice that P1's waiting (9) and response (0) now differ — the preemptive case separates the two measures, because P1 entered the CPU instantly at time 0 but was pulled out at time 1 and had to wait to come back.

5.6.4 Student Questions and Answers

Q: Why is there a break in P1's Gantt chart? P1 was running, and suddenly it stops.

A: That is because of preemption — this is the preemptive version of shortest job first. Even if a process is in the middle of execution, when the next job that arrives is shorter, the previously executing job has to come out. The system takes P1 out of the CPU, voluntarily, and places it back in the ready queue; it has not completed. Then it brings the next process, P2, for execution. P2 needs only 4 time units, which is shorter compared to P1's remaining 7, so P2 runs. While P2 executes, P3 arrives at time 2 with burst 9 — longer compared to P2's remaining time, so P2 is not taken out and continues. At time 3, P4 arrives with burst 5, again longer than P2's remaining time, so P2 continues until it completes at time 5. Among the remaining P1, P3, and P4, P4 is shorter, so it runs 5 to 10; then P1 is shorter than P3, so P1 finishes 10 to 17; P3 runs last. That is why the chart shows P1 in two pieces — it was pulled out at time 1 and brought back at time 10. The rule of thumb behind the whole trace: at every arrival, compare the new process's burst with the remaining time of the running process; preempt only if the newcomer is shorter.

5.6.5 Estimating the Next CPU Burst: Exponential Averaging

The examples assume the scheduler knows every burst length in advance. In reality it does not: we do not know how many processes will arrive, or how long the next process will take. The practical answer is prediction. The scheduler predicts the next CPU burst from the lengths of the previous ones, using exponential averaging. The parameters: $t_{n}$ is the actual (observed) length of the $n$ -th CPU burst; $τ_{n}$ is the predicted length for the $n$ -th burst; $τ_{n + 1}$ is the predicted length for the next burst; and $α$ is a scaling factor, a weight between 0 and 1, usually set to one half.

$τ_{n + 1} = α t_{n} + (1 - α) τ_{n}$

The word "exponential" comes from the recursive character of the formula: the prediction for the next burst is a blend of the most recent actual burst and the previous prediction. The weight $α$ controls which of the two dominates. At the extreme $α = 0$ , the formula collapses to $τ_{n + 1} = τ_{n}$ : the prediction never changes, and the current burst is not taken into account at all. At the extreme $α = 1$ , $τ_{n + 1} = t_{n}$ : the prediction equals the last observed CPU burst, and everything older is forgotten. A histogram of past burst lengths shows the idea: the lengths zigzag, for instance 6, 4, 6, 4, never even. The prediction produced by exponential averaging follows the same pattern, roughly matching the recent past rather than jumping to arbitrary values.

Why the name "exponential". Unroll the recursion to see that every past burst still counts, but with geometrically shrinking weight. Substitute $τ_{n} = α t_{n - 1} + (1 - α) τ_{n - 1}$ into the formula:

$τ_{n + 1} = α t_{n} + (1 - α) τ_{n} = α t_{n} + (1 - α) [α t_{n - 1} + (1 - α) τ_{n - 1}] = α t_{n} + α (1 - α) t_{n - 1} + (1 - α)^{2} α t_{n - 2} + \dots + (1 - α)^{n} τ_{1}$

The weights on $t_{n}, t_{n - 1}, t_{n - 2}, \dots$ are $α, α (1 - α), α (1 - α)^{2}, \dots$ — each older observation gets a smaller weight because $1 - α < 1$ , so the influence of history decays exponentially. The initial value $τ_{1}$ can be a constant or an overall system average.

Worked trace with real numbers. Let $α = \frac{1}{2}$ , initial prediction $τ_{1} = 5$ , and observed bursts $t_{1} = 6, t_{2} = 4, t_{3} = 6, t_{4} = 4$ . Step by step:

$τ_{2} τ_{3} τ_{4} τ_{5} = \frac{1}{2} (6) + \frac{1}{2} (5) = 3 + 2.5 = 5.5 = \frac{1}{2} (4) + \frac{1}{2} (5.5) = 2 + 2.75 = 4.75 = \frac{1}{2} (6) + \frac{1}{2} (4.75) = 3 + 2.375 = 5.375 = \frac{1}{2} (4) + \frac{1}{2} (5.375) = 2 + 2.6875 = 4.6875$

The predictions wander in the same zigzag band as the observations (5.5, 4.75, 5.375, 4.69), never hitting the extremes — they track the recent past with smoothing. Sense-check: with $α = \frac{1}{2}$ the prediction is always the midpoint between the newest observation and the old prediction, so it can never overshoot the observed range by more than half the previous gap. A larger $α$ , say 0.8, would track changes faster (weights 0.8, 0.16, 0.032 on the last three bursts) but would also jitter more after a brief surge; a smaller $α$ reacts slowly but is smoother. This is the same blend-old-and-new idea used in network round-trip-time estimation (TCP), load forecasting, and smoothing stock data.

5.6.6 SJF versus FCFS

The same problem solved under FCFS instead of SJF gives larger numbers: the average turnaround time and the average waiting time both come out higher than under SRTF. That is why SJF is considered somewhat optimal compared to FCFS — it genuinely reduced the turnaround time in our example, and preemption reduced it further. With the same four processes, the SJF family always beats FCFS on the averages.

The same four processes under FCFS, for comparison. FCFS runs P1 (0–8), then P2 (8–12), P3 (12–21), P4 (21–26). Completion times 8, 12, 21, 26; turnaround times 8, 11, 19, 23 (sum 61); waiting times 0, 7, 10, 18 (sum 35). Averages: turnaround $61/4 = 15.25$ , waiting $35/4 = 8.75$ .

Scheme	Avg turnaround	Avg waiting
FCFS	15.25	8.75
Non-preemptive SJF	14.25	7.75
Preemptive SJF (SRTF)	13.00	6.50

Sense-check: each step down the table improves both averages — SJF beats FCFS, and preemption beats non-preemption — while throughput stays $4/26 \approx 0.154$ in all three, because the last process finishes at time 26 under every scheme. The one-liner: SJF wins on the averages; preemption wins even more.

Exam note. Remember the two optimization rules the professor repeats: always maximize CPU utilization and throughput; always minimize turnaround, waiting, and response times. And the Gantt chart must be right — if anything is wrong in the chart, every value derived from it (completion, turnaround, waiting, response) will be wrong.

Pitfalls of SJF.

The unknown-burst problem: SJF assumes burst lengths are known; in a short-term scheduler they must be predicted, and predictions can be wrong — the schedule is only as good as the forecast.
Starvation is possible: a steady supply of short jobs can keep a long job waiting indefinitely (the mirror image of the convoy effect); SJF is not starvation-free.
Tie handling: when two bursts are equal, FCFS breaks the tie — forgetting this can produce a different (wrong) chart.
Reading the Gantt chart under preemption: a process can appear in multiple pieces; the completion time is its last moment on the CPU, not its first, and waiting time is the sum of all its ready-queue stretches.

Recap and bridge. SJF runs the shortest next burst first, is provably optimal on average waiting time, and comes in non-preemptive and preemptive (SRTF) flavors — preemption cutting the averages further in the worked example. Its flaw is clairvoyance, patched by exponential averaging prediction. Handoff: priority scheduling generalizes SJF — the shortest burst is just one possible way to assign a priority number.

SJF-style thinking shows up wherever resources are scarce and sizes are known in advance. Cloud batch schedulers and HPC systems use shortest-job-first or backfilling to minimize average wait. Disk schedulers approximate it by sorting pending requests by position (elevator algorithms) — the shortest "distance" first. And the prediction machinery is everywhere: operating systems estimate process runtimes for load balancing, web servers predict request sizes, and the TCP congestion and timing code performs the same exponential smoothing with the same formula, so every web page you load is tuned by an exponential average.

5.7 Priority Scheduling

5.7.1 The Algorithm

Priority scheduling gives every process a priority as an integer number. The convention: the smallest integer gets the highest priority. A process with priority 0 has the highest priority and executes first; a process with priority 10 has less priority and waits. As with the other algorithms, there are preemptive and non-preemptive versions: in the preemptive version a higher-priority process that arrives takes the CPU away from the running lower-priority one; in the non-preemptive version the running process finishes first.

Formal picture. A priority is associated with each process, and the CPU is allocated to the process with the highest priority; equal-priority processes are scheduled in FCFS order. Priorities are generally drawn from a fixed range of integers, for instance 0 to 7 or 0 to 4095. Be careful with the convention: there is no universal agreement on whether 0 is the highest or the lowest priority — some systems use low numbers for high priority (the convention of this lecture and of the reference text), while others, such as Windows, use high numbers for high priority. Always check which way the problem means it.

Where priorities come from. Priorities can be defined internally or externally. Internally defined priorities are computed from measurable quantities of the process: time limits, memory requirements, the number of open files, or the ratio of average I/O burst to average CPU burst. External priorities are set by criteria outside the operating system: the importance of the process, who is paying for the computation, which department sponsors the work, and other, often administrative, factors. So the same scheduling machinery serves both technical (SJF-style) and business-motivated ordering.

5.7.2 SJF as a Special Case of Priority Scheduling

SJF is really priority scheduling in disguise. When the priority of a process is defined as the inverse of its predicted next CPU burst, the shortest predicted burst gets the highest priority and runs first:

$priority = \frac{1}{predicted next CPU burst}$

Under that definition, SJF itself is a priority scheduling scheme. So the two algorithms share machinery; they differ only in how the priority number is assigned.

The relationship, spelled out. The larger the predicted CPU burst, the smaller the fraction $\frac{1}{predicted burst}$ — hence the lower the priority. The smallest burst produces the largest priority value under the "smallest number wins" convention... but note the subtlety: because the priority here is a fraction between 0 and 1, we say "highest priority" meaning the process with the smallest burst, and the reference text states the same idea as: SJF is simply a priority algorithm where the priority is the inverse of the (predicted) next CPU burst. The two algorithms share the same machinery; the only difference is how the priority number is assigned — by a prediction in SJF, by whatever the system chooses in general priority scheduling.

5.7.3 Starvation and Aging

Priority scheduling has a serious problem: lower-priority processes have to wait. Even if a process has a very small burst time, its low priority number keeps it out of the CPU, and it may wait a very long time. That condition is starvation — a process that never gets the CPU. The remedy is aging: gradually increase the priority of waiting processes. Concretely, give every process a priority number, and after every 15 minutes decrease the priority value of the low-priority processes by one. A process with priority 150 becomes 149 after 15 minutes, 148 after 30, and so on — "increasing the priority" means reducing this number. After a day or two the number has dropped so far that the process automatically has the highest priority in the system and gets the CPU. Aging works to some extent precisely because it guarantees that no process stays starved forever.

Starvation — the professor's warning, with history. Indefinite blocking (starvation) is the classic failure of priority scheduling: in a heavily loaded system, a steady stream of higher-priority processes can prevent a low-priority process from ever getting the CPU. Either the process eventually runs — at 2 a.m. on Sunday when the system is finally lightly loaded — or the system crashes and loses the waiting process. The reference text tells the cautionary tale: when the IBM 7094 at MIT was shut down in 1973, a low-priority process was found that had been submitted in 1967 and had never run — six years of starvation.

Aging, concretely. The professor's rule: every 15 minutes, decrease the priority value of waiting low-priority processes by one — "increasing the priority" means reducing this number, because smaller numbers mean higher priority. A process at priority 150 reaches 0 after $150 \times 15 = 2250$ minutes, about 37.5 hours — "a day or two" — and by then it automatically has the highest priority in the system and gets the CPU. Aging works precisely because it is a guarantee: no process can stay starved forever, because time itself raises its priority. The reference text gives the same recipe with a 127-to-0 range: increasing priority by 1 every 15 minutes ages a priority-127 process to the top in no more than 32 hours.

5.7.4 Non-preemptive Priority — Worked Example

Five processes with arrival, burst, and priority data: P1 arrives at 0, burst 10, priority 3; P2 arrives at 1, burst 1, priority 1; P3 arrives at 2, burst 2, priority 4; P4 arrives at 3, burst 1, priority 5; P5 arrives at 4, burst 5, priority 2. This is the non-preemptive version.

The Gantt chart:

0–10	10–11	11–16	16–18	18–19
P1	P2	P5	P3	P4

P1 arrives first at time 0, so under non-preemptive rules it executes first and runs its full 10 time units — even though its priority (3) is not the best. By time 10 all other processes have arrived, and now priority decides. P2 has priority 1, the smallest value, so it runs for 1 time unit, completing at 11. Among the remaining P3 (priority 4), P4 (5), and P5 (2), P5 has the highest priority and runs 5 time units, completing at 16. P3 (priority 4) runs next, completing at 18, and P4 (priority 5) runs last for 1 time unit, completing at 19.

Full table. Completion times: P1 = 10, P2 = 11, P3 = 18, P4 = 19, P5 = 16. Turnaround times: $10 - 0 = 10$ , $11 - 1 = 10$ , $18 - 2 = 16$ , $19 - 3 = 16$ , $16 - 4 = 12$ . Waiting times: $10 - 10 = 0$ , $10 - 1 = 9$ , $16 - 2 = 14$ , $16 - 1 = 15$ , $12 - 5 = 7$ . Response times: P1 enters at 0 (0); P2 arrives at 1 but enters at 10, so $10 - 1 = 9$ ; P3 arrives at 2 but enters at 16, so $16 - 2 = 14$ ; P4 arrives at 3 but enters at 18, so $18 - 3 = 15$ ; P5 arrives at 4 but enters at 11, so $11 - 4 = 7$ .

Process	Arrival	Burst	Priority	Completion	Turnaround	Waiting	Response
P1	0	10	3	10	10	0	0
P2	1	1	1	11	10	9	9
P3	2	2	4	18	16	14	14
P4	3	1	5	19	16	15	15
P5	4	5	2	16	12	7	7

Averages: turnaround $(10 + 10 + 16 + 16 + 12) /5 = 64/5 = 12.8$ time units; waiting $(0 + 9 + 14 + 15 + 7) /5 = 45/5 = 9$ time units. The professor's stated totals — 64 for turnaround, 45 for waiting — confirm the table exactly. Throughput: 5 processes in 19 time units, so $5/19 \approx 0.26$ processes per time unit. As with all non-preemptive schemes, waiting time and response time coincide column by column. Sense-check: the smallest burst (P2 and P4, both 1 unit) does not automatically win — priority, not length, decides; P4 runs last despite having the smallest burst, exactly the divergence from SJF that this example is built to show.

Exam note. Remember the non-preemptive averages — 12.8 for turnaround and 9 for waiting — because the preemptive version of the same problem is solved next session, and the exam-style comparison between the two sets of numbers is the point. A quiz follows this material; the announcement contains the details.

5.7.5 Preview: Preemptive Priority Scheduling

The preemptive version of priority scheduling is the immediate next step: when a process with a higher priority arrives while a lower-priority process runs, the running process is pulled out and the higher-priority one takes the CPU immediately. The same five-process problem will be reworked under those rules, and the resulting average turnaround time and waiting time compared with the non-preemptive values (12.8 and 9). Throughput stays the same either way, because the total completion time is unchanged.

Thinking ahead — where the preemptive version will bite. Under preemption, P1 will no longer hold the CPU for its full 10 units: P2 arrives at time 1 with priority 1 (higher than P1's 3), so P1 gets yanked out after just 1 unit. The schedule becomes a sequence of priority-driven preemptions, and the averages change — this is precisely the mechanism that can push low-priority processes into starvation without aging. The comparison to remember: non-preemptive gives 12.8 / 9; the preemptive numbers will be different, and preemption generally favors high-priority processes at the expense of everyone else.

Recap and bridge. Priority scheduling orders the ready queue by integer priority — smallest number first — with preemptive and non-preemptive versions; SJF is its special case when priority is the inverse of the predicted burst; and its fatal flaw, starvation, is cured by aging. Handoff: the preemptive version of this exact example is solved next session; and round robin, the fourth core algorithm, provides the time-slicing fairness that preemptive systems need.

Priority scheduling is the backbone of real operating systems. Windows uses priority levels from 0 to 31 (with higher numbers meaning higher priority) for its kernel threads, and boosts a thread's priority temporarily when the user interacts with its window — a burst of aging-like behavior. Linux real-time scheduling (SCHED_FIFO/SCHED_RR) uses fixed priorities from 1 to 99 over the normal scheduler. Embedded automotive systems assign priorities to tasks by safety criticality: the airbag task outranks the entertainment system. And in networking, QoS (quality of service) routers schedule packets by priority so that voice calls leapfrog bulk downloads — the same scheme, applied to data instead of processes, with the same starvation-and-aging dynamics.

Exam Guidance Summary

For any scheduling problem, the fixed procedure is: draw the Gantt chart first, then build a table with the completion time, turnaround time, waiting time, and response time for every process, then compute the averages.
If arrival times are not given, assume all processes arrived at the same time; the example with bursts 24, 3, and 3 shows this.
Remember the formulas: turnaround time is completion time minus arrival time; waiting time is turnaround time minus burst time; response time is the first CPU access minus arrival time; throughput is the number of completed processes divided by the total time taken.
Always maximize CPU utilization and throughput; always minimize turnaround time, waiting time, and response time.
The Gantt chart must be right: if anything is wrong in the chart, every value derived from it — completion, turnaround, waiting, response — will be wrong.
In non-preemptive algorithms the waiting time and response time values coincide; they separate only under preemptive scheduling.
Next session covers preemptive priority scheduling; remember the non-preemptive averages (12.8 for turnaround, 9 for waiting) so the two can be compared.
A quiz follows this material; the announcement contains the details and the deadline.

Exam note: the one-page revision strategy. Re-derive each worked example from scratch with the fixed procedure — Gantt chart, table, averages. The four algorithms covered (FCFS, non-preemptive and preemptive SJF, non-preemptive priority) are differentiated by a single rule each, and the preemptive priority version of the five-process example is the natural next question. If you can reproduce the tables for bursts 24/3/3, 2/1/6, 7/3/4/6, 8/4/9/5, and the five-process priority example, you have the entire examinable surface of this session covered.

Key Industry Applications

Real-world: interactive systems and real-time systems require the CPU to be at least 40% busy; non-interactive systems operate at a much lower level. This rule of thumb guides how aggressively the scheduler should fill idle CPU time.
Real-world: the convoy effect (one CPU-bound process holding up many I/O-bound processes) is a real failure mode of FCFS in systems that mix compute-heavy and I/O-heavy workloads; SJF-style and priority-based policies exist partly to prevent it.
Real-world: exponential averaging is the prediction technique schedulers use when they cannot know a process's future CPU burst length in advance — the same blend-old-and-new idea appears throughout system design.

Where this lecture meets the industry. The three applications above are the visible tips of the scheduling iceberg. Cloud autoscalers and HPC batch schedulers (SLURM, PBS) implement FCFS-with-backfilling to defeat the convoy effect in real queues; Linux's Completely Fair Scheduler and Windows' priority-boosted thread scheduler are priority scheduling with aging-like compensation, protecting interactivity; and exponential averaging is the identical formula used by TCP for round-trip-time estimation — so the concepts in this session are not textbook-only, they are the mechanism of every modern workload scheduler.

OS Lecture 5 notes · CPU Scheduling

Operating Systems· postgraduate· 2026-08-15

Sections Breakdown

1Multiprogramming and the CPU Burst Cycle

Why an operating system keeps several programs in memory and the alternating CPU and I/O burst cycle of every process.

2The Scheduler, Scheduling Decisions, and the Dispatcher

The short term scheduler, the four situations that trigger a scheduling decision, preemptive versus non-preemptive scheduling, and dispatch latency.

3Scheduling Criteria

The five criteria used to judge a scheduler — CPU utilization, throughput, turnaround time, waiting time, and response time — and the optimization goals.

4The Scheduling Algorithms at a Glance

A preview of the four core algorithms: FCFS, SJF, priority scheduling, and round robin.

5First Come, First Served (FCFS)

FCFS with three fully worked Gantt-chart examples and the convoy effect that explains why it is abandoned.

6Shortest Job First (SJF)

The optimal but non-clairvoyant SJF algorithm, non-preemptive and preemptive (SRTF) worked examples, and exponential averaging prediction.

7Priority Scheduling

Integer priorities with the smallest number first, SJF as a special case, starvation, aging, and a non-preemptive worked example.

8Exam Guidance Summary

The professor's exam strategy: the fixed Gantt-chart procedure, the formulas, and the optimization rules.

9Key Industry Applications

Where these scheduling ideas appear in real systems: cloud autoscalers, HPC schedulers, and TCP timing.

Postgraduate students studying Operating Systems

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Multiprogramming and the CPU Burst Cycle

Must-know: Multiprogramming = more than one program in memory at once, so the CPU always has work; a process alternates CPU bursts and I/O bursts; I/O-bound processes have many short CPU bursts, CPU-bound processes have a few long ones.

Top pitfall: Confusing CPU-bound with I/O-bound: an I/O-bound process is not the one that uses the CPU a lot — it is the one that waits for I/O a lot and only needs short CPU bursts.

Self-check: Why does the histogram's peak at the short end keep the CPU busy under multiprogramming?

Connects to: The Scheduler, Scheduling Decisions, and the Dispatcher.

The Scheduler, Scheduling Decisions, and the Dispatcher

Must-know: Four scheduling situations: running→waiting (1) and termination (4) are non-preemptive; running→ready (2) and waiting→ready (3) are preemptive. The scheduler decides, the dispatcher switches, and dispatch latency is the switch overhead.

Top pitfall: Assuming every scheduling situation is a free choice: situations 1 and 4 force a decision; only 2 and 3 give the scheduler real choice, which is what makes a scheme preemptive.

Self-check: Why must the scheduler be careful before preempting a process that is in kernel mode or updating shared data?

Connects to: Multiprogramming and the CPU Burst Cycle; Scheduling Criteria.

Scheduling Criteria

Must-know: Optimization of scheduling = maximize CPU utilization and throughput; minimize turnaround, waiting, and response time. Non-preemptive scheduling makes waiting equal response; only preemption separates them.

$T T = C T - A T$ $W T = T T - B T$ $R T = (first CPU access) - A T$ $Throughput = \frac{processes completed}{total time}$

Top pitfall: Treating response time as completion time: response time is only the first CPU access minus arrival, and it stays fixed even if the process is later preempted repeatedly.

Self-check: With 5 processes finished in 19 time units, what is the throughput?

Connects to: The Scheduler, Scheduling Decisions, and the Dispatcher; First Come, First Served (FCFS).

The Scheduling Algorithms at a Glance

Must-know: The four core algorithms are FCFS, SJF, Priority Scheduling, and Round Robin; each is compared by average waiting time, turnaround time, response time, and preemptiveness.

Top pitfall: Forgetting that Round Robin is preemptive while FCFS and SJF (as usually taught) are non-preemptive.

Self-check: Name the four core scheduling algorithms.

Connects to: First Come, First Served (FCFS); Shortest Job First (SJF); Priority Scheduling.

First Come, First Served (FCFS)

Must-know: Fixed procedure: draw the Gantt chart first, then the completion/turnaround/waiting/response table, then averages; when arrival times are missing, assume all processes arrived at the same time.

$T T = C T - A T, W T = T T - B T$

Top pitfall: Gantt chart mistakes cascade: if the chart is wrong, every value read off it is wrong; also, average waiting time changes with arrival order.

Self-check: In Example 3 (arrivals 0/8/3/5, bursts 7/3/4/6), why does P2 wait 9 time units although it has the shortest burst?

Connects to: Scheduling Criteria; Shortest Job First (SJF).

Shortest Job First (SJF)

Must-know: SJF is optimal on average waiting time; SRTF preempts when a newcomer's burst is shorter than the running process's remaining time; exponential averaging predicts the next burst via tau_{n+1} = alpha*t_n + (1-alpha)*tau_n with alpha usually 1/2.

$τ_{n + 1} = α t_{n} + (1 - α) τ_{n}$

Top pitfall: Under preemptive SJF, forgetting to compare the newcomer's burst with the running process's remaining time (not its total burst), and reading completion as the first CPU entry rather than the last.

Self-check: With alpha = 1/2, tau_1 = 5 and observed bursts 6, 4, what is tau_3?

Connects to: First Come, First Served (FCFS); Priority Scheduling.

Priority Scheduling

Must-know: Smallest priority number runs first; priority = 1/predicted burst makes SJF a special case; low-priority processes starve and aging fixes this by decreasing the priority value by one every 15 minutes.

$priority = \frac{1}{predicted next CPU burst}$

Top pitfall: Confusing priority with burst length: in the non-preemptive example, P4 has the smallest burst (1) but runs last because its priority number (5) is worst.

Self-check: Why does a priority-150 process eventually reach the highest priority under aging, and after how long?

Connects to: Shortest Job First (SJF); The Scheduling Algorithms at a Glance.

Exam Guidance Summary

Must-know: Draw the Gantt chart first; assume equal arrival times when none are given; formulas: TT=CT-AT, WT=TT-BT, RT=first CPU access minus AT, throughput=completed/total time.

Top pitfall: Skipping the Gantt chart and computing values from memory; every table value must be read off the chart.

Self-check: What are the non-preemptive priority averages to compare against next session?

Connects to: First Come, First Served (FCFS); Shortest Job First (SJF); Priority Scheduling.

Key Industry Applications

Must-know: Interactive/real-time systems need at least 40% CPU utilization; the convoy effect motivates SJF-style policies; exponential averaging is used by schedulers and by TCP for round-trip-time estimation.

Top pitfall: Assuming real systems use the pure textbook algorithms; in practice they combine FCFS backfilling, priority, and round-robin ideas.

Self-check: Where else is the exponential-averaging formula used besides CPU burst prediction?

Connects to: Multiprogramming and the CPU Burst Cycle; First Come, First Served (FCFS); Shortest Job First (SJF).

Previous LectureLecture 04 · Threads and Multithreading

Next LectureLecture 06 · CPU Scheduling

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Process	Arrival	Burst	Priority	Completion	Turnaround	Waiting	Response
P1	0	10	3	10	10	0	0
P2	1	1	1	11	10	9	9
P3	2	2	4	18	16	14	14
P4	3	1	5	19	16	15	15
P5	4	5	2	16	12	7	7

Process	Arrival	Burst	Priority	Completion	Turnaround	Waiting	Response
P1	0	10	3	10	10	0	0
P2	1	1	1	11	10	9	9
P3	2	2	4	18	16	14	14
P4	3	1	5	19	16	15	15
P5	4	5	2	16	12	7	7

5.1 Multiprogramming and the CPU Burst Cycle

5.1.1 What Multiprogramming Means

5.1.2 The CPU and I/O Burst Cycle

5.2 The Scheduler, Scheduling Decisions, and the Dispatcher

5.2.1 The Schedulers

5.2.2 The Four Situations That Trigger Scheduling Decisions

5.2.3 Preemptive vs Non-preemptive Scheduling

5.2.4 The Dispatcher and Dispatch Latency

5.3 Scheduling Criteria

5.3.1 CPU Utilization

5.3.2 Throughput

5.3.3 Turnaround Time

5.3.4 Waiting Time

5.3.5 Response Time

5.3.6 The Optimization Goals

5.3.7 Student Questions and Answers

5.4 The Scheduling Algorithms at a Glance

5.4.1 The Four Core Algorithms

5.5 First Come, First Served (FCFS)

5.5.1 The Algorithm

5.5.2 Worked Example 1 — Three Processes, No Arrival Times

5.5.3 Worked Example 2 — Arrival Times and an Idle CPU

5.5.4 Worked Example 3 — Four Processes in Arrival Order

5.5.5 The Convoy Effect

5.6 Shortest Job First (SJF)

5.6.1 The Algorithm and Its Central Difficulty

5.6.2 Non-preemptive SJF — Worked Example

5.6.3 Preemptive SJF (Shortest Remaining Time First) — Worked Example

5.6.4 Student Questions and Answers

5.6.5 Estimating the Next CPU Burst: Exponential Averaging

5.6.6 SJF versus FCFS

5.7 Priority Scheduling

5.7.1 The Algorithm

5.7.2 SJF as a Special Case of Priority Scheduling

5.7.3 Starvation and Aging

5.7.4 Non-preemptive Priority — Worked Example

5.7.5 Preview: Preemptive Priority Scheduling

Exam Guidance Summary

Key Industry Applications

OS Lecture 5 notes · CPU Scheduling

Sections Breakdown

Exam Revision Notes

Multiprogramming and the CPU Burst Cycle

The Scheduler, Scheduling Decisions, and the Dispatcher

Scheduling Criteria

The Scheduling Algorithms at a Glance

First Come, First Served (FCFS)

Shortest Job First (SJF)

Priority Scheduling

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat

Process	Arrival	Burst	Priority	Completion	Turnaround	Waiting	Response
P1	0	10	3	10	10	0	0
P2	1	1	1	11	10	9	9
P3	2	2	4	18	16	14	14
P4	3	1	5	19	16	15	15
P5	4	5	2	16	12	7	7