Multitasking and resource allocation

You can stream music, edit a document and download a file at the same time, while dozens of background services run unseen. This is multitasking, and making it work, and keeping it working, is one of the operating system's hardest jobs. This section brings together the ideas from A1.3.2 and A1.3.3 and looks at what goes wrong when many processes compete for the same things.

On one core only one process runs at a time. The OS creates the effect of many by giving each a short turn and switching between them hundreds of times a second. Each switch is a context switch: the running process's registers and program counter are saved in its record in the process table, and the next process's are loaded. On a multi-core CPU several processes really do run at once, one per core, and the scheduler also decides which core each one uses.

Multitasking is about processes, each with its own memory. Multithreading is the same idea inside one process: several threads (A1.3.2) share the process's memory and run concurrently. Sharing memory makes threads cheap to create and switch between, but it is also exactly why the contention problems below arise.

The scheduler (A1.3.3) has to balance competing goals: interactive programs need to respond quickly, background jobs need to make progress, important tasks should go first, and yet every process should get a fair share. Context switches make multitasking possible, but each one costs time, so switching too often slows everything down.

• Memory: with paging, memory is split into fixed-size pages placed wherever there is room; with segmentation, a program is split into variable-size logical parts (code, data, stack), each protected separately. Virtual memory extends RAM onto disk.
• Devices: accessed only through drivers and the OS, which queues requests so two programs do not use a device in a conflicting way.
• Files: the file system controls who may open a file and stops two programs writing to it at once.
• Limits: the OS monitors how much CPU, memory and disk each process uses and can cap it (a quota), so one runaway process cannot bring the system down.

Contention happens when several processes want the same resource at the same moment and it can only serve one. If two processes write to the same file at once, their data can be interleaved and corrupted.

Shared data has the same problem in a subtler form. Two threads (or two processes sharing data) each add 1 to a shared counter that holds 5. Each reads 5, each adds 1, each writes 6: one update is lost, and the counter says 6 when it should say 7. The result depends on the exact timing of the two processes, which is why this is called a race condition, and why it is so hard to find: it may happen once in a million runs. The cure is mutual exclusion: only one process at a time may be in the code that uses the shared resource (its critical section).

A lock (mutex) is the simplest tool: a process must take the lock before using the resource and give it back afterwards; anyone else who wants it waits. A semaphore generalises this to a pool of identical resources. It is a counter: taking a resource decreases it, releasing one increases it, and at zero a process must wait. Taking and releasing are each done in one indivisible step, so two processes can never both see the last free resource. A binary semaphore can only be 0 or 1 and behaves exactly like a lock; a counting semaphore starts at the number of resources. Here is a counting semaphore guarding three database connections:

A readers–writer lock relaxes the rule where it is safe to: any number of processes may read a resource at once, because reading changes nothing, but a writer must have it to itself. Higher-level tools such as monitors wrap the shared data and the code that uses it together, so the lock is taken and released automatically, and let a process wait inside until some condition is true (“the queue is not empty”).

Badly managed contention causes its own problems:

• Starvation: a process never gets the resource because others always get there first.
• Priority inversion: a high-priority process needs a lock held by a low-priority process, which itself cannot run because medium-priority work keeps pre-empting it. The urgent process is stuck behind the least urgent. (A fix: temporarily raise the lock holder's priority.)
• Livelock: processes keep reacting to each other (each politely backing off and retrying) so they stay busy but never make progress.
• Thrashing: too many processes for the RAM, so pages are swapped in and out constantly and almost no real work gets done.

Deadlock is the worst case: a group of processes each holding something another one needs, all waiting in a cycle. Nobody can continue, and nobody will let go. It needs four things at once: resources that only one process can use at a time; processes that hold one resource while waiting for another; no way to take a resource away from a process; and a circular chain of waiting. Remove any one and deadlock cannot happen.

The OS can deal with deadlock in four ways: