OPTIMAL PRIORITY ASSIGNMENT AND FEASIBILITY OF STATIC PRIORITY TASKS WITH ARBITRARY START TIMES

Abstract

Within the hard real-time community, static priority pre-emptive scheduling is receiving increased attention. Current optimal priority assignment schemes require that at some point in the system lifetime all tasks must be released simultaneously. Two main optimal priority assignment schemes have been proposed: rate-monotonic, where task period equals deadline, and deadline-monotonic where task deadline maybe less than period. When tasks are permitted to have arbitrary start times, a common release time between all tasks in a task set may not occur. In this eventuality, both rate-monotonic and deadline-monotonic priority assignments cease to be optimal. This paper presents an method of determining if the tasks with arbitrary release times will ever share a common release time. This has complexity O(m log e m) in the longest task period. Also, an optimal priority assignment method is given, of complexity O(n² + n) in the number of tasks. Finally, an efficient feasibility test is presen...