cheat sheet

Everything in one place

One-line definitions, comparison tables, formulas, the numbers examiners love, and the questions that keep coming back. Organised by lecture, printable as a PDF.

Open terminal

Introduction to Operating Systems

10 definitions · 3 tables · 0 formulas · 5 exam prompts

Full notes

Definitions in one line

Operating system: Software that manages hardware and software resources and provides common services for programs.
Four components: Hardware, operating system, application programs, users. A compiler is an application program.
Device controller: Owns one device type and a local buffer. Signals completion to the CPU with an interrupt.
Multiprocessor: Several CPUs sharing memory under one OS. Gains: throughput, economy of scale, reliability (graceful degradation).
SMP vs asymmetric: SMP: every CPU does every task (Intel Core, Ryzen). Asymmetric: each CPU has a fixed role (ARM big.LITTLE).
Dual mode: User mode (mode bit 1) for applications, kernel mode (mode bit 0) for privileged instructions.
Multiprogramming: Several jobs in memory at once so the CPU is never idle. Needs CPU scheduling and memory management.
Batch OS: Operator groups similar punch-card jobs and runs them without interaction. High throughput, no responsiveness.
Distributed OS: Autonomous computers with their own CPU and memory cooperating over a network. Network failure stops everything.
Real-time OS: Strict response-time requirements. Hard: no missed deadline (airbag). Soft: occasional lateness tolerated (gaming).

Numbers to remember

4components of a computer system
1 / 0mode bit in user mode / kernel mode
3advantages of multiprocessors: throughput, economy of scale, reliability
5types of OS on the slides: batch, multiprogramming, multiprocessor, distributed, real-time

Compare

Dual mode

Aspect	User mode	Kernel mode
Mode bit	1	0
Privilege	Lower	Higher
Hardware access	Restricted	Unrestricted
Memory access	Limited to own space	Full
Runs	User applications	OS and kernel components
Crash impact	Only that process dies	Whole system can crash
Exception handling	Limited	Comprehensive
Switch in	Return from system call or interrupt	System call, interrupt, or trap

Types of operating system

Type	Key idea	Main advantage	Main disadvantage	Example
Batch	Operator runs batches of similar jobs	High throughput, easy to repeat big work	Hard to debug, one failed job stalls the rest	Payroll, bank statements
Multiprogramming	Several jobs in memory, CPU switches among them	High CPU utilisation	Needs scheduling and memory management	Classic mainframes, every modern OS
Multiprocessor	Several CPUs, shared memory, one OS	Throughput, reliability, cost sharing	Expensive, complex, needs large memory	SMP servers, desktop multicore
Distributed	Independent machines over a network	Scalable, one node failing does not stop others	Network failure stops all communication	Clusters, cloud
Real-time	Guaranteed response time	Maximum device utilisation, fast task switching	Few tasks at once, complex algorithms	Missile control, robots, airbags

SMP vs asymmetric multiprocessing

	Symmetric (SMP)	Asymmetric
Roles	All processors equal, each runs OS and user code	Master processor schedules, others run user code
Scheduling	Each processor self-schedules	Master decides everything
Example	Intel Core, AMD Ryzen	ARM Cortex-A73 + A53 big.LITTLE

Classic exam questions

1Why can a crash in user mode not bring down the OS, while a crash in kernel mode can?
2Differentiate symmetric and asymmetric multiprocessing with one example each.
3List the four core functions of an OS and the five other important activities.
4Hard vs soft real-time systems: definition and two examples of each.
5What does the device controller do when its operation finishes, and why is that mechanism needed?

System Calls and Interrupts

10 definitions · 3 tables · 1 formulas · 5 exam prompts

Full notes

Definitions in one line

System call: The interface between a process and the OS. Invoked through a trap into kernel mode.
API: Library functions that wrap system calls. Three common ones: Win32, POSIX, Java API.
System call table: Indexed by system call number, each entry holds the address of the kernel routine.
Interrupt: A signal that breaks the current sequence of execution. The OS is interrupt driven: it runs only when one arrives.
Hardware interrupt: Raised by a device, asynchronous, can occur at any time (keyboard, timer, disk completion).
Trap: Software interrupt raised intentionally by a program: system call instruction, breakpoint.
Exception: Unplanned interrupt from an error. Fault is recoverable (page fault). Abort is not (divide by zero on the slides).
Maskable interrupt: Can be ignored by setting a bit in the interrupt mask register (IMR). Lower priority. 8085 RST 5.5, 6.5, 7.5.
Non-maskable interrupt: No mask bit, can never be ignored. Highest priority. 8085 TRAP.
Interrupt vector table: One entry per interrupt number holding the handler address. The number indexes the table.

Numbers to remember

3common APIs: Win32, POSIX, Java
6system call categories: process control, file, device, information, communication, protection
RST 5.5 / 6.5 / 7.5maskable interrupts of the 8085
TRAPthe 8085 non-maskable interrupt

Compare

Interrupt, trap, exception

	Hardware interrupt	Trap	Exception
Source	External device	Program, on purpose	Program, by error
Timing	Asynchronous, any time	Synchronous with the instruction	Synchronous with the instruction
Purpose	Device needs attention	Request OS service	Report a fault or abort
Example	Timer tick, keypress, disk done	System call, debugger breakpoint	Page fault, divide by zero

Maskable vs non-maskable

	Maskable	Non-maskable
Can be disabled?	Yes, via IMR bit	No
Priority	Lower	Higher (timers, critical hardware)
Handled when	After the current instruction	Immediately, state pushed on the stack
8085 example	RST 5.5, RST 6.5, RST 7.5	TRAP

Windows vs UNIX system calls

Category	Windows	UNIX
Process control	`CreateProcess()` `ExitProcess()` `WaitForSingleObject()`	`fork()` `exit()` `wait()`
File manipulation	`CreateFile()` `ReadFile()` `WriteFile()` `CloseHandle()`	`open()` `read()` `write()` `close()`
Device manipulation	`SetConsoleMode()` `ReadConsole()` `WriteConsole()`	`ioctl()` `read()` `write()`
Information maintenance	`GetCurrentProcessID()` `SetTimer()` `Sleep()`	`getpid()` `alarm()` `sleep()`
Communication	`CreatePipe()` `CreateFileMapping()` `MapViewOfFile()`	`pipe()` `shmget()` `mmap()`
Protection	`SetFileSecurity()` `InitializeSecurityDescriptor()`	`chmod()` `umask()` `chown()`

Formulas

Interrupt handling sequence
```
pause current instruction -> save context -> index vector table -> run handler -> restore context
```
Priority levels in the interrupt controller decide order when several arrive together.

Classic exam questions

1What is stored in the system call table and how is it indexed?
2Why do programs use an API instead of calling system calls directly?
3Write the system call sequence for copying one file to another.
4Distinguish an interrupt, a trap and an exception with one example each.
5What determines the order when several interrupts arrive at the same time?

OS Design and Structures

9 definitions · 3 tables · 0 formulas · 5 exam prompts

Full notes

Definitions in one line

User goals: Convenient, easy to learn, reliable, safe, fast.
System goals: Easy to design, implement and maintain. Flexible, reliable, error-free, efficient.
Policy vs mechanism: Policy: what will be done. Mechanism: how. Timer is a mechanism, how long to set it is policy.
Simple structure: No clear layering, any part touches any other. MS-DOS. Fast but one bad program crashes everything.
Monolithic: All services in one kernel and one address space. Original UNIX. Fast, but one failure kills all, hard to extend.
Layered: Layer 0 hardware, layer N user interface. Each layer uses only lower ones. Easy to debug, hard to plan, slow across layers.
Microkernel: Only minimal process, memory and IPC in the kernel. Rest as user programs talking via messages. Portable, secure, slower.
Modular: Core kernel plus loadable kernel modules that call each other directly. Linux, Solaris. Slide verdict: best current methodology.
System programs: Convenient environment for development and execution. Six types from file manipulation to communication.

Numbers to remember

5structures: simple, monolithic, layered, microkernel, modular
6types of system programs
layer 0 / layer Nhardware / user interface in the layered approach

Compare

OS structures

Structure	Idea	Advantages	Disadvantages	Example
Simple	No well-defined layers	Simple to develop, superior performance	One bad program breaks the OS, no data hiding	MS-DOS
Monolithic	Everything in one kernel	Simple to design, fast (same address space)	One failed service kills the system, inflexible	Original UNIX
Layered	Stack of layers, each uses the one below	Simple construction and debugging	Careful planning needed, slow through layers	THE, early layered systems
Microkernel	Minimal kernel, services in user mode	Portable, secure, testable, isolated failures	Message passing hurts performance, complex	Mach, QNX, Minix
Modular	Core kernel plus loadable modules	Small kernel, no message passing, modules call directly	Module interfaces must be designed well	Linux, Solaris

Policy vs mechanism

	Policy	Mechanism
Question	What will be done?	How is it done?
Changes	Often, per site or user	Rarely
Example	How long the timer runs for a user	The timer hardware and its interrupt
Why separate	Maximum flexibility when policy changes later

Six types of system programs

Type	Examples
File manipulation	create, delete, copy, rename, print, dump, list
Status information	date, time, free memory or disk, number of users, logs
File modification	text editors, search and transform commands
Programming language support	compilers, assemblers, debuggers, interpreters
Program loading and execution	absolute loaders, relocatable loaders, linkage editors, overlay loaders
Communication	messaging, browsing, email, remote login, file transfer

Classic exam questions

1Distinguish policy from mechanism with the timer example. Why separate them?
2Compare monolithic and microkernel structures: performance, reliability, portability.
3Why is the modular approach described as combining the best of layered and microkernel designs?
4Give the advantages and disadvantages of the layered approach.
5List the six types of system programs with an example of each.

Processes and Operations on Processes

11 definitions · 4 tables · 3 formulas · 6 exam prompts

Full notes

Definitions in one line

Process: A program in execution: code plus current activity (program counter, registers, stack, resources). Active entity.
Program: A passive file of instructions on disk. Becomes a process when loaded into memory.
Process memory: Text (code), data (globals, statics), heap (malloc, grows up), stack (locals, grows down).
PCB: State, program counter, CPU registers, scheduling info, memory info, accounting info, I/O status.
fork(): Copies the caller. Returns 0 to the child, the child PID to the parent, negative on failure. Both continue after the call.
exec(): Replaces the process image with a new program. Same PID and PPID, no new process. Code after a successful exec never runs.
wait(): Parent blocks until a child ends. Returns the child's PID and stores its exit status. Reading the status is reaping.
exit(): Terminates the caller, returns an integer status to the parent. OS frees memory, files, I/O buffers.
Zombie: Exited child not yet reaped by wait(). Holds only a process-table entry, no memory or CPU.
Orphan: Child whose parent exited first. Adopted immediately by init (PID 1).
Cascading termination: Some systems kill all children and grandchildren when a parent exits. UNIX re-parents them to init instead.

Numbers to remember

1PID of init, the root of the process tree and adopter of orphans
0fork() return value in the child
4sections of process memory: text, data, heap, stack
7process states on the slides, including the two suspend states
7children created by if(!fork()){ if(!fork()) fork(); } fork();

Compare

Program vs process

	Program	Process
Nature	Passive	Active
Lives	On disk as an executable	In main memory
Has	Instructions	Program counter, registers, stack, heap, open files
Count	One file	Many processes can run one program

fork() vs exec()

	fork()	exec()
Creates a new process?	Yes, a child	No, replaces the caller
PID	Child gets a new PID	Unchanged (PPID too)
Address space	Copy of the parent, separate	Overwritten with the new program
Return	0 in child, child PID in parent, negative on error	Only returns on failure
After the call	Both run the next instruction	Only the new program runs; old code after exec is skipped
Typical use	Shell spawns a child	Child becomes the command

Seven process states and where they live

State	Present in	Enter from	Leave to
New	Secondary memory	Program initiated	Ready (loaded by long-term scheduler)
Ready	Main memory	New, Run (preempted), Wait (I/O done), Suspend Ready	Run (dispatched), Suspend Ready (swapped out)
Run	Main memory	Ready	Terminate, Wait (I/O), Ready (preempt)
Block / Wait	Main memory	Run (needs I/O or resource)	Ready (event done), Suspend Wait (swapped out)
Suspend Ready	Secondary memory	Ready (memory full), Suspend Wait (I/O done)	Ready (memory available)
Suspend Wait	Secondary memory	Wait (memory full)	Suspend Ready (I/O done)
Terminate	none	Run (exit)

Wait never goes straight to Run. Suspend states exist only because main memory was full.

Zombie vs orphan

	Zombie	Orphan
Who died	The child	The parent
Who is alive	The parent (has not called wait)	The child (still running)
Costs	One process-table entry	Nothing special, re-parented to init
Fix	Parent calls wait()	init reaps it when it exits

Formulas

Processes after n forks
```
2^n processes, 2^n - 1 children
```
Three sequential fork() calls print hello 8 times and create 7 children.
fork() return value
```
child: 0    parent: child PID (> 0)    failure: < 0
```
if (fork() == 0) is the child branch. if (!fork()) means the same thing.
Exit status
```
wait(&status); WIFEXITED(status) ? WEXITSTATUS(status) : signal
```
Only the low 8 bits of the exit code survive: exit(64) gives 64, exit(256) gives 0.

Classic exam questions

1Predict the output of a program with three consecutive fork() calls followed by a printf.
2In pid = fork(); if (pid == 0) ++x; else --x; what does each process print, and why do they not share x?
3How many child processes does if(!fork()){ if(!fork()) fork(); } fork(); create? Draw the tree.
4Why does a printf placed after a successful execv() never run? What is printed if execv fails?
5Define zombie and orphan. Which system call clears a zombie, and who adopts an orphan?
6List the seven fields of a PCB and say which are saved during a context switch.

Process Scheduling

9 definitions · 3 tables · 2 formulas · 5 exam prompts

Full notes

Definitions in one line

Job queue: All processes in the system. The only queue that can hold processes not yet in main memory.
Ready queue: Processes in main memory waiting for the CPU. Linked list of PCBs with a header pointing to first and last.
Device queue: Processes waiting for one particular I/O device. One per device.
Long-term scheduler: Job scheduler. Admits processes into memory. Rare (seconds, minutes), can be slow. Controls the degree of multiprogramming.
Short-term scheduler: CPU scheduler. Picks the next ready process. Runs every few milliseconds, must be fast. Often the only scheduler.
Medium-term scheduler: Swaps processes out to disk and back to reduce the degree of multiprogramming.
I/O bound vs CPU bound: I/O bound: many short CPU bursts. CPU bound: few long bursts. The long-term scheduler wants a good mix.
Context switch: Save the old process state in its PCB, load the new one. Pure overhead. Cost depends on hardware and PCB complexity.
Stack vs queue: Stack is LIFO (push, pop, one end). Queue is FIFO (enqueue at rear, dequeue at front).

Numbers to remember

9%CPU wasted when a 10 ms decision precedes a 100 ms run
12.5%CPU spent scheduling when 25 decisions of 5 ms happen per second
3schedulers: long, short, medium term
3queues: job, ready, device

Compare

The three schedulers

	Long-term	Short-term	Medium-term
Also called	Job scheduler	CPU scheduler	Swapper
Selects	Which jobs enter memory (New to Ready)	Which ready process runs (Ready to Run)	Which process to swap out or in
Frequency	Seconds or minutes	Milliseconds	As memory pressure demands
Speed	Can be slow	Must be very fast	Moderate
Controls	Degree of multiprogramming, process mix	CPU allocation	Reduces degree of multiprogramming
Present in	Batch systems; often absent in time-sharing	Every system	Systems that swap

Scheduling queues

Queue	Holds	Where in memory
Job queue	Every process in the system	May include secondary memory
Ready queue	Processes waiting only for the CPU	Main memory
Device queue	Processes waiting for a specific device	Main memory

What happens after dispatch

Event	Process goes to	Then
Issues I/O request	Device queue (Waiting)	Ready queue when the I/O completes
Creates a child and waits	Waiting	Ready queue when the child terminates
Interrupt or quantum expiry	Ready queue directly	Dispatched again later
Terminates	Removed from all queues	PCB and resources deallocated

Formulas

Scheduling overhead
```
overhead % = decision time / (decision time + run time) x 100
```
10 ms to decide, 100 ms to run: 10/110 = 9% wasted.
Overhead per second
```
overhead % = (decisions x decision time) / total time
```
25 decisions of 5 ms each in 1000 ms: 125/1000 = 12.5%.

Classic exam questions

1Compare the three schedulers on frequency, speed and what they control.
2Why must the short-term scheduler be fast while the long-term scheduler can be slow?
3A scheduler needs 5 ms per decision and makes 25 decisions per second. What fraction of CPU time is overhead?
4Which queue can contain processes that are not in main memory, and why?
5Why is context-switch time called overhead, and what hardware feature reduces it?

CPU Scheduling

10 definitions · 5 tables · 9 formulas · 7 exam prompts

Full notes

Definitions in one line

Dispatcher: Gives the CPU to the chosen process: context switch, switch to user mode, jump to the right instruction.
Non-preemptive: A process keeps the CPU until it terminates or blocks. FCFS, non-preemptive SJF, non-preemptive priority.
Preemptive: A running process can be forced off the CPU (quantum expiry, higher-priority arrival). SRTF, RR, preemptive priority, MLQ, MLFQ.
Criteria: Maximise CPU utilisation and throughput. Minimise turnaround, waiting and response time.
Convoy effect: In FCFS one long burst holds up every short process behind it.
Starvation: A process never gets the CPU because others keep taking priority. Cure: aging.
Time quantum: The RR slice. Large q behaves like FCFS. Small q behaves like processor sharing but multiplies context switches.
MLQ: Fixed subqueues by process property, each with its own algorithm, higher queue first. Lower queues can starve.
MLFQ: MLQ where processes move between queues: heavy CPU users sink, long waiters rise (aging). Windows and macOS.
Exponential averaging: Predicts the next burst from history so SJF can be approximated.

Numbers to remember

32Windows priority levels, 0 to 31
16 to 31Windows soft real-time priorities, need privileges; 0 to 15 normal; 0 reserved for the OS
O(log N)Linux CFS complexity (pick in O(1), reinsert in O(log N))
4macOS MLFQ bands: normal, system high, kernel only, real-time
17 vs 3FCFS average WT for bursts 24, 3, 3 in order P1 P2 P3 vs P2 P3 P1
4 vs 3average WT for the slide set P1=0/7 P2=2/4 P3=4/1 P4=5/4 under SJF vs SRTF
73average WT for RR q=20 with bursts 53, 17, 68, 24
7context switches in the slide MLQ example (P4 TAT 12, P6 TAT 16)

Compare

Scheduling algorithms

Algorithm	Preemptive?	Selection rule	Starvation?	Best for	Weakness
FCFS	No	Earliest arrival, FIFO queue	No	Batch, simplicity	Convoy effect, order-dependent WT, bad for time-sharing
SJF	No	Smallest next CPU burst, FCFS tie-break	Yes (long jobs)	Minimum average WT when all arrive together, long-term scheduling	Burst must be known, cannot run at short-term level
SRTF	Yes	Smallest remaining time, re-checked on every arrival	Yes (long jobs)	Minimum average WT with staggered arrivals	Needs burst estimates, more context switches
Priority	Either	Highest priority (smallest number on the slides)	Yes, fixed by aging	Systems where importance differs	Choosing priorities, indefinite blocking
Round robin	Yes	FIFO with a time quantum q	No	Time-sharing, interactive systems	Long average WT, quantum tuning
MLQ	Yes (between queues)	Highest non-empty queue, its own rule inside	Yes (low queues)	Mixed foreground/background workloads	Permanent assignment, inflexible
MLFQ	Yes	Like MLQ but processes migrate by behaviour	No (aging)	General-purpose OS	Complex, many parameters, overhead

Preemptive vs non-preemptive

	Non-preemptive	Preemptive
CPU released when	Process terminates or blocks	Also on quantum expiry or higher-priority arrival
Response time	Can be poor	Better for interactive work
Overhead	Fewer context switches	More context switches, needs a timer
Shared data	Safe within a burst	Needs synchronisation
Algorithms	FCFS, SJF, priority (NP)	SRTF, RR, priority (P), MLQ, MLFQ

Scheduling criteria

Criterion	Meaning	Goal
CPU utilisation	Fraction of time the CPU is busy	Maximise
Throughput	Processes completed per unit time	Maximise
Turnaround time	Submission to completion	Minimise average
Waiting time	Time spent in the ready queue	Minimise average
Response time	Submission to first response	Minimise, matters most for interactive
Deadlines	Real-time constraints met	Meet all (hard) or most (soft)

MLQ vs MLFQ

	Multilevel queue	Multilevel feedback queue
Queue assignment	Permanent, by property (priority, type, memory)	Dynamic, by observed CPU behaviour
Movement	None	Down when CPU heavy, up when waiting long (aging)
Starvation	Possible in lower queues	Prevented by aging
Complexity	Simpler	Complex, more overhead

Multiprocessor scheduling

	Asymmetric	Symmetric
Who schedules	One master processor	Every processor for itself
Others do	Only user code	Everything
Queues	Master's queue	Common ready queue or private per-CPU queues
Issues	Master is a bottleneck	Locking, shared data, cache coherence

Formulas

Turnaround time
```
TAT = CT - AT
```
Completion minus arrival. Also WT + BT when there is no I/O.
Waiting time
```
WT = TAT - BT
```
Time in the ready queue only.
Response time
```
RT = first CPU allocation - AT
```
Zero for a process that starts the moment it arrives.
CPU utilisation
```
busy time / total time x 100
```
Per core in multiprocessor questions: 12/17 = 70.58%.
Throughput
```
processes completed / total time
```
Exponential averaging
```
tau(n+1) = alpha * t(n) + (1 - alpha) * tau(n),   0 <= alpha <= 1
```
alpha 0.5, tau1 5, bursts 4 8 5 6: tau2 4.5, tau3 6.25, tau4 5.625, tau5 5.8125.
Round robin bound
```
no process waits more than (n - 1) q between turns
```
n processes in the ready queue, quantum q.

Round robin limits

q -> large: FCFS      q -> small: processor sharing at 1/n speed

Priority
```
smallest integer = highest priority (default on the slides)
```
Read the question: one slide example flips it to larger = higher.

Classic exam questions

1Draw the Gantt chart and compute average WT and TAT for FCFS, SJF, SRTF and RR (q given) on a table of arrivals and bursts.
2Explain the convoy effect with the 24, 3, 3 example and show how reordering changes average waiting time.
3Why is SJF optimal, and why can it not be implemented exactly at the short-term level?
4Estimate the next CPU burst with exponential averaging given alpha, tau1 and a list of actual bursts.
5What happens to RR as q grows very large or very small? Discuss the context-switch trade-off.
6MLQ with Q1 SRTF, Q2 FCFS, Q3 RR: draw the Gantt chart, state queue contents at a given time, count context switches.
7Three-core global preemptive priority scheduling: draw per-CPU Gantt charts and compute per-CPU utilisation.

Threads

9 definitions · 4 tables · 1 formulas · 5 exam prompts

Full notes

Definitions in one line

Thread: Basic unit of CPU utilisation, a lightweight process. Own thread ID, PC, registers, stack. Shares code, data, open files.
Heavyweight process: A traditional process with a single thread of control.
Benefits: Responsiveness, resource sharing, economy, utilisation of multiprocessors.
User-level thread: Managed by a library in user space. Kernel unaware. Fast, portable, but one blocking call blocks the whole process.
Kernel-level thread: Managed by the kernel. Slower to create and switch, but blocking one thread does not block the others and they can use several CPUs.
Many-to-one: Many user threads on one kernel thread. Efficient, but no parallelism and a blocking call blocks all. Green Threads.
One-to-one: Each user thread has a kernel thread. Parallelism and non-blocking, but kernel-thread overhead. Windows, Linux.
Many-to-many: User threads multiplexed onto a smaller or equal number of kernel threads. Avoids both shortcomings. IRIX, HP-UX, Solaris 8.
Two-level: Many-to-many plus the option to bind a user thread to one kernel thread.

Numbers to remember

4benefits of threads: responsiveness, resource sharing, economy, multiprocessor utilisation
3 + 1models: many-to-one, one-to-one, many-to-many, plus the two-level variant
2maximum concurrent user threads on 2 cores in the two-level exam question

Compare

Process vs thread

	Process	Thread
Address space	Own	Shared with sibling threads
Owns	Code, data, heap, files, PCB	Thread ID, PC, registers, stack
Creation cost	High (memory, resources)	Low
Context switch	Slow, changes address space	Fast, no address-space change
Communication	Shared memory or message passing, set up explicitly	Shared memory by default
Isolation	A crash is contained	One thread can corrupt the others

User-level vs kernel-level threads

	User-level threads	Kernel-level threads
Managed by	Thread library in user space	The kernel
Kernel aware?	No	Yes
Create and switch	Fast, no mode switch	Slower, needs mode switch
Blocking system call	Blocks the entire process	Blocks only that thread
Multiprocessor use	Cannot run in parallel	Threads on different CPUs
Portability	Any OS	OS specific

Multithreading models

Model	Mapping	Blocking call	Parallel on multicore?	Cost	Examples
Many-to-one	N user : 1 kernel	Blocks whole process	No	Lowest	Solaris Green Threads, GNU Portable Threads
One-to-one	1 user : 1 kernel	Blocks one thread	Yes	Kernel thread per user thread	Windows 95/98/NT/2000, OS/2, Linux
Many-to-many	N user : M kernel, M <= N	Blocks one kernel thread	Yes	Moderate	IRIX, HP-UX, Solaris 8
Two-level	Many-to-many plus bound threads	Bound thread behaves 1:1	Yes	Moderate	IRIX, HP-UX, Tru64, Solaris 8 and earlier

Per-thread vs shared

Private to each thread	Shared by all threads of a process
Thread ID, program counter, register set, stack	Code section, data section, heap, open files, signals, other OS resources

Formulas

Threads that can run at once
```
min(cores, kernel threads with runnable work)
```
Two-level example: 5 user threads, 2 bound plus 3 over 2 kernel threads, 2 cores: at most 2 run at once.

Classic exam questions

1What is private to a thread and what is shared? Why does that make thread switching cheaper?
2Why does a blocking system call in a many-to-one system block the whole process?
3Compare user-level and kernel-level threads on creation cost, blocking, and multiprocessor use.
4Which model offers the best balance of concurrency and flexibility, and what problem does it fix?
5Why do modern operating systems prefer kernel-level threads despite their overhead?

Deadlock

11 definitions · 5 tables · 4 formulas · 7 exam prompts

Full notes

Definitions in one line

Deadlock: Each process in a set waits for an event only another process in the set can cause. None can run, release, or be awakened.
Resource use: Request, use, release. If denied: block, continue without it, or fail.
Preemptable resource: Can be taken away safely (CPU, memory page). Non-preemptable cannot (printer mid-job, semaphore). Deadlocks need non-preemptable ones.
Four conditions: Mutual exclusion, hold and wait, no preemption, circular wait. All four must hold at once.
RAG: Processes (circles), resource types (boxes with instance dots). Request edge P to R, assignment edge R to P, claim edge dashed P to R.
Cycle rule: No cycle: no deadlock. Cycle with single instances: deadlock. Cycle with multiple instances: deadlock possible.
Prevention: Deny one of the four conditions in the design. No future knowledge needed, low utilisation.
Avoidance: Processes declare maximum needs. Grant a request only if the result is a safe state.
Safe state: A safe sequence exists in which each process can finish with what is free plus what earlier ones release. Unsafe does not mean deadlocked.
Banker's algorithm: Avoidance for multiple instances. Available, Max, Allocation, Need. Pretend to allocate, run the safety check.
Detection and recovery: Let deadlock happen, find it (wait-for graph or Banker-style detection), then kill, preempt or roll back.

Numbers to remember

4necessary conditions for deadlock
3handling strategies: never enter, detect and recover, ignore
P1, P0, P2safe sequence in the 12 tape drive example (max 10/4/9, allocated 5/2/2, 3 free)
P1, P3, P4, P0, P2safe sequence in the Banker's example with Available (3,3,2)
O(m n^2)detection with multiple instances
O(n^2)cycle search in a wait-for graph

Compare

Prevention vs avoidance

	Deadlock prevention	Deadlock avoidance
Approach	Make one of the four conditions impossible	Grant requests only when the result stays safe
Information needed	None about future requests	Maximum need of every process in advance
When decided	At design time, for all requests	At run time, per request
Utilisation	Low, resources idle while held early	Better, but still conservative
Algorithms	Ordering of resources, request all at start, release on wait	RAG claim-edge algorithm, Banker's algorithm
Cost	Starvation possible, poor throughput	Overhead of the safety check on every request

Four conditions and how prevention attacks each

Condition	Meaning	Prevention	Cost
Mutual exclusion	One process at a time per resource	Cannot be denied for non-sharable resources	Not practical
Hold and wait	Holding one resource while waiting for another	Request all resources before starting, or request only when holding none	Low utilisation, starvation
No preemption	Resources released only voluntarily	If a request cannot be met, release everything held and retry later	Wasted work, restarts
Circular wait	Chain of processes each waiting on the next	Total ordering of resource types, request in increasing order	Programmer discipline, possible inefficiency

Three ways to handle deadlock

Strategy	Idea	Used by
Never enter	Prevention or avoidance	Real-time and safety-critical systems
Enter and recover	Detection algorithm plus recovery	Databases, some servers
Ignore (ostrich)	Pretend deadlocks never happen	Most general-purpose OSes including UNIX

Detection by resource multiplicity

	Single instance per type	Multiple instances per type
Structure	Wait-for graph (RAG with resources removed)	Available, Allocation, Request matrices
Deadlock if	The graph has a cycle	Banker-style pass leaves some process unfinished
Complexity	O(n^2) for cycle detection	O(m n^2)

Recovery methods

Method	What happens	Trade-off
Abort all	Kill every deadlocked process	Simple, loses all their work
Abort one at a time	Kill a victim, re-check, repeat	Less loss, repeated detection runs
Resource preemption	Take a resource from its owner and give it to another	Fine for a printer, bad for a half-written record
Rollback	Restore a victim to a periodic checkpoint	Needs checkpoint files, may repeat work

Formulas

Need matrix

Need[i][j] = Max[i][j] - Allocation[i][j]

Safety algorithm

Work = Available; Finish[] = false
repeat: pick i with Finish[i] = false and Need_i <= Work; Work += Allocation_i; Finish[i] = true
safe iff every Finish[i] = true

The order in which you pick processes is a safe sequence.

Resource-request algorithm

Request_i <= Need_i else error
Request_i <= Available else wait
pretend: Available -= Request; Allocation_i += Request; Need_i -= Request
safe ? grant : restore and wait

Complexities

wait-for graph cycle: O(n^2)      Banker-style detection: O(m n^2)

n processes, m resource types.

Classic exam questions

1State the four necessary conditions and explain how prevention attacks each. Which one cannot be attacked?
2Given a RAG, decide whether deadlock exists. What changes when a resource has multiple instances?
3Given Allocation and Max with Available, compute Need, run the safety algorithm, and give a safe sequence.
4P1 requests (1,0,2). Can it be granted? Then check (3,3,0) by P4 and (0,2,0) by P0.
5Explain why an unsafe state is not necessarily a deadlocked state.
6Compare deadlock prevention and avoidance on information needed and utilisation.
7Describe the recovery options and give one application where killing a process is acceptable and one where it is not.