運行於“計算型網格”上的應用程式，經常會同時利用分散各地的網路資源作資源聯合配置，來降低工作的執行時間。由於網路資源的同質性，使得資源聯合保留的需求不是唯一，因此目前一種允許應用程式擁有多種同質資源需求的資源保留架構已提出。本篇論文確保應用程式在此架構中，成功聯合保留分散於不同領域的網路資源。為了增進效能，我們提出了一種利用先佔式資源達到高效能及死結避免的保留協定，簡稱DFRP2。它允許應用程式將已被保留但尚未使用的資源，能被其他應用程式先行使用，以提昇資源的使用率，此外應用程式可以平行式請求對資源作聯合保留。DFRP2具備了三種特性，高彈性、死結的預防，以及應用程式和資源管理者之間不需要任何的訊息傳遞。模擬結果證明DFRP2比現存的死結預防協定明顯地獲得效能上的改進，尤其是在資源競爭的計算型網格環境中。

Applications executing on “Computational Grid” simultaneously co-reserve multiple resources frequently scattered over Internet to decrease execution time. The redundancy of Internet resources makes the requirement of co-reservation no longer unique, the resource co-reservation structure allowing each application to possess multiple resource requirements is proposed. This thesis ensures that each application successfully co-reserves Internet resources spanning over multiple administrative domains in the resource co-reservation structure. For improving performance, a novel algorithm, Deadlock-Free Reservation Protocol with Preempting resource (DFRP2), is proposed. DFRP2 allows that reserved resources, which are not used by an application, can be preempted and used by the other applications, and allows that applications co-reserve resources defined in the requirements by parallel requests. DFRP2 has three characterizations as follows: (1) high flexibility, (2) freedom from deadlock (3) no communication among applications and resource managers. Simulation results show that DFRP2 outperforms the existing deadlock prevention protocol, especially in the resource competitive Computational Grid.

[1] I. Foster and C. Kesselman, The Grid: Blueprint for a New Computing Infrastructure. San Mateo, CA: Morgan Kaufman, 1998.
[2] K. Czajkowski, and I. Foster, “A resource management architecture for metacomputing systems,” in Proc. the Workshop on Job Scheduling Strategies for Parallel Processing, 1997, pp. 62–82.
[3] K. Czajkowski, I. Foster, and C. Kesselman, “Resource Co-Allocation in Computational Grids,” in Proc. 8th IEEE Int. Symp. High Performance Distributed Computing, 1999, pp. 219-228.
[4] Globus Project. http://www.globus.org
[5] J. Park. “A deadlock and livelock free protocol for decentralized internet resource coallocation,” IEEE Trans. Systems, Man, and Cybernetics, pp. 123–131, Jan. 2004.
[6] M. Singhal and N. G. Shivaratri, Advanced Concepts in Operating Systems: Distributed, Database, and Multiprocessor Operating Systems. New York: McGraw-Hill, 1994.
[7] J. Park. “A scalable protocol for deadlock and livelock free co-allocation of resources in internet computing,” in Proc. Symp. Applications and the Internet, pp. 66–73, Jan. 2003.
[8] M. Singhal, “Deadlock detection in distributed systems,” IEEE Computer, pp. 37–48, Nov. 1989.
[9] J. Park and S. Reveliotis, “Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings,” IEEE Trans. Automat. Contr., vol. 46, pp. 1572–1583, Oct. 2001.
[10] W. A. Chang, G. K. Chung, and Z. C. You, “Soft reservation multiple access with priority assignment (SRMA/PA): a novel MAC protocol for QoS-guaranteed integrated services in mobile ad-hoc networks,” presented at the Vehicular Technology Conference on 52nd IEEE VTS-Fall VTC, vol. 2, pp. 942–947, Sept. 2000.
[11] D. C. Kozen, Automata and Computability. New York: Springer-Verlag, 1997.
[12] L. A. Goldberg and P. D. MacKenzie, “Analysis of practical backoff protocols for contention resolution with multiple servers,” in Proc. 7th Annual Symp. Discrete Algorithms, 1996, pp. 554–563.