接上一篇：http://caoyaojun1988-163-com.iteye.com/admin/blogs/1279097

 

3.3 队列

     框架的核心是维护阻塞线程的队列，队列的策略是先进先出（FIFO），因此，该框架不支持基于优先级的同步

      一直以来，对于同步队列的最合适的选择是无阻塞的数据结构有不小的争议，这种数据结构本身并不需要使用较低级别的锁来构造。其中有两个主要的观点：Mellor-Crummey与Scott的变体锁(MCS) [9]和 Craig, Landin, 和Hagersten的变体锁 (CLH)[5][8][10].从历史上看，CLH锁仅仅被用于自旋锁，然而，在同步框架中使用它们比MCS似乎更适合，因为他们更容易处理取消和超时，因此我们选择它作为基础。虽然最终的设计远远偏离了CLH的设计结构；

     CLH队列与经典的队列不同，其入队和出队操作与使用锁是紧密联系在一起的。它是一个链表，通过两个可原子更新的节点头部和尾部访问队列，双方最初都指向一个虚拟节点；

     一个新的节点入队列的时候，使用下面的原子操作：

 

 

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

 

 

     每个节点的释放状态域保存其前一个节点的地址。所以，一个自旋锁（spinlock）的“自旋”的样子如下：

 

 

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

 

 

     当自旋简单的设置了head域指向node时，出队列（dequeue）操作如下：

 

 

head = node;

     CLH锁的优势是入队和出队速度快，无锁，并畅通无阻（即使在竞争的情况下，插入操的线程永远获得执行的权限），并且在检测是否有线程在排队是很快（只需要检测头尾是否相同）、释放状态是分散的，可以减少内存冲突；

 

     CLH锁的原始版本并不是双向连接。自旋锁里，PRED变量作为一个域来保存。然而， Scott 和Scherer[10]展示了，通过明确地维护节点里的pre域，CLH锁是可以处理超时和其他形式的取消的。如果一个节点的前一个节点被取消，该节点可以滑动使用前一个节点的状态域；

     要使用CLH队列构建阻塞同步器，主要的修改点是：一个节点必须提供一种有效的方式找到下一个节点。自旋锁的时候，由于仅仅在它被下一个节点通知的时候在改变它的状态；所以找个下一个节点的链接是不必要的；但在阻塞同步器中，一个节点需要明确地唤醒（unpark）它的下一个节点。

     AbstractQueuedSynchronizer队列节点包含指向下一个节点的域。但因为没有合适的技术可以对双向链表节点实现无锁的原子插入，即便使用compareAndSet。所以这个连接的操作并不包含在原子插入的操作里面;在插入操作后，它被简单地赋值，操作如下：

 

pred.next = node;

找到下一节点的路径只是作为一个优化的路径。如果一个节点的下一个节点通过next域判断不存在（或者取消），总是从列表的尾部开始使用PRED域做反向遍历准确检查是否真的不存在。

 

     第二个修改点是使用每个节点的状态域来控制阻塞而不是自旋。在同步框架中，一个队列中的线程，仅仅在它通过了一个定义在具体子类中tryAcquire方法，获取到锁才返回；这样仅仅一个“释放”位就不够了。同时仍然需要控制，以确保活动线程只有当它在队列的头部是才能调用tryAcquire;虽然在这种情况下，它任然可能会获取失败，并（重新）阻塞。这个可以通过检查当前节点的前一个节点是头节点来确认，而不需要查看每个节点的状态标志；与自旋锁不同的是，读头节点操作没有很多内存冲突。当然，取消状态仍然必须保存在状态域里面。

     队列节点的状态域也用于避免不必要的park和unpark调用。虽然他们可以避免在Java、JVM和操作系统之间交互开销，比阻塞原语快。一个线程调用park之前，先设置一个“信号”位，然后调用park前再次重新检查同步和节点状态。一个释放线程清除状态。这样可以减少无谓地尝试，这些block操作的开销是不值得的，特别是浪费时间去与其他竞争线程竞争获取锁，同时这也避免了释放线程确定其继任执行者的时间，因为继任者已经设置的信号位；如果信号没有一起被取消，就避免了必须遍历多个节点，直到next域为null的开销。

     也许用于同步框架的CLH变种锁和其他场景之间的主要区别是，它的垃圾回收机制通过管理节点的实现，从而避免了复杂性和开销。然而，当他们永远不会再用到的时候GC还负责讲链接到的域赋值为null，通过简单的出队列操作即可实现，否则，未使用的节点仍然可以访问，致使他们无法收回。

     当然还有一些优化调整，包括延迟初始化：CLH队列在第一次竞争发生时才初始话所需的虚拟节点，这些详细描述在J2SE1.5版本的源代码的文档里。

    忽略这些细节，实现一个具有基本操作（互斥，不可中断，超时）的一般形式是：

 

if (!tryAcquire(arg)) {
    node = create and enqueue new node;//创建一个新的节点，入队列
    pred = node's effective predecessor;//pred 执行当前节点的前一个有效节点
    while (pred is not head node || !tryAcquire(arg)) {//当前一个节点不是头节点或者获取锁失败
        if (pred's signal bit is set)//前一个节点的信号位被设置
            park();//阻塞自己
        else
            compareAndSet pred's signal bit to true;//讲前一个节点的信号量设置位true
       pred = node's effective predecessor;//执行当前节点的前一个有效节点
    }
   head = node;
}

 

 

一个释放操作如下:

 

if (tryRelease(arg) && head node's signal bit is set) {
	compareAndSet head's signal bit to false;//head节点信号位设置位false
	unpark head's successor, if one exists//唤醒head节点的下个节点
}

    循环迭代的次数，取决于tryAcquire性质，因此，在没有取消的情况下，获取和释放的时间都是O（1），跨线程的开销，和任何花费在基于park的OS的线程调度都可以忽略；

 

     对取消操作的支持，主要是需要在每次循环中park操作返回之后检查中断或超时，由于超时或中断被取消的线程负责设置节点的状态，并且unparks它的后继者，所以它可能会重置链接；取消操作，可能会确定的前一个节点和后一个节点，并且重置状态，遍历的时间复杂度是O（N）（其中n是队列长度）。因为一个线程永远不会为取消而被block，所以链接和状态往往很快重新稳定。

 

3.4 条件队列

 

     同步框架提供了一个维护互斥同步的同步器和供Lock接口使用的ConditionObject的类。许多condition对象可能会关联到一个锁对象，提供经典的基于监视器（monitor）风格的等待（await），、唤醒（signal）和唤醒全部（signalAll）的操作，包括超时，以及一些检查和监测方法，

     通过操纵一些设计决策,ConditionObject类可以有效地与其他同步操作相结合。这个类仅仅支持java风格的监视器访问规则，既是仅仅当当前线程的锁的条件满足时操作才是允许的（请参阅[4]替代方案的讨论）；因此，一个ConditionObject关联到ReentrantLock的方式与内置的监视器一样（通过Object.wait等），唯一的不同是方法名称，额外的功能，而事实上，用户可以在每个锁上申明多个条件。

     一个ConditionObject与同步器使用相同的内部队列节点，但它们维护在一个单独的条件队列中；唤醒操作通过从条件队列转移到锁队列来实现；一个线程已经重新获取了锁，不需要唤醒已经唤醒的线程；

     基本等待（await）操作是：

 

create and add new node to condition queue;//新建一个node，添加到条件队列中
release lock;//释放锁
block until node is on lock queue; //阻塞直到node转移到锁队列上
re-acquire lock; //重新获取锁

    唤醒的操作是：

 

 

将条件队列的第一个节点转移到锁队列中；

     因为这些操作只有持有锁的时候才允许，因此可以使用有序链表队列（使用节点的nextWaiter域）维护条件队列；转移操作简单取出条件队列中的第一个节点，然后使用CLH的插入操作添加到锁队列；

 

     实现这些操作最复杂的地方在于处理因为await操作超时或Thread.interrupt而引起的取消操作。取消操作和唤醒几乎在同时发生，产生一个竞争，其结果符合内置监视器的规范；在修订JSR133的时候，要求如果一个中断信号在唤醒之前发生，那么等待的方法必须重新获取锁后，抛出InterruptedException。但是如果一个中断信号在唤醒之后，则该方法必须返回，不抛出异常，同时线程设置为中断状态。

     为了维持正常的顺序，队列中的节点有一个状态域记录节点是否已经转移（或者已经在执行中）。唤醒和取消都使用compareAndSet来尝试更新状态。如果一个唤醒操作竞争失败，如果存在下一个节点，将转移队列中的下一个节点。如果取消操作竞争失败，就必须中止转移，然后等待重新获取锁。后一种情况，可能引入了一个无限自旋。直到一个节点已成功转移到锁队列中，否则一个被取消的等待不能重新开始获取锁，所以必须自旋等待被唤醒的线程在CLH队列上执行compareAndSet类型的插入成功。在这里的自旋是罕见的，通过Thread.yield暗示一个理想唤醒的线程调度执行。虽然这里可以为取消插入节点实现一个帮助策略，但是这种场景是非常罕见，并且意味着增加开销。在其他所有的场景下，所有的基本机制，都不会使用自旋或yields，来保持合理的单处理器的性能。

 

原文见第一篇的附件

 

下一篇：http://caoyaojun1988-163-com.iteye.com/admin/blogs/1302936