1. 并发编程中的原子操作基础
原子操作(Atomic Operation)是并发编程中最基础也最重要的概念之一。在单线程环境中,我们编写的代码总是按顺序执行,每个操作都是"原子性"完成的。但在多线程环境下,当多个线程同时访问共享资源时,如果没有适当的同步机制,就会出现竞态条件(Race Condition)。
原子操作指的是不可被中断的一个或一系列操作。这些操作要么全部执行成功,要么全部不执行,不会出现执行到一半被其他线程打断的情况。现代CPU提供了多种原子指令,如CAS(Compare-And-Swap)、LL/SC(Load-Linked/Store-Conditional)等,这些都是实现无锁数据结构的基础。
注意:原子性不同于可见性。即使操作是原子的,在多核CPU环境下,由于缓存的存在,一个线程的修改可能不会立即被其他线程看到,这就是为什么还需要内存屏障(Memory Barrier)来保证可见性。
2. CAS操作原理深度解析
2.1 CAS工作机制
CAS(Compare-And-Swap)是CPU提供的一种原子指令,其伪代码表示如下:
cpp复制bool CAS(T* ptr, T expected, T new_value) {
if (*ptr == expected) {
*ptr = new_value;
return true;
}
return false;
}
这个操作是原子的,意味着在执行过程中不会被其他线程打断。CAS操作需要三个参数:
- 内存位置(ptr)
- 期望值(expected)
- 新值(new_value)
只有当内存中的当前值等于期望值时,才会将内存位置的值更新为新值,并返回true;否则不做任何操作并返回false。
2.2 CAS的ABA问题
虽然CAS操作很强大,但它存在一个经典的ABA问题。考虑以下场景:
- 线程1读取内存位置X的值为A
- 线程2将X的值从A改为B
- 线程2又将X的值从B改回A
- 线程1执行CAS操作,发现X的值仍然是A,于是操作成功
尽管最终CAS操作成功了,但实际上内存位置X的值已经经历了A→B→A的变化。这在某些场景下可能会导致问题,比如链表操作中节点被释放后又重新分配的情况。
解决ABA问题的常见方法有:
- 使用带版本号的指针(如Java的AtomicStampedReference)
- 使用双重CAS(DCAS)
- 在某些场景下可以忽略ABA问题(如果它不影响正确性)
3. 基于CAS的无锁编程实践
3.1 无锁计数器实现
让我们看一个最简单的无锁计数器实现:
java复制public class AtomicCounter {
private AtomicInteger count = new AtomicInteger(0);
public void increment() {
int oldValue;
int newValue;
do {
oldValue = count.get();
newValue = oldValue + 1;
} while (!count.compareAndSet(oldValue, newValue));
}
public int get() {
return count.get();
}
}
这个实现展示了典型的CAS使用模式:
- 读取当前值
- 计算新值
- 尝试CAS更新
- 如果失败(说明有其他线程修改了值),则重试
3.2 无锁栈实现
更复杂的无锁数据结构如栈的实现:
java复制public class LockFreeStack<T> {
private AtomicReference<Node<T>> top = new AtomicReference<>();
public void push(T item) {
Node<T> newHead = new Node<>(item);
Node<T> oldHead;
do {
oldHead = top.get();
newHead.next = oldHead;
} while (!top.compareAndSet(oldHead, newHead));
}
public T pop() {
Node<T> oldHead;
Node<T> newHead;
do {
oldHead = top.get();
if (oldHead == null) {
return null;
}
newHead = oldHead.next;
} while (!top.compareAndSet(oldHead, newHead));
return oldHead.item;
}
private static class Node<T> {
final T item;
Node<T> next;
Node(T item) {
this.item = item;
}
}
}
这个实现展示了如何用CAS构建更复杂的数据结构。注意pop操作中的空检查,以及如何处理并发情况下的栈顶变化。
4. 锁的实现原理与对比
4.1 互斥锁的基本实现
虽然CAS可以实现无锁编程,但传统的锁机制仍然是并发编程中的重要工具。一个简单的自旋锁实现如下:
java复制public class SpinLock {
private AtomicBoolean locked = new AtomicBoolean(false);
public void lock() {
while (!locked.compareAndSet(false, true)) {
// 自旋等待
}
}
public void unlock() {
locked.set(false);
}
}
这种锁称为自旋锁(Spin Lock),因为获取不到锁的线程会一直循环(自旋)等待。自旋锁适用于锁持有时间很短的场景,避免了线程上下文切换的开销。
4.2 锁与CAS的性能对比
锁和CAS各有优缺点,适用于不同场景:
| 特性 | 锁 | CAS |
|---|---|---|
| 实现复杂度 | 简单 | 复杂 |
| 阻塞行为 | 可能阻塞线程 | 通常自旋 |
| 适用场景 | 临界区较大 | 简单操作 |
| 内存开销 | 较高 | 较低 |
| 竞争激烈时 | 性能下降明显 | 可能更好 |
| 公平性 | 可实现公平 | 通常不公平 |
在实际应用中,通常遵循以下原则:
- 对于简单的原子操作(如计数器),优先使用CAS
- 对于复杂的操作或临界区较大的情况,使用锁
- 在高竞争环境下,考虑分层策略(如先用CAS尝试,失败后再用锁)
5. 高级并发模式与最佳实践
5.1 乐观锁与悲观锁
乐观锁和悲观锁是两种不同的并发控制策略:
- 悲观锁:假设会发生冲突,先获取锁再操作(如synchronized)
- 乐观锁:假设不会冲突,先操作再检查(如CAS)
乐观锁通常性能更好,但在高竞争环境下可能导致大量重试。选择策略时应考虑:
- 冲突概率:冲突少用乐观锁,冲突多用悲观锁
- 操作成本:操作重(如IO)用悲观锁,操作轻用乐观锁
- 一致性要求:强一致用悲观锁,弱一致可用乐观锁
5.2 内存可见性与happens-before
即使使用CAS或锁,还需要注意内存可见性问题。Java内存模型定义了happens-before规则,确保某些操作的内存可见性:
- 解锁操作happens-before后续的加锁操作
- volatile写happens-before后续的volatile读
- 线程启动happens-before该线程的任何操作
- 线程中的所有操作happens-before其他线程检测到该线程终止
正确使用这些规则可以避免内存可见性问题,而不需要过度同步。
5.3 避免常见陷阱
在实际使用CAS和锁时,需要注意以下陷阱:
- 过度同步:在不必要的地方使用同步会降低性能
- 死锁:多个锁的获取顺序不一致可能导致死锁
- 活锁:线程不断重试但无法前进(可通过随机退避解决)
- 优先级反转:高优先级线程被低优先级线程阻塞
- 虚假共享:多个线程修改同一缓存行的不同变量导致性能下降
6. 现代并发库的实现分析
6.1 Java并发包中的CAS应用
Java的java.util.concurrent包广泛使用了CAS。例如:
- AtomicInteger/AtomicLong:基于CAS的原子数值
- ConcurrentHashMap:分段锁+CAS
- CopyOnWriteArrayList:写时复制+CAS
- LongAdder:高竞争下的优化计数器
以LongAdder为例,它在高竞争环境下比AtomicLong性能更好,因为它使用了分散热点的策略:
java复制public void add(long x) {
Cell[] as; long b, v; int m; Cell a;
if ((as = cells) != null || !casBase(b = base, b + x)) {
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
(a = as[getProbe() & m]) == null ||
!(uncontended = a.cas(v = a.value, v + x)))
longAccumulate(x, null, uncontended);
}
}
6.2 无锁队列的实现模式
无锁队列是并发编程中的经典问题。Michael-Scott队列是最著名的无锁队列算法之一:
java复制public class LockFreeQueue<T> {
private static class Node<T> {
final T item;
final AtomicReference<Node<T>> next;
Node(T item) {
this.item = item;
this.next = new AtomicReference<>(null);
}
}
private final AtomicReference<Node<T>> head;
private final AtomicReference<Node<T>> tail;
public LockFreeQueue() {
Node<T> dummy = new Node<>(null);
head = new AtomicReference<>(dummy);
tail = new AtomicReference<>(dummy);
}
public void enqueue(T item) {
Node<T> newNode = new Node<>(item);
while (true) {
Node<T> curTail = tail.get();
Node<T> tailNext = curTail.next.get();
if (curTail == tail.get()) {
if (tailNext != null) {
// 有其他线程正在添加节点,帮忙推进tail
tail.compareAndSet(curTail, tailNext);
} else {
if (curTail.next.compareAndSet(null, newNode)) {
tail.compareAndSet(curTail, newNode);
return;
}
}
}
}
}
public T dequeue() {
while (true) {
Node<T> curHead = head.get();
Node<T> curTail = tail.get();
Node<T> headNext = curHead.next.get();
if (curHead == head.get()) {
if (curHead == curTail) {
if (headNext == null) {
return null;
}
tail.compareAndSet(curTail, headNext);
} else {
T item = headNext.item;
if (head.compareAndSet(curHead, headNext)) {
return item;
}
}
}
}
}
}
这个实现展示了无锁编程的复杂性,以及如何通过"帮助"其他线程(推进tail)来提高整体性能。
7. 性能优化与实战技巧
7.1 减少争用的策略
在高并发环境下,减少争用是提高性能的关键:
- 数据分片:将共享数据分成多个部分,减少争用(如ConcurrentHashMap的分段)
- 本地化处理:先在本地处理,再合并结果(如ForkJoinPool)
- 退避策略:争用失败时不立即重试,而是等待一段时间
- 消除共享:尽可能避免共享数据(如线程局部变量)
7.2 基准测试与性能分析
选择并发策略时,应该基于实际场景进行基准测试。JMH(Java Microbenchmark Harness)是Java中常用的基准测试工具:
java复制@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
public class CounterBenchmark {
private AtomicCounter atomicCounter = new AtomicCounter();
private LockCounter lockCounter = new LockCounter();
@Benchmark
public void testAtomicCounter() {
atomicCounter.increment();
}
@Benchmark
public void testLockCounter() {
lockCounter.increment();
}
public static class AtomicCounter {
private AtomicInteger count = new AtomicInteger();
public void increment() {
count.incrementAndGet();
}
}
public static class LockCounter {
private int count = 0;
private final Object lock = new Object();
public void increment() {
synchronized (lock) {
count++;
}
}
}
}
这样的测试可以帮助我们了解在不同线程数、不同竞争程度下各种实现的性能表现。
7.3 实际项目中的选择
在实际项目中,选择并发控制策略需要考虑:
- 开发成本:无锁编程通常更难实现和调试
- 维护成本:复杂的并发代码更难维护
- 性能需求:是否真的需要极致性能
- 团队经验:团队对并发编程的熟悉程度
通常的建议是:
- 首先考虑使用现有的并发容器(如ConcurrentHashMap)
- 其次考虑使用锁
- 只有在确实需要且团队有能力时才使用无锁编程