簡易檢索 / 詳目顯示

研究生: 林哲生
Che-Sheng Lin
論文名稱: 利用可達性測試法驗證具忙碌等待迴圈之並行程式
Reachability Testing for Concurent Programs with Busy-Waiting Loops
指導教授: 黃冠寰
Hwang, Gwan-Hwan
學位類別: 碩士
Master
系所名稱: 資訊教育研究所
Graduate Institute of Information and Computer Education
論文出版年: 2005
畢業學年度: 93
語文別: 英文
中文關鍵詞: 可達性測試法忙碌等待迴圈並行程式軟體測試
英文關鍵詞: Reachability Testing, Busy-Waiting Loops, Concurrent Program, Software Testing
論文種類: 學術論文
相關次數: 點閱:168下載:6
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 現行軟體架構日趨複雜,並行式系統已然普遍存在各式軟體架構之中;舉凡任何涉及存取共同資料的程式,皆可歸為並行式系統的範疇。
    並行式系統最大的特點在於執行上的「不可決定行為」,意即在相同的輸入條件下,程式可能因為相互間各個細部指令執行順序(SYN-sequence)上的不同,而衍生執行結果的差異;這是因為整個系統於運作時,有許多單元或程式會同時去讀取或修改相同的共享資料而產生race condition。
    此篇研究主要在於發展一種測試的方法,用以偵測並行式系統執行中可能產生的錯誤。並以現有的Reachability Testing為基礎,改進測試具有迴圈指令程式時的效率性。

    Contents 2 Figures 4 Abstract 5 Chapter 1 Introduction 7 1.1 Testing and Debugging 7 1.2 Concurrent Programs 8 1.2.1 Repeat Execution and Nondeterministic Behavior 10 1.2.2 Probe Effect 12 1.3 Difficulties of Testing Concurrent Programs 12 1.3 Reachability Testing 13 1.3.1 Problems When Dealing with Busy-Waiting Loops 14 1.4 Organization of Thesis 15 Chapter 2 Reachability Testing and Busy-Waiting Loops 16 2.1 Terminologies used in Reachability Testing 16 2.2 Taxonomy of Busy-Waiting Loops 17 2.2.1 Deadlock 18 2.2.2 Livelock 19 2.3 Inside Reachability Testing 20 2.3.1 An Example 20 2.4 Problems When Reachability Testing Dealing with Loops 21 Chapter 3 Spontaneous Locating of Infinite Loops 23 3.1 Target Model 23 3.1.1 Structure of Loop Statements 23 3.1.2 Abstract of the Algorithms 24 3.2 A New Monitor Protocol of Reachability Testing 24 3.2.1 Details of Implementation 24 3.2.2 Example 1 26 3.2.3 Example 2 27 3.2.4 Example 3 28 3.2.5 Example 4 29 3.2.6 Example 5 30 3.3 Dependency Graph 31 Chapter 4 Prune away Unnecessary Analysis in Reachability Testing for Analysis Livelock 33 4.1 RV Derivation of Reachability Testing 33 4.2 Improvement of RV Derivation 34 4.4 An Example 36 Chapter 5 Conclusion and Future Works 39 5.1 Future Work 39 Bibliography 40

    [1]
    IBM System Journal: Software Testing and Verification, Volume 41, Number 1, 2002
    [2]
    E. W. Dijkstra, "Notes on Structured Programming," Structured Programming, O.-J. Dahl, E. W. Dijkstra, and C. A. R. Hoare, Editors, Academic Press, London (1972), pp. 1-82
    [3]
    B. Hailperm, P. Santhanam, "Software debugging, testing, and verification". IBM System Journal: Software Testing and Verification, Volume 41, Number 1, 2002
    [4]
    Wen C. Pai, Selecting Software Testing Criterion based on Complexity Measurement
    [5]
    Silbershcatz, Operating System Concepts 6th Edition
    [6]
    Gwan-Hwan Hwang, Master Thesis, "A Systematic Parallel Testing Method for Concurrent Programs"
    [7]
    Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", Communication of the ACM, Volume 21, Number 7, pp.95-114
    [8]
    Gwan-Hwan Hwang , Sheng-Jen Chang, and Huey-Der Chu, "Technology for Testing Nondeterministic Client/Server Database Applications". IEEE Transaction on Software Engineering, Volume 30, Number 1, pp. 59-77, January 2004.

    QR CODE