Concurrent Synchronizer Framework（3）

?

这章来自3.3《Queues》。

?

???????? 这个framework的核心是排队阻塞线程。这里的排队限制为先进先出，因此，framework不支持基于优先级的排队。

???????? 对于同步队列使用非阻塞队列，从而不用构造一些low-level的锁这一个选择，几乎是没有争论的。有两个选择，

CLH Lock和MCS Lock。原始的CLH Lock仅仅使用自旋锁，但是相对于MSC Lock，它更容易处理cancel和timeout，所以选择了CLH Lock。最后设计出来的变种CLH Lock和原始的CLH Lock有较大的差别，需要描述一下。

?

???????? 一个CLH Queue看起来不太像一个queue，因为它的出队和入队操作像是一个锁（原文：because its enqueuing and dequeuing operations are intimately tied to its uses as a lock）。它是一个实用两个原子更新字段的linked queue。分别是head和tail，在初始化时指向同一个node。

?

???????? 一个新的node入队时是一个原子操作：

???????? do { pred = tail;} while(!tail.compareAndSet(pred, node));

?

???????? 每个node的release 状态保存在它的前驱node中，所以它的自旋锁的自旋操作：

???????? while (pred.status != RELEASED) ; // spin

????????

出队操作在自旋后，要把head设置为node。

head = node;

?

CLH Lock的优点：出队和入队都非常快；lock-free；无障碍（obstruction free，即使是在竞争情况下，总有一个线程赢得竞争）；快速检测是否有其他线程在等待（比较head是否等于tail）；release 状态是分散的，避免了内存竞争。

?

在原始版本的CLH Lock，nodes是没有被链起来的（见《线程锁系列（1）：CLH Lock》）。但是如果每个node维护一个指向前驱的指针，CLH Lock可以处理timeout和一些cancel操作：如果一个node的前驱被cancle，这个node可以上滑使用前驱的状态字段。

?

为了使CLH Queues适合blocking synchronizers，一个额外的主要改动是提供node快速定位它的后继。在自旋锁里，node只需要改变自身状态，后继会在下一个自旋发现状态的改变。所以链接到后继是不必要的。但是在blocking synchronizers里，node需要明确的唤醒（unpark)）它的后继。

?

一个AbstractQueuedSynchronizer queue node包含指向后继和前驱的指针。但是对于双向链表，没有使用compareAndSet，合适的lock-free，原子插入的算法。对指向后继的指针赋值不是插入操作的原子的一部分。它只是被简单的赋值：pred.next = node。插入后，会反映在所有的用法上。指向后继的指针只是一个优化的路径，如果一个后继好像不存在（可能被cancel），会定位到列表的tail，通过前驱指针，向上遍历，精确的检测是否有后继。

?

第二个变动是在每个node里使用一个状态字段去控制阻塞，而不是自旋。在framework里，一个排队的线程调用acquire，只有在通过了子类实现的tryAcquire才能返回。一个单独的“release”位是不能满足的。控制方法保证了只有在队里头部的活动线程才允许调用tryAcquire；在某些情况，线程可能acquire失败，重新block。这个保证不需要额外的状态，只需要检测node的前驱是否是head。和自旋锁不一样，通过复制减少了读head的内存冲突（And unlike the case of spinlocks, there is not enough memory contention reading head to warrant replication）。但是，cancle的状态需要在状态位描述。

?

Queue nodes 状态字段也会被用来避免不必要的park和unpark。当调用方法相当的快，它们有可能可以避免在jvm和os中切换（park和unpark需要在jvm和os中切换）。一个线程在调用park前，会把状态位设为“single me”，在park前再一次的检测状态位。一个释放lock的线程会清除这个状态位。这避免了不必要的block，通常来说，引入的额外开销也是值得的，特别是锁类，等待下一个获得线程的锁浪费了时间，加重竞争。这也避免了一个释放线程需要决定它的后继，除非后继状态位被设成“single me”。这可以消除后继指针为null的遍历开销，但是如果是cancel，开销仍然无法避免。

?

framework里的CLH Locks和其他语言实现的CLH Locks的最大不同可能是nodes的回收利用依赖于GC。它减少了复杂性和开销。但是即使依赖于GC，当指针被确定不需要再使用，仍然需要把它们置null，这通常发生在出队。否则仍然是可达的，导致不能被回收。

?

另外还有一些微小的改动，包括head使用的假节点延迟初始化。

?

忽略这些细节，一个基本的acquire实现（独占的，不可中断的，没有超时的）大体如下：

?

if (!tryAcquire(arg)) {
	node = create and enqueue new node;
	pred = node's effective predecessor;
	while (pred is not head node || !tryAcquire(arg)) {
		if (pred's signal bit is set)
			park();
		else
			compareAndSet pred's signal bit to true;
			pred = node's effective predecessor;
	}
		head = node;
}

?

Release操作如下：

?

if (tryRelease(arg) && head node's signal bit is set) {
	compareAndSet head's signal bit to false;
	unpark head's successor, if one exists
}

?

对于acquire，循环的次数依赖于tryAcquire,如果不考虑cancel和分摊park等os的线程调度，acquire和release都是O（1）操作。

?

为了支持cancel，在acquire循环中，需要检查超时和中断。一个由超时或中断引起的被取消的线程需要设置它的状态和unpark它的后继，所以它可能重置指针。随着cancel，决定前驱后继和重置状态，可能会包含O（n）的遍历（n是Queue的长度）。因为一个已经被cancle的线程永远不可能再次阻塞，链接和状态需要被迅速的重建。