本系列是 The art of multipropcessor programming 的读书笔记,在原版图书的根底上,联合 OpenJDK 11 以上的版本的代码进行了解和实现。并依据集体的查资料以及了解的经验,给各位想更深刻了解的人分享一些集体的材料
硬件根底
首先, 咱们无需把握大量的底层计算机系统结构设计常识的细节 ,如果大家对于计算机系统构造十分感兴趣,那么我十分举荐大家搜一下 CSE 502 Computer Architecture 的课件,我看了这门课的 CPU 和 缓存章节,受益匪浅。这里列出的硬件基础知识,次要为了能让咱们了解编程语言为了进步性能做的设计。
咱们个别能轻松写进去适宜单处理器运行的代码,然而面对多处理器的状况,可能同样的代码效率就低很多,请看上面这个例子:假如两个线程须要拜访一个资源,这个资源不能被多线程同时拜访,拜访前必须上锁,拿到锁之后能力拜访这个资源,并且须要在拜访完资源后开释锁。
咱们这里应用一个 boolean 域实现锁,如果这个 boolean 为 false 则锁是闲暇状态,否则就是正在被应用。应用 compareAndSet
来获取锁,这个调用返回 true 就是批改胜利,即获取锁胜利,返回 false 则批改失败,即获取锁失败。假如咱们有如下这个锁的接口:
public interface Lock {void lock();
void unlock();}
对于这个锁,咱们有以下两种实现,第一个是:
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
public class TASLock implements Lock {
private boolean locked = false;
// 操作 lock 的句柄
private static final VarHandle LOCKED;
static {
try {
// 初始化句柄
LOCKED = MethodHandles.lookup().findVarHandle(TASLock.class, "locked", boolean.class);
} catch (Exception e) {throw new Error(e);
}
}
@Override
public void lock() {
// compareAndSet 胜利代表获取了锁
while(!LOCKED.compareAndSet(this, false, true)) {
// 让出 CPU 资源,这是目前实现 SPIN 成果最好的让出 CPU 的形式,当线程数量远大于 CPU 数量时,成果比 Thread.yield 好,从及时性角度成果远好于 Thread.sleep
Thread.onSpinWait();}
}
@Override
public void unlock() {
// 须要 volatile 更新,让其余线程感知到
LOCKED.setVolatile(this, false);
}
}
另一个锁的实现是:
public class TTASLock implements Lock {
private boolean locked = false;
// 操作 locked 的句柄
private static final VarHandle LOCKED;
static {
try {
// 初始化句柄
LOCKED = MethodHandles.lookup().findVarHandle(TTASLock.class, "locked", boolean.class);
} catch (Exception e) {throw new Error(e);
}
}
@Override
public void lock() {while (true) {
// 一般读取 locked,如果被占用,则始终 SPIN
while ((boolean) LOCKED.get(this)) {
// 让出 CPU 资源,这是目前实现 SPIN 成果最好的让出 CPU 的形式,当线程数量远大于 CPU 数量时,成果比 Thread.yield 好,从及时性角度成果远好于 Thread.sleep
Thread.onSpinWait();}
// 胜利代表获取了锁
if (LOCKED.compareAndSet(this, false, true)) {return;}
}
}
@Override
public void unlock() {LOCKED.setVolatile(this, false);
}
}
为了灵活性和对立,咱们两个锁都是应用了句柄,而不是 volatile 变量或者是 AtomicBoolean,因为咱们在这两个锁中会有 volatile 更新,一般读取,以及原子更新;如果读者不习惯,能够应用 AtomicBoolean 近似代替。
接下来咱们应用 JMH 测试这两个锁的性能以及有效性,咱们将一个 int 类型的变量应用多线程加 500 万次,并且应用咱们实现的这两个锁确保并发平安,查看耗时。
// 测试指标为单次调用工夫
@BenchmarkMode(Mode.SingleShotTime)
// 须要预热,排除 jit 即时编译以及 JVM 采集各种指标带来的影响,因为咱们单次循环很屡次,所以预热一次就行
@Warmup(iterations = 1)
// 单线程即可
@Fork(1)
// 测试次数,咱们测试 10 次
@Measurement(iterations = 10)
// 定义了一个类实例的生命周期,所有测试线程共享一个实例
@State(value = Scope.Benchmark)
public class Test {
private static class ValueHolder {int count = 0;}
// 测试不同线程数量
@Param(value = {"1", "2", "5", "10", "20", "50", "100"})
private int threadsCount;
@Benchmark
public void testTASLock(Blackhole blackhole) throws InterruptedException {test(new TASLock());
}
@Benchmark
public void testTTASLock(Blackhole blackhole) throws InterruptedException {test(new TTASLock());
}
private void test(Lock lock) throws InterruptedException {ValueHolder valueHolder = new ValueHolder();
Thread[] threads = new Thread[threadsCount];
// 测试累加 5000000 次
for (int i = 0; i < threads.length; i++) {threads[i] = new Thread(() -> {for (int j = 0; j < 5000000 / threads.length; j++) {lock.lock();
try {valueHolder.count++;} finally {lock.unlock();
}
}
});
threads[i].start();}
for (int i = 0; i < threads.length; i++) {threads[i].join();}
if (valueHolder.count != 5000000) {throw new RuntimeException("something wrong in lock implementation");
}
}
public static void main(String[] args) throws RunnerException {Options opt = new OptionsBuilder().include(Test.class.getSimpleName()).build();
new Runner(opt).run();}
}
后果是:
Benchmark (threadsCount) Mode Cnt Score Error Units
Test.testTASLock 1 ss 10 0.087 ± 0.012 s/op
Test.testTASLock 2 ss 10 0.380 ± 0.145 s/op
Test.testTASLock 5 ss 10 0.826 ± 0.310 s/op
Test.testTASLock 10 ss 10 1.698 ± 0.563 s/op
Test.testTASLock 20 ss 10 2.897 ± 0.699 s/op
Test.testTASLock 50 ss 10 5.448 ± 2.513 s/op
Test.testTASLock 100 ss 10 7.900 ± 5.011 s/op
Test.testTTASLock 1 ss 10 0.083 ± 0.003 s/op
Test.testTTASLock 2 ss 10 0.353 ± 0.067 s/op
Test.testTTASLock 5 ss 10 0.543 ± 0.123 s/op
Test.testTTASLock 10 ss 10 0.743 ± 0.356 s/op
Test.testTTASLock 20 ss 10 1.437 ± 0.161 s/op
Test.testTTASLock 50 ss 10 1.926 ± 0.769 s/op
Test.testTTASLock 100 ss 10 2.428 ± 0.878 s/op
能够看出,这两个锁尽管逻辑上是等价的,然而性能上确有很大差别,并且随着线程的减少,这个差别越来越大,如下图所示:
本章为了解释这个问题,会涵盖要写出高效的并发算法和数据结构所须要的对于多处理器系统结构的大多数常识。咱们会思考如下这些组件:
- 处理器 (processors):执行软件线程(threads)的设施。通常状况下,线程数远大于处理器个数,处理器须要切换,即运行一个线程一段时间之后切换到另一个线程运行。
- 互连线 (interconnect):连贯处理器与处理器或者处理器与内存。
- 内存 (memory):具备档次的存储数据的组件,包含多层高速缓存和速度绝对较慢的大容量主内存。了解这些档次之间的互相关系是了解许多并发算法理论性能的根底。