并发编程的艺术07非阻塞同步演进
前言
不知道大家有没有发现几乎每个专业领域中都充斥着很多抽象的专业名词，如果没有相关的基础知识很难知道这些专业名词是什么意思，就比如说我们的这个标题“粗粒度同步”。川建国听了想骂娘，什么是TMD“粗粒度同步”？最近我对理查德·费曼做了一些了解，他在阐述一个事物的时候强调要用通俗易懂的语言，让人容易理解的方式而不是专业名词满天飞。对于一个事物能够给一个孩子或者是一个对此不了解的外行人讲明白就说明你自己是真的明白了。所以我们的技术类文章也会力求用通俗易懂的方式把事物讲的让人更容易理解，而不是使用大量的专业名词。
本章内容我们将以一个集合作为例子，集合中有 add , remove ,contains 三个函数。
add(x) 函数将元素 x 添加到集合中，当且仅当集合中原先不存在 x 时返回 true。
remove(x) 函数将元素 x 从集合中删除，当且仅当集合中原来存在 x 的时候返回 true 。
当且仅当集合中包含 x 元素时 contains(x) 返回 true。
链表中除了包含集合元素的常规节点外，还使用了两个称为 head ， tail 的哨兵节点，作为链表的第一个节点和最后一个节点。哨兵节点不能被添加，删除，或查找，它们的 key 值分别为整数值的最小和最大值，也就是说 key 值越大的元素排序越靠后。
粗粒度同步
“粗粒度同步”这个专业名词我们先把它拆解为两部分来解释，一个是“粒度”，另一个是“同步”。
上面这两张图展示了“粒度”的概念，第一张图两条黄色竖线之间间隔较大，对黑线分割的次数较少。第二张图两条黄色竖线之间的间隔较小，对黑线分割的次数较多。第一张图展示了粗粒度。第二张图展示了细粒度。
“同步”可以理解为“保持一致”，“同步”这个词实际上是强调结果，就是说要求最终的结果是一致的。少了主语，比如说生活中我们会听到有人说几个不同的部门要保证工作同步进行。这里他所指的是工作进度的同步，所以完整的描述是“工作进度同步”。而我们在并发编程系列文章中所讲的同步都是“数据同步”。也就是要保持数据的一致性。
举一个例子高铁，飞机上的洗手间，通常情况下只允许一个人进入。在一位乘客看到洗手间的门时打开的，并且确认里面没有人时。这位乘客进入后就会立刻关上门，这位乘客出来时就会打开门。这就是粗粒度同步的场景。
回到计算机的世界中来，粗粒度同步是一种策略，准确的说是“粗粒度”是一种方法，“同步”是最终我们需要达成的结果。它的实现方式简单：首先构造这个类的顺序实现（单线程实现），然后增加一个可扩展的锁域，并保证每个方法调用都应该获取和释放这个锁。
public class CoarseList<T> { private class Node {
T item;
int key;
Node next;
Node(T item) {
this.item = item;
this.key = item.hashCode();
}
Node(int key) {
this.item = null;
this.key = key;
}
}
private Node head = new Node(Integer.MIN_VALUE);
private Node tail = new Node(Integer.MAX_VALUE);
private Lock lock = new ReentrantLock();
public CoarseList() {
head.next = this.tail;
}
public boolean add(T item) {
Node pred, curr;
int key = item.hashCode();
lock.lock();
try {
pred = head;
curr = pred.next;
while (curr.key < key) {
pred = curr;
curr = curr.next;
}
if (key == curr.key) {
return false;
} else {
Node node = new Node(item);
node.next = curr;
pred.next = node;
return true;
}
} finally {
lock.unlock();
}
}
public boolean remove(T item) {
Node pred, curr;
int key = item.hashCode();
lock.lock();
try {
pred = this.head;
curr = pred.next;
while (curr.key < key) {
pred = curr;
curr = curr.next;
}
if (key == curr.key) {
pred.next = curr.next;
return true;
} else {
return false;
}
} finally {
lock.unlock();
}
}
public boolean contains(T item) {
Node pred, curr;
int key = item.hashCode();
lock.lock();
try {
pred = head;
curr = pred.next;
while (curr.key < key) {
pred = curr;
curr = curr.next;
}
return (key == curr.key);
} finally {
lock.unlock();
}
}
}
链表本身具有一个锁，每个函数调用都必须要获取这个锁。该算法最大的优点点就是其显而易见的正确性。所有函数只有在获取锁时才能对链表进行操作，所以执行实际上是串行的。CoarseList 满足与它的锁相同的演进条件：如果 lock 是无饥饿的，则实现也是无饥饿的。如果竞争不激烈，那么该算法是实现链表的一种很好的方式。然而如果竞争激烈，则即使锁本身非常好，线程也会延迟等待其他线程。
粗粒度同步的效果是很好的，但是在某些重要场合却并非如此。一个类中如果使用单一的锁来协调控制所有的函数调用，即使锁本身是可以扩展的情形下也并非总是可扩展的。当并发程度较低时，粗粒度同步效果很好，但如果有很多个线程试图同时存取一个对象，这个对象将变成一个顺序的瓶颈，从而使得线程必须排队等待。
细粒度同步
现在我们希望提高函数的并发性，显然粗粒度同步的方式已经不能满足我们的需求，这时候我们考虑使用细粒度同步的方式。在粗粒度的方式中，我们是锁定了整个函数，而在细粒度方式中我们把锁定目标改为单个节点。
给每个节点增加一个 lock 以及对应的lock() ，unlock() 函数。当线程访问链表的时候，若它是第一个访问节点的线程，则锁住被访问的节点，在随后的某个时刻再释放锁。这种细粒度的锁机制允许并发线程以流水线的方式遍历链表。
注意这种方式需要同时获得pred，curr节点的锁，因为在进行操作过程中对这两个节点都会产生影响，如果不同时锁主这两个节点就无法保障是否有其他线程对其中的某一个节点做了操作。这就类似于在公路上开车的时候，你需要同时注意你前面车的动向和后面车的动向，因为它们的任何一方的动作都会对你产生影响。通常这种状况被称为耦合锁：
考虑两个节点a,b,其中a指向b。在对b上锁之前对a进行解锁是不安全的，因为a被解锁后另一个线程很可能将b从链表中删除(改变 a.next 域的指向即可)。然而线程必须以一种“交叉手”的方式来获取锁：除了初始的head哨兵节点外，只有在获取到了pred节点的锁时，才能获得curr节点的锁。这种锁协议有时称为耦锁耦合。
public class FineList<T> { private class Node {
T item;
int key;
Node next;
Lock lock;
Node(T item) {
this.item = item;
this.key = item.hashCode();
this.lock = new ReentrantLock();
}
Node(int key) {
this.item = null;
this.key = key;
this.lock = new ReentrantLock();
}
void lock() {lock.lock();}
void unlock() {lock.unlock();}
}
private Node head = new Node(Integer.MIN_VALUE);
public FineList() {
head.next = new Node(Integer.MAX_VALUE);
}
public boolean add(T item) {
int key = item.hashCode();
head.lock();
Node pred = head;
try {
Node curr = pred.next;
curr.lock();
try {
while (curr.key < key) {
pred.unlock();
pred = curr;
curr = curr.next;
curr.lock();
}
if (curr.key == key) {
return false;
}
Node newNode = new Node(item);
newNode.next = curr;
pred.next = newNode;
return true;
} finally {
curr.unlock();
}
} finally {
pred.unlock();
}
}
public boolean remove(T item) {
Node pred = null, curr = null;
int key = item.hashCode();
head.lock();
try {
pred = head;
curr = pred.next;
curr.lock();
try {
while (curr.key < key) {
pred.unlock();
pred = curr;
curr = curr.next;
curr.lock();
}
if (curr.key == key) {
pred.next = curr.next;
return true;
}
return false;
} finally {
curr.unlock();
}
} finally {
pred.unlock();
}
}
public boolean contains(T item) {
Node last = null, pred = null, curr = null;
int key = item.hashCode();
head.lock();
try {
pred = head;
curr = pred.next;
curr.lock();
try {
while (curr.key < key) {
pred.unlock();
pred = curr;
curr = curr.next;
curr.lock();
}
return (curr.key == key);
} finally {
curr.unlock();
}
} finally {
pred.unlock();
}
}
}
FineList 算法是无饥饿的，但对这个特性的证明比在粗粒度情形要难。假设每一个锁都是无饥饿的。由于所有函数以相同的顺着链表的次序获取锁，所以不会发生死锁。如果线程A试图锁定head并最终成功，从这个点开始，因为没有死锁发生，由A之前的其他线程获取的链表中的锁最终都会被释放，线程A将成功获取pred和curr节点的锁。
乐观同步
我们先来与一个例子来理解“乐观同步”这个术语中的“乐观”的意思。小明和小华约定好了周末去小华家玩。周末到了小明想反正和小华都约定好了，他就在早上出发很快就到了小华家，但是敲门却没人应答，这时候他给小华打了电话询问，小华早上出去晨练了。于是小明白白浪费了时间。在这个例子中，如果小明把打电话确认小华是否在家的动作提前，就不会出现到了门口进不去门的情况。小明认为反正已经约定好了我只要去了小华家里小华就会在家。这就是小明乐观的心态，他把整个过程想的太完美了处于自己的角度。
虽然我们用细粒度同步对粗粒度同步做了改进，但是依然存在着频繁的获取锁，释放锁，并且在遍历链表的时候必须是获取了锁的。细粒度同步仍然可能出现长时间排队等待获取锁和释放锁的情况。而且，访问链表中不同部分的线程仍然可能互相阻塞。例如，一个正在删除链表中第二个节点的线程将会阻塞所有试图查找后继节点的线程。
现在我们又希望提高我们代码的并发性，那么能不能在集合中查找元素过程中不需要获取锁呢，而在找到节点之后再对节点进行加锁，然后确认锁住的节点是否正确（是否还在这个集合中，或者在集合中的位置是否发生了改变，因为该节点很可能已经被其他线程改变）。
下面这个故事带给我们一些启示：
一个旅行者在国外的一个城镇搭乘一辆出租车。出租车司机加速闯过了一个红灯，这位旅行者惊恐的问道："为什么这么做？"司机回答说："别担心，我是个老手。"司机又加速闯过了几个红灯。这位旅行者几乎崩溃，再一次焦虑的抱怨。司机回答道："放松点，是一个老手在开车。"突然绿灯亮了，司机急忙刹车，出租车打转停住了。旅行者大喊着跳出出租车："为什么在绿灯亮时停车？"司机回答道："太危险了，可能是另外一个老手正在穿过路口。"
遍历一个动态变化的基于锁的数据结构而又不用锁需要慎重的考虑（还有其他老手线程也在这里）。必须要使用某种形式的验证并保证无干扰性。
乐观同步这种技术只有在成功次数高于失败次数时才有价值，试想如果验证总是失败的话也就意味着一直在浪费时间做无用功。
注意在 OptimisticList 中 validate() 函数是通过遍历链表来验证节点的正确性的。
public class OptimisticList<T> { private class Node {
T item;
int key;
Node next;
Lock lock;
Node(T item) {
this.item = item;
this.key = item.hashCode();
this.lock = new ReentrantLock();
}
Node(int key) {
this.item = null;
this.key = key;
this.lock = new ReentrantLock();
}
void lock() {lock.lock();}
void unlock() {lock.unlock();}
}
private Node head = new Node(Integer.MIN_VALUE);
public OptimisticList() {
head.next = new Node(Integer.MAX_VALUE);
}
public boolean add(T item) {
int key = item.hashCode();
while (true) {
Node pred = this.head;
Node curr = pred.next;
while (curr.key <= key) {
pred = curr; curr = curr.next;
}
pred.lock(); curr.lock();
try {
if (validate(pred, curr)) {
if (curr.key == key) {
return false;
} else {
Entry entry = new Entry(item);
entry.next = curr;
pred.next = entry;
return true;
}
}
} finally {
pred.unlock(); curr.unlock();
}
}
}
public boolean remove(T item) {
int key = item.hashCode();
while (true) {
Node pred = this.head;
Node curr = pred.next;
while (curr.key < key) {
pred = curr; curr = curr.next;
}
pred.lock(); curr.lock();
try {
if (validate(pred, curr)) {
if (curr.key == key) {
pred.next = curr.next;
return true;
} else {
return false;
}
}
} finally {
pred.unlock(); curr.unlock();
}
}
}
public boolean contains(T item) {
int key = item.hashCode();
while (true) {
Node pred = this.head;
Node curr = pred.next;
while (curr.key < key) {
pred = curr; curr = curr.next;
}
try {
pred.lock(); curr.lock();
if (validate(pred, curr)) {
return (curr.key == key);
}
} finally {
pred.unlock(); curr.unlock();
}
}
}
private boolean validate(Node pred, Node curr) {
Node node = head;
while (node.key <= pred.key) {
if (node == pred)
return pred.next == curr;
node = node.next;
}
return false;
}
}
惰性同步
有时候将较难的工作推迟完成也是一种好的处理方式。例如，从一个数据结构中删除某个部分可以分为两个阶段：通过设置标识位来逻辑删除这个部分，然后再通过从数据结构中移除这部分来物理删除。
当不用锁遍历两次链表的代价比使用锁遍历一次链表的代价小许多时，OptimisticList 实现的效果非常好。这种算法的缺点之一是 contains() 函数在遍历时需要获得锁，这一点并不令人满意，原因在于对 contains() 的调用要比对其他函数的调用频繁得多。
对该算法进行改进，使得 contains() 调用是无等待的，同时 add() , remove() 函数即使在被阻塞的情况下也只需要遍历一次链表。对每个节点增加一个布尔类型的 marked 域，用于说明该节点是否在集合中。现在遍历不再需要锁定目标节点，也没必要通过重新遍历整个链表来验证节点是否可达。而是由算法维护一个不变式：所有未被标记的节点必是可达的。如果遍历链表的线程没有找到节点或是发现节点被标记，则该元素值不再集合中。总之，contains() 只需要一次无等待的遍历。
public class LazyList<T> { private class Node {
T item;
int key;
Node next;
Lock lock;
boolean marked;
Node(T item) {
this.item = item;
this.key = item.hashCode();
this.lock = new ReentrantLock();
this.marked = false;
}
Node(int key) {
this.item = null;
this.key = key;
this.lock = new ReentrantLock();
this.marked = false;
}
void lock() {lock.lock();}
void unlock() {lock.unlock();}
}
public boolean add(T item) {
int key = item.hashCode();
while (true) {
Node pred = this.head;
Node curr = head.next;
while (curr.key < key) {
pred = curr; curr = curr.next;
}
pred.lock();
try {
curr.lock();
try {
if (validate(pred, curr)) {
if (curr.key == key) {
return false;
} else {
Node node = new Node(item);
node.next = curr;
pred.next = node;
return true;
}
}
} finally {
curr.unlock();
}
} finally {
pred.unlock();
}
}
}
public boolean remove(T item) {
int key = item.hashCode();
while (true) {
Node pred = this.head;
Node curr = head.next;
while (curr.key < key) {
pred = curr; curr = curr.next;
}
pred.lock();
try {
curr.lock();
try {
if (validate(pred, curr)) {
if (curr.key != key) {
return false;
} else {
curr.marked = true;
pred.next = curr.next;
return true;
}
}
} finally {
curr.unlock();
}
} finally {
pred.unlock();
}
}
}
public boolean contains(T item) {
int key = item.hashCode();
Node curr = this.head;
while (curr.key < key)
curr = curr.next;
return curr.key == key && !curr.marked;
}
private boolean validate(Node pred, Node curr) {
return !pred.marked && !curr.marked && pred.next == curr;
}
}
现在所有函数不用锁就可以遍历链表了。add() , remove() 函数和以前一样锁住pred和curr节点，然而验证不再需要重新遍历整个链表来确定一个节点是否还在集合中。对于contains() 由于节点在被物理删除以前必须要作标记，所以验证只需要确认curr还没被标记。对于插入和删除，由于pred节点是被修改的节点，所以必须验证pred节点本身没有被标记且它仍然指向节点curr。逻辑删除需要对抽象映射做一点修改：当且仅当一个数据元素被一个未标记的可达节点指向时，该数据元素在集合中。需要注意的是，可达节点的路径中可能包含已标记的节点。正如在 OptimisticList 算法中一样，add() , remove() 函数不是无饥饿的，因为有可能会被其他正在进行修改的线程延迟。
惰性同步的优点之一就是能够将类似于设置一个flag这样的逻辑操作与类似删除节点的链接这种对结构的物理改变相分开。这里给出的例子比较简单，其原因在于一个时刻只允许解除一个节点的链接。然而通常情况下，延迟操作可以是批处理方式进行的，且某个方便的时候再懒惰的进行处理，从而降低了对结构进行物理修改的整体破裂性。
惰性同步的主要缺点是 add() ,remove() 调用是阻塞的：如果一个线程延迟，那么其他线程也将延迟。
非阻塞同步
有时候我们可以完全的消除锁，而是依靠类似 test-and-set 的内置原子操作进行同步。
通过惰性同步我们了解到在物理删除链表中某个节点之前将该节点标记为逻辑删除的思想有时候是非常有益的。接下来我们研究如何扩展这种思想以完全消除锁，从而使add(),remove(),contains()都变成非阻塞的。add(),remove() 是无锁的，contains()是无等待的。一种想法是使用 test-and-set 来改变next域的值，但是这种方法是不适用的。下面我们来举例说明为什么简单的 test-and-set 是不适用的：
假设线程A准备删除链表中的节点a,同时线程B准备插入节点b。
线程A对a节点的删除使用CAS是这样的：head.next.cas(a , c)。
线程B对b节点的插入使用CAS是这样的：a.next.cas(c , b)。
无论A，B线程的那个CAS先执行完成都会导致节点a被删除了，但是节点b却没有被插入的链表中。原因在于虽然a节点被移除出了链表但是仍然有线程对它的next域进行了操作。即使a被移除出了链表但是a.next亦然指向了c ，所以 a.next.cas(c , b) 会返回 true。
显然，需要一种方式来确保在节点被逻辑或物理删除后，该节点的域不能再被修改。所采用的方法就是将节点的next域和marked域看作是单个原子单位：当marked域为true时，对next的任何修改都将失败。
可以让每个节点的next域为一个 AtomicMarkableReference<Node>。线程A通过设置节点next域中的标志位来逻辑删除curr，和其他正在执行add()或remove()的线程共享物理删除。那么什么叫共享物理删除？就是当每个线程遍历链表时，通过物理删除（使用CAS）所有被标记的节点来清理链表。也就是说在遍历链表的过程中如果发现被标记的节点，就会立刻对这些节点执行物理删除。
AtomicMarkableReference 维护对象引用以及可以原子更新的标记位：
Window对象是一种具有pred，curr域的结构。find()函数以一个head节点和一个key值a作为参数，查找并让pred指向具有比a小的最大key值节点，让curr指向大于等于a的最小key值的节点。当线程遍历链表时，会检查节点是否被标记，如果被标记则会通过CAS的方式物理删除节点。这个调用既检查域的引用又要检查布尔标记值，如果任意一个值发生了变化都会失败。如果发生失败将从head节点重新遍历链表。
public class LockFreeList<T> {
private class Node {
T item;
int key;
AtomicMarkableReference<Node> next;
Node(T item) {
this.item = item;
this.key = item.hashCode();
this.next = new AtomicMarkableReference<Node>(null, false);
}
Node(int key) { // sentinel constructor
this.item = null;
this.key = key;
this.next = new AtomicMarkableReference<Node>(null, false);
}
}
class Window {
public Node pred;
public Node curr;
Window(Node pred, Node curr) {
this.pred = pred; this.curr = curr;
}
}
Node head;
public LockFreeList() {
this.head = new Node(Integer.MIN_VALUE);
Node tail = new Node(Integer.MAX_VALUE);
while (!head.next.compareAndSet(null, tail, false, false));
}
public boolean add(T item) {
int key = item.hashCode();
boolean splice;
while (true) {
Window window = find(head, key);
Node pred = window.pred, curr = window.curr;
if (curr.key == key) {
return false;
} else {
// splice in new node
Node node = new Node(item);
node.next = new AtomicMarkableReference(curr, false);
if (pred.next.compareAndSet(curr, node, false, false)) {
return true;
}
}
}
}
public boolean remove(T item) {
int key = item.hashCode();
boolean snip;
while (true) {
Window window = find(head, key);
Node pred = window.pred, curr = window.curr;
if (curr.key != key) {
return false;
} else {
// snip out matching node
Node succ = curr.next.getReference();
snip = curr.next.attemptMark(succ, true);
if (!snip)
continue;
pred.next.compareAndSet(curr, succ, false, false);
return true;
}
}
}
public boolean contains(T item) {
int key = item.hashCode();
Node curr = this.head;
while (curr.key < key)
curr = curr.next;
return curr.key == key && !curr.marked;
}
public Window find(Node head, int key) {
Node pred = null, curr = null, succ = null;
boolean[] marked = {false}; // is curr marked?
boolean snip;
retry: while (true) {
pred = head;
curr = pred.next.getReference();
while (true) {
succ = curr.next.get(marked);
while (marked[0]) { // replace curr if marked
snip = pred.next.compareAndSet(curr, succ, false, false);
if (!snip) continue retry;
curr = pred.next.getReference();
succ = curr.next.get(marked);
}
if (curr.key >= key)
return new Window(pred, curr);
pred = curr;
curr = succ;
}
}
}
}
通过基于链表的锁的发展变化，在这个演进过程中，锁的粒度和使用频率逐步减小，最后得到一个无阻塞的链表。从 LazyList 最终到 LockFreeList ,为并发程序设计者提供了一些直接可用的设计策略。像乐观同步和惰性同步这样的一些方法，在设计更为复杂的数据结构时也经常用到。
一方面 LockFreeList 算法能够保证在面对任意的延迟时，线程可以继续演进。当然，这种强演进保证需要一些代价：
对引用和布尔标记的原子修改需要额外的性能损耗。
当add()和remove()遍历链表的时候，它们必须参与对已经逻辑删除节点的并发清理，从而导致线程之间发生争用，即使在每个线程试图修改的节点附近没有发生改变，有时候也会使线程重新遍历链表。
另一方面基于锁的惰性链表在面对任意延迟时并不保证演进：它的 add() 和 remove() 函数正在阻塞。但是，与无锁算法不同，它并不要求每个节点有原子的可标记引用，也不需要遍历链表来清除逻辑删除的节点。它们顺着链表前进，不用考虑被标记的节点。
那一种方法更加适用取决于应用。最后，对诸如任意线程延迟的可能，add() 和 remove() 调用的相对频率，实现原子地可标记引用的代价等因素综合平衡，决定了是否使用锁以及使用什么粒度的锁。
往期精彩回顾
并发编程的艺术01-面试中被问到并发知识答不上来？
并发编程的艺术02-过滤锁算法
并发编程的艺术03-Bakery互斥算法
并发编程的艺术04-TAS自旋锁
并发编程的艺术05-队列自旋锁
并发编程的艺术06-复合&层次自旋锁
关注微信公众号「黑帽子技术」
第一时间浏览技术干活文章
以上是 并发编程的艺术07非阻塞同步演进 的全部内容， 来源链接： utcz.com/z/514932.html
