I. What Are Concurrency and Parallelism
Concurrency and parallelism are two closely related but distinct concepts.
1. Concurrency
Concurrency refers to a system's ability to handle multiple tasks within the same time period.
Multiple tasks can make logical progress at the same time, but they do not necessarily execute at the same physical instant.
For example, a single-core CPU can execute multiple tasks through task switching:
- Task A executes for a period of time.
- The operating system saves task A's execution state.
- The CPU switches to task B.
- Task B executes for a period of time.
- The CPU switches back to task A.
From the perspective of the system as a whole, multiple tasks are all making progress, so it has concurrency capability.
Concurrency focuses on:
- How multiple tasks are organized.
- How tasks alternate execution.
- How to handle dependencies between tasks.
- How to share resources.
- How to coordinate the execution order of tasks.
2. Parallelism
Parallelism means multiple tasks truly execute at the same instant.
For example, a CPU with 8 physical cores can run multiple threads simultaneously on different cores.
If there are no dependencies between tasks, they can be assigned to different cores for execution.
Parallelism focuses on:
- How multiple tasks run simultaneously.
- How to allocate computing resources.
- How to reduce task execution time.
- How to balance the load across different processing units.
- How to handle data races in parallel execution.
3. Key Differences Between Concurrency and Parallelism
| Comparison Dimension | Concurrency | Parallelism |
|---|---|---|
| Core objective | Manage the progress of multiple tasks | Execute multiple tasks simultaneously |
| Time relationship | Alternate progress or overlap within the same time period | Execute at the same instant |
| CPU requirement | Can be achieved on a single core | Usually requires multiple execution units |
| Focus | Task organization, coordination, and scheduling | Computing resource allocation and execution efficiency |
| Typical applications | Network services, asynchronous I/O, task scheduling | Image processing, matrix computation, scientific computing |
| Main challenges | Race conditions, deadlocks, state coordination | Data races, load balancing, synchronization overhead |
It should be noted that concurrency and parallelism are not mutually exclusive.
A program can:
- Have only concurrency, without parallelism.
- Have both concurrency and parallelism.
- Be concurrent at one stage and parallel at another stage.
II. Execution Models of Concurrency and Parallelism
1. Single-Core Concurrency
A single-core CPU can usually execute only one ordinary instruction stream at any given moment, but the operating system can use time-slice scheduling to let multiple tasks execute alternately.
flowchart TB
A["Single-core CPU"] --> B["Scheduler"]
B --> C["Task A"]
B --> D["Task B"]
B --> E["Task C"]
C --> F["Time-slice switching"]
D --> F
E --> F
F --> B
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
style E fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style F fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
From the timeline perspective:
Time ─────────────────────────────────>
CPU: A A A | B B B | C C | A A | B B
A, B, and C do not execute at the same instant; instead, they advance alternately through CPU time slices.
This is single-core concurrency.
2. Multi-Core Parallelism
A multi-core CPU can assign different tasks to different cores so that they execute at the same instant.
flowchart TB
A["Task Set"] --> B["Task Scheduling"]
B --> C["CPU Core 1"]
B --> D["CPU Core 2"]
B --> E["CPU Core 3"]
B --> F["CPU Core 4"]
C --> G["Task A runs simultaneously"]
D --> H["Task B runs simultaneously"]
E --> I["Task C runs simultaneously"]
F --> J["Task D runs simultaneously"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style E fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style G fill:#FFF5DE,stroke:#E8D29A,color:#334155
style H fill:#FFF5DE,stroke:#E8D29A,color:#334155
style I fill:#FFF5DE,stroke:#E8D29A,color:#334155
style J fill:#FFF5DE,stroke:#E8D29A,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
Execution timeline of multi-core parallelism:
Time ─────────────────────────────────>
Core 1: A A A A A A A A
Core 2: B B B B B B B B
Core 3: C C C C C C C C
Core 4: D D D D D D D D
Multiple cores can truly execute different tasks at the same time.
3. Combining Concurrency and Parallelism
In real systems, concurrency and parallelism usually coexist.
For example, a web service may handle thousands of requests at the same time:
- Requests have a concurrent relationship with one another.
- CPU-intensive tasks can be assigned to different cores for parallel execution.
- I/O operations can wait for external resources through asynchronous mechanisms.
- The operating system is responsible for thread scheduling and processor resource allocation.
Therefore, concurrency describes how a program organizes tasks, while parallelism describes how tasks are actually executed.
III. Processes, Threads, and Coroutines
The implementation of concurrency and parallelism usually involves processes, threads, and coroutines.
They are at different levels of abstraction and cannot be simply equated.
1. Process
A process is an important unit for resource allocation and management in an operating system.
A process usually has an independent virtual address space and related system resources.
A process usually contains:
- Virtual memory space.
- Code segment.
- Data segment.
- Heap.
- Threads.
- File descriptors or handles.
- Other operating system resources.
Different processes usually exchange data through inter-process communication (IPC).
Common communication methods:
- Pipe.
- Message Queue.
- Shared Memory.
- Socket.
- Signal.
Processes have relatively independent resource boundaries, but process creation, switching, and communication usually incur some overhead.
2. Thread
A thread is an important unit of scheduling and execution in an operating system.
Multiple threads within the same process usually share:
- The process address space.
- Heap memory.
- Global variables.
- Static data.
- Process resources such as file descriptors.
Each thread has its own execution context, usually including:
- Program counter.
- Register state.
- Stack.
- Thread-local storage (TLS).
- Scheduling state.
Threads sharing an address space makes data exchange between threads more convenient, but it also introduces synchronization and data race issues.
3. Coroutine
A coroutine is a program execution unit that can be suspended and resumed.
Coroutines are usually scheduled by the language runtime, a coroutine library, or a framework.
A coroutine can be suspended during execution, save the necessary execution state, and later resume from the suspension point.
For example:
import asyncio
async def task_a():
print("任务 A 开始")
await asyncio.sleep(1)
print("任务 A 结束")
async def task_b():
print("任务 B 开始")
await asyncio.sleep(1)
print("任务 B 结束")
async def main():
await asyncio.gather(task_a(), task_b())
asyncio.run(main())
In this example, the two coroutines advance alternately through the event loop.
When one coroutine waits for an asynchronous operation, the event loop can schedule another coroutine to execute.
Note that:
- Coroutines are not necessarily scheduled directly by the operating system.
- Coroutines do not necessarily correspond to independent threads.
- Single-threaded coroutines can achieve high-concurrency I/O.
- Coroutines can only achieve true parallel execution when they run on multiple execution threads or processing cores.
4. Comparison of Processes, Threads, and Coroutines
| Comparison Dimension | Process | Thread | Coroutine |
|---|---|---|---|
| Abstraction level | Operating system resource management | Operating system execution unit | Program execution unit |
| Resource space | Usually an independent address space | Threads in the same process share an address space | Depends on the owning thread and runtime |
| Scheduling entity | Operating system | Usually scheduled by the operating system | Language runtime or coroutine scheduler |
| Switching overhead | Usually higher | Usually lower than process switching | Usually lower, but depends on the implementation |
| Data sharing | Requires IPC or shared memory | Can directly share process data | Can share data accessible to the owning thread |
| Concurrency capability | Supported | Supported | Supported |
| Parallelism capability | Multiple processes can run in parallel | Multiple threads can run in parallel | Depends on the scheduler and execution threads |
Note that modern systems include implementations such as user-level threads, M:N threading models, and green threads; you cannot judge the scheduling method solely from the name "thread" or "coroutine."
IV. Core Mechanisms of Concurrency
Concurrent programs need not only to create multiple tasks, but also to manage their execution states and resource access.
1. Context Switching
Context switching is the process by which the processor switches from one executing task to another.
During a switch, the system needs to save the execution state of the current task and restore the execution state of the target task.
This typically involves:
- Register state.
- Program counter.
- Stack pointer.
- Scheduling information.
- Address-space-related state (depending on the type of switch).
A thread context switch may occur when:
- The time slice is exhausted.
- The thread blocks voluntarily.
- Waiting for I/O.
- Waiting for a lock.
- A higher-priority task becomes ready.
- Voluntarily yielding the CPU.
Context switching has costs:
- Saving and restoring registers.
- Running the scheduler.
- Cache locality is affected.
- May incur TLB and cache-related overhead.
- Too many threads increase system scheduling pressure.
Therefore, more threads are not always better.
2. Thread Scheduling
Thread scheduling is responsible for deciding which ready thread gets a chance to execute on the CPU.
Common scheduling policies include:
- First Come First Served (FCFS).
- Round Robin.
- Priority scheduling.
- Multilevel feedback queue.
- Fair scheduling.
Modern operating systems usually adopt more complex scheduling policies, taking into account priority, fairness, processor affinity, and load conditions.
The scheduling process can be abstracted as:
flowchart TB
A["Create thread"] --> B["Ready queue"]
B --> C["Scheduler selects thread"]
C --> D["Gets CPU execution"]
D --> E{"Execution state"}
E -->|"Continue running"| D
E -->|"Time slice exhausted"| B
E -->|"Waiting for resources"| F["Blocked queue"]
F --> G["Resources ready"]
G --> B
E -->|"Execution complete"| H["Terminated state"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
style E fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style F fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style G fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style H fill:#F3EDFC,stroke:#C4B2E3,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
3. Synchronization
When multiple threads concurrently access shared resources, data races may occur.
For example:
class Counter {
int count = 0;
void increment() {
count++;
}
}
count++ is not necessarily an indivisible atomic operation.
Its logic usually consists of:
- Reading the current value.
- Performing the addition.
- Writing back the new value.
If two threads execute it at the same time, a lost update may occur.
For example:
Initial value: count = 0
Thread A: reads 0
Thread B: reads 0
Thread A: computes 1
Thread B: computes 1
Thread A: writes 1
Thread B: writes 1
Final result: 1
The expected result is 2, but the actual result is 1.
This is a typical race condition.
Common synchronization mechanisms:
| Mechanism | Purpose |
|---|---|
| Mutex | Ensures that only one thread enters the critical section at a time |
| Semaphore | Controls the number of tasks that can access a resource at the same time |
| Condition Variable | Waits for a condition to become true |
| Read-Write Lock | Distinguishes read operations from write operations |
| Atomic Operation | Ensures that a specific operation is indivisible |
| Barrier | Waits for multiple tasks to reach a synchronization point |
4. Atomicity, Visibility, and Ordering
Three basic properties often need attention in concurrent programming.
Atomicity
An operation either executes completely or does not leave a partially visible intermediate state.
For example, using an atomic integer to perform an increment operation can avoid lost updates in the ordinary read-modify-write process.
Visibility
A modification made by one thread to a shared variable can be observed by other threads according to the synchronization relationships specified by the memory model.
Ordering
Compilers, CPUs, and runtimes may reorder instructions, as long as this does not violate the semantics allowed by the corresponding language and hardware memory models.
Concurrent programs must establish the necessary ordering constraints through appropriate synchronization mechanisms.
For example, Java's volatile can provide certain visibility and ordering guarantees, but it cannot turn an ordinary count++ into an atomic operation.
V. Typical Problems in Concurrent Programming
1. Race Condition
A race condition means that the program result depends on the execution timing of multiple tasks, and this timing may change.
For example:
if (account.balance >= amount) {
account.balance -= amount;
}
If two threads simultaneously check the balance and perform a deduction, an excessive deduction may occur.
The problem is not only in the reading and writing of a single variable, but also in the lack of atomicity between the check and the update.
Solutions:
- Use a mutex to protect the entire business operation.
- Use database transactions.
- Use atomic state transitions.
- Use a message queue for serial processing.
- Use immutable data structures to reduce shared writes.
2. Deadlock
A deadlock means that multiple tasks wait for resources held by each other, causing all involved tasks to be unable to continue executing.
Classic scenario:
- Thread A holds lock 1 and waits for lock 2.
- Thread B holds lock 2 and waits for lock 1.
flowchart TB
A["Thread A"] --> B["Holds lock 1"]
B --> C["Waiting for lock 2"]
D["Thread B"] --> E["Holds lock 2"]
E --> F["Waiting for lock 1"]
C --> G["Deadlock"]
F --> G
G --> H["Neither thread can continue"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#FFF5DE,stroke:#E8D29A,color:#334155
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style F fill:#FFF5DE,stroke:#E8D29A,color:#334155
style G fill:#FBE9E9,stroke:#D9AAAA,color:#334155
style H fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
A deadlock usually requires four conditions to be satisfied simultaneously:
- Mutual exclusion: A resource cannot be held exclusively by multiple tasks at the same time.
- Hold and wait: A task holds resources while waiting for other resources.
- No preemption: Resources cannot be forcibly taken away from a task.
- Circular wait: Multiple tasks form a resource-waiting cycle.
Common preventive measures:
- Use a consistent lock acquisition order.
- Reduce the scope of lock holding.
- Avoid nested locks.
- Use timeout locks.
- Reduce shared resources.
- Use lock-free or message-passing models.
3. Livelock
A livelock means that multiple tasks keep adjusting their states but never complete actual work.
For example:
After two threads discover a resource conflict, both voluntarily release the resource and retry, resulting in the same operation being repeated continuously.
Unlike deadlock:
- Deadlock: tasks cannot continue executing.
- Livelock: tasks continue executing but make no effective progress.
Livelock can be mitigated through random backoff, retry intervals, and coordination strategies.
4. Starvation
Starvation means that a task cannot obtain the resources it needs or an opportunity to execute for a long time.
Common causes:
- High-priority tasks continuously occupy the CPU.
- Locks are repeatedly acquired by certain threads.
- The scheduling policy lacks fairness.
- Resource allocation is unreasonable.
Solutions include:
- Fair locks.
- Priority adjustment.
- Fair scheduling.
- Limiting the time resources are held.
- Introducing timeouts and queuing mechanisms.
5. Comparison of Concurrency Problems
| Problem | Core symptom | Typical cause |
|---|---|---|
| Race condition | Result depends on execution timing | Shared state lacks proper synchronization |
| Deadlock | Tasks wait on each other and cannot proceed | Circular resource waiting |
| Livelock | Continuous activity but no completion | Constant conflicts and retries |
| Starvation | Some tasks never get resources for a long time | Unfair scheduling or resource allocation |
VI. Core Mechanisms of Parallel Computing
The goal of parallel computing is to split computational tasks across multiple processing units for execution.
1. Data Parallelism
Data parallelism means splitting data into multiple parts and performing the same or similar computations on each part.
For example, squaring every element in a large array.
result = [x * x for x in data]
In parallel computing, the data can be divided into multiple shards:
flowchart TB
A["Large Dataset"] --> B["Data Sharding"]
B --> C["Shard 1"]
B --> D["Shard 2"]
B --> E["Shard 3"]
B --> F["Shard 4"]
C --> G["Processing Unit 1"]
D --> H["Processing Unit 2"]
E --> I["Processing Unit 3"]
F --> J["Processing Unit 4"]
G --> K["Merge Results"]
H --> K
I --> K
J --> K
K --> L["Final Result"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style E fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style G fill:#FFF5DE,stroke:#E8D29A,color:#334155
style H fill:#FFF5DE,stroke:#E8D29A,color:#334155
style I fill:#FFF5DE,stroke:#E8D29A,color:#334155
style J fill:#FFF5DE,stroke:#E8D29A,color:#334155
style K fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style L fill:#E5F4EC,stroke:#A3CBB5,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
Typical scenarios:
- Image pixel processing.
- Matrix computation.
- Large-scale array operations.
- Machine learning tensor computation.
- Scientific computing.
2. Task Parallelism
Task parallelism means assigning different computational tasks to different processing units for execution.
For example, a video processing system can simultaneously perform:
- Video decoding.
- Audio decoding.
- Image filters.
- Audio enhancement.
- Data encoding.
Different tasks may run different algorithms, and their inputs and outputs may also differ.
3. Pipeline Parallelism
Pipeline parallelism splits a complex task into multiple stages, and different stages can process different data at the same time.
For example, video processing:
flowchart LR
A["Read data"] --> B["Decode"]
B --> C["Image processing"]
C --> D["Encode"]
D --> E["Output"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
style E fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
When different stages process different data blocks, a pipeline can be formed in which execution overlaps.
For example:
- Stage 1 reads the 3rd data block.
- Stage 2 processes the 2nd data block.
- Stage 3 encodes the 1st data block.
The advantage of pipeline parallelism lies in improving overall throughput, but it does not necessarily reduce the full end-to-end latency of a single data block.
4. Data Parallelism vs. Task Parallelism
| Comparison dimension | Data parallelism | Task parallelism |
|---|---|---|
| Object of division | Data collection | Computational tasks |
| Execution content | Usually the same or similar | Can be completely different |
| Data relationship | Usually relatively independent | Task dependencies may exist |
| Typical scenarios | Matrices, images, arrays | Multi-stage processing, independent services |
| Main challenges | Data partitioning and result merging | Task scheduling and dependency coordination |
VII. Performance Analysis of Concurrency and Parallelism
Concurrency and parallelism do not necessarily improve program performance.
Task decomposition, synchronization, communication, and scheduling all incur additional costs.
1. Throughput and Latency
Throughput
The number of tasks a system completes per unit of time.
For example:
- Processing 1,000 HTTP requests per second.
- Completing 500 database transactions per second.
- Processing 1 million data elements per second.
Latency
The time required for a single task from start to completion.
For example:
- One HTTP request takes 50 ms.
- One database query takes 20 ms.
- Processing one image takes 200 ms.
Concurrency can usually improve a system's ability to handle multiple requests at the same time, but it does not necessarily reduce the latency of a single request.
Parallelism, on the other hand, may shorten the execution time of a computational task, but if the synchronization and communication costs are too high, it can also lead to performance degradation.
2. Amdahl's Law
Amdahl's Law describes the theoretical limit that parallelization places on the overall speedup of a program.
Assume:
- P: the proportion of the program that can be executed in parallel.
- 1-P: the proportion that must be executed serially.
- N: the number of parallel processing units.
Theoretical speedup:
For example:
If in a program:
- 80% of the code can be parallelized.
- 20% of the code must be serial.
- 4 processing units are used.
Then:
That is, the theoretical speedup is 2.5 times.
Even if the number of processing units approaches infinity:
When P=0.8:
This means the serial portion limits the maximum speedup of the program.
Real systems also need to account for additional overheads such as communication, synchronization, scheduling, and load imbalance, so the actual speedup is usually lower than the ideal model.
3. Gustafson's Law
Amdahl's Law mainly analyzes the effect of adding processing units under a fixed problem size.
Gustafson's Law, by contrast, analyzes parallel computing from the perspective of a fixed running time and an enlarged problem size.
Its expression is:
Where:
- N: the number of processing units.
- \alpha: the proportion of the serial portion in the total execution time.
It emphasizes that as computing resources increase, larger problems can be handled, rather than merely speeding up tasks of a fixed size.
4. Performance Bottlenecks of Parallel Computing
Common bottlenecks include:
- Excessive proportion of serial code.
- Uneven task partitioning.
- Thread scheduling overhead.
- Lock contention.
- Inter-process communication overhead.
- Memory bandwidth limitations.
- CPU cache misses.
- NUMA remote memory access.
- Data synchronization cost.
5. Load Balancing
Load balancing means distributing tasks reasonably so that the workloads of different processing units are as even as possible.
If one core has already finished its tasks while another core is still processing a large number of tasks, the overall system completion time is still limited by the slowest task.
Common strategies:
- Static task partitioning.
- Dynamic task allocation.
- Work stealing.
- Chunked processing.
- Task queues.
Work stealing is an important scheduling strategy in many parallel runtimes: idle worker threads can take tasks from other threads' task queues to improve processor utilization.
VIII. I/O-Intensive and CPU-Intensive Tasks
The task type directly affects the choice of concurrency and parallelism approach.
1. CPU-Intensive Tasks
CPU-intensive tasks mainly consume processor computing resources.
For example:
- Image processing.
- Video encoding.
- Data compression.
- Cryptographic computation.
- Numerical computation.
- Machine learning inference.
Such tasks are usually suitable for utilizing multiple CPU cores through multiprocessing, multithreading, or parallel computing frameworks.
If tasks can be split into independent computational units and synchronization costs are low, parallel execution is usually more worthwhile.
2. I/O-Intensive Tasks
I/O-intensive tasks mainly wait for external resources.
For example:
- Network requests.
- Database queries.
- File reads and writes.
- RPC calls.
- Message queue consumption.
While waiting for I/O, execution units may be unable to continue their current work.
Asynchronous I/O, event loops, or thread pools can allow other tasks to continue progressing during the wait.
3. Processing Strategies for the Two Task Types
| Comparison Dimension | CPU-Intensive | I/O-Intensive |
|---|---|---|
| Main bottleneck | CPU computing capability | External I/O waiting |
| Typical tasks | Image processing, compression | Network requests, database queries |
| Common approaches | Multi-core parallelism, process pools | Asynchronous I/O, thread pools |
| Primary goal | Increase computational throughput | Improve resource utilization and concurrency capability |
| Number of threads | Usually designed around the number of CPU cores | Can be adjusted based on wait time and resource limits |
| Key risks | Uneven computational load, synchronization overhead | Connection exhaustion, resource buildup, timeouts |
These are only general recommendations. The actual number of threads is also affected by task granularity, runtime implementation, memory, I/O limits, and system scheduling policies.