針對Java Monitor的可達性測試

Reachability Testing with Java Monitor

林恆毅(Heng-Yi Lin)

指導教授 ： 黃冠寰

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2012年)

摘要

隨著多核心電腦的快速發展，軟體也趨向多執行緒開發，然而，並行程式會造成非決定性行為，也就是說給定一組輸入，執行多次後可能會產生多個不同運行順序和結果，這產生了一個關於同步程式測試的重要議題：如何將目標程式所有可能執行順序找出來，在這篇論文中，我們提出了一個動態測試架構，可運用在Java監視器和共享記憶體上，這個動態測試架構只需要去分析在執行時蒐集到的同步序列，而不需要對語法以及語義做靜態測試，更不需要使用測試模組來找出所有可能的交錯執行順序，只要可行的同步序列是有限的，就能使用我們提出的架構來進行測試，找出並行程式所有可能的執行順序，達到測試的效果。

關鍵字

並行程式 ； 訊號機 ； 共享記憶體 ； 非決定性行為 ； 並行測試 ； 同步序列 ； 可達性測試 ； 動態效率測試 ； 監視器

並列摘要

Concurrent programs exhibit nondeterministic behavior in that multiple executions thereof with the same input might produce different sequences of synchronization events and different results. This is because different executions of a concurrent major issues in the testing of concurrent programs is to explore different interleavings or exhaust all the possible interleavings of the target programs. In this paper we present a framework we have developed for performing dynamic testing on monitor-based and shared-memory concurrent programs. The proposed scheme only has to analyze the synchronization sequences (SYN-sequences) that are collected during the dynamic testing of the concurrent program – static analysis of syntax and semantics of the target concurrent program is unnecessary. It also does not need to employ a model checker to explore the feasible interleavings of the execution of the concurrent program. If the SYN-sequence of the tested concurrent program is finite, our scheme can perform dynamic testing on all the feasible SYN-sequences. The implementation and experimental results obtained with real codes and some benchmark programs demonstrate the feasibility of the proposed scheme.

並列關鍵字

Concurrent program ； Semaphore ； Shared-memory ； Nondeterministic behavior ； Concurrent testing ； SYN-sequence ； Reachability testing ； Dynamic effective testing ； Java monitor

參考文獻

[1]Charles E. Mcdowell and David P. Helmold, "Debugging Concurrent Programs," ACM Computing Surveys, Volume 21, Issue 4, December 1989.

[2]Anne Dinning, "A Survey of Synchronization Methods for Parallel Computers, " IEEE Computer, July 1989.

[4]Gwan-Hwan Hwang, Kuo-Chung Tai, and Ting-Lu Huang, "Reachability Testing: An Approach To Testing Concurrent Software, " International Journal of Software Engineering and Knowledge Engineering, 5, 4, pp. 493-510, December 1995.

[5]Gwan-Hwan Hwang, "A Systematic Parallel Testing Method for Concurrent Programs, "Master Thesis, Institute of Computer Science and Information Engineer, National Chiao-Tung University, Taiwan, 1993.

[7]K. C. Tai, "Testing of Concurrent Software, " Proceeding of the 13th annual International Computer Software and Applications Conference, pp. 62-64, 1989.