Insights on Non-Partitioned Fixed-Priority
Preemptive Scheduling
BJÖRN ANDERSSON
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
ABSTRACT
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