CLH

思路

保持时序的锁基本思路就是将等待获取锁的线程放入集合，锁释放后，等待线程之一获取到锁。

问题

如何排队？
- CLH使用反向链表的形式进行排队。也就是后继节点主动询问，而不是前继节点主动通知。

排队是否公平？
- CLH是公平锁。即后申请获取锁的排在队列末尾。

如何唤醒？
- CLH通过每个线程自旋。每个等待线程通过不断自旋前继节点状态判断是否能获取到锁。

实现

CLH排队使用公平方式，锁内部需要保存【尾节点】的引用，每次排队线程加入到队列最末尾。

CLH锁使用反向链表方式进行排队，那么每个线程就需要维护【自己的状态】和保持一个【前向节点的引用】。

CLH使用一个【boolean值】表示当前线程获取锁状态。false表示当前线程释放锁；true表示当前线程等待获取锁或已经获取到锁。

代码

Lock.java

xxxxxxxxxx
package com.zby.clh;
​
public interface Lock {
​
   void lock();
​
   void unlock();
}
​

CLHLock.java

xxxxxxxxxx
package com.zby.clh;
​
import java.util.concurrent.atomic.AtomicReference;
​
public class CLHLock implements Lock {
​
   private final AtomicReference
              tail;
   private final ThreadLocal
              myPred;
   private final ThreadLocal
              myNode;
​
   public CLHLock() {
       tail = new AtomicReference
             (new QNode());
       myNode = new ThreadLocal
             () {
           @Override
           protected QNode initialValue() {
               return new QNode();
           }
       };
       myPred = new ThreadLocal
             () {
           @Override
           protected QNode initialValue() {
               return null;
           }
       };
   }
​
   @Override
   public void lock() {
       QNode qnode = myNode.get();
       qnode.locked = true;
       QNode pred = tail.getAndSet(qnode);
       myPred.set(pred);
       while (pred.locked) {
       }
   }
​
   @Override
   public void unlock() {
       QNode qnode = myNode.get();
       qnode.locked = false;
       // myNode.set(myPred.get());这一行是否有必要？？？
   }
​
   private static class QNode {
       public volatile boolean locked;
   }
}
​

测试

xxxxxxxxxx
package com.zby.clh;
​
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
​
public class CLHMain {
   private Lock lock = new CLHLock();
​
   public void say(String msg) {
       System.out.println(Thread.currentThread().getName() + " ： 尝试获取锁");
       lock.lock();
       System.out.println(Thread.currentThread().getName() + " ： 获取到锁");
       try {
           System.out.println(Thread.currentThread().getName() + msg + "?");
           TimeUnit.SECONDS.sleep(1);
           System.out.println(Thread.currentThread().getName() + msg + "!");
           TimeUnit.SECONDS.sleep(1);
           System.out.println(Thread.currentThread().getName() + msg + ".");
           TimeUnit.SECONDS.sleep(1);
       } catch (Exception e) {
           e.printStackTrace();
       } finally {
           lock.unlock();
           System.out.println(Thread.currentThread().getName() + " ： 释放锁");
       }
   }
​
   public static void main(String[] args) throws Exception {
       String msg = "Hello,World";
       CLHMain clhMain = new CLHMain();
       ExecutorService executorService = Executors.newCachedThreadPool();
       for (int i = 0; i < 5; i++) {
           executorService.submit(new Runnable() {
​
               @Override
               public void run() {
                   clhMain.say(msg);
​
               }
           });
       }
       executorService.awaitTermination(20, TimeUnit.SECONDS);
   }
​
}
​

结果

xxxxxxxxxx
pool-1-thread-1 ： 尝试获取锁
pool-1-thread-2 ： 尝试获取锁
pool-1-thread-1 ： 获取到锁
pool-1-thread-1Hello,World?
pool-1-thread-3 ： 尝试获取锁
pool-1-thread-4 ： 尝试获取锁
pool-1-thread-5 ： 尝试获取锁
pool-1-thread-1Hello,World!
pool-1-thread-1Hello,World.
pool-1-thread-1 ： 释放锁
pool-1-thread-2 ： 获取到锁
pool-1-thread-2Hello,World?
pool-1-thread-2Hello,World!
pool-1-thread-2Hello,World.
pool-1-thread-2 ： 释放锁
pool-1-thread-3 ： 获取到锁
pool-1-thread-3Hello,World?
pool-1-thread-3Hello,World!
pool-1-thread-3Hello,World.
pool-1-thread-3 ： 释放锁
pool-1-thread-4 ： 获取到锁
pool-1-thread-4Hello,World?
pool-1-thread-4Hello,World!
pool-1-thread-4Hello,World.
pool-1-thread-4 ： 释放锁
pool-1-thread-5 ： 获取到锁
pool-1-thread-5Hello,World?
pool-1-thread-5Hello,World!
pool-1-thread-5Hello,World.
pool-1-thread-5 ： 释放锁
​