針對Java monitor的動態測試

Abstract

在並行程式中會透過同步機制保護共享資源的存取和進行執行緒間的通訊。在測試並行程式時，我們必須要考慮並行程式的非確定性行為。透過紀錄及控制程式執行的方式，發現並行程式潛在的錯誤。然而對於使用各種同步機制的並行程式而言，同步機制可能使得記錄與控制執行的方式更為複雜，需要更進一步針對各種同步機制的行為進行研究，才能適當地完成測試。Java程式語言中提供了monitor作為主要的同步機制之一。相較於semaphore，monitor提供了更多同步操作，諸如wait及notify等，複雜度較高。除此，誤用monitor可能會造成程式死結，這也是需要透過測試發現的。本篇論文運用dynamic effective testing，對Java monitor進行測試。能夠找出並行程式中死結的發生位置，以及產生並行程式使用Java monitor的所有狀態。在運用時我們需要實做Java monitor的prefix-based replay protocol，並且提出一個演算法濾除不符合Java monitor semantic的race variant。最後我們做了簡化的動作，大幅度的降低程式的測試時間。In this thesis, we study how to apply the dynamic effective testing to Java programs which the synchronization mechanism is the Java monitor. Compare with the shared-memory access and shared semaphore based concurrent program, Java monitor based concurrent programs exhibit much more complicated synchronization behavior as the Java monitor contains "wait", "notify", "notify all", and exclusive execution of synchronization methods and a segment of codes. Thus, we need to design new prefix-based replay protocol for Java monitor based concurrent program to conduct dynamic effective testing. We also design an algorithm to make the feasibility check of generated race variants. According to the implementation and experimental results, we demonstrate that we can perform dynamic effective testing on Java monitor based concurrent program to achieve the goal of state-cover testing.