Saturated Assignment Algorithm with Ordered Static Priority
Xiaohui Liu · 2009
In the area of communication,radar,navigation and various electronic production,embedded real-time scheduling has became the control kernel of those electronic and electrical systems,where the cost and the performance-price ratio are major concerns for the system designers.In practical applications,those systems only support limited priority levels when the task number is greater than the number of priority levels,those well-known optimal algorithms,such as DM(deadline monotonic) and RM(rate monotonic),are impractical.However,they can still provide natural priority to assist system design.A saturated assignment algorithm with ordered static priority was proposed based on transcendental knowledge of natural priority.It was proved to be the optimal ordered assignment.Further researches show that the saturated assignment with DM ordered priority leads to minimal priority levels,as long as any task is of deadline less than or equal to its period.Our method is of low time complexity,the number of scheduling determination is equal to the total task number,which is much less than the well-known AGP(assignment of priority group) and LNPA(least-number priority assignment).