閱讀594 返回首頁    go 阿裏雲 go 技術社區[雲棲]

剖析同步器

雖然許多同步器（如鎖，信號量，阻塞隊列等）功能上各不相同，但它們的內部設計上卻差別不大。換句話說，它們內部的的基礎部分是相同（或相似）的。了解這些基礎部件能在設計同步器的時候給我們大大的幫助。這就是本文要細說的內容。

注：本文的內容是哥本哈根信息技術大學一個由Jakob Jenkov，Toke Johansen和Lars Bjørn參與的M.Sc.學生項目的部分成果。在此項目期間我們谘詢Doug Lea是否知道類似的研究。有趣的是在開發Java 5並發工具包期間他已經提出了類似的結論。Doug Lea的研究，我相信，在《Java Concurrency in Practice》一書中有描述。這本書有一章“剖析同步器”就類似於本文，但不盡相同。

大部分同步器都是用來保護某個區域（臨界區）的代碼，這些代碼可能會被多線程並發訪問。要實現這個目標，同步器一般要支持下列功能：

  1. 狀態
  2. 訪問條件
  3. 狀態變化
  4. 通知策略
  5. Test-and-Set方法
  6. Set方法

並不是所有同步器都包含上述部分，也有些並不完全遵照上麵的內容。但通常你能從中發現這些部分的一或多個。

狀態

同步器中的狀態是用來確定某個線程是否有訪問權限。在Lock中，狀態是boolean類型的，表示當前Lock對象是否處於鎖定狀態。在BoundedSemaphore中，內部狀態包含一個計數器（int類型）和一個上限（int類型），分別表示當前已經獲取的許可數和最大可獲取的許可數。BlockingQueue的狀態是該隊列中元素列表以及隊列的最大容量。

下麵是Lock和BoundedSemaphore中的兩個代碼片段。

01 public class Lock{
02   //state is kept here
03   private boolean isLocked = false;
04   public synchronized void lock()
05   throws InterruptedException{
06     while(isLocked){
07       wait();
08     }
09     isLocked = true;
10   }
11   ...
12 }
01 public class BoundedSemaphore {
02   //state is kept here
03   private int signals = 0;
04   private int bound   = 0;
05        
06   public BoundedSemaphore(int upperBound){
07     this.bound = upperBound;
08   }
09   public synchronized void take() throws InterruptedException{
10     while(this.signals == bound) wait();
11     this.signal++;
12     this.notify();
13   }
14   ...
15 }

訪問條件

訪問條件決定調用test-and-set-state方法的線程是否可以對狀態進行設置。訪問條件一般是基於同步器狀態的。通常是放在一個while循環裏，以避免虛假喚醒問題。訪問條件的計算結果要麼是true要麼是false。

Lock中的訪問條件隻是簡單地檢查isLocked的值。根據執行的動作是“獲取”還是“釋放”，BoundedSemaphore中實際上有兩個訪問條件。如果某個線程想“獲取”許可，將檢查signals變量是否達到上限；如果某個線程想“釋放”許可，將檢查signals變量是否為0。

這裏有兩個來自Lock和BoundedSemaphore的代碼片段，它們都有訪問條件。注意觀察條件是怎樣在while循環中檢查的。

01 public class Lock{
02   private boolean isLocked = false;
03   public synchronized void lock()
04   throws InterruptedException{
05     //access condition
06     while(isLocked){
07       wait();
08     }
09     isLocked = true;
10   }
11   ...
12 }
01 public class BoundedSemaphore {
02   private int signals = 0;
03   private int bound = 0;
04    
05   public BoundedSemaphore(int upperBound){
06     this.bound = upperBound;
07   }
08   public synchronized void take() throws InterruptedException{
09     //access condition
10     while(this.signals == bound) wait();
11     this.signals++;
12     this.notify();
13   }
14   public synchronized void release() throws InterruptedException{
15     //access condition
16     while(this.signals == 0) wait();
17     this.signals--;
18     this.notify();
19   }
20 }

狀態變化

一旦一個線程獲得了臨界區的訪問權限，它得改變同步器的狀態，讓其它線程阻塞，防止它們進入臨界區。換而言之，這個狀態表示正有一個線程在執行臨界區的代碼。其它線程想要訪問臨界區的時候，該狀態應該影響到訪問條件的結果。

在Lock中，通過代碼設置isLocked = true來改變狀態，在信號量中，改變狀態的是signals–或signals++;

這裏有兩個狀態變化的代碼片段：

01 public class Lock{
02  
03   private boolean isLocked = false;
04  
05   public synchronized void lock()
06   throws InterruptedException{
07     while(isLocked){
08       wait();
09     }
10     //state change
11     isLocked = true;
12   }
13  
14   public synchronized void unlock(){
15     //state change
16     isLocked = false;
17     notify();
18   }
19 }
01 public class BoundedSemaphore {
02   private int signals = 0;
03   private int bound   = 0;
04  
05   public BoundedSemaphore(int upperBound){
06     this.bound = upperBound;
07   }
08  
09   public synchronized void take() throws InterruptedException{
10     while(this.signals == bound) wait();
11     //state change
12     this.signals++;
13     this.notify();
14   }
15  
16   public synchronized void release() throws InterruptedException{
17     while(this.signals == 0) wait();
18     //state change
19     this.signals--;
20     this.notify();
21   }
22 }

通知策略

一旦某個線程改變了同步器的狀態，可能需要通知其它等待的線程狀態已經變了。因為也許這個狀態的變化會讓其它線程的訪問條件變為true。

通知策略通常分為三種：

  1. 通知所有等待的線程
  2. 通知N個等待線程中的任意一個
  3. 通知N個等待線程中的某個指定的線程

通知所有等待的線程非常簡單。所有等待的線程都調用的同一個對象上的wait()方法，某個線程想要通知它們隻需在這個對象上調用notifyAll()方法。

通知等待線程中的任意一個也很簡單，隻需將notifyAll()調用換成notify()即可。調用notify方法沒辦法確定喚醒的是哪一個線程，也就是“等待線程中的任意一個”。

有時候可能需要通知指定的線程而非任意一個等待的線程。例如，如果你想保證線程被通知的順序與它們進入同步塊的順序一致，或按某種優先級的順序來通知。想 要實現這種需求，每個等待的線程必須在其自有的對象上調用wait()。當通知線程想要通知某個特定的等待線程時，調用該線程自有對象的notify() 方法即可。饑餓和公平中有這樣的例子。

下麵是通知策略的一個例子（通知任意一個等待線程）：

01 public class Lock{
02  
03   private boolean isLocked = false;
04  
05   public synchronized void lock()
06   throws InterruptedException{
07     while(isLocked){
08       //wait strategy - related to notification strategy
09       wait();
10     }
11     isLocked = true;
12   }
13  
14   public synchronized void unlock(){
15     isLocked = false;
16     notify(); //notification strategy
17   }
18 }

Test-and-Set方法

同步器中最常見的有兩種類型的方法，test-and-set是第一種（set是另一種）。Test-and-set的意思是，調用這個方法的線程檢查訪問條件，如若滿足，該線程設置同步器的內部狀態來表示它已經獲得了訪問權限。

狀態的改變通常使其它試圖獲取訪問權限的線程計算條件狀態時得到false的結果，但並不一定總是如此。例如，在讀寫鎖中，獲取讀鎖的線程會更新讀寫鎖的狀態來表示它獲取到了讀鎖，但是，隻要沒有線程請求寫鎖，其它請求讀鎖的線程也能成功。

test-and-set很有必要是原子的，也就是說在某個線程檢查和設置狀態期間，不允許有其它線程在test-and-set方法中執行。

test-and-set方法的程序流通常遵照下麵的順序：

  1. 如有必要，在檢查前先設置狀態
  2. 檢查訪問條件
  3. 如果訪問條件不滿足，則等待
  4. 如果訪問條件滿足，設置狀態，如有必要還要通知等待線程

下麵的ReadWriteLock類 的lockWrite()方法展示了test-and-set方法。調用lockWrite()的線程在檢查之前先設置狀態 (writeRequests++)。然後檢查canGrantWriteAccess()中的訪問條件，如果檢查通過，在退出方法之前再次設置內部狀 態。這個方法中沒有去通知等待線程。

01 public class ReadWriteLock{
02     private Map<Thread, Integer> readingThreads =
03         new HashMap<Thread, Integer>();
04  
05     private int writeAccesses    = 0;
06     private int writeRequests    = 0;
07     private Thread writingThread = null;
08  
09     ...
10      
11     public synchronized void lockWrite() throws InterruptedException{
12       writeRequests++;
13       Thread callingThread = Thread.currentThread();
14       while(! canGrantWriteAccess(callingThread)){
15         wait();
16       }
17       writeRequests--;
18       writeAccesses++;
19       writingThread = callingThread;
20     }
21      
22     ...
23 }

下麵的BoundedSemaphore類有兩個test-and-set方法：take()和release()。兩個方法都有檢查和設置內部狀態。

01 public class BoundedSemaphore {
02   private int signals = 0;
03   private int bound   = 0;
04  
05   public BoundedSemaphore(int upperBound){
06     this.bound = upperBound;
07   }
08  
09   public synchronized void take() throws InterruptedException{
10     while(this.signals == bound) wait();
11     this.signals++;
12     this.notify();
13   }
14  
15   public synchronized void release() throws InterruptedException{
16     while(this.signals == 0) wait();
17     this.signals--;
18     this.notify();
19   }
20 }

set方法

set方法是同步器中常見的第二種方法。set方法僅是設置同步器的內部狀態，而不先做檢查。set方法的一個典型例子是Lock類中的unlock()方法。持有鎖的某個線程總是能夠成功解鎖，而不需要檢查該鎖是否處於解鎖狀態。

set方法的程序流通常如下：

  1. 設置內部狀態
  2. 通知等待的線程

這裏是unlock()方法的一個例子：

1 public class Lock{
2   private boolean isLocked = false;
3    
4   public synchronized void unlock(){
5     isLocked = false;
6     notify();
7   }
8 }



文章轉自 並發編程網-ifeve.com

最後更新：2017-05-22 18:01:40

  上一篇：go  Write Combining
  下一篇：go  穀歌發布基於機器學習的Android APP安全檢測係統：Google Play Protect