接上一篇: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
本站支持 pay for your wishes
相关推荐
在 java.util.concurrent 多线程框架中,还提供了多种其他机制,包括并发集合、同步器、lock 等,以便开发者更方便地编写高效、可靠的多线程程序。并发集合提供了多种机制,包括 CopyOnWriteArrayList、...
Java.util.concurrent是Java 5.0引入的一个重要包,它为多线程编程提供了一组高级并发工具。这个包的设计者是Doug Lea,它的出现是JSR-166的一部分,也被称作Tiger更新。Java.util.concurrent的引入是为了解决传统...
`java.util.concurrent`包中的`AbstractQueuedSynchronizer`框架为Java开发者提供了一个强大的工具箱,使得他们能够高效地实现各种同步器。通过对同步状态的有效管理、阻塞和唤醒机制的优化以及灵活的扩展性设计,...
文档标题“java.util.concurrent同步器框架”和描述“Doug Lea的java.util.concurrent同步器框架”表明本文将探讨由Doug Lea所撰写的关于Java并发编程中同步器框架的内容。文档中提到了AbstractQueuedSynchronizer类...
AQS(AbstractQueuedSynchronizer)是Java.util.concurrent包中同步器的基础框架,它的核心设计思想与实现方法在Doug Lea先生的这篇论文中有详细的介绍。论文详细阐述了AQS框架的原理、设计、实现、应用以及性能等...
在Java并发编程中,`java.util.concurrent`(简称JUC)提供了丰富的类和接口,如Executor框架、线程池、并发集合、同步工具类等。这些工具使得程序员能够更方便地管理线程,避免了传统的锁和同步机制带来的复杂性和...
Java.util.concurrent(JUC)是Java平台中的一个核心包,专门用于处理多线程并发问题。这个包包含了大量的工具类和接口,极大地简化了并发编程的复杂性,提高了程序的性能和可伸缩性。本测试源文件主要是针对JUC并发...
总之,`java.util.concurrent` 提供的工具使得并发编程变得更加容易和高效,是 Java 并发编程的基石,无论是对于初学者还是经验丰富的开发者,理解和掌握这个包都是非常重要的。通过熟练运用这些工具,开发者可以...
然而,现代的多线程编程通常更倾向于使用并发集合,如`java.util.concurrent.CopyOnWriteArrayList`,它在读多写少的场景下有更好的性能。 6. **编程高手箴言** - 虽然`Vector`提供了线程安全,但其性能可能不满足...
在实际项目中,结合`java.util.concurrent`包与其他工具,比如Spring框架的ThreadPoolTaskExecutor,可以构建出高效、可扩展的并发解决方案。同时,持续学习和实践是提升并发编程能力的关键,不断探索新的并发模式和...
23. **`java.util.concurrent.locks.Lock`** 和 **`java.util.concurrent.locks.ReentrantLock`**: 锁机制,用于线程同步。 24. **`java.util.ArrayList`**: 用于创建堆栈、队列和双端队列的实现,如`ArrayDeque`。...
8. **Fork/Join框架**: `java.util.concurrent.ForkJoinPool` 和 `RecursiveTask` 或 `RecursiveAction` 用于并行执行可拆分任务,适合大量计算工作。 9. **ScheduledExecutorService**: 提供定时及周期性任务的...
`java.util.Queue`接口及其实现如ArrayDeque、LinkedList(作为Queue的实现),以及`java.util.concurrent`包下的并发队列如LinkedBlockingQueue、ConcurrentLinkedQueue等,提供高效的数据同步和处理机制。...
Java定时执行方法与节拍器是程序开发中常见的需求,特别是在服务器端应用或者后台服务中,需要定期执行某些任务,例如数据同步、日志清理、定时推送等。本篇文章将深入探讨Java中如何实现定时执行的方法,并介绍一个...
`Thread`类允许创建和管理独立执行的线程,而`java.util.concurrent`包包含了许多高级并发工具,如线程池、未来结果(Future)和同步器(Semaphore)。 4. **网络编程**:`java.net`包提供了网络通信的接口和类,如...
java.util.concurrent.locks 为锁和等待条件提供一个框架的接口和类,它不同于内置同步和监视器。 java.util.jar 提供读写 JAR (Java ARchive) 文件格式的类,该格式基于具有可选清单文件的标准 ZIP 文件格式。 ...
3. **同步容器**: `java.util.concurrent`包中的`BlockingQueue`接口及其实现(如`ArrayBlockingQueue`, `LinkedBlockingQueue`)是线程安全的数据结构,适用于生产者-消费者模型。此外,还有`ConcurrentHashMap`,...
- `java.util.concurrent` 包:包含线程池、并发容器、同步工具类,如`ExecutorService`、`CountDownLatch`、`CyclicBarrier`等。 7. **反射工具类**: - `java.lang.reflect` 包:提供反射API,可以在运行时动态...