On-line Scheduling in Real-Time Multiprocessor Systems

With the trend toward using multiprocessor systems to handle computing intensive applications, the analysis of on-line scheduling algorithms becomes the main interesting issue for real-time multiprocessor systems in recent decades. However, it is difficult to analyze on-line scheduling algorithms in real-time multiprocessor systems because the behavior of a process in a multiprocessor system is more complicated than that in a single processor system. Therefore, in the dissertation, we study on-line scheduling algorithms to explore some nice properties of on-line scheduling algorithms in real-time multiprocessor systems. The scheduling algorithms for real-time systems can be categorized into two classes: non-priority-driven scheduling algorithm and priority driven scheduling algorithms. We focus on the schedulability issue of a non-priority-driven scheduling algorithm and a priority-driven scheduling algorithm for multiprocessor systems. In the first part of the dissertation, we study a non-priority-driven scheduler: Earliest Deadline until Zero Laxity (EDZL) scheduling algorithm. EDZL algorithm is a hybrid algorithm of Earliest Deadline First (EDF) algorithm and Least Laxity First (LLF) algorithm. A set of tasks scheduled by EDZL algorithm is initially scheduled using EDF algorithm until any job has a zero laxity. To avoid a job from missing its deadline, the priority of the job is immediately promoted to the highest priority among all active jobs. Based on the flexible scheduling policy of EDZL, we derive the schedulability bound of 3/2+|umax–1/2| for two-processor systems, where umax is the maximum utilization of an individual task in the given task set. For a comprehensive analysis of EDZL, we further explore some nice properties of EDZL for task sets with some restricted conditions and provide some special cases for EDZL scheduling algorithm. We also discuss the best known upper bound and lower bound on EDZL schedulability conditions. A variation of EDZL algorithm, called EDZL_GCD algorithm, is also discussed and is proved to be an optimal scheduling algorithm. In the second part of the dissertation, we study a priority-driven scheduler: Rate Monotonic (RM) algorithm. We aims to find the schedulable utilization bound of global RM scheduling algorithm for periodic real-time tasks on m identical processors. A method to estimate the allocation of a set of tasks scheduled by RM algorithm in multiprocessor systems is proposed. Based on the analysis of allocation of the tasks, we present a better utilization lower bound of RM in m processor systems for m >1. Compared with earlier results, the proposed schedulability bound is closer to the upper bound on the achievable schedulability condition of RM.