並行Java程式測試環境中並行路徑選取方法之研究

Abstract

執行一並行Java程式，若所執行之main()函式會啟動一或多個主動物件之run()函式，則這些run()函式將與main()並行執行，所有可能並行執行的路徑組合均需驗證其正確性，方可保證這條main()函式路徑的正確性，如何選擇最少並行路徑組合予以測試是一個重要課題，唯目前尚無系統化方法被提出，本研究之目的在提出一系統化方法以解決此問題。 欲以最少數目的並行路徑來測試上述執行行為，需保證每一run()之路徑及每一由shared object所產生之不同run()的路徑互動行為皆被驗證。本研究提出以直接資料流來代表二個不同run()之路徑呼叫同一shared object/class函式之互動行為，由於一條路徑可能呼叫多個不同shared object/class的函式，因此二直接資料流將產生互動影響而構成間接資料流。運用資料流關係可以找出所有有互動關係之路徑組合，這些路徑組合皆需被測試；這些路徑組合與所有未呼叫shared object的函式之路徑均需被測試。 尋找最少組合之並行路徑來驗證所有路徑組合與所有未呼叫shared object的函式路徑之問題竟然與graph coloring之問題相等，無法在polynomial time內找出最佳解，本研究採用gaming tree之look-ahead策略來尋找並行路徑，其計算複雜度為O(N^4)。 經用多個範例驗證，本研究所提方法所找出並行路徑數目確為最佳解，且可在短時間內找出，證實本研究所提方法實用性與有效性。

In concurrent Java program, the main() method may create one or more threads to execute the run() methods of active objects. Thus, the run() methods would be executed parallel with the main() method. There are many different combinations of paths that may be executed parallel, and a combination is named a concurrent path. In order to ensure the correctness of the main() method, it is necessary to verify the correctness of all different concurrent paths. In concurrent program testing, it is a very important issue how we select the fewest concurrent paths to test. Unfortunately, there is not a systematic measure to solve this problem. So this research is about to propose one systematic measure to solve this problem. If we want to test all execution behaviors of a concurrent program with fewest concurrent paths, we need to ensure every run() path and every inter-thread interaction could be verified during testing. In this research, we propose that there might exist data-flows between two paths belonging to different run() methods when they call the same shared object’s functions. We also notice that a path may call different shared objects’ functions. Thus one directly data-flow may affect another. This is so-called indirectly data-flow. We can find all combinations of paths which have interactions by using data-flows, and all combinations that have been found should to be tested. These combinations and other paths without shared objects should to be tested. The problem of finding the fewest path combinations is equivalent to the graph coloring problem. It is impossible to find the optimal solution in polynomial time. Thus, this research adopts the look-ahead policy of the Gaming Tree mechanism to find the concurrent paths, and it has time complexity of O(N^4). Via various examples, it shows that the proposed mechanism in this research can find the optimal solution for this problem quickly and ensures the practicality and validity.