Scheduling methods for efficient utilization of cluster computing environments

Scheduling a large number of applications on a cluster computing environment is a serious obstacle to achieving good performance. This becomes more critical in real time systems. Due to the NP-completeness of the scheduling problem, most of the related work is based on heuristic techniques with the objective of finding high performance solutions. ^ A cluster scheduler without enough knowledge of the cluster and the scheduled tasks of given applications cannot adequately manage the cluster resources. Consequently, the cluster resources may not be utilized effectively. Much of current allocation and scheduling work dealing with real-time applications has not provided mechanisms to satisfy the application performance requirements while maximizing the processing power utilization. ^ In this thesis, we developed a set of new algorithms and heuristics to schedule real time applications on a cluster. We assumed that each application is represented as a task graph. The objective of these algorithms is to satisfy the deadlines of applications\u27 tasks, to improve the processing power utilization, and to increase the throughput. Our scheduling approaches utilized the available processing power on each processor to accommodate as many different applications\u27 tasks as possible while satisfying the required deadline of each task. The algorithms reduce the communication cost among tasks and the possibility of processing power fragmentation. ^ We proposed scheduling algorithms for different applications\u27 structures: the sequential structures, the fork join structures, conditional structures, and loop structures. We combined the four techniques to schedule general structures. We proved that they produced a better acceptance rate compared to treating each application as one unit. The proposed scheduling techniques have been evaluated through extensive simulation studies and yielded better performance.