Insights on Non-Partitioned Fixed-Priority Preemptive Scheduling




Licentiate thesis to be presented at room HC3, Hörsalsvägen 14, Chalmers, Friday June 8 2001, 13.15


Supervisor: Dr. Jan Jonsson


Discussion leader: Professor Lars Lundberg, Institutionen för Programvaruteknik och Datavetenskap,

Blekinge Tekniska Högskola




This thesis considers real-time scheduling algorithms for a multiprocessor. The objective is to schedule a set of periodically arriving tasks to meet their deadlines. This problem has traditionally been solved by partitioning the tasks, such that a task is allowed to be executed only on its assigned processor. This approach offers the advantage that uniprocessor scheduling can be applied when partitioning has been done, making the problem easier to solve. Unfortunately, the partitioning decision requires knowledge of tasks' execution time.When there is a large variability in the execution times, and the execution time of a task is not known when it arrives, the partitioned method gives poor performance.


This thesis deals with the non-partitioned method, where tasks are allowed to be executed on any processor even when they are resumed after having been preempted. I make the following major contributions. First, I have found that the non-partitioned method exhibits properties different from those of uniprocessor scheduling. In particular, the non-partitioned method suffers from period-based preemptive scheduling anomalies, something that plagues most multiprocessor scheduling algorithms. I have designed a protocol that avoids scheduling anomalies. Second, I have designed a new priority-assignment scheme that performs no worse than the best partitioning schemes in a simulated environment. I have also designed another priority-assignment scheme that has been proven to schedule all task sets if the average processor utilization is less than 25%. I also present an improved version of that scheme.


Keywords: real-time systems, real-time scheduling, fixed-priority scheduling, static-priority scheduling, global scheduling, non-partitioned method, multiprocessor, shared-memory multiprocessor, Dhall's effect, scheduling anomalies