Capturing urgency and parallelism using quasi-deadlines for real-time multiprocessor scheduling

Recent trends toward multi-core architectures in real-time embedded systems pose challenges in designing efficient real-time multiprocessor scheduling algorithms. We believe that it is important to take into consideration both timing constraints of tasks (urgency) and parallelism restrictions of multiprocessor platforms (parallelism) together when designing scheduling algorithms. Motivated by this, we define the quasi-deadline of a job as a weighted sum of its absolute deadline (capturing urgency) and its worst case execution time (capturing parallelism) with a system-level control knob to balance urgency and parallelism effectively. Using the quasi-deadline to prioritize jobs, we propose two new scheduling algorithms, called EQDF (earliest quasi-deadline first) and EQDZL (earliest quasi-deadline until zero laxity), that are categorized into job-level fixed-priority (JFP) scheduling and job-level dynamic-priority (JDP) scheduling, respectively. This paper provides a new schedulability analysis for EQDF/EQDZL scheduling and addresses the problem of priority assignment under EQDF/EQDZL by determining a right value of the system-level control knob. It presents optimal and heuristic solutions to the problem subject to our proposed EQDF and EQDZL analysis. Our simulation results show that EQDF and EQDZL can improve schedulability significantly compared to EDF and EDZL, respectively.