首页天道酬勤两个栈实现一个队列java,java怎么处理高并发

两个栈实现一个队列java,java怎么处理高并发

张世龙 05-04 18:09 34次浏览

CLH算法的实现在前面已经写好了,本文参考了[大新博客],在此表示感谢! (https://www.cn blogs.com/Daxin/p/3365324.html )

对于java并发编程,AQS同步器框架的底层实现通过FIFO队列维护线程之间的等待和唤醒机制。 此队列不是实际存在的队列,而是只保存节点之间关系的队列。

CLH队列中的节点QNode包含锁定字段。 如果此字段为true,则表示线程必须获得锁定,且不会解除锁定;如果为false,则表示线程已解除锁定。 节点之间用看不见的链表连接。 之所以称为不可见的链表,是因为这些节点之间没有明显的next指针,myPred指向的节点变化会影响myNode的行为。 CLHLock还有一个末端指针,它始终指向队列中的最后一个节点。 CLHLock的类图如下:

如果线程需要获取锁定,则会创建新的QNode。 如果其中的locked设置为true,则表示需要获取锁定。 然后,线程对tail域调用getAndSet方法,使其位于队列末尾,获取向前的引用myPred,并旋转它,直到在前方节点的locked字段中解除锁定。 如果线程需要解锁,请将当前节点的locked域设置为false,以同时回收前一个节点。 如下图所示,线程a需要获取锁定。 myNode域为true,tail指向线程a的节点,线程b也添加在线程a之后,tail指向线程b的节点。 然后,线程a和b在其myPred域上旋转,并且如果myPred节点的locked字段为false,则可以获取锁定。 很明显,线程a的myPred locked域为false,此时线程a获得了锁定。

整个CLH的代码如下所示。 其中,使用ThreadLocal类,将QNode绑定到每个线程,同时使用AtomicReference。 对尾指针的更改是通过调用它的getAndSet ) )操作实现的,以确保对象引用以原子方式更新。

publicclassclhlock { atomicreferenceqnodetail=newatomicreferenceqnode (new qnode ) }; ThreadLocalQNode myPred; ThreadLocalQNode myNode; public static class QNode { //注意如果不将volatile放入此位置,线程将永远死亡并循环//关于volatile的使用,请参阅我的另一篇文章3358 www.cn blogs.com/Daxin/p public CLHLock () ({ myNode=new ThreadLocalQNode ) ) { protected QNode initialValue ) { return new QNode; }; myPred=new ThreadLocalQNode () { protected QNode initialValue ) { return null; }; }公共void lock () { QNode qnode=myNode.get ); qnode.locked=true; qnodepred=tail.getandset(qnode ); mypred.set(pred; while(pred.locked )//非阻塞算法) } } public void unlock () { QNode qnode=myNode.get; qnode.locked=false; mynode.set(mypred.get ) ); }

aqs,sv队列