On Priority Assignment in Fixed Priority Scheduling

In static priority pre-emptive scheduling there are two areas of related work: priority assignment and feasibility analysis. Given a priority ordering over a task set, feasibility analysis determines whether all task deadlines will be met at run-time. In asynchronous periodic systems, all tasks are periodic, but are never all released simultaneously. Asynchronous task sets are characterised by the first release of each task being offset from the start of the system. Thus, two tasks with identical periods but different offsets could never be released simultaneously during the lifetime of the system. For asynchronous periodic systems, Leung and Whitehead prove that the deadline-monotonic priority ordering is not optimal (1982). Indeed, they suggest that the only method for finding the optimal priority ordering is to enumerate all $n!$ possible priority orderings. In summary, Leung and Whitehead posed the following open question: ``We also note that Theorem 3.8 does not imply that the problem of finding an optimal priority assignment is NP-hard, for the apparent difficulties in determining whether or not a task set is feasible on one processor may entirely be due to the difficulties in deciding whether or not the schedule produced by particular priority assignment is valid.'' This paper provides two contributions for asynchronous periodic systems: (1) Resolution of the above open issue -- we show that the priority assignment can be solved in polynomial time. (2) Identification of the minimum number of priority levels required for a task set.