Multiprogramming, Multitasking, and Time-Sharing

Why one CPU is almost always idle

You already know that a running program is an process, and that the kernel is the building manager handing out the hardware. Now here is the awkward fact that shaped the whole history of operating systems: most of the time, a single program leaves the CPU doing nothing. The moment a program says "read this file from disk" or "wait for a key press," it has to stop and wait, often for millions of CPU cycles. The processor, the most expensive part of the machine, sits idle while a slow device crawls along.

This rhythm of "compute a little, then wait for I/O, then compute again" is so universal it has a name: the CPU–I/O burst cycle. Every program is really a chain of short bursts of calculation separated by long stretches of waiting. A text editor computes for a microsecond, then waits whole seconds for your next keystroke. The insight that launched modern computing was simple: if one program is going to spend all that time waiting, why not let another program use the CPU in the gap?

Multiprogramming: keep several jobs loaded

The first answer was multiprogramming. Instead of loading one job, running it to the end, then loading the next — the old batch way — the OS keeps several jobs resident in memory at once. Whenever the running job stops to wait for I/O, the OS picks another loaded job and gives it the CPU. The goal here is pure efficiency: keep that expensive processor busy as close to 100% of the time as possible. Multiprogramming is about throughput, not about you feeling served quickly.

Picture a single chef (the CPU) with three pots on three burners (three loaded jobs). The chef stirs pot A; pot A now needs to simmer for ten minutes (an I/O wait); rather than stand and watch it, the chef turns to pot B and starts chopping; when B needs to rest, the chef moves to C. No burner heats faster, but the chef is never standing still. That is multiprogramming: not one job finishing sooner, but the machine as a whole getting far more done per hour.

Time-sharing: switch fast enough to fool everyone

Multiprogramming switches only when a job chooses to wait for I/O. That is fine for batch jobs, but it is no good for a person sitting at a terminal: a job doing a long calculation would hog the CPU and freeze everyone else. Time-sharing (also called multitasking) adds the missing ingredient — it switches even when the running program does not want to give up the CPU. The OS hands each program a tiny slice of time, and when that slice runs out, it forcibly takes the CPU back and gives it to someone else.

How does the OS forcibly take the CPU back from a program that is busy computing and not making any system calls? With a hardware alarm clock. Before it lets a program run, the OS arms a timer chip to fire an interrupt after a few milliseconds — think of it as a doorbell set to ring on a schedule. When the timer rings, the CPU drops whatever the program was doing and jumps into the kernel, which now gets to decide who runs next. This is the heartbeat of time-sharing: a tick, a chance to switch, a tick, a chance to switch.

Concurrency is not parallelism

This is the single most important distinction in the whole topic, and beginners get it wrong constantly. Concurrency means several tasks are in progress over the same span of time, making progress in turns — like our one chef juggling three pots. On a machine with a single core, the programs are never truly running at the same instant; the OS just interleaves them so finely that they all advance. Parallelism means several tasks are literally executing at the same instant, which requires more than one core — two chefs in the kitchen, each at their own stove.

So time-sharing on a single-core machine gives you concurrency but not parallelism. You can have ten programs concurrently in progress on one core; you cannot have two of them executing in the same nanosecond. A modern laptop with eight cores can do both at once: it runs eight things in true parallel while time-sharing dozens more concurrently on each core. Concurrency is about dealing with many things; parallelism is about doing many things at once. Keeping them separate in your head will save you endless confusion later.

Round-robin: a fair slice for everyone

The simplest fair way to share time is round-robin scheduling. Line all the ready processes up in a queue. Give the one at the front a fixed slice of CPU time called a time quantum — say 4 milliseconds. When its quantum is used up (the timer interrupt rings), the OS moves it to the back of the line and hands the CPU to the next process. Round and round it goes, like a teacher giving every child in a circle a turn to speak before coming back to the first.

Let us trace three processes P1, P2, P3 that each need 10 ms of CPU, with a 4 ms quantum. P1 runs 0–4 ms, then is bumped to the back with 6 ms left. P2 runs 4–8 ms (6 ms left). P3 runs 8–12 ms (6 ms left). Now back to P1: runs 12–16 ms (2 ms left), P2 16–20 (2 left), P3 20–24 (2 left). Final lap: P1 24–26 (done), P2 26–28 (done), P3 28–30 (done). Nobody waited unbearably long for their first turn — that quick first response is exactly why interactive systems love this scheme.

time (ms):  0    4    8    12   16   20   24   26   28   30
running:   [P1] [P2] [P3] [P1] [P2] [P3] [P1] [P2] [P3]
quantum:    4    4    4    4    4    4    2    2    2
           (P1,P2,P3 each need 10 ms; quantum = 4 ms)

A round-robin schedule of three equal jobs; each row of the queue gets one quantum before yielding to the next.

Choosing the quantum is a balancing act, and it is worth being honest about the trade-off. Make it too large and round-robin degrades back toward letting one job hog the CPU — responsiveness suffers. Make it too small and the CPU spends a wasteful fraction of its time on the switching machinery itself rather than on real work. Which brings us to what that switch actually costs.

The price of switching: the context switch

Every time the OS takes the CPU from one process and gives it to another, it must perform a context switch. A process's "context" is everything the CPU was holding for it: the program counter (which instruction is next), all the register values, and bookkeeping about its memory. To switch, the OS must save the outgoing process's entire context so it can be resumed later exactly where it left off, then load the incoming process's saved context. Think of one student leaving a desk and carefully bookmarking their textbook and pocketing their notes, so the next student can lay out their own — then later the first returns to find their page exactly as they left it.

A trigger fires — either the timer interrupt rings (quantum used up) or the running process makes a system call that must wait. The CPU jumps into the kernel.
The kernel saves the outgoing process's context — program counter, registers, and memory bookkeeping — into that process's record, so its exact state is not lost.
The scheduler picks the next process to run (for round-robin, the one now at the front of the queue).
The kernel loads the chosen process's saved context back into the CPU and switches the CPU to point at that process's memory.
The CPU resumes the chosen process exactly where it last stopped — it never even notices it was ever paused.

Here is the honest catch: a context switch is pure overhead. During those saves and loads, no user program is making progress at all — the machine is busy doing nothing but housekeeping. A switch is fast (often well under a microsecond), but switch thousands of times a second and the cost adds up. That is the real reason the quantum cannot be tiny, and it is why a well-tuned scheduler tries to switch often enough to feel responsive yet rarely enough to keep overhead small. Switching is the tax you pay for the illusion that one CPU is serving everyone at once.