192      阿裏雲  技術社區[雲棲]

Java的LockSupport.park()實現分析

LockSupport類是Java6(JSR166-JUC)引入的一個類，提供了基本的線程同步原語。LockSupport實際上是調用了Unsafe類裏的函數，歸結到Unsafe裏，隻有兩個函數：

  public native void unpark(Thread jthread);
  public native void park(boolean isAbsolute, long time);

isAbsolute參數是指明時間是絕對的，還是相對的。

僅僅兩個簡單的接口，就為上層提供了強大的同步原語。

先來解析下兩個函數是做什麼的。

unpark函數為線程提供“許可(permit)”，線程調用park函數則等待“許可”。這個有點像信號量，但是這個“許可”是不能疊加的，“許可”是一次性的。

比如線程B連續調用了三次unpark函數，當線程A調用park函數就使用掉這個“許可”，如果線程A再次調用park，則進入等待狀態。

注意，unpark函數可以先於park調用。比如線程B調用unpark函數，給線程A發了一個“許可”，那麼當線程A調用park時，它發現已經有“許可”了，那麼它會馬上再繼續運行。

實際上，park函數即使沒有“許可”，有時也會無理由地返回，這點等下再解析。

park和unpark的靈活之處

上麵已經提到，unpark函數可以先於park調用，這個正是它們的靈活之處。

一個線程它有可能在別的線程unPark之前，或者之後，或者同時調用了park，那麼因為park的特性，它可以不用擔心自己的park的時序問題，否則，如果park必須要在unpark之前，那麼給編程帶來很大的麻煩！！

考慮一下，兩個線程同步，要如何處理？

在Java5裏是用wait/notify/notifyAll來同步的。wait/notify機製有個很蛋疼的地方是，比如線程B要用notify通知線程A，那麼線程B要確保線程A已經在wait調用上等待了，否則線程A可能永遠都在等待。編程的時候就會很蛋疼。

另外，是調用notify，還是notifyAll？

notify隻會喚醒一個線程，如果錯誤地有兩個線程在同一個對象上wait等待，那麼又悲劇了。為了安全起見，貌似隻能調用notifyAll了。

park/unpark模型真正解耦了線程之間的同步，線程之間不再需要一個Object或者其它變量來存儲狀態，不再需要關心對方的狀態。

HotSpot裏park/unpark的實現

每個java線程都有一個Parker實例，Parker類是這樣定義的：

class Parker : public os::PlatformParker {
private:
  volatile int _counter ;
  ...
public:
  void park(bool isAbsolute, jlong time);
  void unpark();
  ...
}
class PlatformParker : public CHeapObj<mtInternal> {
  protected:
    pthread_mutex_t _mutex [1] ;
    pthread_cond_t  _cond  [1] ;
    ...
}

在Parker類裏的_counter字段，就是用來記錄所謂的“許可”的。

當調用park時，先嚐試直接能否直接拿到“許可”，即_counter>0時，如果成功，則把_counter設置為0,並返回：

void Parker::park(bool isAbsolute, jlong time) {
  // Ideally we'd do something useful while spinning, such
  // as calling unpackTime().


  // Optional fast-path check:
  // Return immediately if a permit is available.
  // We depend on Atomic::xchg() having full barrier semantics
  // since we are doing a lock-free update to _counter.
  if (Atomic::xchg(0, &_counter) > 0) return;

如果不成功，則構造一個ThreadBlockInVM，然後檢查_counter是不是>0，如果是，則把_counter設置為0，unlock mutex並返回：

  ThreadBlockInVM tbivm(jt);
  if (_counter > 0)  { // no wait needed
    _counter = 0;
    status = pthread_mutex_unlock(_mutex);

否則，再判斷等待的時間，然後再調用pthread_cond_wait函數等待，如果等待返回，則把_counter設置為0，unlock mutex並返回：

  if (time == 0) {
    status = pthread_cond_wait (_cond, _mutex) ;
  }
  _counter = 0 ;
  status = pthread_mutex_unlock(_mutex) ;
  assert_status(status == 0, status, "invariant") ;
  OrderAccess::fence();

void Parker::unpark() {
  int s, status ;
  status = pthread_mutex_lock(_mutex);
  assert (status == 0, "invariant") ;
  s = _counter;
  _counter = 1;
  if (s < 1) {
     if (WorkAroundNPTLTimedWaitHang) {
        status = pthread_cond_signal (_cond) ;
        assert (status == 0, "invariant") ;
        status = pthread_mutex_unlock(_mutex);
        assert (status == 0, "invariant") ;
     } else {
        status = pthread_mutex_unlock(_mutex);
        assert (status == 0, "invariant") ;
        status = pthread_cond_signal (_cond) ;
        assert (status == 0, "invariant") ;
     }
  } else {
    pthread_mutex_unlock(_mutex);
    assert (status == 0, "invariant") ;
  }
}

關於"Spurious wakeup"，參考上一篇blog：https://blog.csdn.net/hengyunabc/article/details/27969613

  if (time == 0) {
    status = pthread_cond_wait (_cond, _mutex) ;
  }

這也就是為什麼Java dos裏提到，當下麵三種情況下park函數會返回：

• Some other thread invokes unpark with the current thread as the target; or
• Some other thread interrupts the current thread; or
• The call spuriously (that is, for no reason) returns.

相關的實現代碼在：

https://hg.openjdk.java.net/build-infra/jdk7/hotspot/file/52c4a1ae6adc/src/share/vm/runtime/park.hpp
https://hg.openjdk.java.net/build-infra/jdk7/hotspot/file/52c4a1ae6adc/src/share/vm/runtime/park.cpp
https://hg.openjdk.java.net/build-infra/jdk7/hotspot/file/52c4a1ae6adc/src/os/linux/vm/os_linux.hpp
https://hg.openjdk.java.net/build-infra/jdk7/hotspot/file/52c4a1ae6adc/src/os/linux/vm/os_linux.cpp  

其它的一些東東：

Parker類在分配內存時，使用了一個技巧，重載了new函數來實現了cache line對齊。

// We use placement-new to force ParkEvent instances to be
// aligned on 256-byte address boundaries.  This ensures that the least
// significant byte of a ParkEvent address is always 0.
 
void * operator new (size_t sz) ;

volatile int Parker::ListLock = 0 ;
Parker * volatile Parker::FreeList = NULL ;

Parker * Parker::Allocate (JavaThread * t) {
  guarantee (t != NULL, "invariant") ;
  Parker * p ;

  // Start by trying to recycle an existing but unassociated
  // Parker from the global free list.
  for (;;) {
    p = FreeList ;
    if (p  == NULL) break ;
    // 1: Detach
    // Tantamount to p = Swap (&FreeList, NULL)
    if (Atomic::cmpxchg_ptr (NULL, &FreeList, p) != p) {
       continue ;
    }

    // We've detached the list.  The list in-hand is now
    // local to this thread.   This thread can operate on the
    // list without risk of interference from other threads.
    // 2: Extract -- pop the 1st element from the list.
    Parker * List = p->FreeNext ;
    if (List == NULL) break ;
    for (;;) {
        // 3: Try to reattach the residual list
        guarantee (List != NULL, "invariant") ;
        Parker * Arv =  (Parker *) Atomic::cmpxchg_ptr (List, &FreeList, NULL) ;
        if (Arv == NULL) break ;

        // New nodes arrived.  Try to detach the recent arrivals.
        if (Atomic::cmpxchg_ptr (NULL, &FreeList, Arv) != Arv) {
            continue ;
        }
        guarantee (Arv != NULL, "invariant") ;
        // 4: Merge Arv into List
        Parker * Tail = List ;
        while (Tail->FreeNext != NULL) Tail = Tail->FreeNext ;
        Tail->FreeNext = Arv ;
    }
    break ;
  }

  if (p != NULL) {
    guarantee (p->AssociatedWith == NULL, "invariant") ;
  } else {
    // Do this the hard way -- materialize a new Parker..
    // In rare cases an allocating thread might detach
    // a long list -- installing null into FreeList --and
    // then stall.  Another thread calling Allocate() would see
    // FreeList == null and then invoke the ctor.  In this case we
    // end up with more Parkers in circulation than we need, but
    // the race is rare and the outcome is benign.
    // Ideally, the # of extant Parkers is equal to the
    // maximum # of threads that existed at any one time.
    // Because of the race mentioned above, segments of the
    // freelist can be transiently inaccessible.  At worst
    // we may end up with the # of Parkers in circulation
    // slightly above the ideal.
    p = new Parker() ;
  }
  p->AssociatedWith = t ;          // Associate p with t
  p->FreeNext       = NULL ;
  return p ;
}


void Parker::Release (Parker * p) {
  if (p == NULL) return ;
  guarantee (p->AssociatedWith != NULL, "invariant") ;
  guarantee (p->FreeNext == NULL      , "invariant") ;
  p->AssociatedWith = NULL ;
  for (;;) {
    // Push p onto FreeList
    Parker * List = FreeList ;
    p->FreeNext = List ;
    if (Atomic::cmpxchg_ptr (p, &FreeList, List) == List) break ;
  }
}

總結與扯談

JUC(Java Util Concurrency)僅用簡單的park, unpark和CAS指令就實現了各種高級同步數據結構，而且效率很高，令人驚歎。

在C++程序員各種自製輪子的時候，Java程序員則有很豐富的並發數據結構，如lock，latch，queue，map等信手拈來。

要知道像C++直到C++11才有標準的線程庫，同步原語，但離高級的並發數據結構還有很遠。boost庫有提供一些線程，同步相關的類，但也是很簡單的。Intel的tbb有一些高級的並發數據結構，但是國內boost都用得少，更別說tbb了。

最開始研究無鎖算法的是C/C++程序員，但是後來很多Java程序員，或者類庫開始自製各種高級的並發數據結構，經常可以看到有分析Java並發包的文章。反而C/C++程序員總是在分析無鎖的隊列算法。高級的並發數據結構，比如並發的HashMap，沒有看到有相關的實現或者分析的文章。在C++11之後，這種情況才有好轉。

因為正確高效實現一個Concurrent Hash Map是很困難的，要對內存CPU有深刻的認識，而且還要麵對CPU不斷升級帶來的各種坑。

我認為真正值得信賴的C++並發庫，隻有Intel的tbb和微軟的PPL。

https://software.intel.com/en-us/node/506042     Intel® Threading Building Blocks 

https://msdn.microsoft.com/en-us/library/dd492418.aspx   Parallel Patterns Library (PPL)

另外FaceBook也開源了一個C++的類庫，裏麵也有並發數據結構。

https://github.com/facebook/folly

最後更新：2017-04-03 08:26:22

  上一篇： java.util.concurrent包(3)——線程間通信wait/notify和await/signal

  下一篇： SQL Server---觸發器