雲端計算環境中雙階層計畫與工作排程演算法

This study addresses a two-tier scheduling problem in a cloud computing environment. In this problem, a project represents a cloud user’s request consisting of multiple jobs, and each job requires several resources for its processing. The goals are to reduce the project turn-around time and to support priority scheduling by employing suitable scheduling algorithms. Due to the lack of efficient algorithms for such a two-tier scheduling problem, here we propose a set of two-tier backfilling algorithms which extend the well-known conservative backfilling algorithm with project’s slack and priority concepts. Among the proposed algorithms, Two-Tier Strict Backfilling (2TSB) does not allow preemption in job and project waiting queues. On the other hand, preemption is considered by Two-tier Flexible Backfilling (2TFB) which has two versions: 2TFB and 2TFB-SF (slack factor). In 2TFB, a new incoming project can preempt waiting jobs but not waiting projects; while 2TFB-SF permits preemption in both job and project waiting queues. Two-Tier Priority Backfilling (2TPB) algorithm takes priority into account such that only high-priority projects can preempt the low-priority ones. The experimental results indicate that, compared to 2TSB, 2TFB-SF could reduce the mean job turn-around time by 15% and 2TPB could reduce the mean turn-around time of high-priority projects by 25%.

關鍵字

雲端排程；雙層；回填法；寬鬆係數；優先等級排程法

並列摘要

本研究旨在解決當今雲端計算環境下的雙層排班(two-tier scheduling)問題。在此問題之中，一個計畫(project)就代表著一位雲端使用者的請求，是由多項工作(job)所組合而成，而每項工作的處理需要數種資源。研究目標是使用適合的排程演算法來縮短計畫的回復時間(turn-around time) 以及支援優先等級排程 (priority scheduling) 。由於這種雙層排班問題一直以來缺少有效率之演算法，我們在此提出一組雙層回填(Two-tier Backfilling)演算法，而這組演算法乃根據著名的保守回填(Conservative Backfilling)演算法並結合計畫的寬鬆係數與優先權等概念所擴展而來。雙層嚴格回填(Two-tier Strict Backfilling, 2TSB) 演算法不允許在工作或計劃等待佇列內搶佔 (preemption) 。另一方面，可允許搶佔的雙層彈性回填(Two-tier Flexible Backfilling)演算法則有兩種版本：2TFB和2TFB-SF。在2TFB演算法中，新抵達的工作可以搶佔正在等待的工作，可是新抵達的計畫不能搶占正在等待的計畫；相比之下，2TFB-SF演算法允許在工作和計畫佇列內搶佔。雙層優先等級回填(Two-tier Priority Backfilling, 2TPB)演算法把優先權納入考量，因此只有某些高優先權計劃能夠搶佔低優先權計畫。實驗結果指出2TFB-SF演算法可以縮短工作平均回復時間約15%，而和2TSB 相比，2TPB演算法可以縮短高優先權計畫的平均回復時間約25%。

並列關鍵字

cloud scheduling ； two-tier ； backfilling ； slack factor ； priority scheduling

參考文獻

[17] S. Srinivasan, R. Kettimuthu, V. Subramani, P. Sadayappan, “Selective reservation strategies for backﬁll job scheduling,” in Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), vol. 2537 of LNCS, pp 55–71. Springer Verlag, 2002.

[1] L. Ai, M. Tang, C. Fidge, “Resource allocation and scheduling of multiple composite web services in cloud computing using Cooperative Coevolution,” in International Conference on Neural Information Processing (ICONIP 2011), Shanghai, China, pp.13-17, Sep. 2011.

[3] A.P.A. Vestjens, “On-line Machine Scheduling,” Ph.D. Thesis, Department of Mathematics and Computing Science, Technische Universiteit Eindhoven, Eindhoven, The Netherlands, 1997.

[4] A. Benoit, L. Marchal, J.-F. Pineau, Y. Robert, F. Vivien, "Scheduling Concurrent Bag-of-Tasks Applications on Heterogeneous Platforms," in IEEE Transactions on Computers, vol.59, no.2, pp.202–217, Feb. 2010.

[5] C. Anglano, M. Canonico, "Scheduling algorithms for multiple Bag-of-Task applications on Desktop Grids: A knowledge-free approach," in IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2008), pp.14–18, April 2008.

國際替代計量

雲端計算環境中雙階層計畫與工作排程演算法

全文下載

主題瀏覽