Efficient real-time task scheduling in heterogeneous clusters with network limitations

We investigate the problem of scheduling real-time applications in cluster computing environments. The challenge associated with this problem lies in developing scheduling algorithms that efficiently utilize available resources of the cluster, that vary widely with time, to accommodate as many applications as possible while satisfying their strict deadlines. This problem is known to be NP-complete in general. Therefore, a large number of heuristics, each of which works under different circumstances, have been proposed in literature to provide sub-optimal schedules. However, most of these algorithms treat applications as single units and do not exploit their structural features to improve deadlines\u27 satisfaction. In addition, they employ a task allocation technique that reserves a fixed processing power for each task during its interval. As a result, they suffer from inefficient utilization of processing power that degrades their acceptance rate. In this research, we introduce a new scheduling approach for real-time applications structured by task graphs in cluster environments. Our approach offers novel scheduling algorithms that efficiently utilize processing power of the cluster\u27s processors to improve acceptance rate of the applications. First, acceptance rate on a single processor is improved by assigning a variable processing power to a task instead of rejecting it if a constant processing power cannot be guaranteed. Second, on the cluster level, we develop a multi-objective function to optimize different performance criteria namely, processing power fragmentation, context switching, and communication cost. Optimizing these criteria results in better utilization of the processing power of the cluster\u27s processors and consequently improves applications\u27 acceptance rate. We develop scheduling algorithms for applications represented by tandem and fork-join task graphs. Other application models can also be scheduled after converting them to equivalent tandem and/or fork-join structures. We present scheduling algorithms for homogeneous and heterogeneous fully connected clusters. We further extend our work for heterogeneous clusters with limited connectivity. The performance of our approach is evaluated through extensive experiments. A simulation study is used to show the merits of our approach with respect to previous approaches.