Java Concurrent (2)

本文節選自 Effective Java by Joshua Bloch 和 Concurrent Programming in Java by Doug Lea.

1．3 原子資料的同步

   java語言保證讀或寫一個變量是原子(atomic)的，除非這個變量的類型是long或double.換句話說，讀入一個非long或double類型的變量，可以保證傳回值一定是某個線程儲存在該變量中的，即使多個線程在沒有同步的時候并發地修改這個變量，也是如此。  

    雖然原子性保證了一個線程在讀寫資料的時候，不會看到一個随機的數值，但是它并不保證一個線程寫入的值對于另外一個線程是可見的。java的記憶體模型決定，為了線上程之間可靠地通信，以及為了互斥通路，對原子資料的讀寫進行同步是需要的。考慮下邊的序列号生成程式：

private static int nextSerialNumber = 0;
public static int generateSerialNumber()
{
    return nextSerialNumber++;
}
           

    這個程式的意圖是保證每次調用generateSerialNumber都會傳回一個不同的序列号，然而，如果沒有同步，這個方法并不能正确的工作。遞增操作符（++）既要讀nextSerialNumber域，也要寫nextSerialNumber域，是以它不是原子的。讀和寫互相獨立的操作。是以，多個并發的線程可能會看到nextSerialNumber有相同的值，因而傳回相同的序列号。此外，一個線程重複地調用generateSerialNumber，獲得從0到n的一系列序列号之後，另外一個線程調用generateSerialNumber并獲得一個序列号是0，這是有可能發生的。如果沒有同步機制，第二個線程可能根本看不到第一個線程所作的改變。

1．4 監控機制

    正如每個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類似，不同的隻是等待集合中所有的線程（同時）都要執行那些操作。然而等待集合中的線程必須要在競争到目标對象的同步鎖之後，才能繼續執行。

interrupt。如果對一個因為調用了wait方法而被挂起的對象調用Thread.interrupt方法，那麼這個方法的執行機制就和notify類似，隻是在重新獲得對象鎖後，該方法就會抛出InterruptedException異常，并且該線程的中斷狀态被置為false。

   對于Object.wait()方法，它一定是在一個同步區域中被調用，而且該同步區域鎖住了被調用的對象。下邊是使用Object.wait()方法的标準模式：

synchronized(obj)
{
    while( condition checking)
    {
       obj.wait();
    }
    …// Other operations
}
           

    總是要使用wait循環模式來調用wait方法，永遠不要在循環的外邊調用wait方法。循環的作用在于在等待的前、後都能測試條件。在等待之前測試條件，如果條件成立的話則跳過等待，這對于確定程式的活性（liveness）是必要的。如果條件已經成立，而且線上程等待之前notify（或者notifyAll）方法已經被調用過，那麼無法保證該線程将總會從等待中醒過來。在等待之後測試條件，如果條件不成立的話則繼續等待，這對于確定程式的安全性（safety）是必要的。當條件不成立的時候，如果線程繼續執行，那麼可能破壞被鎖保護的限制關系。當條件不成立的時候，有以下一些理由可以使一個線程醒過來：

1. 從一個線程調用notify方法的時刻起，到等待線程被喚醒的時刻之間，另一個線程得到了鎖，并且改變了被保護的狀态。
2. 條件沒有成立，但是另外一個線程可能意外或者惡意地調用了notify方法。在公有對象上調用wait方法，這其實是将自己暴露在危險的境地中。因為任何持有這個對象引用的線程都可以調用該對象的notify方法。
3. 在沒有被通知的情況下等待線程也可能被喚醒。這被稱為“僞喚醒（spurious wakeup）”。雖然《Java語言規範(The Java Language Specification )》并沒有提到這種可能，但是許多JVM實作都使用了具有僞喚醒功能的線程設施，盡管用的很少。

與此相關的一個問題是，為了喚醒正在等待的線程，到底應該使用notify方法還是應該使用notifyAll方法。假設所有的wait調用都是在循環的内部，那麼使用notifyAll方法是一個合理而保守的做法。它總會産生正确的結果，它可以保證會喚醒所有需要被喚醒的線程。當然，這樣也會喚醒其它一些線程，但是這不會影響程式的正确性。這些線程醒來之後會檢查等待條件，發現條件不滿足，就會繼續等待。使用notifyAll方法的另外一個優點在于可以避免來自不相關線程的意外或者惡意等待。否則的話，這樣的等待可能會“吞掉”一個關鍵的通知，使真正的接收線程無限地等待下去。關于使用notifyAll方法的一個不足在于，雖然使用notifyAll方法不會影響程式的正确性，但是會影響程式的性能。 

1．5 死鎖

    盡管完全同步的原子操作很安全，但是線程可能卻是以失去了活性（liveness）。死鎖（dead lock）是在兩個或多個線程都有權限通路兩個或多個對象，并且每個線程都在已經得到一個鎖的情況下等待其它線程已經得到的鎖。假設線程A持有的對象X的鎖，并且正在試圖獲得對象Y的鎖，同時，線程B已經擁有的對象Y的鎖，并在試圖獲得對象X的鎖。是以沒有哪個線程能夠執行進一步的操作，死鎖就産生了。例如：

public class Cell {
	private long value;
	
	public Cell(long value) {
		this.value = value;
	}
	
	public synchronized long getValue() {
		return value;
	}

	public synchronized void setValue(long value) {
		this.value = value;
	}
	
	public synchronized void swap(Cell other) {
		long t = getValue();  
		long v = other.getValue();  
		setValue(v);  
		other.setValue(t);
	}
	
	public static void main(String args[]) throws Exception {
		//
		final Cell c1 = new Cell(100);
		final Cell c2 = new Cell(200);
		
		//
		Thread t1 = new Thread(new Runnable() {
			public void run() {
				long count = 0;
				try {
					while(true) {
						c1.swap(c2);
						count++;
						if(count % 100 == 0) {
							System.out.println("thread1's current progress: " + count);
						}
					}
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		});
		t1.setName("thread1");
		
		//
		Thread t2 = new Thread(new Runnable() {
			public void run() {
				long count = 0;
				try {
					while(true) {
						c2.swap(c1);
						count++;
						if(count % 100 == 0) {
							System.out.println("thread2's current progress: " + count);
						}
					}
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		});
		t2.setName("thread2");
		
		//
		t1.start();
		t2.start();
		t1.join();
		t2.join();
	}
}
           

   如果按照下面的時序執行時序，就會導緻死鎖：

線程A	線程B
進入a.swap(b)時獲得a的鎖
在執行t = getValue()時，順利獲得a的鎖（因為已經持有）	進入b.swap(a)時獲得b的鎖
執行v = other.getValue()時，由于需要b的鎖而處于等待的狀态	在執行t = getValue()時，順利獲得b的鎖
執行v = other.getValue()時，由于需要a的鎖而處于等待狀态

   以上的代碼執行一段時間後可能就會發生死鎖。此時可以通過thread dump獲得線程的棧跟蹤資訊。在Unix平台下可以通過向JVM發送SIGQUIT信号（kill -3）獲得thread dump，在Windows平台下則通過Ctrl+Break。以上代碼在死鎖時的thread dump如下：

   Found one Java-level deadlock:

    =============================

    "thread2":

      waiting to lock monitor 0x0003e664 (object 0x230c3f40, a Cell),

      which is held by "thread1"

    "thread1":

      waiting to lock monitor 0x0003e6a4 (object 0x230c3f50, a Cell),

      which is held by "thread2"

    Java stack information for the threads listed above:

    ===================================================

    "thread2":

            at Cell.getValue(Cell.java:18)

            - waiting to lock <0x230c3f40> (a Cell)

            at Cell.swap(Cell.java:27)

            - locked <0x230c3f50> (a Cell)

            at Cell$2.run(Cell.java:65)

            at java.lang.Thread.run(Unknown Source)

    "thread1":

            at Cell.setValue(Cell.java:22)

            - waiting to lock <0x230c3f50> (a Cell)

            at Cell.swap(Cell.java:29)

            - locked <0x230c3f40> (a Cell)

            at Cell$1.run(Cell.java:46)

            at java.lang.Thread.run(Unknown Source)

    Found 1 deadlock.

   為了避免死鎖的危險，在一個同步的方法或者代碼塊中，永遠不要放棄對客戶的控制。換句話說，在一個被同步的區域内部，不要調用一個可被改寫的公有或受保護的方法。從包含該同步區域的類的角度來看，這樣的一個方法是一個外來者（alien）。這個類不知道該方法會做什麼事情，也控制不了它。假設客戶的方法建立另一個線程，再回調到這個類中。然後，建立的線程試圖擷取原線程所擁有的那把鎖，這樣就會導緻建立的線程被阻塞。如果建立該線程的方法正在等待這個線程完成任務，則會導緻死鎖。  

    另外一種比較簡單的避免死鎖的獨占技術是順序化資源（resource ordering），它的思想就是把一個嵌套的synchronized方法或塊中使用的對象和一個數字标簽關聯起來。如果同步操作是根據對象标簽的最小優先（least first）的原則，那麼剛才介紹的例子的情況就不會發生。也就是說，如果線程A和線程B都按照相同的順序獲得鎖，就可以避免死鎖的發生。對于數字标簽的選擇，可以使用System.identityHashCode的傳回值，盡管沒有什麼機制可以保證identityHashCode的惟一性，但是在實際運作的系統中，這個方法的惟一性在很大程度上得到了保證。swap的一個更好的實作如下：

public void swap(Cell other)
{
    if(this == other) return; // Alias check
    else if(System.identityHashCode(this) < System.identityHashCode(other))
    {
        this.doSwap(other);
    }
    else
    {
        other.doSwap(this);
    }
}

private synchronized void doSwap(Cell Other)
{
    long t = getValue();
    long v = other.getValue();
    setValue(v);
    other.setValue(t);
}