concurrency programming

	分類	項目	日期
1	Java	java.util.concurrent.locks - 臨界區間的讀寫	2015/08/13
2	Java	java.util.concurrent - Future & Callable	2015/08/15
3	Java	java.util.concurrent - ExecutorService	2015/08/16
4	C	fork Function	2015/06/06
5	Design Pattern	Producer-Consumer Pattern	2015/10/17

java.util.concurrent.locks - 臨界區間的讀寫

java 在推出時，提供 synchronized、notify、wait 的簡單方式，讓多執行緒程式可以控制臨界區間的存取，到了 Java 5 之後加入  java.util.concurrent 這個 package，又提供了一些 interface (介面) 及 class (類別)，這些新的 interface、class 比之前的方法更有彈性、更有效率，這裡簡要的說明 java.util.concurrent.locks 下的主要類別與介面。下圖的 class diagram (類別圖) 僅是主要的 interface、class 及其包含的主要 method，要了解全貌，請參考 Java Documentation。

• ReadWriteLock

ReadWriteLock lock = new ReentrantReadWriteLock();
//...
lock.writeLock().lock(); //取得寫入鎖定
try {
    ...
}
finally {
    lock.writeLock().unlock(); //解除寫入鎖定
}

上面的程式稱不上是一個範例，主要說明使用 ReadWriteLock 的優缺點及注意事項:

1. 跟 synchronized 比起來，解除了只能針一個 method 或一個 block 設定臨界區間的限制，但是要注意一定要記得 unlock，否則會防礙到其他執行緒進入臨界區間，所以上面的程式，將 unlock() 放在 finally 以確保其最後一定會被執行。
2. 請回頭看一下類別圖中的 ReadWriteLock，它提供的是有 read lock 和 write lock，這可以改善 synchronized 的效率，synchronized 只要有一個 thread 搶到了 lock，就得等它執行完臨界區間內所有程式，並離開後，其它等著進入臨界區間的 thread 才能進入。現在分出了 read lock 及 write lock，當取得 write lock 的 thread 進入了臨界區間，其它 thread 也只能等待，但是，如果是取得 read lock 的 thread 進入臨界區間，是可以有多個 read lock thread 同時進入，這就改善了效率，又不會讓資料不一致。 

• Lock

ReentrantLock lock = new ReentrantLock();

try {
    if (lock.tryLock()) {
        //臨界區間 - do something
    }
}
finally {
    if (lock.isHeldByCurrentThread()) {
        lock.unlock();
    }
}

interface Lock 只有一個實作類別 ReetrantLock，這裡要特別注意 tryLock() 這個 method，它相當有趣，因為當遇到臨界區間時，使用這個 method，如果取得 lock 就傳 true，沒有取得就傳回 false，程式可以依傳回值決定做什麼事，以免有 thread 呆呆的一直等著進臨界區間而浪費時間。

要記得，unlock 前也要先用 isHeldByCurrentThread() 這個 method 判斷一下目前是否有取得 lock，有的話才 unlock。

• Condition

 前面提到的 lock 是可用來取代 synchronized 的新解法，Condition 的 signal、await 則是與 notify、wait 相當。使用的方法可以參考官網 Condition 的範例如下: 

 1  class BoundedBuffer {
 2    final Lock lock = new ReentrantLock();
 3    final Condition notFull  = lock.newCondition(); 
 4    final Condition notEmpty = lock.newCondition(); 
 5 
 6    final Object[] items = new Object[100];
 7    int putptr, takeptr, count;
 8 
 9    public void put(Object x) throws InterruptedException {
10      lock.lock();
11      try {
12        while (count == items.length)
13          notFull.await();
14        items[putptr] = x;
15        if (++putptr == items.length) putptr = 0;
16        ++count;
17        notEmpty.signal();
18      } finally {
19        lock.unlock();
20      }
21    }
22 
23    public Object take() throws InterruptedException {
24      lock.lock();
25      try {
26        while (count == 0)
27          notEmpty.await();
28        Object x = items[takeptr];
29        if (++takeptr == items.length) takeptr = 0;
30        --count;
31        notFull.signal();
32        return x;
33      } finally {
34        lock.unlock();
35      }
36    }
37  }

這是一個很簡單的"生產者"、"消費者"的例子，當陣列中沒有任何物件時，消費者 (take) 就需等待 (line 27)，當陣列滿了時，生產者 (put) 也需等待 (line 13); 如果有新的物件產生生產者會通知消費者 (line 17)，如果陣列還有空間，消費者也會通知生產者 (line 31)。

特別注意一下 2~4 行，Condition 是由 lock 的 newCondition() 產生，還有，就如 notify、wait 必需位於 synchronized 區間內一樣，Condition 的 await、signal 也要位於 lock、unlock 之間。

• StampedLock

前面提到的 ReadWriteLock 可允許多個 readLock 的執行緒同時進入臨界區間，但只允許一個 writeLock 的執行緒進入臨界區間，且當有 writeLock 的執行緒位於臨界區間內，即不允許其它執行緒取得 readLock、writeLock，這會有個問題，當程式有很多讀取的執行緒，只有很少的寫入執行緒，臨界區間大部份時間被取得 readLock  執行緒佔據，寫入的執行緒會很難取得 writeLock 而長期處於等待狀態。為了解決這個問題，Java 8 提供了 StampedLock 這個新類別。

 1 public class BankAccountStampedLock {
 2   private final StampedLock sl = new StampedLock();
 3   private long balance;
 4 
 5   public BankAccountStampedLock(long balance) {
 6     this.balance = balance;
 7   }
 8 
 9   public void deposit(long amount) {
10     long stamp = sl.writeLock();
11     try {
12       balance += amount;
13     } finally {
14       sl.unlockWrite(stamp);
15     }
16   }
17 
18   public void withdraw(long amount) {
19     long stamp = sl.writeLock();
20     try {
21       balance -= amount;
22     } finally {
23       sl.unlockWrite(stamp);
24     }
25   }
26 
27   public long getBalance() {
28     long stamp = sl.readLock();
29     try {
30       return balance;
31     } finally {
32       sl.unlockRead(stamp);
33     }
34   }
35 
36   public long getBalanceOptimisticRead() {
37     long stamp = sl.tryOptimisticRead();
38     long balance = this.balance;
39     if (!sl.validate(stamp)) {
40       stamp = sl.readLock();
41       try {
42         balance = this.balance;
43       } finally {
44         sl.unlockRead(stamp);
45       }
46     }
47     return balance;
48   }
49 }

這是一個存、提款的範例程式，來源是 javaspecialists 網站。這個程式和完全只使用 ReadWriteLock 最大差別在於 getBalanceOptimisticRead()，第 37 行先呼叫 tryOptimisticRead 取得一個樂觀讀取鎖定，第 38 行取得存款餘額，第 39 行判斷看看是否在取得樂觀讀取鎖定後，有臨界區間有取得寫入鎖定的執行緒進入，沒有的話，直接回傳存款餘額 (line 47)，萬一有的話，balance 的值有可能已經被改變，所以就要謹慎的取得讀取鎖定 (line 40)，再取得真正最新的值後再解鎖 (line 44)。

fork Function

在「Advanced.Programming.in.the.UNIX.Environment, 3rd.Edition」一書中的8.3節 (p. 230)，有個小程式，如下，是用來說明 UNIX 環境中，使用 fork 產生子行程 (child process)，要注意的一些事，先看一下程式:

 1 #include <stdio.h>

 2 #include <unistd.h>
 3 
 4 int globvar = 6;
 5 char buf[] = "a write to stdout\n";
 6 
 7 int main(void) {
 8     int var;
 9     pid_t pid;
10 
11     var = 88;
12     if (write(STDOUT_FILENO, buf, sizeof(buf)-1) != sizeof(buf)-1)
13         printf("write error");
14     printf("before fork\n");
15 
16     if ((pid = fork()) < 0) {
17         printf("fork error");
18     }
19     else if (pid == 0) {
20         globvar++;
21         var++;
22     }
23     else {
24         sleep(2);
25     }
26 
27     printf("pid = %ld, getpid = %ld, glob = %d, var = %d\n", (long) pid, (long) getpid(), globvar, var);
28     _exit(0);
29 }

上面的程式很簡單的利用 fork 產生一個子行程，等待 2 秒後，印出一段訊息，顯示 fork 傳回值、行程的 pid (process id)、全域變數及區域變數，執行結果如下: (我的程式命名為 forEx01.c)

[steven@CentOS7 Debug]$ ./forkEx01
a write to stdout
before fork
pid = 0, getpid = 9214, glob = 7, var = 89
pid = 9214, getpid = 9213, glob = 6, var = 88
[steven@CentOS7 Debug]$ 

根據上述的執行結果，說明如下:

1. fork 函數會產生一個子行程，子行程會執行父行程 (parent process) fork 之後的指令。
2. fork 函數在父行程會傳回子行程的 pid，在子行程則傳回 0，子行程如果要得到父行程的 pid，可以透過 getppid 函數得到值。
3. 上面程式讓父行程睡 2 秒後再印出結果，所以第一個結果是子程式印出的，第二個結果是父行程印出的，通常確實是會得到如上的結果 (除了 pid、getpid 的值會不同之外)，但是，實際上有時會是父行程先印出，因為那個行程先執行，由 OS 決定，這裡父行程睡 2 秒只是增加子行程先執行的機率。
4. 上述程式的全域變數 (global variable) 和區域變數 (local variable) 於子行程中都被加 1，但是都沒有影響到父行程的值，這表示不管是全域變數或區域變數，父行程、子行程都不共用!
5. 子行程的輸出接在父行程 fork 前已輸出的內容之後，父行程後面的輸出又接在子行程的輸出之後，完全不會互相覆蓋，因為父行程和子行程會共享在 fork 之前已開啟的所有檔案描述符 (file descriptions)，也就是說兩個行程會共享這些檔案的檔案指標! 標準輸出是在父行程一開始執行時就被開啟的，所以會被兩個行程共享。

除了上述程式所展現的父行程、子行程關係外，另外針對行程的一些基本觀念整理如下:

1. UNIX 系統在系統啟動後，會啟動許多 process 來處理一些系統面的事，其中一個 pid 為 1 的 process 稱為 init process，是負責啟動和關閉系統。
2. 程式以 fork 啟動一個或數個子行程，當子行程結束後，父行程要負責將其佔用的資源都回收後，才可真正將其結束，在子行程已經執行完，但是父行程尚未將其資源回收前，這個子行程就稱為 zombie (僵屍)。
3. 如果父行程比子行程更早結束，子行程並不會被迫結束，而是會交由 init process 管理，也就是說，子行程的 ppid 會被改為 1，之後子行程結束，其資源會由 init process 進行回收。