Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters

作     者：朱晓敏 陆佩忠 

作者机构：School of Computer ScienceFudan University 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2009年第24卷第3期

页      面：434-446页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：supported by the National Natural Science Foundation of China under Grant No.60673082 the Special Funds of Authors of Excellent Doctoral Dissertation in China under Grant No.200084. 

主　　题：clusters scheduling multi-dimensional heterogeneous real-time makespan 

摘      要：Multiple performance requirements need to be guaranteed in some real-time applications such as multimedia data processing and real-time signal processing in addition to timing constraints. Unfortunately, most conventional scheduling algorithms only take one or two dimensions of them into account. Motivated by this fact, this paper investigates the problem of providing multiple performance guarantees including timeliness, QoS, throughput, QoS fairness and load balancing for a set of independent tasks by dynamic scheduling. We build a scheduler model that can be used for multi-dimensional scheduling. Based on the scheduler model, we propose a heuristic multi-dimensional scheduling strategy, MDSS, consisting of three steps. The first step can be of any existing real-time scheduling algorithm that determines to accept or reject a task. In step 2, we put forward a novel algorithm MQFQ to enhance the QoS levels of accepted tasks, and to make these tasks have fair QoS levels at the same time. Another new algorithm ITLB is proposed and used in step 3. The ITLB algorithm is capable of balancing load and improving throughput of the system. To evaluate the performance of MDSS, we perform extensive simulation experiments to compare MDSS strategy with MDSR strategy, DASAP and DALAP algorithms. Experimental results show that MDSS significantly outperforms MDSR, DASAP and DALAP.