并行与并发 (Concurrency & Parallelism)

一、核心概念

并发 (Concurrency)

定义:多个任务在同一时间段内交替执行,宏观上同时进行,微观上轮流使用资源。

本质:处理多个独立的事情,不一定同时。

关键:单核 CPU 也能做到(通过时间片切换)。

并行 (Parallelism)

定义:多个任务在同一时刻真正同时执行。

本质:处理多个同时的事情,需要硬件支持(多核、多 CPU、多机器)。

关键:必须有多核/多 CPU 才能实现真正的并行。

一句话对比

并发:看起来同时跑,实际是快速切换
并行:真正的同时跑

Go 语言之父 Rob Pike 的经典比喻: - 并发是关于处理(dealing with) 多个事物 - 并行是关于做(doing) 多个事物

二、为什么需要并发和并行

1. 提高 CPU 利用率

单核单线程执行时,经常需要等待 I/O(磁盘、网络)
等待时 CPU 闲置,浪费资源
多任务可以重叠 I/O 与计算,提高效率

2. 提高吞吐量

同时处理更多请求
服务器(Web、数据库)用多线程/多进程处理并发连接

3. 改善响应性

GUI 程序:工作线程做后台任务,UI 线程保持响应
防止"卡死"

4. 解决多核 CPU 性能

单线程程序只能用一个核,多核 CPU 浪费
多线程/多进程能利用多核,性能近乎线性增长

三、并发与并行的关系

维度	并发	并行
关注点	任务结构	任务执行
必要条件	不需要多核	必须多核
关键能力	任务切换	真正同时跑
资源占用	共享资源,逻辑上的"同时"	真正消耗多份资源
编程难度	同步/竞态	数据一致性更复杂
适合	IO 密集型	CPU 密集型

重要关系:

并行是并发的子集:并行一定并发,并发不一定并行
现代系统两者并存:多核 CPU 上跑多线程,既是并发也是并行

单核 CPU:
  ┌──────────────────────────┐
  │ T1 → T2 → T1 → T3 → T2   │ ← 时间片轮转(并发)
  └──────────────────────────┘
       (每个时刻只跑 1 个线程)

多核 CPU:
  ┌──────────────┬──────────────┐
  │ T1 → T1 → T1 │ T2 → T2 → T2 │ ← 真正同时(并行)
  └──────────────┴──────────────┘
  核心 1         核心 2

四、并发/并行的基本单位

1. 进程 (Process)

资源分配的基本单位
拥有独立地址空间
切换开销大(页表、文件描述符、信号等)

2. 线程 (Thread)

CPU 调度的基本单位
同一进程内线程共享地址空间
切换开销小(只需切换寄存器和栈)

3. 协程 (Coroutine / Goroutine)

用户态的"轻量级线程"
由程序自己调度,无需内核介入
切换极快(纳秒级)
代表:Goroutine (Go)、Kotlin 协程、Python asyncio、C++20 coroutine

4. 对比

单位	创建开销	切换开销	并行	数量级
进程	大(MB)	μs 级	是	几十~几百
线程	小(KB)	μs 级	是	几百~几千
协程	极小(B)	ns 级	否	几万~几百万

五、并发模型

1. 多进程 (Multi-Process)

每个任务一个进程
进程间通信 (IPC):管道、消息队列、共享内存、Socket
隔离性好(一个进程崩溃不影响其他)
代表:Apache prefork、Nginx(早期)、浏览器 Chrome

2. 多线程 (Multi-Thread)

同一进程内多个线程,共享地址空间
同步/通信:共享变量、锁、信号量、条件变量
资源占用少,通信快
但容易出现竞态条件
代表:Java/Python/C++ 线程、Tomcat

3. 协程 (Coroutine)

用户态调度
单线程内并发,无竞态(共享变量安全)
适合 IO 密集型(高并发 Web 服务)
缺点:无法利用多核(需配合多线程/多进程)
代表:Go goroutine、Python asyncio、Rust tokio

4. Actor 模型

每个 Actor 独立,通过消息传递通信
天然无共享,无锁
代表:Erlang/AKKA (Scala)/ Elixir

5. 反应式编程 (Reactive)

事件驱动 + 异步回调
适合 IO 密集
代表:Node.js、Reactor (Java)、RxJS

6. CSP (Communicating Sequential Processes)

协程 + Channel
Go 语言的并发模型
"不要通过共享内存通信,反过来通过通信共享内存"

7. Fork/Join 框架

分治:把大任务拆成小任务,递归并行执行,最后合并
Java ForkJoinPool、Go errgroup

8. MapReduce

大规模数据并行处理
Map 分片处理,Reduce 汇总
代表:Hadoop、Spark

六、线程详解

1. 线程的生命周期

       ┌──────────┐
       │  New     │ ← 刚创建
       └────┬─────┘
            ↓ start()
       ┌──────────┐
   ┌──→│ Runnable │ ← 可运行(就绪 + 运行)
   │   └────┬─────┘
   │        ↓ 等待 I/O、锁等
   │   ┌──────────┐
   │   │ Blocked  │ ← 阻塞
   │   └────┬─────┘
   │        ↓ 资源到位
   │   ←───┘
   │        ↓ 异常/超时
   │   ┌──────────┐
   │   │ Terminated │ ← 终止
   │   └──────────┘
   └────── (回到 Runnable)

2. 线程的 5 种状态 (Java)

NEW:新建
RUNNABLE:可运行
BLOCKED:阻塞,等待锁
WAITING:等待(无超时),如 wait() / join()
TIMED_WAITING:限时等待,如 sleep(1000) / wait(1000)
TERMINATED:终止

3. 用户级线程 vs 内核级线程

类型	调度者	切换开销	数量
用户级线程	用户态库	极小	几乎无限
内核级线程	OS 内核	中等	几千

映射模型:

N:1 (协程):N 个用户线程 → 1 个内核线程,无法并行
1:1 (Pthread, Java Thread):1 个用户线程 → 1 个内核线程,可并行
M:N (Goroutine):M 个用户线程 → N 个内核线程,折中

七、同步与锁

为什么需要同步

多个线程/进程同时访问共享资源时,可能产生竞态条件 (Race Condition)
导致数据不一致、死锁、活锁等问题

1. 锁的分类

按功能

锁类型	用途
互斥锁 (Mutex)	一次只允许一个线程进入临界区
读写锁 (RWLock)	读可并发,写独占
自旋锁 (Spinlock)	短临界区,不睡眠,忙等
递归锁	同一线程可重入
悲观锁	假定冲突,先加锁
乐观锁	假定无冲突,失败重试(CAS)
公平锁	按等待顺序获取锁
非公平锁	不保证顺序,性能好

按实现

软件锁:Peterson 算法、Dekker 算法、 bakery algorithm
硬件锁:CAS (Compare-And-Swap)、TAS (Test-And-Set)、FAA
内核锁:pthread_mutex、semaphore

2. 信号量 (Semaphore)

计数信号量:值 > 1,表示可用资源数
二元信号量:值 = 1,等价于互斥锁
P 操作 (wait):值减 1,若 < 0 则阻塞
V 操作 (signal):值加 1,唤醒等待者
应用:生产者-消费者、读者-写者

3. 条件变量 (Condition Variable)

线程等待某个条件成立
配合互斥锁使用
wait()、signal()、broadcast()

4. CAS (Compare-And-Swap)

原子操作,硬件支持,无锁编程基础。

int cas(int *addr, int expected, int new_value) {
    int old = *addr;
    if (old == expected) {
        *addr = new_value;
        return 1;
    }
    return 0;
}

应用:

乐观锁
无锁队列/栈
原子变量 (Java AtomicInteger)

5. 内存屏障 (Memory Barrier / Fence)

解决 CPU 乱序执行和缓存一致性问题
类型:mfence(全)、sfence(写)、lfence(读)
Linux 内核:smp_mb()、smp_rmb()、smp_wmb()

6. 死锁 (Deadlock)

4 个必要条件:

互斥:资源一次只能被一个线程占用
占有并等待:持有资源的线程还在等新资源
不可抢占:资源不能被强制抢走
循环等待:形成环路 T1 → T2 → T1

解决: - 破坏任一条件即可 - 常用:资源有序分配、加锁超时、死锁检测、银行家算法

7. 活锁 (Livelock)

线程一直活跃,但没有进展
例子:两人在走廊相遇,都让对方,都不过
解决:随机退避、优先级

8. 饥饿 (Starvation)

某个线程一直得不到资源
解决:公平锁、优先级提升

八、经典并发问题

1. 生产者-消费者 (Producer-Consumer)

一组生产者往缓冲区写,一组消费者从缓冲区读
用信号量/互斥锁同步
经典模型,广泛应用(消息队列、线程池)

2. 读者-写者 (Readers-Writers)

多个读者可并发读共享数据
写者必须独占
用读写锁解决

3. 哲学家就餐 (Dining Philosophers)

5 个哲学家,5 把叉子,每两人之间 1 把
必须同时拿两把叉子才能吃
经典死锁/资源竞争问题
解决:资源有序分配、奇偶分叉

4. 睡眠理发师 (Sleeping Barber)

1 个理发师、N 把椅子、无顾客时睡觉
顾客来了:椅子空则坐,否则走
经典 IPC 问题,用信号量解决

九、线程池

为什么用线程池

线程创建/销毁有开销
线程太多,系统资源耗尽
线程池复用线程,控制并发数

线程池参数

核心线程数 (corePoolSize):常驻线程数
最大线程数 (maxPoolSize):允许的最大线程数
队列 (workQueue):任务等待队列
拒绝策略 (RejectedExecutionHandler):队列满时的处理
AbortPolicy(抛异常)
CallerRunsPolicy(调用者执行)
DiscardPolicy(丢弃)
DiscardOldestPolicy(丢弃最老)

工作流程

1. 提交任务
2. 核心线程未满 → 创建核心线程执行
3. 核心线程满 → 任务入队
4. 队列满 → 创建非核心线程执行
5. 线程数达 max → 触发拒绝策略

常见线程池

Java:ThreadPoolExecutor
C++:std::thread pool、Boost.Asio
Go:goroutine 本质就是协程池
Python:concurrent.futures.ThreadPoolExecutor

十、并行计算模型

1. Flynn 分类法

类型	指令流	数据流	代表
SISD	1	1	传统单核 CPU
SIMD	1	多	GPU、向量化指令(SSE/AVX/NEON)
MISD	多	1	容错系统(罕见)
MIMD	多	多	多核 CPU、集群

2. SIMD (Single Instruction Multiple Data)

一条指令处理多个数据
CPU 扩展:
x86:SSE (128-bit) → AVX (256-bit) → AVX-512 (512-bit)
ARM:NEON
适合:图像处理、机器学习、科学计算
编译器自动向量化或使用 intrinsic 函数

3. MIMD

多核 CPU、集群都是 MIMD
又分:
共享内存 (SMP):多核共享同一内存,如多核 CPU
分布式内存 (MPP):多机通过网线通信,如超算集群
NUMA:混合,部分内存近、部分远

4. 异构计算

CPU + GPU + FPGA/ASIC
CPU 适合复杂逻辑,GPU 适合并行计算
平台:NVIDIA CUDA、OpenCL、ROCm、昇腾 CANN

十一、并发/并行编程挑战

1. 数据竞争 (Data Race)

多个线程同时读写同一变量,至少一个写
解决:加锁、volatile(可见性)、原子变量

2. 死锁

见上文。

3. ABA 问题

CAS 时,值从 A 变 B 又变回 A,误以为没变
解决:版本号 (AtomicStampedReference)

不同变量在同一 Cache 行(64 字节)
多核写时,行失效导致性能下降
解决:padding 凑齐 64 字节、@Contended

5. 优先级反转 (Priority Inversion)

低优先级任务持有高优先级任务需要的锁
高优先级任务等待
解决:优先级继承协议 (Linux pthread mutex 默认)

6. 惊群效应 (Thundering Herd)

多线程等待同一事件,事件发生时全部唤醒
解决:epoll、kqueue、IOCP

十二、并行算法设计

1. 分治 (Divide and Conquer)

把大问题拆成小问题,递归解决
例子:并行归并排序、并行快速排序

2. MapReduce

Map:每个节点处理一部分数据
Reduce:汇总结果

3. 流水线 (Pipeline)

任务分阶段,各阶段并行
例子:CPU 流水线、CI/CD 流水线

4. 工作窃取 (Work Stealing)

空闲线程从繁忙线程"偷"任务
实现:ForkJoinPool、TBB、Go scheduler

5. 数据并行

同一操作应用于不同数据
例子:并行 for 循环、SIMD

十三、并行性能评估

1. 加速比 (Speedup)

S = T(1) / T(n)

理想线性加速比:S = n
阿姆达尔定律:S = 1 / (s + p/n)
s = 串行部分比例
p = 并行部分比例
n = 处理器数

2. 效率 (Efficiency)

E = S / n

理想为 1,实际 0~1

3. 可扩展性 (Scalability)

加机器后,加速比能跟着线性增长
Gustafson 定律:S = s + p × n(更乐观)

4. 性能瓶颈

木桶效应:最慢的环节决定整体性能
阿姆达尔定律:串行部分是上限

十四、常见并行框架与库

语言/平台	框架
Java	ForkJoinPool、ExecutorService、Disruptor
C++	std::thread、TBB、OpenMP、CUDA
Go	goroutine、errgroup、Channel
Python	multiprocessing、concurrent.futures、asyncio
Rust	tokio、rayon、async-std
JavaScript	Web Workers、Cluster (Node.js)
.NET	TPL (Task Parallel Library)、PLINQ
大数据	Hadoop MapReduce、Spark、Flink
GPU	CUDA、OpenCL、Vulkan Compute

十五、Go 语言的并发模型(经典案例)

Goroutine + Channel

// 启动 goroutine
go func() {
    fmt.Println("Hello from goroutine")
}()

// Channel 通信
ch := make(chan int)
ch <- 42       // 发送
x := <-ch      // 接收

// 经典例子:生产者-消费者
func main() {
    ch := make(chan int, 10)
    go producer(ch)
    go consumer(ch)
}

func producer(ch chan<- int) {
    for i := 0; i < 100; i++ {
        ch <- i
    }
    close(ch)
}

func consumer(ch <-chan int) {
    for v := range ch {
        fmt.Println(v)
    }
}

Go 的并发哲学:

不要通过共享内存通信,通过通信共享内存
goroutine:轻量级协程,几 KB 栈,可启百万级
GMP 调度模型:
G (Goroutine)
M (Machine,内核线程)
P (Processor,逻辑处理器)
M:N 调度,工作窃取

Go 的同步原语

sync.Mutex 互斥锁
sync.RWMutex 读写锁
sync.WaitGroup 等待组
sync.Once 单次执行
sync.Cond 条件变量
sync.Map 并发安全 map
atomic 包 CAS 操作
context 上下文控制

十六、其他语言/框架的并发模型

Java

线程 + 锁:synchronized、ReentrantLock、ReentrantReadWriteLock
并发集合:ConcurrentHashMap、CopyOnWriteArrayList
线程池:ThreadPoolExecutor、ForkJoinPool
异步:CompletableFuture、Reactor、RxJava
协程:Loom (Java 19+ 虚拟线程)

C++

线程:std::thread、std::async
锁:std::mutex、std::lock_guard、std::unique_lock
原子:std::atomic<T> (CAS、fetch_add)
协程:C++20 co_await、co_return

Python

线程:threading (受 GIL 限制)
多进程:multiprocessing
协程:asyncio (async/await)
并发库:concurrent.futures
GIL:全局解释器锁,限制 CPU 密集型多线程

Rust

无畏并发:编译期检查数据竞争
线程:std::thread::spawn
同步:Mutex、RwLock、mpsc Channel
异步:async/await + tokio 运行时
Send/Sync trait:类型系统保证线程安全

十七、操作系统层面的并发支持

1. 进程/线程调度

OS 调度器决定哪个线程在哪个核上跑
调度算法:
CFS (Linux):完全公平调度器,基于红黑树
O(1) 调度器(Linux 2.6):按优先级分桶
Windows UMS:用户模式调度
FreeBSD ULE:BSD 的 CFS 类似

2. CPU 亲和性 (Affinity)

把线程绑到特定核上
减少 Cache 失效
taskset、sched_setaffinity

3. 中断亲和性

把设备中断绑到特定核
减少跨核中断处理开销

4. 实时调度

SCHED_FIFO:先来先服务,不抢占同等优先级
SCHED_RR:时间片轮转
SCHED_DEADLINE:截止时间调度

5. NUMA 优化

多插槽服务器,内存有"近""远"之分
线程尽量用本地内存
numactl 工具

十八、现代并发趋势

1. 协程原生化

Go goroutine
Kotlin coroutine
Rust async/await
Java Virtual Threads (Project Loom)
C# async/await

2. 无锁数据结构 (Lock-Free)

CAS 实现的无锁队列、栈、map
Java ConcurrentLinkedQueue
减少锁竞争,提升性能

3. 异步 I/O (Async I/O)

Linux:io_uring、epoll
Windows:IOCP (I/O Completion Port)
BSD:kqueue
适合高并发网络服务

4. 反应式流 (Reactive Streams)

背压(Backpressure)机制
Project Reactor、Akka Streams

5. SIMD + GPU 加速

异构计算:HPC、AI 训练
框架:OpenMP、CUDA、SYCL

6. 事务内存 (Software Transactional Memory, STM)

数据库事务思想应用到内存并发
Haskell、Clojure 已支持

十九、核心要点速记

并发 = 看起来同时(任务结构)
并行 = 真正同时(任务执行)
并行 ⊂ 并发:并行一定并发
单核只能并发,多核才能并行
3 大并发单位:进程(隔离)、线程(共享)、协程(轻量)
核心矛盾:共享 vs 同步
关键工具:锁、信号量、条件变量、CAS
常见问题:数据竞争、死锁、活锁、饥饿、ABA、伪共享
4 个死锁条件:互斥、占有并等待、不可抢占、循环等待
线程池:复用线程,控制并发
Flynn 分类:SISD/SIMD/MISD/MIMD
阿姆达尔定律:加速比上限 = 1 / (s + p/n)
Go 哲学:不共享内存,通过 Channel 通信
现代趋势:协程 + 无锁 + 异步 I/O + 异构计算
CPU 亲和性 + NUMA 优化是高性能调优的常见手段
GIL 限制 Python 多线程 CPU 密集型,改用多进程