本系列是 The art of multipropcessor programming 的读书笔记,在原版图书的基础上,结合 OpenJDK 11 以上的版本的代码进行理解和实现。并根据个人的查资料以及理解的经历,给各位想更深入理解的人分享一些个人的资料
之前实现的基于回退的锁,除了通用性以外,还有如下两个问题:
可以将线程放入一个队列,来解决上面两个问题:
最后,通过队列,也是实现了 FIFO 的公平性。
我们通过一个数组来实现队列的功能,其流程是:
其源码是:
public class ArrayLock implements Lock {
private final ThreadLocal<Integer> mySlotIndex = ThreadLocal.withInitial(() -> 0);
private final AtomicInteger tail = new AtomicInteger(0);
private final boolean[] flags;
private final int capacity;
public ALock(int capacity) {
this.capacity = capacity;
this.flags = new boolean[capacity];
}
@Override
public void lock() {
int current = this.tail.getAndIncrement() % capacity;
this.mySlotIndex.set(current);
while (!this.flags[current]) {
}
}
@Override
public void unlock() {
int mine = this.mySlotIndex.get();
this.flags[mine] = false;
this.flags[(mine + 1) % capacity] = true;
}
}
在这个源码实现上,我们还可以做很多优化:
Thread.onSpinWait()
。this.flags[current]
这个读取数组的操作需要放在循环外面,防止每次读取数组的性能消耗。优化后的源码是:
public class ArrayLock implements Lock {
private final ThreadLocal<Integer> mySlotIndex = ThreadLocal.withInitial(() -> 0);
private final AtomicInteger tail = new AtomicInteger(0);
private final ContendedBoolean[] flags;
private final int capacity;
private static class ContendedBoolean {
//通过注解实现缓存行填充
@Contended
private boolean flag;
}
//通过句柄实现 volatile 更新
private static final VarHandle FLAG;
static {
try {
//初始化句柄
FLAG = MethodHandles.lookup().findVarHandle(ContendedBoolean.class, "flag", boolean.class);
} catch (Exception e) {
throw new Error(e);
}
}
public ArrayLock(int capacity) {
capacity |= capacity >>> 1;
capacity |= capacity >>> 2;
capacity |= capacity >>> 4;
capacity |= capacity >>> 8;
capacity |= capacity >>> 16;
capacity += 1; //大于N的最小的2的N次方
this.flags = new ContendedBoolean[capacity];
for (int i = 0; i < this.flags.length; i++) {
this.flags[i] = new ContendedBoolean();
}
this.capacity = capacity;
this.flags[0].flag = true;
}
@Override
public void lock() {
int current = this.tail.getAndIncrement() & (capacity - 1);
this.mySlotIndex.set(current);
ContendedBoolean contendedBoolean = this.flags[current];
while (!contendedBoolean.flag) {
Thread.onSpinWait();
}
}
@Override
public void unlock() {
int mine = this.mySlotIndex.get();
FLAG.setVolatile(this.flags[mine], false);
FLAG.setVolatile(this.flags[(mine + 1) & (capacity - 1)], true);
}
}
但是,即使有这些优化,在高并发大量锁调用的时候,这个锁的性能依然会很差。这个我们之后会分析优化。