CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 5 of 6 · 4 min read

Goals

Throughput, utilisation and the trade-offs

Think of it this way. A restaurant owner may want the most meals per hour, the fewest idle cooks, or the shortest wait for each guest. These goals pull in different directions, and the owner must choose. The analogy stops at one point: a restaurant can add cooks, but a scheduler must work with the processors it has.

The measures for the whole system are:

  • Throughput: the number of processes finished per unit of time (the same word as on Level 2, page 7).
  • CPU utilisation: the fraction of time that the processor spends running processes rather than idling. On a busy server, it should be near 100 per cent. On a lightly loaded laptop, a low figure is normal.
  • Fairness: each process gets a reasonable share, and none waits forever.

In plain words: In the example above, the throughput is 4 processes in 18 time units, and the utilisation is 100 per cent, because the processor was never idle between time 0 and 18, and the dispatch time is ignored.

Different users want different goals, as the table shows.

System Main goal Typical measure to lower
Batch computing (payroll, simulation) Finish much work Turnaround time, and high throughput
Interactive desktop Feel quick Response time
Server Serve many requests Throughput with bounded response time
Real-time control Meet deadlines Missed deadlines (page 6)

Some goals conflict. Switching often gives short response times but costs dispatch time, which lowers throughput (page 3). Running the shortest jobs first gives the best average waiting time but can leave long jobs waiting for ever (page 2). A policy is a trade, not a free gain.

CPU utilisation

CPU utilisation is the fraction of elapsed time during which a processor executes a process, instead of being idle, usually given as a percentage.

Example: a processor that runs processes for 90 seconds in a 100-second window has a utilisation of 90 per cent.

Read it as

Policy answers "who runs next". The measures on this page answer "was that a good answer". Every later page picks a policy and then computes these measures for it.

Common mistake

Judging a policy on one workload. A policy that looks best on one table of processes can look worst on another. Page 2 shows this with the order of arrival.

Interview angle

Answer in your head first, then open it.

What is the difference between turnaround time and response time?

Turnaround is arrival to completion. Response is arrival to the first run.

What does the dispatcher do?

It switches the processor to the process the scheduler chose: it saves and loads the context and returns to user mode.

What is preemptive scheduling?

The kernel can take the processor away from a running process.

What is the difference between CPU-bound and I/O-bound?

CPU-bound processes compute for long bursts, and I/O-bound ones wait often.

Why can there be no perfect scheduler?

The goals conflict, for example response time against throughput.

Check yourself: 1. Compute the throughput of the example workload. 2. Which goal matters most on a desktop, and which on a payroll batch? 3. Why does switching more often lower throughput?

Words you will meet

Word Meaning
CPU burst Time a process computes between two waits
I/O burst Time a process waits for input or output
Scheduler Kernel code that picks the next process to run
Dispatcher Kernel code that switches to the chosen process
Ready queue The processes that could run now
Preemptive The kernel may take the processor from a running process
Turnaround time Arrival to completion
Waiting time Time spent ready but not running
Response time Arrival to the first run
Utilisation Fraction of time the processor is busy

Quick notes

  • A CPU burst is the time a process executes on a processor between two waits, that is, from the moment it starts running until it blocks for input or output or ends.
  • Preemptive scheduling is a policy in which the kernel may stop a running process and give the processor to another one before the first has waited or ended, usually on.
  • Turnaround time is the time from a process's arrival to its completion.
  • CPU utilisation is the fraction of elapsed time during which a processor executes a process, instead of being idle, usually given as a percentage.