Algorithms and techniques for joint task scheduling in open computing systems
Michael E. Thomadakis, Jyh-Charn Steve Liu · 1999
Emerging and future open real-time systems are faced with the Joint-Task Scheduling Problem (JTSP), where tasks with mixed timing constraints and workload parameters, must be guaranteed timely access to system resources. This dissertation investigates the JTSP focusing on preemptive, priority driven scheduling methods. We decompose the JTSP into a number of sub-problems, all of which require the guaranteed scheduling of critical periodic tasks along with different types of aperiodic tasks. First, we address the firm aperiodic scheduling, in which the scheduler must guarantee on-line the timely execution of firm tasks. Second, we address the soft aperiodic scheduling, where the scheduler must guarantee to service soft tasks at the earliest possible time. Both problems are challenging, with present state-of-the-art methods requiring pseudo-polynomial complexity to provide these guarantees to each single aperiodic task. In this research we develop linear time algorithms for these two problems, capitalizing on our Extreme-Schedule (ExS) framework and Workload-Matrix (WM) methods. The ExS characterizes quantitatively the two unique, fixed-priority schedules of a periodic task set, the Fixed-Priority First (FPF) and the Latest-Deadline Last (LDL). FPF and LDL are non-idling and idling schedules, respectively, which capture the dynamic temporal relocation limits of the periodic tasks. We prove that switching between them, at the appropriate time, enables the optimal allocation of service to non-periodic tasks, without violating deadlines. The WM method quantifies the idle processor capacity precisely within arbitrary schedule intervals, in time Θ( n). It is the first published method to accomplish this in linear time, with previous methods requiring pseudopolynomial time. For interactive (IA) tasks we propose a two-level capacity reservation to guarantee acceptable response times to fine-grained tasks and minimum progress of the overall IA workload. For each task type we provide several scheduling algorithms optimizing their service with different criteria. Finally, we discuss the details of a scheduler for our algorithms that could be implemented efficiently in the OS kernel. Experiments show that the WM computation and the proposed algorithms incur minimal actual execution time overhead.