Consider the problem of scheduling independent periodic tasks on a
homogeneous multiprocessor using fixed-priority preemptive scheduling.
This problem can be solved using two different methods based on how
to assign the tasks to the processors.
The traditionally-used method (partitioned method) first partitions the task
set and then applies uniprocessor scheduling on each processor. The
alternative method (non-partitioned method) allows a task to execute on any
processor, even when resuming after having been preempted. While there exists
a good understanding of the theoretical properties of the partitioned method,
the non-partitioned counterpart has not been fully explored and has therefore
received much less attention.
We present an in-depth analysis of the non-partitioned
method. To this end, we make three important contributions towards
a better understanding of the method.
First, we identify a set of anomalies for fixed-priority preemptive
multiprocessor scheduling and explain the reasons for their existence.
Second, we identify several difficulties in determining
critical instants
and generating optimal priority assignments for the non-partitioned method.
Third, we identify underlying causes for the so-called Dhall's effect,
a scheduling dilemma hitherto believed to be an inherent property of the
non-partitioned method. For several of these findings, we propose
strategies for circumventing the problems.
