並行Java程式不確定執行行為之測試方法

Abstract

Java程式語言是一個具跨平台特性之物件導向程式語言，且Java程式語言提供並行機制並具有豐富的類別函式庫，因此越來越多的並行程式以Java程式語言來開發。 然而並行Java程式與其他並行語言程式一樣，有不確定執行行為的問題，所謂不確定執行行為現象即以相同輸入資料反覆地執行同一並行Java程式卻產生不同的輸出結果，因而造成並行Java程式難以測試；本論文針對並行Java程式之不確定執行行為提出一測試方法。 一條並行路徑是由多個執行緒所執行的展開路徑所組成，執行緒之間的執行可能是彼此獨立的或者有溝通與同步的關係，執行緒可藉由呼叫Thread物件的start()或join()函式或者呼叫共用物件的同步函式或wait()/notify()/notifyAll()來達成啟動、同步與溝通的目的。這些執行緒之間的啟動、同步、溝通行為稱為inter-thread activity，本論文將不同的inter-thread activity執行順序視為不同的執行行為，並且利用可達性分析的方法來產生一條並行路徑的所有執行行為。 為了測試的完整性，測試工程師必須對一條有不確定執行行為的並行路徑之所有執行行為皆做測試，然而同一並行路徑之有些不同的執行行為卻有相同的執行結果，從錯誤偵測的角度來看只需要測試其中一種執行行為即可。本論文從共用物件的讀取與寫入動作來分析，發現有相同read/write pattern的inter-thread activity執行順序之不同執行行為，其執行結果是一樣的，因此這些執行行為只需要選取一個來做測試即可。 本研究並將所提的並行Java程式不確定執行行為測試方法加入本實驗室所開發的循序Java程式測試環境，擴充成為並行Java程式測試環境。

The Java programming language makes writing multithreaded code easier by building support for multithreading into the language. As a result, more and more concurrent Java programs are produced. However, the area of concurrent Java program testing has received little attention in research. The phenomenon of non-deterministic execution behavior is that repeated executions of a concurrent program with the same input may exercise different execution behaviors and produce different outputs at different executions. Similar to other concurrent programs, concurrent Java programs may also have non-deterministic execution behaviors. This thesis identifies the issues caused by non-deterministic execution behavior in concurrent Java program testing and proposes solutions. A concurrent path consists of the expanded paths executed by distinct threads. The threads can be independent or have start/synchronization/communication relationships: threads can start(synchronize) other threads by calling the Thread object's start(join) method or communicate with each others by sending messages to the same object. These start/synchronization/communication activities are called inter-thread activity. Different inter-thread activity execution sequences are treated as different execution behavior. This thesis uses the reachability analysis technique to generate the all execution behaviors of a concurrent path. For the completeness of program testing, testers must test all execution behaviors of a concurrent path. But some different execution behaviors of a concurrent path have the same execution result. In consideration of test efficiency, test one of them is enough because no new errors will be uncovered by testing other ones. This thesis abstract the read/write pattern of the inter-thread activity execution sequence and found that different inter-thread activity execution sequences that have the same read/write pattern will produce the same execution result，so that test one of theses inter-thread activity execution sequences is enough. A testing environment based on the proposed solutions has been implemented.