Concurrency Concepts

If you've spent any time in software engineering discussions about multithreading, distributed systems, or high-performance computing, you've likely heard the terms concurrency and parallelism used interchangeably. This conflation is one of the most pervasive sources of confusion in computing—and it leads directly to poorly designed systems, subtle bugs, and fundamental misunderstandings about program behavior.

These two concepts, while related, represent fundamentally different ideas. Conflating them is like confusing architecture with construction—one is about structure and design, while the other is about execution and resources. Before we can reason about concurrent programs, synchronization primitives, or threading models, we must establish this distinction with absolute clarity.

Concurrency is about dealing with multiple things at once—not necessarily doing them at the same instant.

More precisely, concurrency is a program structure or compositional property that describes how a system is organized to handle multiple tasks. A concurrent program is one that has been designed and structured to handle multiple tasks, regardless of whether those tasks actually execute simultaneously.

Consider this formal definition:

Concurrency: The composition of independently executing processes or threads, where the program structure allows for tasks to make progress in overlapping time periods, potentially interleaving their execution.

The key insight is that concurrency is fundamentally about structure, design, and logical independence—not about physical simultaneous execution.

The structural nature of concurrency:

When we say a program is concurrent, we're describing its architecture—how it's organized into components that can, in principle, operate independently. Consider a web server:

1. It must handle incoming HTTP requests
2. It must read from databases
3. It must compute responses
4. It must write to logs
5. It must manage session state

A concurrent design structures these as logically independent operations that can interleave. The web server might:

• Accept a new request while a database query is in flight
• Begin computing one response while waiting for disk I/O on another
• Write to the log while a network send is pending

This is concurrency—the ability to handle multiple concerns, the structure that permits interleaving. Whether these operations actually happen in the same physical instant depends on parallelism.

Parallelism is about doing multiple things at the same physical instant.

While concurrency is about program structure, parallelism is about execution. It describes what happens at runtime when multiple computational operations occur simultaneously on multiple physical execution units.

The formal definition:

Parallelism: The simultaneous execution of multiple computations on distinct physical processors or cores, where operations genuinely overlap in time.

Parallelism requires physical resources—multiple CPU cores, multiple machines, or specialized hardware like GPUs. You cannot have parallelism with a single execution unit, no matter how your program is structured.

The execution nature of parallelism:

When we say code runs in parallel, we mean that at some instant t, multiple physical processors are simultaneously executing instructions:

• Core 0 is executing instruction A
• Core 1 is executing instruction B
• Core 2 is executing instruction C

All three are happening at the same time—not interleaved, not time-sliced, but genuinely simultaneous.

Types of parallelism:

1. Data parallelism — The same operation is applied to multiple data elements simultaneously (e.g., applying a filter to each pixel of an image across 1000 GPU cores)

2. Task parallelism — Different tasks or functions execute simultaneously on different processors (e.g., one core handles network I/O while another core processes data)

3. Pipeline parallelism — Different stages of a pipeline execute simultaneously, each processing different data (e.g., CPU instruction pipeline: fetch, decode, execute, writeback)

4. Speculative parallelism — Multiple possible execution paths are computed in parallel until one is confirmed correct (e.g., branch prediction in modern CPUs)

Here lies the critical insight that most developers miss: concurrency and parallelism are orthogonal dimensions. A program can be:

• Concurrent but not parallel — Structured for multiple tasks, but executed on a single core via time-slicing
• Parallel but not concurrent — Multiple identical operations on data, but no compositional structure for independent tasks
• Both concurrent and parallel — Structured for multiple independent tasks that execute simultaneously on multiple cores
• Neither concurrent nor parallel — A single, sequential computation

These are independent properties. Understanding their orthogonality is essential for reasoning about systems.

Quadrant 1: Sequential (Neither Concurrent nor Parallel)

for i in range(1000000):
    result += compute(data[i])

A straightforward loop. One thing happens, then the next. No concurrency (single logical thread of control), no parallelism (single core executing).

Quadrant 2: Data-Parallel (Parallel, Not Concurrent)

// GPU computation: 1000 cores each computing one element
parallel_for i in range(1000000):
    result[i] = compute(data[i])

Thousands of cores execute simultaneously, but there's no compositional structure—no interleaving of independent tasks. It's the same operation replicated, not different composed tasks.

Quadrant 3: Concurrent on Single Core (Concurrent, Not Parallel)

// Single-core web server using async I/O
async def handle_request(req):
    data = await db.query(req)      # Yields to event loop
    result = process(data)           # Runs when data ready
    await response.send(result)      # Yields again

Multiple requests are in-flight (concurrent), but on one core. When one request waits for I/O, another runs. The structure is concurrent; the execution is sequential (time-sliced).

Quadrant 4: Concurrent and Parallel

// Multi-core server: each core runs concurrent tasks
for core in cores:
    spawn_thread(handle_requests_concurrently)

Multiple concurrent task handlers, each using async/await or similar, all running simultaneously on different cores. Both dimensions are present.

Let's develop a visual intuition for the distinction using a timeline representation.

Scenario: We have three tasks (A, B, C) to complete.

Sequential execution (neither concurrent nor parallel):

Time →
Core 1: [====A====][====B====][====C====]

One task runs to completion, then the next begins. Total time = A + B + C.

Concurrent execution on single core (concurrent, not parallel):

Time →
Core 1: [A][B][A][C][B][A][C][B][C]

Tasks interleave. A might run, then yield; B runs briefly; A resumes. From the outside, all three tasks are "in progress" simultaneously, but only one executes at any instant. Total time ≈ A + B + C (with some context-switch overhead).

Parallel execution (parallel, potentially concurrent):

Time →
Core 1: [====A====]
Core 2: [====B====]
Core 3: [====C====]

All three tasks execute simultaneously. Total time = max(A, B, C). This is pure speedup from parallelism.

Another illustration: highways and lanes

• Sequential: A single-lane road. Only one car passes any given point at a time.
• Concurrent: A single-lane road with efficient traffic management. Cars take turns smoothly, interleaving access. Many journeys are "in progress," but only one car occupies any point at once.
• Parallel: A multi-lane highway. Multiple cars pass the same longitudinal point simultaneously, each in their own lane.
• Concurrent + Parallel: Multi-lane highway where each lane handles independently scheduled cars that interleave with others in their lane.

The hardware constraint:

Parallelism is constrained by physical lanes. If you have 4 cores, you can have at most 4 parallel operations. Concurrency has no such hard limit—you can have thousands of concurrent tasks on a single core, limited only by memory and context-switch overhead.

This is why modern systems typically have far more concurrent tasks (goroutines, async tasks, lightweight threads) than physical parallelism (cores). A server might have 8 cores but handle 10,000 concurrent connections.

Understanding this distinction profoundly impacts how you design and optimize systems.

When concurrency matters (regardless of parallelism):

1. I/O-bound workloads — A web server waiting for database responses, file reads, or network calls. The CPU is idle during I/O; concurrency lets it do other work during waits.

2. Responsiveness — A UI application that must remain responsive while doing background work. Concurrency lets the UI thread process events while work happens elsewhere.

3. Simplifying complexity — A system with multiple independent concerns (logging, metrics, request handling) benefits from concurrent structure even on one core.

When parallelism matters:

1. CPU-bound computation — Tasks that use 100% of a CPU (mathematical computation, image processing, encryption). Only parallelism—more cores—reduces wall-clock time.

2. Throughput maximization — When you must process the maximum amount of work per unit time, parallelism multiplies capacity.

3. Latency-critical paths — When even optimal single-threaded code is too slow, parallel decomposition can reduce latency.

Different programming models emphasize different aspects of concurrency and parallelism. Understanding which model targets which dimension helps in selecting the right approach for your problem.

Primarily concurrency-focused models:

1. Async/Await (JavaScript, Python asyncio, C# async) — Structures programs as concurrent tasks that yield at I/O boundaries. Typically runs on a single thread (concurrency without parallelism).

2. Event loops (Node.js, libuv) — A single thread processes events from multiple sources, interleaving handling. Highly concurrent, not parallel.

3. Coroutines (Kotlin, Lua, Go goroutines) — Lightweight concurrent units that can suspend and resume. May or may not involve parallelism depending on the runtime.

Primarily parallelism-focused models:

1. SIMD (Single Instruction, Multiple Data) — Hardware-level parallelism where one instruction operates on multiple data elements simultaneously. Pure parallelism, minimal concurrency.

2. GPU computing (CUDA, OpenCL) — Thousands of threads executing the same operation on different data. Massive parallelism, limited concurrency structure.

3. Parallel loops (OpenMP, parallel streams) — Automatically distributes loop iterations across cores. Parallelism without complex concurrent structure.

Choosing the right model:

• I/O-bound, many connections → Async/await or event loop. You need concurrency to handle many waiting operations; parallelism often provides little benefit.

• CPU-bound, data-independent → Thread pool or parallel loops. You need parallelism to utilize multiple cores; complex concurrency structure adds overhead without benefit.

• Mixed workload → Combination: async I/O with parallel computation offloading. This is the common case for web applications that serve requests (I/O-bound) but also process data (CPU-bound).

• Distributed systems → Actor model or CSP. High concurrency with message isolation prevents shared-state bugs while allowing both concurrency and parallelism.

The distinction between concurrency and parallelism wasn't always as important as it is today. Understanding the historical evolution helps explain why this distinction matters now.

The single-processor era (1950s-1990s):

Early computers had one processor. Operating systems like UNIX introduced time-sharing and processes—pure concurrency without parallelism. The OS rapidly switched between tasks, creating the illusion of simultaneous execution.

In this era, 'concurrent programming' primarily meant dealing with interleaving—ensuring that programs that time-shared a single CPU didn't corrupt each other's state. Parallelism existed only in specialized supercomputing contexts.

The multi-core revolution (2005-present):

When CPU clock speeds hit physical limits around 2005, manufacturers shifted to adding cores. Suddenly, ordinary desktop computers had true parallelism. The distinction between concurrency (structure) and parallelism (execution) became critical.

Programs written for a single-core world—concurrent but not parallel—suddenly ran on parallel hardware. When they weren't designed to exploit parallelism, all those extra cores sat idle. When they were naively parallelized without proper concurrent design, they exhibited race conditions and deadlocks.

Let's directly address misconceptions that persist even among experienced developers.

Misconception 1: "More threads = more parallelism"

Reality: Parallelism is bounded by physical cores. If you have 4 cores and spawn 100 threads, at most 4 run in parallel; the rest just add scheduling overhead. Excessive threads cause thrashing—the OS spends more time context-switching than doing work.

Misconception 2: "Async programming is about performance"

Reality: Async programming is about concurrency—handling many operations without blocking. For I/O-bound work, it improves throughput by not wasting time waiting. For CPU-bound work, async provides zero speedup; you need parallel execution (actual cores doing computation).

Misconception 3: "Concurrent programs run faster"

Reality: Pure concurrency (on one core) doesn't make computation faster—it makes resource usage more efficient. If task A waits for I/O, task B can run instead of wasting time. The CPU isn't faster; it's less idle.

Misconception 4: "Parallel programs are automatically concurrent"

Reality: Parallelism doesn't require concurrent structure. A SIMD operation processes 8 integers simultaneously with zero concurrency—it's one instruction, replicated across data. Similarly, a parallel loop may have no interleaving; each iteration runs to completion on one core.

One of the most important theoretical results concerning parallelism is Amdahl's Law, formulated by computer scientist Gene Amdahl in 1967. It places a hard limit on the speedup achievable through parallelism.

Amdahl's Law states:

The maximum speedup of a program using N processors is limited by the sequential portion of the program.

The formula:

$$S = \frac{1}{(1-P) + \frac{P}{N}}$$

Where:

• S = speedup factor
• P = proportion of the program that can be parallelized (0 to 1)
• N = number of processors

Example: If 90% of your code can be parallelized (P = 0.9):

• With 2 processors: S = 1 / (0.1 + 0.9/2) = 1.82× speedup
• With 10 processors: S = 1 / (0.1 + 0.9/10) = 5.26× speedup
• With 100 processors: S = 1 / (0.1 + 0.9/100) = 9.17× speedup
• With ∞ processors: S = 1 / 0.1 = 10× speedup (maximum possible!)

Even with infinite processors, you're limited to 10× speedup because 10% of the program is inherently sequential.

What this means for system design:

1. Identify sequential bottlenecks first — Before adding parallelism, profile to find what can be parallelized. Making parallel portions faster provides diminishing returns if serial portions dominate.

2. Invest in reducing sequential fractions — Often, redesigning to reduce sequential portions provides more speedup than adding more cores to already-parallel portions.

3. Recognize when parallelism stops helping — There's a point where adding more processors provides negligible speedup. Beyond this, effort is better spent elsewhere.

4. Concurrency helps differently — Amdahl's Law applies to parallelism (speedup from simultaneous execution). Concurrency's benefits (better I/O utilization, responsiveness) work on a different axis.

Beyond Amdahl: Gustafson's Law

Gustafson's Law provides a more optimistic view: as problem sizes grow, the parallelizable portion often grows proportionally, while the serial portion remains fixed. For many real-world problems, bigger datasets mean better parallel efficiency, partially offsetting Amdahl's pessimism.

We've established the fundamental distinction that underpins all concurrent programming. Let's consolidate the key insights:

What's next:

With this distinction clear, we can now explore the challenges that arise when multiple tasks (whether concurrent, parallel, or both) interact with shared resources. The next page examines sequential consistency—the memory model that defines what it means for concurrent operations to 'make sense' and why modern hardware makes this surprisingly complex.