容錯叢集下工作排程的改善方法

Improvement for Scheduling within fault-Tolerant Cluster

簡少凡(Shao-Fan Jian)

指導教授 ： 薛智文

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201803211

摘要

容錯叢集是即時系統中重要的議題之一。工作容錯排程演算法中，已經有大量的文獻提出以副本平行運算來預防 CPU 故障的各種演算法，甚至有文獻提出的演算法有良好的排程策略，如最小化 CPU 之最大負載。但少有文獻提出待機副本的排程演算法，也就是需要時才啟用。同時針對使用平行運算與待機副本的情況，我們提出貪婪演算法 (WFDK)降低 CPU 使用數量，並得到良好的排程結果，盡可能達到 CPU 間負載平衡。我們證明了 WFDK 演算法的上界，也分析了演算法結果和相關演算法效能比較，還有與最佳解之間的差異。因為其簡單性且又能有效地減少過度浪費的 CPU 資源，我們認為 WFDK 演算法在容錯叢集系統中有很大的應用潛力。

關鍵字

容錯叢集 ； 排程演算法 ； 最差合適 ； 工作副本

並列摘要

Fault-tolerant cluster has been playing an important role in real-time system for a long time. Researches during the past few decades on the topic of scheduling within fault-tolerant cluster have been focused on various algorithms with running the parallel replicas operation to prevent processor from failures. Even some of the papers indicated great scheduling strategies of algorithms such as minimized processor of maximum loading. However, a few theses have been reported for scheduling algorithms of standby replicas, which means that it would be executed when needed. In the case of running parallel computing and standby replicas, we propose the greedy algorithm (WFDK) to reduce the usage of processors and get better results of scheduling operation which is trying to achieve load balancing among processors. According to WFDK which is based on the worst fit decreasing, we found its upper bound. We analyze the performance of the greedy algorithm and compare its performance to other relative algorithms. Through the experiments, we get the gap in the number of processors between worst case of WSDK and optimum solution. Because of the simplicity of operating WFDK and its ability to effectively reduce the number of processors, we believe that the WFDK algorithm has significant potential applications in fault-tolerant cluster systems.

並列關鍵字

fault-tolerant cluster ； scheduling algorithms ； worst-fit ； working replicas

參考文獻

[1] C. L. Liu and J. Layland, ”Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,” Journal of the ACM, vol. 10, no. 1, pp.46–61, Jan. 1973.

[2] D. S. Johnson,Near optimal bin packing algorithms, Ph. D. Th., MIT, Cambridge, Mass., June 1973.

[3] COFFMAN, JR, E. G., GAREY, M. R., AND JOHNSON, D. S. An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7 (1978), 1-17.

[4] D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey andR. L. Graham, Worst case bounds for simple one-dimensional packing algorithms,SIAM J. Comptg. 3 (1974), 299–325.

[5] D. S. Johnson, Fast algorithms for bin packing,J. Comptr. Syst. Sci. 8 (1974), 272–314.