Some Insights on Fixed-Priority Preemptive Non-Partitioned Multiprocessor Scheduling

Fixed-priority preemptive scheduling of independent periodictasks on a homogeneous multiprocessor is solved usingone of two different methods based on how tasks are assignedto the processors at run-time. In the partitioned method,all instances of a task are executed on the same processor,where the processor used for each task is determined beforerun-time by a partitioning algorithm. In the non-partitionedmethod, a task is allowed to execute on any processor, evenwhen resuming after having been preempted. Two fundamentalproperties have been shown for the addressed problem. First, the problem of deciding whether a task set isschedulable is NP-hard for both methods. Second, there aretask sets which are schedulable with an optimal priority assignmentwith the non-partitioned method, but are unschedulablewith an optimal partitioning algorithm and conversely.Among the two methods, the non-partitioned method hasreceived considerably less attention, mainly because it is believedto suffer from several scheduling-related shortcomings.The most well-known of these is Dhall’s effect, ascheduling dilemma wherein some task sets may be unschedulableon multiple processors even though they havea low utilization. Another shortcoming is that existingnecessary and sufficient schedulability tests all have exponentialtime complexity, and existing sufficient testshave polynomial complexity but are pessimistic. It hasalso been shown that the RM (rate-monotonic) priorityassignmentscheme is not optimal, and no optimalpriority-assignment schemes with polynomial time complexityhave been found.In this paper, we present an in-depth analysis of the nonpartitionedmethod in terms of its scheduling-related properties.We (i) identify a set of anomalies for preemptivescheduling with migration, which are the first ever reportedin the open research literature, (ii) identify several difficultiesin conveying techniques from uniprocessor schedulingto the multiprocessor case, and (iii) conjecture that there mayexist priority-assignment schemes that can contribute to circumventingDhall’s effect, something that has believed to beinherently impossible with the non-partitioned method