| 研究生: |
許家華 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.
[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.