There is no single agreed definition. The working one: the OS is the program that runs at all times on the computer — the kernel — plus system programs and application programs.

What it does

It sits between the user and the hardware and acts as resource allocator and control program. It has to be fair, efficient, and prevent programs from interfering with each other.

Interrupts — how the OS ever gets control back

Once a user program is running, the CPU is its CPU. The only reason the OS ever runs again is an interrupt.

• Hardware interrupt — a device signals the CPU over the system bus.
• Trap / exception — a software-generated interrupt: an error, or a deliberate system call.
• The CPU stops, saves state, jumps through the interrupt vector to the handler, then resumes.

Dual-mode operation

One mode bit in hardware separates user mode (1) from kernel mode (0). Dangerous instructions are privileged and only run in kernel mode.

This is the single most examined diagram in Chapter 1. Without hardware support for two modes, no protection is possible at all.

Storage hierarchy

registers → cache → main memory → SSD → hard disk → tape. Going down: bigger, slower, cheaper, and more persistent. Volatile above the disk line, non-volatile below.

Multiprogramming and multitasking

Multiprogramming keeps several jobs in memory so the CPU always has something to run — when one waits for I/O, another gets the CPU. Multitasking (time sharing) switches so frequently that users can interact with each job. That switching requires CPU scheduling (Ch 5) and, if memory is short, swapping or virtual memory.

Services, in two groups

• Helpful to the user: user interface, program execution, I/O operations, file-system manipulation, communications, error detection.
• Efficient operation of the system itself: resource allocation, logging/accounting, protection and security.

System calls — the only door into the kernel

Programs almost never issue system calls directly; they call an API (Win32, POSIX, the Java API) and the run-time library issues the call. Each call has a number; the OS keeps a system-call table indexed by that number.

Three ways to pass parameters: in registers; in a block/table in memory with the address in a register; or pushed on the stack. Registers are fastest but there may be more parameters than registers.

Four kernel structures — know the trade-off

Real systems are hybrid: Linux is monolithic plus modules; macOS and iOS layer a hybrid Mach/BSD kernel; Windows is mostly monolithic with a microkernel heritage.

A process is a program in execution. The program is passive — a file on disk. The process is active, with a program counter and resources.

The four parts of a process in memory

Five states

Only one process is running per CPU core at any instant. Many can be ready, many can be waiting.

The PCB — the process's identity card

The Process Control Block stores everything needed to restart a process: state, program counter, CPU registers, scheduling information, memory-management information, accounting information, I/O status.

Creating and ending processes

In UNIX, fork() makes a copy of the parent and returns 0 to the child and the child's pid to the parent. Usually the child then calls exec() to replace its image with a new program, while the parent may wait().

• Zombie — the process has terminated but the parent has not yet called wait().
• Orphan — the parent terminated first; init/systemd adopts it.

Interprocess communication — two models

The producer–consumer problem is the standard shared-memory example, and it walks straight into Chapter 6 — an unsynchronised bounded buffer has a race condition.

A thread is the unit of CPU use. Threads of one process share text, data, heap and open files, but each has its own thread ID, program counter, register set and stack.

Four benefits

• Responsiveness — the UI keeps running while another thread blocks.
• Resource sharing — free, because they share by default.
• Economy — creating a thread is far cheaper than creating a process.
• Scalability — a multithreaded process can genuinely run in parallel on multiple cores.

Concurrency ≠ parallelism

Concurrency = making progress on more than one task. Parallelism = actually performing more than one at the same instant. A single core can be concurrent but never parallel.

Amdahl's Law — the ceiling on what more cores can buy you, where S is the strictly serial fraction:

If 25% of the work is serial, then even with infinite cores the speedup can never exceed 4×. Serial fraction, not core count, is the limit.

Multithreading models

Implicit threading

Concurrency is hard, so hand it to a library: thread pools, fork-join, OpenMP, Grand Central Dispatch. A thread pool also caps the number of threads, which stops a server from being flattened by requests.

Threading issues

• fork() and exec() — does fork duplicate all threads or only the caller? If exec follows immediately, duplicating them all is wasted.
• Signal handling — which thread receives the signal? The one it applies to, every thread, or a dedicated thread.
• Thread cancellation — asynchronous (kill it now; may leave data inconsistent) vs deferred (it checks a cancellation point and exits cleanly). Deferred is safer.
• Thread-local storage — per-thread data, unlike local variables which vanish per call.

The whole chapter rests on one observation: process execution is a CPU–I/O burst cycle. A process computes for a while, then waits for I/O, and repeats. The burst distribution is what scheduling exploits — there are many short bursts and few long ones.

When does the scheduler run?

Four moments. A process:

1. switches from running → waiting (e.g. an I/O request)
2. switches from running → ready (an interrupt)
3. switches from waiting → ready (I/O finished)
4. terminates

The dispatcher then does the handover: switch context, switch to user mode, jump to the right location. The time this takes is dispatch latency.

The five criteria — and which way is better

Learn those three lines and most scheduling questions become arithmetic. Note waiting time is not "time before it first runs" — it accumulates every time the process is put back in the ready queue.

The algorithms

• FCFS — first come, first served. Simple, nonpreemptive, and vulnerable to the convoy effect: one long process at the front makes everyone wait. Average waiting time depends heavily on arrival order.
• SJF — shortest job first. Provably optimal for minimum average waiting time. The catch: you cannot know the next burst length, so you predict it by exponential averaging of past bursts.
• SRTF — preemptive SJF. A newly arrived shorter job preempts the running one.
• Round Robin — each process gets a quantum q, then goes to the back of the queue. No process waits more than (n−1)q. Large q degenerates to FCFS; tiny q drowns in context-switch overhead. Typically 10–100 ms.
• Priority — highest priority first; SJF is priority scheduling where the priority is the predicted burst. Risk: starvation of low-priority processes. Fix: ageing — raise priority the longer a process waits.
• Multilevel queue — a separate queue per priority, often by process type. Multilevel feedback queue lets processes move between queues, which is how a real OS separates interactive from CPU-bound work automatically.

Beyond one CPU

Multiprocessor: usually symmetric (SMP), each core self-scheduling from a common queue or its own. Watch for load balancing (push and pull migration) and processor affinity — a process prefers the core whose cache is already warm.

Real-time: soft real-time gives critical processes preference; hard real-time guarantees a deadline. Rate-monotonic scheduling assigns priority by period (shorter period = higher priority); earliest-deadline-first assigns it dynamically.

Concurrent access to shared data can leave it inconsistent. That is a race condition — the outcome depends on the order in which threads happen to run.

Three machine instructions, not one. Interleave two threads' copies of those three and an increment silently disappears. This is why counter++ is not atomic.

The critical-section problem

Each process has a critical section where it touches shared data. A correct solution must satisfy all three:

1. Mutual exclusion — only one process in its critical section at a time.
2. Progress — if no one is in the critical section, someone wanting in must get in; the decision cannot be postponed indefinitely.
3. Bounded waiting — a limit on how many others may enter before a waiting process gets its turn.

Peterson's solution is the classic software-only proof of the idea, using a shared turn and a flag[] array. It satisfies all three — but it is not guaranteed on modern hardware, because processors reorder reads and writes. It is taught for the reasoning, not for use.

Hardware support

• Memory barriers — force all earlier memory changes to become visible before continuing.
• Atomic instructions — test_and_set() and compare_and_swap() do read-modify-write in one uninterruptible step.
• Atomic variables — the usable face of the above, e.g. an integer that increments atomically.

The three tools you must be able to compare

Liveness — three ways to be stuck

• Deadlock — each waits for an event only the other can cause.
• Priority inversion — a high-priority process waits on a lock held by a low-priority one. Fixed by priority inheritance.
• Starvation — a process waits forever on a semaphore queue.

Three classical problems. They exist to test any newly proposed synchronisation scheme — if your primitive cannot express these cleanly, it is not good enough.

1 · Bounded buffer (producer–consumer)

Producers add to a buffer of n slots, consumers remove. Three semaphores:

The producer waits on empty and signals full; the consumer does the reverse. Order matters: take mutex after the counting semaphore, never before, or you deadlock holding the lock.

2 · Readers–writers

Many readers may read at once; a writer needs exclusive access. The variants differ in who gets preference:

• First variant — readers preferred. No reader waits unless a writer already holds it → writers can starve.
• Second variant — writers preferred. A waiting writer blocks new readers → readers can starve.

Some systems provide this directly as a reader–writer lock.

3 · Dining philosophers

Five philosophers, five chopsticks, each needs the two beside them. The naive solution — pick up left, then right — deadlocks if all five pick up their left chopstick simultaneously. That is the whole point of the problem, and it is a live demonstration of Chapter 8's four conditions.

Fixes: allow at most four at the table; pick up both chopsticks only if both are free (in a critical section); or make odd philosophers take left-then-right and even ones right-then-left, breaking the circular wait.

A set of processes is deadlocked when every process in the set is waiting for an event that only another process in the set can cause.

The four necessary conditions — all must hold

All four must hold simultaneously — so preventing deadlock means making sure at least one can never happen. In practice, ordering resources to break circular wait is the usable one.

Resource-allocation graph

Processes are circles, resource types are rectangles with a dot per instance. A request edge P→R, an assignment edge R→P.

• No cycle → definitely no deadlock.
• Cycle, one instance per resource type → definitely deadlock.
• Cycle, several instances → possibly deadlock. A cycle alone is not proof.

Four ways to handle it

1. Prevention — structurally forbid one of the four conditions.
2. Avoidance — require processes to declare their maximum claim in advance, then only ever enter safe states. This is the Banker's algorithm.
3. Detection and recovery — let it happen, notice, then recover.
4. Ignore it — pretend deadlocks never occur. What UNIX, Linux and Windows all actually do, on the grounds that they are rare and the cost of prevention is high.

Safe state — the idea behind avoidance

A state is safe if there is a sequence of all processes such that each can obtain its remaining need from what is currently available plus what the earlier processes will release. Then:

Banker's algorithm handles multiple instances per resource type using Available, Max, Allocation and Need, where Need = Max − Allocation. A request is granted only if the resulting state is still safe.

Recovery

Abort processes — all deadlocked ones, or one at a time until the cycle breaks. Or preempt resources, which raises three questions: which victim to choose (cost), how far to roll back, and how to avoid always picking the same victim — starvation.