Skip to content
Kernelpedia

Multitasking

Multitasking is the illusion, maintained by an operating system, that more than one program is running at the same time on hardware that, for any single CPU core, can only ever execute one instruction stream at a given instant. The illusion is produced by rapidly switching which task a core is actually executing, frequently enough that no individual task can distinguish genuine parallelism from being paused and resumed many times per second.

Cooperative versus preemptive

Section titled “Cooperative versus preemptive”

Two fundamentally different models exist for deciding when a switch between tasks happens. Under cooperative multitasking, a running task keeps control of the CPU until it voluntarily relinquishes it, by making a system call that blocks or by explicitly yielding, which means a single task that never voluntarily gives up control can freeze the entire system indefinitely. Under preemptive multitasking, the operating system itself can forcibly interrupt a running task, most commonly through a periodic timer interrupt, without that task’s cooperation or awareness, guaranteeing that every task eventually gets a turn regardless of how any individual task behaves. Essentially every general-purpose operating system in current use is preemptive; cooperative multitasking survives mainly in specific, constrained contexts: some embedded systems, or user-level threading libraries layered on top of an underlying preemptive kernel.

Processes versus threads

Section titled “Processes versus threads”

A process is an independent unit of execution with its own private virtual address space: two processes cannot see each other’s memory except through mechanisms the kernel explicitly provides for that purpose (shared memory, pipes). A thread is a unit of execution that shares its address space with one or more sibling threads belonging to the same process, each with its own execution state (registers, stack) but no memory isolation from the others. Both are, from a scheduler’s perspective, simply things that get a turn on a CPU; the distinction matters primarily for what happens on a context switch between them: switching between two threads of the same process can skip the (comparatively expensive) step of switching the active page tables, since both threads already share the same address space, while switching between processes cannot.

Tracking task state

Section titled “Tracking task state”

Whatever a kernel is switching between, processes or threads, it needs somewhere to record each task’s state while it is not the one currently running: its saved register values, the state of its stack, its virtual address space (for a process), its scheduling priority, and bookkeeping such as whether it is currently runnable, blocked waiting on something, or has already terminated. This record is conventionally called a Process Control Block (PCB), or a task struct, and the full population of these blocks, together with whatever data structure the scheduler uses to select among them, constitutes a kernel’s complete view of everything currently running or waiting to run.

struct task {
    uint64_t saved_rsp;      // stack pointer at the moment this task was last switched out
    uint64_t cr3;            // this task's page table root, if it has its own
    enum { RUNNING, READY, BLOCKED, TERMINATED } state;
    int priority;
    struct task *next;       // linkage into whatever scheduling structure is in use
};

Triggering a switch

Section titled “Triggering a switch”

A preemptive kernel most commonly drives switching decisions from a periodic timer interrupt: a hardware timer firing at a fixed interval, with each firing giving the kernel an opportunity to decide whether the currently running task has used enough of its allotted time and should be switched out in favor of another. A switch can also be triggered outside of this periodic tick: a task blocking on I/O or a lock voluntarily gives up the CPU immediately rather than waiting for the next timer tick, since there is no reason to let it continue occupying a CPU it cannot currently make progress on. Deciding which task to run next, once a switch has been triggered by either path, is the responsibility of the scheduler rather than of the multitasking mechanism itself: multitasking is the capability to switch at all, while scheduling is the policy governing what to switch to.

Implementation notes

Section titled “Implementation notes”

A kernel’s very first task, before any user process exists, is often not created through the same path later tasks are; it is simply whatever code is already running when multitasking infrastructure is initialized, retroactively given a PCB describing its current state so the scheduler can treat it uniformly with tasks created afterward. Bootstrapping this correctly, so the “already running” code and a freshly created task look identical to the scheduler once both exist, is a detail that catches many first implementations by surprise, since every task created after the first one is explicitly constructed with a fresh stack and entry point, while the first one is retrofitted rather than created.

References

Section titled “References”
  1. ^ A. Silberschatz, P. Galvin, and G. Gagne, Operating System Concepts: the standard textbook treatment of process and thread abstractions referenced above.

See also

Section titled “See also”