Friday, September 18, 2015

Inside AbstractQueuedSynchronizer



Inside AbstractQueuedSynchronizer (1)
      那么LockSupport和Java语言内置的monitor机制有什么区别呢?它们的语义是不同的。LockSupport是针对特定Thread来进行block/unblock操作的;wait()/notify()/notifyAll()是用来操作特定对象的等待集合的。为了防止知识生锈,在这里简单介绍一下Java语言内置的monitor机制(详见:http://whitesock.iteye.com/blog/162344 )。正如每个Object都有一个锁, 每个Object也有一个等待集合(wait set),它有wait、notify、notifyAll和Thread.interrupt方法来操作。同时拥有锁和等待集合的实体,通常被成为监视器(monitor)。每个Object的等待集合是由JVM维护的。等待集合一直存放着那些因为调用对象的wait方法而被阻塞的线程。由于等待集合和锁之间的交互机制,只有获得目标对象的同步锁时,才可以调用它的wait、notify和notifyAll方法。这种要求通常无法靠编译来检查,如果条件不能满足,那么在运行的时候调用以上方法就会导致其抛出IllegalMonitorStateException。

    wait() 方法被调用后,会执行如下操作:
  • 如果当前线程已经被中断,那么该方法立刻退出,然后抛出一个InterruptedException异常。否则线程会被阻塞。
  • JVM把该线程放入目标对象内部且无法访问的等待集合中。
  • 目标对象的同步锁被释放,但是这个线程锁拥有的其他锁依然会被这个线程保留着。当线程重新恢复质执行时,它会重新获得目标对象的同步锁。
    notify()方法被调用后,会执行如下操作:
  • 如果存在的话,JVM会从目标对象内部的等待集合中任意移除一个线程T。如果等待集合中的线程数大于1,那么哪个线程被选中完全是随机的。
  • T必须重新获得目标对象的同步锁,这必然导致它将会被阻塞到调用Thead.notify()的线程释放该同步锁。如果其他线程在T获得此锁之前就获得它,那么T就要一直被阻塞下去。
  • T从执行wait()的那点恢复执行。
    notifyAll()方法被调用后的操作和notify()类似,不同的只是等待集合中所有的线程(同时)都要执行那些操作。然而等待集合中的线程必须要在竞争到目标对象的同步锁之后,才能继续执行。

LockSupport类中比较重要的方法有如下几个:
其中park()和park(Object blocker)方法用于block当前线程,unpark(Thread thread)方法用于unblock制定的线程。 跟Thread.suspend()和Thread.resume()不同的是,LockSupport通过许可(permit)机制保证:如果当前线程拥有许可,那么park系列方法会消费掉该许可,并且立即返回(不会被阻塞)。也就是说如下代码在执行的时候,不会被阻塞:
许可不会被累计。也就是说在park调用之前的多次unpark调用,只会unblock一次park调用。即以下代码会被阻塞.
http://whitesock.iteye.com/blog/1336920
    AbstractQueuedSynchronizer用一个int(private volatile int state)来保存同步状态,以及对应的getter/setter/compareAndSetState方法。Java6新增了一个AbstractQueuedLongSynchronizer,它用一个long来保存同步状态,貌似目前没有被java.util.concurrent中的其它synchronizer所使用。对于ReentrantLock,state为0则意味着锁没有被任何线程持有;否则state保存了持有锁的线程的重入次数。
3.3 WaitQueue
    WaitQueue是AbstractQueuedSynchronizer的核心,它用于保存被阻塞的线程。它的实现是"CLH" (Craig, Landin, and Hagersten) lock queue的一个变种。

    标准的CLH lock queue通常被用来实现spin lock,它通过TheadLocal变量pred引用队列中的前一个节点(Node本身没有指向前后节点的引用),以下是标准的CLH lock queue的一个参考实现:
  1. public class ClhSpinLock {  
  2.     private final ThreadLocal<Node> pred;  
  3.     private final ThreadLocal<Node> node;  
  4.     private final AtomicReference<Node> tail = new AtomicReference<Node>(new Node());  
  5.   
  6.     public ClhSpinLock() {  
  7.         this.node = new ThreadLocal<Node>() {  
  8.             protected Node initialValue() {  
  9.                 return new Node();  
  10.             }  
  11.         };  
  12.   
  13.         this.pred = new ThreadLocal<Node>() {  
  14.             protected Node initialValue() {  
  15.                 return null;  
  16.             }  
  17.         };  
  18.     }  
  19.   
  20.     public void lock() {  
  21.         final Node node = this.node.get();  
  22.         node.locked = true;  
  23.         Node pred = this.tail.getAndSet(node);  
  24.         this.pred.set(pred);  
  25.         while (pred.locked) {}  
  26.     }  
  27.   
  28.     public void unlock() {  
  29.         final Node node = this.node.get();  
  30.         node.locked = false;  
  31.         this.node.set(this.pred.get());  
  32.     }  
  33.   
  34.     private static class Node {  
  35.         private volatile boolean locked;  
  36.     }  
  37. }  
http://www.zavakid.com/2012/10/12/aqs_1/

  1, spinlock介绍
  spinlock又称自旋锁,线程通过busy-wait-loop的方式来获取锁,任时刻只有一个线程能够获得锁,其他线程忙等待直到获得锁。spinlock在多处理器多线程环境的场景中有很广泛的使用,一般要求使用spinlock的临界区尽量简短,这样获取的锁可以尽快释放,以满足其他忙等的线程。Spinlock和mutex不同,spinlock不会导致线程的状态切换(用户态->内核态),但是spinlock使用不当(如临界区执行时间过长)会导致cpu busy飙高。
  2, spinlock与mutex对比
  2.1,优缺点比较
  spinlock不会使线程状态发生切换,mutex在获取不到锁的时候会选择sleep。
  mutex获取锁分为两阶段,第一阶段在用户态采用spinlock锁总线的方式获取一次锁,如果成功立即返回;否则进入第二阶段,调用系统的futex锁去sleep,当锁可用后被唤醒,继续竞争锁。
  Spinlock优点:没有昂贵的系统调用,一直处于用户态,执行速度快。
  Spinlock缺点:一直占用cpu,而且在执行过程中还会锁bus总线,锁总线时其他处理器不能使用总线。
  Mutex优点:不会忙等,得不到锁会sleep。
  Mutex缺点:sleep时会陷入到内核态,需要昂贵的系统调用。

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts