rainmanyang

所面臨的問題

這幅圖中節點代表一個 single Thread，邊代表執行的步驟。

整幅圖代表的意思是，ROOT 線程執行完畢后執行 T1 線程，T1 執行完畢后并發的執行 T2 和 T3。而從 T2 和 T3 指向 T4 的兩條邊表示的是 T4 必須等 T2 和 T3 都執行完畢以后才能開始執行。剩下的步驟以此類推，直到 END 作為整個過程的結束。當然，這只是個簡略的示意圖，可能面對的一個線程場景會有上百個線程。還有，你可以觀察到這整個場景只有一個入口點和一個出口點，這意味著什么？在下文中為你解釋。

這其中涉及到了 Java 線程的同步互斥機制。例如如何讓 T1 在 T2 和 T3 之前運行，如何讓 T2 和 T3 都執行完畢之后開啟 T4 線程。

模型的描述

如何來描述圖 1 中所示的場景呢？可以采用 XML 的格式來描述我們的模型。我定義一個“Thread” element 來表示線程。

其中 ID 是線程的唯一標識符，PRETHREAD 便是該線程的直接先決線程的ID，每個線程 ID 之間用逗號隔開。

在 Thread 這個 element 里面可以加入你想要該線程執行任務的具體信息。

實際上模型的描述是解決問題非常重要的一個環節，整個線程場景可以用一種一致的形式來描述，作為 Java 多線程并發控制框架引擎的輸入。也就是將線程運行的模式用 XML 來描述出來，這樣只用改動 XML 配置文件就可以更改整個線程運行的模式，不用改動任何的源代碼。

兩種實現機制

對于 Java 多線程的運行框架來說，我們將采用“外”和“內”的兩種模式來實現。

“外” - 主線程輪詢

Thread 是工作線程。ThreadEntry 是 Thread 的包裝類，prerequisite 是一個 HashMap，它含有 Thread 的先決線程的狀態。如圖1中顯示的那樣，T4 的先決線程是 T2 和 T3，那么 prerequisite 中就包含 T2 和 T3 的狀態。TestScenario 中的 threadEntryList 中包含所有的 ThreadEntry。

TestScenario 作為主線程，作為一個“外”在的監控者，不斷地輪詢 threadEntryList 中所有 ThreadEntry 的狀態，當 ThreadEntry 接受到 isReady 的查詢后查詢自己的 prerequisite，當其中所有的先決線程的狀態為“正常結束時”，它便返回 ready，那么 TestScenario 便會調用 ThreadEntry 的 startThread() 方法授權該 ThreadEntry 運行線程，Thread 便通過 run() 方法來真正執行線程。并在正常執行完畢后調用 setPreRequisteState() 方法來更新整個 Scenario，threadEntryList 中所有 ThreadEntry 中 prerequisite 里面含有該 Thread 的狀態信息為“正常結束”。

如圖 1 中所示的 T4 的先決線程為 T2 和 T3，T2 和 T3 并行執行。如圖 4 所示，假設 T2 先執行完畢，它會調用 setPreRequisteState() 方法來更新整個 Scenario， threadEntryList 中所有 ThreadEntry 中 prerequisite 里面含有該 T2 的狀態信息為“正常結束”。此時，T4 的 prerequisite 中 T2 的狀態為“正常結束”，但是 T3 還沒有執行完畢，所以其狀態為“未完畢”。所以 T4 的 isReady 查詢返回為 false，T4 不會執行。只有當 T3 執行完畢后更新狀態為“正常結束”后，T4 的狀態才為 ready，T4 才會開始運行。

其余的節點也以此類推，它們正常執行完畢的時候會在整個的 scenario 中廣播該線程正常結束的信息，由主線程不斷地輪詢各個 ThreadEntry 的狀態來開啟各個線程。

這便是采用主控線程輪詢狀態表的方式來控制 Java 多線程運行框架的實現方式之一。

優點：概念結構清晰明了，實現簡單。避免采用 Java 的鎖機制，減少產生死鎖的幾率。當發生異常導致其中某些線程不能正常執行完畢的時候，不會產生掛起的線程。

缺點：采用主線程輪詢機制，耗費 CPU 時間。當圖中的節點太多的(n>??? 而線程單個線程執行時間比較短的時候 t<??? 需要進一步研究)時候會產生線程啟動的些微延遲，也就是說實時性能在極端情況下不好，當然這可以另外寫一篇文章來專門探討。

“內” - wait&notify

相對于“外”-主線程輪詢機制來說，“內”采用的是自我控制連鎖觸發機制。

Thread 中的 lock 為當前 Thread 的 lock，lockList 是一個 HashMap，持有其后繼線程的 lock 的引用，getLock 和 setLock 可以對 lockList 中的 Lock 進行操作。其中很重要的一個成員是 waitForCount，這是一個引用計數。表明當前線程正在等待的先決線程的個數，例如圖 1 中所示的 T4，在初始的情況下，他等待的先決線程是 T2 和 T3，那么它的 waitForCount 等于 2。

當整個過程開始運行的時候，我們將所有的線程 start，但是每個線程所持的 lock 都處于 wait 狀態，線程都會處于 waiting 的狀態。此時，我們將 root thread 所持有的自身的 lock notify，這樣 root thread 就會運行起來。當 root 的 run 方法執行完畢以后。它會檢查其后續線程的 waitForCount，并將其值減一。然后再次檢查 waitForCount，如果 waitForCount 等于 0，表示該后續線程的所有先決線程都已經執行完畢，此時我們 notify 該線程的 lock，該后續線程便可以從 waiting 的狀態轉換成為 running 的狀態。然后這個過程連鎖遞歸的進行下去，整個過程便會執行完畢。

我們還是以 T2，T3，T4 為例，當進行 initThreadLock 過程的時候，我們可以知道 T4 有兩個直接先決線程 T2 和 T3，所以 T4 的 waitForCount 等于 2。我們假設 T3 先執行完畢，T2 仍然在 running 的狀態，此時他會首先遍歷其所有的直接后繼線程，并將他們的 waitForCount 減去 1，此時他只有一個直接后繼線程 T4，于是 T4 的 waitForCount 減去 1 以后值變為 1，不等于 0，此時不會將 T4 的 lock notify，T4 繼續 waiting。當 T2 執行完畢之后，他會執行與 T3 相同的步驟，此時 T4 的 waitForCount 等于 0，T2 便 notify T4 的 lock，于是 T4 從 waiting 狀態轉換成為 running 狀態。其他的節點也是相似的情況。

當然，我們也可以將整個過程的信息放在另外的一個全局對象中，所有的線程都去查找該全局對象來獲取各自所需的信息，而不是采取這種分布式存儲的方式。

優點：采用 wait&notify 機制而不采用輪詢的機制，不會浪費CPU資源。執行效率較高。而且相對于“外”-主線程輪詢的機制來說實時性更好。

缺點：采用 Java 線程 Object 的鎖機制，實現起來較為復雜。而且采取一種連鎖觸發的方式，如果其中某些線程異常，會導致所有其后繼線程的掛起而造成整個 scenario 的運行失敗。為了防止這種情況的發生，我們還必須建立一套線程監控的機制來確保其正常運行。

延伸

下面的圖所要表達的是這樣一種遞歸迭代的概念。例如在圖1 中展示的那樣，T1 這個節點表示的是一個線程。現在，忘掉線程這樣一個概念，將 T1 抽象為一個過程，想象它是一個銀河系，深入到 T1 中去，它也是一個許多子過程的集合，這些子過程之間的關系模式就如圖 1 所示那樣，可以用一個圖來表示。

可以想象一下這是怎樣的一個框架，具有無窮擴展性的過程框架，我們只用定義各個過程之間的關系，我們不用關心過程是怎樣運行的。事實上，可以在最終的節點上指定一個實際的工作，比如讀一個文件，或者submit一個JCL job，或者執行一條sql statement。

其實，按照某種遍歷規則，完全可以將這種嵌套遞歸的結構轉化成為一個一層扁平結構的圖，而不是原來的分層的網狀結構，但是我們不這樣做的原因是基于以下的幾點考慮：

1. 如果這樣做，會導致圖節點太多，邊太多，令人眼花繚亂。
2. 不這樣做更主要的原因是每一個場景，如圖 7 中的 T1，T13，是狀態聚集的一個單元，具有高復用性和可靠性。
3. 框架是高度抽象的，它實際的執行可以是分布式的，一個單元可以是一個系統，作為和其他系統的分界標志。

實際上，這是一個狀態聚集的層次控制框架，我們可以依賴此框架來執行自主運算。我們將在其它的文章中來討論它的應用。

總結

本文介紹了一種 Java 多線程并發控制的框架，并給出了其兩種實現的模型，它們有各自的優缺點，有各自的適用范圍。當需要進行 Java 線程的并發控制的時候，可以作為參考。

參考資料

• developerWorks Java 專區 Peter Haggar 的文章：Apply the Specific Notification pattern to control the order of thread execution
  
  
• Doug Lea 的著名并發性圖書：Java 并發編程: 設計原則與模式. 第二版(Addison Wesley 1999)
  
  
• 另一本關于并發性的圖書：Java Concurrency in Practice
  
  
• developerWorks Java 專區 Joseph Hartal，Ze'ev Bubis 的文章：使你輕松得進行多線程應用程序編程
  
  
• developerWorks Java 專區 Alex Roetter 的文章：編寫多線程的Java應用程序
  
  
• developerWorks Java 專區 Neel V. Kumar 的文章：Java 程序中的多線程

關于作者

		陳威，華中科技大學碩士，IBM CSDL Software Engineer，所在的 Team 是 DB2 for z/OS。聯系方式：chenwbj@cn.ibm.com