Date Added: Apr 2010
This paper investigates the problem of optimal priority assignment in multiprocessor real-time systems using global fixed task-priority pre-emptive scheduling. Previous work in this area showed that arguably the most effective pseudo-polynomial schedulability tests for global fixed priority pre-emptive scheduling, based on response time analysis, are not compatible with Audsley's Optimal Priority Assignment (OPA) algorithm. In this paper, the authors derive upper and lower bounds on these response time tests that are compatible with the OPA algorithm. They show how these bounds can be used to limit the number of priority ordering combinations that need to be examined, and thus derive an optimal priority assignment algorithm with backtracking that is compatible with response time analysis.