Skip to content
System Design

Fundamentals of Concurrency

This guide covers the fundamental concepts, patterns, and challenges of concurrent programming, designed to be a primer for real-world application.

Table of Contents

  1. Core Concepts
  2. Execution Models
  3. The Problem: Shared State & Race Conditions
  4. The Solution: Synchronization Mechanisms
  5. Common Concurrency Issues
  6. Properties of Concurrent Systems
  7. Theoretical Laws
  8. Advanced Topics

Core Concepts

Concurrency vs. Parallelism

  • Concurrency: The ability of a system to run multiple tasks or parts of a program in overlapping time periods. It’s about dealing with many things at once. The tasks can be executed on a single processor core through context switching.

    Analogy: A chef juggling multiple dishes in a kitchen. They switch between chopping vegetables, stirring a pot, and checking the oven, making progress on all dishes over time.

  • Parallelism: The ability of a system to execute multiple tasks simultaneously. This requires hardware with multiple processing units (e.g., a multi-core CPU).

    Analogy: A team of chefs, each working on a different dish at the same time.

Program vs. Process vs. Thread

  • Program: A passive set of instructions and associated data stored on a disk.
  • Process: A program in execution. The OS provides each process with an isolated execution environment, including its own memory space, CPU time, and other resources.
  • Thread: The smallest unit of execution within a process. A process can have multiple threads that share the process’s memory space and resources. This makes them lightweight but also introduces challenges with shared state.

Asynchronous vs. Synchronous Execution

  • Synchronous: Code executes line-by-line. When a function is called, the program waits for it to complete before moving to the next line. It is “blocking.”
  • Asynchronous: A function call does not block the main thread of execution. The work is done in the background, and the program is notified (e.g., via a callback or promise) when it completes.

Execution Models

Multitasking Approaches

  • Cooperative Multitasking: Tasks voluntarily yield control to allow other tasks to run. If a task gets stuck in a long loop, it can freeze the entire system. (Used by Green Threads/Fibers).
  • Preemptive Multitasking: The operating system’s scheduler is in charge of switching between tasks after a certain time slice. This is the dominant model used in modern operating systems (e.g., Windows, macOS, Linux) as it is safer and more robust.

Threading Models

  • Green Threads: User-level threads managed by a runtime library or virtual machine (e.g., early Java) instead of the OS. They are scheduled cooperatively.
  • Fibers: A very lightweight, user-managed model of execution similar to Green Threads. Often used for non-blocking I/O to simplify concurrency.

The Problem: Shared State & Race Conditions

Critical Section

A section of code that accesses a shared resource (e.g., a global variable, a file) that must not be concurrently accessed by more than one thread. Protecting critical sections is the primary goal of most synchronization mechanisms.

Race Condition

A bug that occurs when the output of a system depends on the unpredictable timing or sequence of events. It commonly happens when multiple threads access a critical section without proper synchronization, leading to corrupted data.

Example: Two threads try to increment a shared counter. Thread A reads the value (5), Thread B reads the value (5), Thread A writes its result (6), and Thread B writes its result (6). The counter should be 7, but it is 6 due to the race.

The Solution: Synchronization Mechanisms

Primitives used to control access to critical sections and coordinate threads.

Mutex (Mutual Exclusion Lock)

A lock that ensures only one thread can access a resource at a time. If a thread wants to enter a critical section, it must first acquire the mutex. If the mutex is already held by another thread, it must wait.

  • Reentrant Lock: A special type of mutex that allows a thread to acquire the same lock multiple times without causing a deadlock. The lock must be released as many times as it was acquired.

Semaphore

A signaling mechanism that controls access to a resource by maintaining a counter. A thread can acquire the semaphore (decrementing the counter) or release it (incrementing the counter). If the counter is zero, acquiring threads will block until it’s released.

  • Use Cases: Can be used as a mutex (if the count is 1, it’s a binary semaphore) or to allow a limited number of threads (e.g., N) to access a resource pool.

Monitor

A high-level synchronization construct that combines a mutex with condition variables. It provides a convenient way to ensure mutual exclusion while allowing threads to wait for specific conditions to become true before proceeding.

Barrier

A synchronization point. Threads in a group must all wait at a barrier until every thread has reached it. Once all threads have arrived, they can all proceed.

Comparison

  • Semaphore vs. Mutex: A mutex is for mutual exclusion (locking a resource). A semaphore is for signaling or controlling access to a pool of resources. A thread that acquires a mutex is the only one that can release it. With a semaphore, any thread can signal (release) it.
  • Semaphore vs. Monitor: A semaphore is a lower-level primitive based on a counter. A monitor is a higher-level language construct that bundles locking and waiting into a single object, which is generally safer and easier to use.

Common Concurrency Issues

Deadlock

A situation where two or more threads are blocked forever, each waiting for a resource held by another thread in the cycle.

The Four Conditions for Deadlock:

  1. Mutual Exclusion: At least one resource must be held in a non-sharable mode.
  2. Hold and Wait: A thread holds at least one resource and is waiting to acquire additional resources held by other threads.
  3. No Preemption: A resource can only be released voluntarily by the thread holding it.
  4. Circular Wait: A set of waiting threads {T1, T2, …} exists such that T1 is waiting for a resource held by T2, T2 is waiting for T3, and so on, with the last thread waiting for a resource held by T1.

LiveLock

A situation where two or more threads are actively trying to resolve a deadlock but are unable to make progress. They are busy changing states but get stuck in a loop of repeated actions.

Analogy: Two people trying to pass each other in a narrow hallway. They both step to the same side, then both step to the other side, and so on, forever.

Starvation

A situation where a thread is perpetually denied the resources it needs to make progress because other threads (often higher-priority ones) are consistently scheduled instead.

Other Issues

  • Priority Inversion: A high-priority task is indirectly preempted by a lower-priority task, which holds a resource the high-priority task needs.
  • Missed Signals: A signal (e.g., from a condition variable) is sent before a thread is in the waiting state, causing the signal to be lost and the thread to wait forever.
  • Spurious Wakeups: A thread is woken up from a waiting state even though the condition it was waiting for is not true. Waiting code should always be in a loop (while (!condition) { wait(); }).
  • ABA Problem: A problem in lock-free data structures where a location is read twice, has the same value both times, but was modified in between. This can lead to incorrect assumptions.

Properties of Concurrent Systems

Liveness

A set of properties ensuring that a concurrent system continues to make forward progress. It answers the question, “Will something good eventually happen?”

Thread Safety

A piece of code is thread-safe if it functions correctly when accessed by multiple threads simultaneously, without causing race conditions or data corruption.

  • Immutability: A powerful strategy for achieving thread safety. If an object cannot be modified after it’s created, it can be safely shared among any number of threads without synchronization.
  • Atomicity: An operation is atomic if it completes in a single, indivisible step from the perspective of other threads. Atomic operations are crucial for lock-free programming.

Theoretical Laws

  • Amdahl’s Law: Predicts the maximum theoretical speedup of a task when only a part of it can be parallelized. It highlights that the serial portion of a task becomes the ultimate bottleneck.
  • Gustafson’s Law: An alternative perspective that argues as you add more processors, the problem size can also scale up, meaning the parallel portion of the work grows, and the serial bottleneck becomes less significant.
  • Moore’s Law: The observation that the number of transistors on a microchip doubles approximately every two years. Its slowing has been a major driver for the shift towards multi-core processors and concurrent programming.

Advanced Topics

  • Lock-Free Programming: Designing algorithms that avoid using locks by relying on atomic “compare-and-swap” (CAS) operations. This can reduce contention and improve performance but is significantly more complex to implement correctly.
  • Wait-Free Algorithms: A stricter guarantee than lock-free. A wait-free algorithm ensures that every thread will complete its operation in a finite number of steps, regardless of the speed or state of other threads.
  • Transactional Memory: A concurrency control mechanism that groups a series of memory operations into a single atomic “transaction.” The system ensures the transaction either completes fully or has no effect, simplifying synchronization for the programmer.