巨型資料光碟櫃中 強化Local-Spin GME演算法之研究

The Research of Local-Spin GME Algorithm Enhancement of Magnificent Data Storage Jukebox

黃世宇(Shyh-yeu Huang)

指導教授 ： 黃士殷

元智大學/資訊學院/資訊工程學系/碩士(2008年)

摘要

CTP問題，指的是一群哲學家為了滿足需求而爭奪一共同資源的典型群組互斥問題，解決方法是必需設計出一種符合「Mutual Exclusion」、「Bounded Delay」、「Concurrent Entering」的演算法。目前已有人設計出一種使用Local-Spin的演算法來解決此問題。

在本篇研究中，我們提出一種改良後的演算法，ELS，應用在巨型資料光碟櫃的行程管理、資源分配。ELS將原本僅一個Critical Section的演算法擴充為複數個，再增加權重機制的設計以區分群組的任務級別，最後為因應同種類任務數量繁多的情況下，再增加資源重複的設計考慮，以充份利用閒置的Critical Section，提昇整體輸出量。最後並提出模擬執行的數據來進一步驗證我們的構想。

關鍵字

光碟櫃 ； 群組互斥 ； 區域性固定變數 ； 負載平衡

並列摘要

Solutions of the CTP problem, a typical group mutual exclusion problem in which a group of philosophers competing for a resource, have to satisfy the requirements of “mutual exclusion”, “bounded delay”, and “concurrent entering.” Local-Spin algorithm has been developed to solve such problems.

In this thesis, we present an enhanced algorithm, ELS, and apply the algorithm on process and resource management of magnificent data storage jukeboxes. The ELS algorithm extends single critical section to multiple critical sections, assigns a weight to each mission to determine the priority of each mission, and make use of idle CD-ROM drives whenever possible to increase the quantity of the data output.The simulation results confirm the effectiveness of the proposed algorithm.

並列關鍵字

Data Storage Jukebox ； Group Mutual Exclusion ； Local-Spin ； Load Balance

參考文獻

[1] P. Keane and M. Moir, “A Simple, Local-Spin Group Mutual Exclusion Algorithm,” Proc. 18th Ann. ACM Symp. Principles of Distriubted Computing, pp. 23-32, 1999.

[2] L. Lamport, “A Fast Mutual Exclusion Algorithm,” ACM Trans. Computer Systems, vol. 5, no. 1, pp. 1-11, 1987.

[3] Y.-J. Joung, “Asynchronous Group Mutual Exclusion,” Proc. 17th Ann. ACM Symp. Principles of Distriubted Computing, pp. 51-60, 1998.

[4] Y.-J. Joung. “The Congenial Talking Philosophers Problem in Computer Networks,” In Proceedings of the 13th International Symposium on Distributed Computing (DISC’99), 1999.

[7] Quorum-based algorithms for group mutual exclusion, Yuh-Jzer Joung Parallel and Distributed Systems, IEEE Transactions on On page(s): 463- 476, Volume: 14, Issue: 5, May 2003