Operating Systems

Subject 2 of 10 · from what an OS does to how disks are scheduled, with the formulas and algorithms that show up on exams.

1. OS Basics

Functions of an operating system

• Multiprogramming: keep the CPU busy by loading several processes into memory. When one blocks on I/O, the CPU switches to another instead of idling.
• Time sharing: give each process short CPU slices so interactive users all feel served at once.
• Resource management: arbitrate CPU, memory, and I/O between competing processes.
• Protection and security: stop processes from interfering with each other or the kernel.

Example: each process spends 80% of its time waiting on I/O (P = 0.8) with 3 processes in memory: utilization = 1 − 0.8³ = 1 − 0.512 ≈ 49%. Add more processes and utilization climbs — until thrashing (chapter 7) ruins it.

Security goals: the CIA triad

Authentication verifies who you are (passwords, biometrics). Authorization decides what you're allowed to do once inside.

Classic security threats

2. Processes & Threads

Program vs process

A program is a passive entity on disk. A process is a program in execution — an active entity with its own address space and system state.

Process memory layout

Process Control Block (PCB)

The OS's file on every process: process ID (PID), parent PID, current state, program counter, CPU register snapshot, scheduling info (priority), accounting info (CPU time used), memory-management info, I/O status, and the list of open files.

Process states

New → Ready → Running → Terminated, with a detour: a running process that waits on I/O goes to Waiting, then back to Ready when the I/O completes. Suspended variants (suspend-ready, suspend-waiting) exist when the OS swaps processes out to disk.

Context switching

Switching the CPU from one process to another: save the old process's registers and program counter into its PCB, load the next process's state. It's pure overhead — the CPU does no useful work during the switch — which is why dispatch latency matters.

Threads

A thread is a lightweight process: it shares the address space, code, data, and open files with its sibling threads, carrying only its own stack, registers, and program counter. Benefits of multithreading: responsiveness (UI stays alive during long work), resource sharing, economy (creating a thread is far cheaper than a process), and scalability across cores.

Multithreading models

Inter-Process Communication (IPC)

• Shared memory: processes read/write a common region. Fast, but they must synchronize access themselves.
• Message passing: send() / receive() primitives. Direct names the other process; indirect goes through a mailbox/port. Synchronous (blocking) vs asynchronous (non-blocking).

3. CPU Scheduling

The short-term scheduler picks which ready process gets the CPU next. The dispatcher performs the actual handoff; dispatch latency is the time a switch takes.

Scheduling criteria

The algorithms

Queues and schedulers

• Job queue — every process in the system. Ready queue — in memory, ready to run. Device queues — waiting on a particular I/O device.
• Long-term scheduler — admission control; sets the degree of multiprogramming. Short-term — the CPU scheduler itself, runs constantly. Medium-term — swapping; moves processes in/out of memory.

4. Process Synchronization

When processes share data, the critical section — the code touching shared state — needs guarding. Any correct solution must provide:

• Mutual exclusion — only one process inside at a time
• Progress — a waiting process can't be blocked forever by processes outside
• Bounded waiting — no starvation; every waiter eventually gets in

Peterson's solution (two processes)

A pure-software solution using a flag[2] array (who wants in) and a turn variable (whose turn it is). It satisfies all three requirements but only works for two processes and assumes atomic loads/stores.

// process i (j is the other)
flag[i] = true;
turn = j;
while (flag[j] && turn == j) ;  // busy wait
// --- critical section ---
flag[i] = false;
// --- remainder ---

Hardware support: Test-and-Set

boolean TestAndSet(boolean *lock) {
    boolean old = *lock;
    *lock = true;      // executed atomically
    return old;
}
// usage: while (TestAndSet(&lock)) ; // critical section; lock = false;

Semaphores

An integer variable touched only through two atomic operations: wait() (P — decrement, block if zero) and signal() (V — increment, wake a waiter).

• Binary semaphore (values 0/1) — behaves like a mutex.
• Counting semaphore — tracks multiple identical resources (e.g. 3 printers free).

Mutex locks vs spinlocks

A mutex is acquire/release around the critical section. A spinlock is a mutex that busy-waits instead of sleeping — wasteful on single-core, but the fastest option for very short critical sections on multicore.

Monitors

A high-level construct: only one process may be active inside a monitor at a time, enforced by the compiler/runtime. Condition variables (wait/signal) let processes sleep inside until some condition holds — the classic bounded-buffer implementation.

Classic synchronization problems

5. Deadlocks

A deadlock is a standstill: each process in a set waits for a resource held by another process in the set, and nobody can move. All four conditions must hold simultaneously:

Resource Allocation Graph (RAG)

Processes are circles, resource types are squares. A request edge P→R means "waiting for"; an assignment edge R→P means "holding". With single-instance resources, a cycle in the graph is a deadlock; with multiple instances, a cycle only means deadlock might exist.

Handling strategies

• Prevention — break one of the four conditions: spooling (breaks mutual exclusion for printers), request-everything-upfront (breaks hold-and-wait), allow preemption, or impose a global resource ordering (breaks circular wait).
• Avoidance — the Banker's algorithm: grant a request only if the system stays in a safe state, i.e. some order (a safe sequence) exists in which every process can still finish. Needs each process's maximum claim upfront. Key relation: Need = Max − Allocation.
• Detection & recovery — let deadlocks happen, find them with a wait-for graph (single-instance) or detection algorithm, then recover by killing processes or preempting resources.

6. Memory Management

The CPU generates logical addresses; RAM speaks physical addresses. The MMU translates between them at runtime, which is what lets every process believe it owns contiguous memory starting at zero.

• Dynamic loading — a routine is loaded only when actually called. Better memory use, but the programmer (or linker) decides what loads when.
• Dynamic linking — linking is postponed to execution time. Shared libraries (.dll, .so) live once in memory and serve every process.

Contiguous allocation

Each process gets one unbroken block of memory. Simple, but suffers external fragmentation — free memory scattered in holes too small to use. Classic placement policies:

Partitioning

• Fixed partitioning — memory split into fixed-size regions. Simple, but wastes space inside each partition (internal fragmentation).
• Variable partitioning — partitions sized to each process. No internal waste, but external fragmentation appears over time; compaction (shuffling everything together) fixes it at a cost.

Paging

Memory is chopped into fixed-size frames; each process is chopped into same-size pages. Pages land in any free frames — no contiguity needed, so external fragmentation disappears. A page table maps page → frame per process.

• Multilevel paging — page the page table itself, so huge address spaces don't need one giant table in RAM.
• Inverted page table — one table for all of physical memory (one entry per frame), with process IDs attached. Smaller, but lookups need hashing.
• Internal fragmentation remains: the last page of a process is rarely full.

Segmentation

Memory is divided by logical meaning — code, data, stack segments of variable size — matching how programmers think. Each segment gets a base + limit in a segment table.

7. Virtual Memory

Virtual memory lets processes use more memory than physically exists: only the pages actually needed live in RAM, the rest wait on disk. Benefits: larger effective address spaces, higher multiprogramming, less I/O per process.

Demand paging

Pages are loaded only on first use — a page fault triggers the load. A valid/invalid bit in the page table marks which pages are resident. Pure demand paging starts with nothing loaded; locality keeps fault rates low after warmup.

Page replacement

When RAM is full and a fault needs a frame, pick a victim page:

Thrashing

When the degree of multiprogramming is too high, processes spend all their time page-faulting instead of executing — CPU utilization collapses even though everyone is "busy". Fixes: reduce multiprogramming, give processes bigger working sets, add RAM. The working-set model tracks each process's current locality to size allocations correctly.

8. File Systems

File concepts and attributes

A file is a named collection of related data on secondary storage. Its metadata: name, type, size, location on disk, protection/permissions, owner, and timestamps.

Allocation methods

Free-space management

• Bit vector — one bit per block. Compact, fast to scan.
• Linked list — free blocks chained together.
• Counting — store (first-free-block, count) pairs for runs of free space.

9. Disk Scheduling

Seek time dominates for random access; rotational delay matters most for sequential access. Example: seek 6 ms + rotational 4.17 ms + transfer 0.5 ms = 10.67 ms per access.

The algorithms

Worked example — requests at tracks 98, 183, 37, 122, 14, 124, 65, 67, head at 53 moving outward: SCAN services 65 → 67 → 98 → 122 → 124 → 183, then reverses to 37 → 14. C-SCAN instead jumps straight back to 0 after 183 and continues 14 → 37. LOOK would reverse at 183 without ever visiting the disk edge.

← Back to all subjects