一种静态最少优先级分配算法

A Static Priority Assignment Algorithm with the Least Number of Priority Levels

随着实时系统越来越多地应用于各种快速更新系统,尤其是各种片上系统,如PDA(personal digital assistant),PSP(play station portable)等,性价比已成为系统设计者的主要关注点.实际应用中,实时系统通常仅支持较少的优先级,常出现系统优先级数小于任务数的情况(称为有限优先级),此时,需将多个任务分配到同一系统优先级,RM(rate monotonic),DM(deadline monotonic)等静态优先级分配算法不再适用.为此,静态有限优先级分配是研究在任务集合静态优先级可调度的情况下,可否以及如何用较少或最少的系统优先级保持任务集合可调度.已有静态有限优先级分配可分为两类:固定数目优先级分配和最少优先级分配.给出了任意截止期模型下任务静态有限优先级可调度的充要条件以及不同静态有限优先级分配间转换时的几个重要性质,指出了系统优先级从低到高分配策略的优越性,定义了饱和任务组与饱和分配的概念,证明了在任务集合静态优先级可调度的情况下,最少优先级分配比固定数目优先级分配更具一般性.最后提出一种最少优先级分配算法LNPA(least-number priority assignment).与现有算法相比,LNPA适用范围更广,且复杂度较低.

With the increased penetration of real time systems into rapidly evolving systems, especially, in on-chip systems such as PDA （personal digital assistant） and PSP （play station portable） etc., the performance/price ratio is becoming a major concern for the system designers. At present, to maximize the performance/price ratio, these systems provide a limited number of priority levels to reduce price and the same priority level is assigned to multiple tasks. Such a trade off makes the most widely used static priority assignment algorithms such as RM （rate monotonic） and DM （deadline monotonic）, impractical. As an alternative approach, static limited priority assignment assigns priority to tasks in such a way that the system feasibility is maintained by employing only a few priority levels. To date, static limited priority assignments can be classified into two categories, fixed-number priority and least-number priority assignment. This paper proposes a necessary and sufficient condition for analyzing task set feasibility under static limited priority assignment to make it suitable for a wide rage of applications. In addition, the superiority of low-to-high priority assignment strategy and the concept of saturated task group/assignment are highlighted along with several important properties for transformation among the limited priority assignments. A formal proof is drawn in favor of the least-number priority assignment when tasks are static priority schedulable. Finally, a least-number priority assignment algorithm with low time complexity is presented and its efficiency is verified by the experimental results.