簡易檢索 / 詳目顯示

研究生: 許家華
Hsu, Chia-Hua
論文名稱: 並行程式分析與並行控制之比較與綜效性研究
Concurrent Program Analysis and Concurrency Control: Their inter-relationship and Synergy
指導教授: 徐立群
Shu, Lih-Chyun
學位類別: 碩士
Master
系所名稱: 管理學院 - 會計學系
Department of Accountancy
論文出版年: 2003
畢業學年度: 91
語文別: 中文
論文頁數: 43
外文關鍵詞: Concurrency, Atomic Actions, At Most Once Property, Transaction Chopping, Assertional Reasioning, Atomicity, Synchronization, Serializability
相關次數: 點閱:114下載:2
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 利用並行技術來滿足系統需求在軟體設計上可說是相當普遍。在過去,「軟體分析」與「資料庫系統」兩大領域各自進行並行技術相關課題的研究,甚少有交集。前者稱此項研究為「並行程式分析」,而後者稱為「並行控制」。值得注意的是兩者的研究模式、欲解決的問題,以及各自發展出的解決方案皆有一些相似處,但也有各自的獨特處。我們的研究發覺單一領域之研究觀點可以對另一領域提供新的啟發,甚至新的發現。我們將原本用在資料庫領域中的transaction chopping技術應用在並行程式分析上,我們證明此應用只需付出合理的代價,即可得到較傳統並行程式分析方法較好的效果。另一方面,我們運用並行程式分析之典型技術―assertional reasoning,來驗證一個即時並行控制協定實現方法的正確性。

    The use of concurrency to resolve challenging system requirements with software is common. In the past, two research communities, namely software analysis and database systems, have independently investigated concurrency-related issues. The former uses the term “concurrent program analysis” while the later coins the term “concurrency control.” It is worth noting that their models, problems, and solutions have close proximity and unique characteristics of their own. Our study indicates that each field can provide more insight or even shed new light on the research of the other field. In particular, a program chopping technique, originated in the database area, can be used to analyze programs, which we show outperforms traditional methods employed in concurrent program analysis. On the other hand, we use the assertional approach, a classical way of reasoning about concurrency, to verify the correctness of an implemention of a real-time concurrency control protocol.

    論文摘要...................................................................Ⅰ 目錄.......................................................................Ⅳ 圖目錄.....................................................................Ⅵ 第一章 緒 論...............................................................1 第二章 並行技術之簡介與比較................................................3 第一節 並行程式分析........................................................3 第二節 並行控制............................................................6 第三節 並行程式分析與並行控制之相異與相似處................................8 第三章 應用並行控制理論於並行程式之正確性推理.............................10 第一節 傳統分析方法之探討.................................................10 第二節 CHOPPING ANALYSIS..................................................13 第三節 ANDERSON與GOUDA之標準..............................................24 第四章 以並行程式分析技術驗證並行控制協定實現方法之正確性.................28 第五章 文獻探討...........................................................38 第六章 結 論..............................................................40 參考文獻..................................................................42 圖目錄 圖1 用來表示同一個PROCESS中ACTION有ORDERING限制的例子.....................17 圖2同一個PROCESS中有ORDERING限制的ACTION會導致NON-ATOMIC執行的模式........18 圖3 在CS1中< AWAIT(!IN2 OR LAST==2);>的CHOPPING GRAPH.....................21 圖4 在CS1中< AWAIT(!IN2 OR LAST==2);>的CHOPPING GRAPH,同時加注CS2中ACTION之ORDERING關係..............................................................21

    [AG92] J. Anderson and M. Gouda. “A Criterion for Atomicity, ” Formal Aspects of Computing: The International Journal of Formal Methods , 4(3):273-298, May 1992.
    [AJR97] P. Ammann, S. Jajodia, and I. Ray. “Applying Formal Methods to Semantic-Based Decomposition of Transactions, ” ACM Trans. on Database Systems, 22(2):215-254, June 1997.
    [Anderson90] James H. Anderson. “Composite Registers,” In Poc. of the 9th ACM SIGA CT-SIGOPS Symposium on Principles of Distributed Computing, page15-29,1990.
    [Andrews91] G.R. Andrews. “Concurrent Programming: Principles and Practice, ” Benjamin/Cummings Publishing Company, 1991.
    [BG81] P. Bernstein and N. Goodman. “Concurrency Control in Distributed Database Systems, ” ACM Computing Surveys, 13(2):185-221, June 1981.
    [BGL99] A.J. Bernstein, D.S. Gerstl, and P.M. Lewis. “Concurrency Control for Step-Decomposed Transactions, ” Information Systems, 24(8): 673-698, 1999.
    [BHG87] P.A. Bernstein, V. Hadzilacos, and N. Goodman. “Concurrency Control and Recovery in Database Systems, ” Addison-Wesley Publishing Company, 1987.
    [CES86] E.M.Clake, E.A Emerson, and A.P. Sistla “Automatic Verfication of Finite State Concurrent Systems using Temporal Logic Specifications,” ACM Transactions on Programming Languages and Systems, 8(2):244-263, 1986.
    [CS96a] R. Cleaveland, S.A. Smolka, et al. “Strategic Directions in Concurrency Research,” ACM Computing Surveys, 28(4):607-625, Dec. 1996.
    [CS96b] “Concurrency,” ACM Computing Surveys, 28(4), Dec. 1996.
    [Hartley98] S. Hartley. “Concurrent Programming – The Java Programming Language, ” Oxford University Press, 1998.
    [Hoare85] C.A.R. Hoare. “Communicating Sequential Processes,”Prentice-Hall,1985.
    [Holzmann97] G.J. Holzmann. “The Model Checker SPIN,”IEEE Transactions on Software Engineering, 23(5):279-294, May 1997.
    [Lea00] Doug Lea. “Concurrent Programming in Java  Design Principles and Patterns” 2nd Edition, Addison-Wesley Publishing Company, 2000.
    [OG76] Susan Owicki and David Gries. “An Axiomatic Proof Technique for Parallel Programs I,” Acta Informatica, 6, 319-340, 1976.
    [SS88] D. Shasha and M. Snir. “Efficient and Correct Execution of Parallel Programs that Share Memory,” ACM Trans. on Programming Languages and Systems, 10(2):282-312, April 1988.
    [SSV92] D. Shasha, E. Simon, and P. Valduriez. “Simple Rational Guidance for Chopping Up Transactions,” In Proc. ACM SIGMOD International Conference on Management of Data, pages 298-307, 1992.
    [SY02] LihChyun Shu and Michal Young. “Versioning Concurrency Control for Hard Real-Time System,” Journal of Systems and Software, 63(3):201-218, Sept. 2002 (SCI).
    [WV02] G. Weikum and G. Vossen. “Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery,” Morgan Kaufmann Publisher, 2002.

    下載圖示 校內:2004-07-07公開
    校外:2004-07-07公開
    QR CODE