Operating Systems

How one machine is shared among programs, safely and durably

About this course

How an operating system shares a processor, coordinates concurrent work, manages address spaces and preserves files across failures — processes and scheduling, synchronisation, virtual memory, filesystems, devices and protection.

What you will be able to do

  • Trace processes through system calls and compare scheduling policies by response time
  • Identify race conditions in shared-state code and fix them with locks, condition variables or semaphores
  • Detect a deadlock and prevent it with resource ordering
  • Translate addresses through a page table and simulate page-replacement policies
  • Explain how a filesystem stores files and uses journaling to recover after a crash

What this course covers

  • Interleaved execution and private state
  • Thread vs. process resource ownership
  • Schedule enumeration and the progress grid
  • Disjoint-slot invariant across all schedules
  • Completion dependency and early collection failure
  • Shared-accumulator interference (lost update)
  • Conditions for correct thread cooperation (summary)
  • Four-layer file abstraction
  • Names as directory edges (hard links)
  • Descriptors, open descriptions, and cursor placement
  • Fork and cross-process description sharing
  • Namespace mutation with live handles
  • Read-loop byte accounting and descriptor lifetime
  • Unified identity and byte-accounting audit
  • Overlapping wait and work on one processor
  • Process vs. program and process state model
  • Event-driven scheduling rules and timeline construction
  • Scheduling metrics: utilization, response, and completion
  • Saved context and correct process continuation
  • Preemption via quantum and its effect on short tasks
  • Mechanism vs. policy separation and failure diagnosis
  • Virtual address spaces and physical translation
  • Region tables: boundaries, permissions, and access checks
  • Arena allocation: blocks, padding, and the partition equation
  • External fragmentation and contiguous placement failure
  • Coalescing free extents after block release
  • First-fit vs. best-fit placement policies
  • Object lifetime, stale aliases, and ownership contracts
  • Request life cycle and accounting invariant
  • Completion vs. observation: polling and interrupt policies
  • Blocking vs. asynchronous caller interface
  • Sleep gap and protected wait protocol
  • Buffer lifetime, DMA, and generation tags
  • Descriptor field ordering before publication
  • Synthesis: evidence required for each protocol action
  • Shared invariant for a reservation record
  • Enumerating interleavings of check and commit
  • Race condition in the unprotected decision interval
  • Broken flag doorway vs. atomic acquisition
  • Critical section scope: check and commit must both be inside
  • Common lock identity: all competing callers must use the same lock
  • Mutual exclusion vs. progress and fairness
  • File representation model: inodes, block maps, and allocator
  • Byte-offset to physical-block address translation
  • Storage accounting: data blocks vs. index blocks
  • Allocation failure and the two-resource requirement
  • Ownership invariants and the allocation graph
  • Reconstructing a boundary-crossing read
  • Shrinking a file: releasing data blocks and the index
  • Permission class selection and rights testing
  • Owner administrative authority vs. data access
  • Directory path lookup and search permission
  • Handle-retained authority vs. new open
  • Unlink vs. file-data write: different objects, different authority
  • Namespace views, shared objects, and retained references
  • Unified six-question decision procedure and model boundaries
  • Virtual-to-physical address translation
  • Address splitting and sparse hierarchical page tables
  • TLB operation and fault classification
  • Page fault handling and repair
  • Replacement policies: FIFO, LRU, and OPT
  • Dirty eviction and value preservation
  • Locality, thrashing, and the residency contract
  • Three-column framework: identity, mode, permission
  • Controlled kernel entry vs. ordinary call
  • Complete range validation for memory requests
  • Counting permitted memory slices
  • Process creation vs. image replacement
  • Process lifetime: exit, zombie state, and collection
  • Synthesis: four mechanism distinctions
  • Crash model and persistence assumptions
  • Recovery contract: old-or-new vector invariant
  • Physical redo journal structure and roles
  • Four-phase journaling protocol and the nine crash cuts
  • Idempotent recovery and interrupted recovery runs
  • Three ordering constraints and their failure modes
  • Scope of the journal guarantee: metadata vs. payload
  • The Lost-Notification Gap
  • Atomic Wait: the Condition-Variable Contract
  • Recheck the Predicate After Wake-Up (while, not if)
  • Condition Notifications vs. Semaphore Credits
  • Two-Slot Bounded Queue with Semaphore Credits
  • Intermediate-State Accounting and Reservations
  • Closing Synthesis: Four Distinctions for Correct Waiting
  • Scheduling metrics: response, turnaround, and waiting
  • First-Come First-Served (arrival-order) scheduling
  • Shortest-Job-First and the adjacent-exchange optimality argument
  • Shortest Remaining Time First (preemptive SJF)
  • Round-Robin scheduling and boundary-event ordering
  • Switching cost and the quantum trade-off
  • Starvation under SRTF and limits of average metrics
  • Four prerequisite objects for a read request
  • Source and destination address translation
  • Pre-flight authority checks and short-read behavior
  • Critical-path timeline with running, blocked, and ready states
  • Availability case comparison (2×2 table)
  • Publication ordering and the done-flag contract
  • Volatile vs. durable completion and the crash-cut table
  • Deadlock via circular ownership dependency
  • Deadlock vs. successful schedule distinction
  • Extending cycles: three-worker ring and independent workers
  • Current wait-for graph vs. historical lock-dependency graph
  • Lock-rank ordering as deadlock prevention
  • Resource model with multiple units and reduction analysis
  • Livelock and the limits of retry policies

Syllabus

  1. Processes and Scheduling

    1. L1 · Who Runs When a Program Waits?
    2. L2 · Processes, System Calls, and Protection
    3. L3 · CPU Scheduling and Response Time

  2. Concurrency and Synchronisation

    1. L4 · Threads and Shared State
    2. L5 · Race Conditions and Mutual Exclusion
    3. L6 · Condition Variables and Semaphores
    4. L7 · Deadlocks and Resource Ordering

  3. Memory Management

    1. L8 · Address Spaces and Memory Allocation
    2. L9 · Paging, Page Faults, and Replacement

  4. Files and Durable Storage

    1. L10 · Files, Directories, and Open Handles
    2. L11 · Inside a Filesystem
    3. L12 · Crash Recovery and Journaling

  5. Devices, Protection and the Whole System

    1. L13 · Devices, Interrupts, and Asynchronous I-O
    2. L14 · Permissions and Isolation
    3. L15 · One Request Through the Operating System