Research Of Some Scheduling Problems For Real-Time Tasks On Heterogeneous Clusters

Owing to outstanding performance-price ratio, excellent extensibility and usability, heterogeneous cluster has gradually become the focus of current computer system structure and parallel processing research. Meanwhile, cluster computing technology appears as effective means in solving problems for real-time applications of computing intensity and data intensity since real-time applications turn up in more fields and systematic complexity keeps being intensified. Performance is a key point for the design of clusters, and it always resorts to scheduling. This dissertation mainly deals with scheduling problems for real-time tasks on heterogeneous clusters to meet timing constraints and improve system performance.Specifically, this dissertation investigates three important scheduling problems as follows:1. Scheduling for security-critical real-time tasks on heterogeneous clusters. Nowadays, increasing attention has been directed toward the issue of security services for real-time applications with security requirements on clusters. In this dissertation, we propose a novel two-phase scheduling strategy TPSS which takes timing constraints and security needs into consideration. In the first phase, we propose a novel algorithm DSRF to schedule tasks. When the system is in heavy load, DSRF is able to degrade the security levels of new tasks and tasks waiting in local queues so as to enhance guarantee ratio. On the contrary, when the system is in light load, DSRF is capable of employing slack time to adequately improve the security quality of new tasks. In the second phase, a new algorithm FMSL is proposed to minimize the difference of security levels of accepted tasks and further improve the security levels of these tasks on the whole, which degrades the probability of applications being attacked. We compare TPSS, DSRF, SAEDF and RF by extensive simulations. The experimental results indicate that TPSS significantly outperforms other algorithms and improves the flexibility and security of systems.2. Multi-dimensional scheduling for real-time tasks on heterogeneous clusters. 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 dissertation 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 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.3. Fault-tolerant scheduling for real-time tasks with QoS requirements on heterogeneous clusters. Fault-tolerant scheduling, effective means of improving system performance, plays a significant role in scheduling research. Despite extensive fault-tolerant scheduling has been proposed for real-time tasks on clusters, QoS requirements of some tasks have not been taken into consideration. This dissertation proposes a fault-tolerance scheduling algorithm FTQ for real-time tasks with QoS needs on heterogeneous clusters. FTQ adopts the primary/backup model and takes the timing constraints of tasks, QoS requirments of tasks, reliability of systems, and system resource utilization into consideration. FTQ is able to dynamically adjust the QoS levels of real-time tasks and the execution scheme of backup copies to improve system flexibility, reliability, schedulability and resource utilization. The system reliability is quantitative measured and combined into FTQ, which improves the system performance. Meantime, FTQ strives to advance start time of primary copies and delay the start time of backup copies to make backup versions adopt passive execution scheme or decrease overlap section of primary and backup copies as much as possible so as to improve resource utilization. FTQ is capable of adaptively adjusting the QoS levels of tasks and the execution sheme of backup copies to attain high system flexibility. Besides, overlapping technology of backup copies is employed. The latest start time of backup copies and its constraints are analyzed and discussed. Compared with NOFTQ and DYFARS, FTQ shows obvious superiority to others with higher scheduling quality by considerable simulation experiments.