Overview
When multiple threads execute concurrently and share mutable state, non-deterministic instruction interleavings can corrupt data structure invariants. Synchronization provides hardware and software mechanisms to restrict instruction interleaving, enforce Mutual Exclusion, protect Critical Sections, and prevent Deadlocks.
Module Structure & Subdirectories
1. Fundamentals & Critical Sections
| Note Link | Description | Key Concepts |
|---|---|---|
| Race Conditions & Shared State | Analyzes non-determinism in multithreaded execution, interleaving mechanics, race condition definitions, thread-private stacks vs. thread-shared heaps/globals, and instruction atomicity assumptions. | Race Conditions, Interleaving, Non-Determinism, Shared Memory |
| Critical Sections & Mutual Exclusion | Defines critical sections, mutual exclusion locks, the 4 goals of concurrent algorithm design, and Safety vs. Liveness properties. | Critical Sections, Mutual Exclusion, Progress, Bounded Waiting |
2. Sub-Modules
📁 Synchronization Primitives Subsystem
- Locks: Explores the Lock ADT (
acquire/release), hardware primitives (disable interrupts, atomictest_and_set), spinlocks, and guarded blocking locks. - Semaphores: Details Dijkstra’s non-negative integer primitive, binary vs counting semaphores, internal wait queue implementations, and atomic
wait()/signal()operations. - Condition Variables: Examines memoryless condition variables, Mesa vs Hoare signal semantics, atomic lock-release sleeping (
wait),signal, andbroadcast. - Monitors: Language-level constructs encapsulating shared data and procedures with compiler-enforced implicit mutual exclusion.
📁 Synchronization Patterns Subsystem
- Producer-Consumer Problem: Formulates bounded buffer synchronization, lost wakeup flaws in naive sleep/wake attempts, and solutions using semaphores or condition variables.
- Reader-Writer Problem: Explores concurrent reader / exclusive writer access rules and semaphore-based implementation (
read_count,block_write).
📁 Deadlocks Subsystem
- Deadlock Fundamentals & Coffman Conditions: Formal definitions, Dining Philosophers, the 4 Coffman conditions, and Resource Allocation Graph (RAG) cycle analysis.
- Deadlock Handling Strategies: Evaluations of Ostrich algorithm, Deadlock Prevention (Resource Ordering), Deadlock Avoidance (Banker’s Algorithm), and Detection & Recovery.