###
DOI:
Journal of Software:2007.18(7):1844-1854

一种静态最少优先级分配算法
邢建生,王永吉,刘军祥,曾海涛,NASROMin-Allah
(中国科学院,软件研究所,互联网软件技术实验室,北京,100080;中国科学院,软件研究所,计算机科学国家重点实验室,北京,100080;中国科学院,研究生院,北京,100049)
A Static Priority Assignment Algorithm with the Least Number of Priority Levels
XING Jian-Sheng,WANG Yong-Ji,LIU Jun-Xiang,ZENG Hai-Tao,NASRO Min-Allah
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2856   Download 3072
Received:June 10, 2006    Revised:January 23, 2007
> 中文摘要: 随着实时系统越来越多地应用于各种快速更新系统,尤其是各种片上系统,如PDA(personal digital assistant),PSP(play station portable)等,性价比已成为系统设计者的主要关注点.实际应用中,实时系统通常仅支持较少的优先级,常出现系统优先级数小于任务数的情况(称为有限优先级),此时,需将多个任务分配到同一系统优先级,RM(rate monotonic),DM(deadline monotonic)等静态优先级分配算法不再适用.为此,静态有限优先级分配是研究在任务集合静态优先级可调度的情况下,可否以及如何用较少或最少的系统优先级保持任务集合可调度.已有静态有限优先级分配可分为两类:固定数目优先级分配和最少优先级分配.给出了任意截止期模型下任务静态有限优先级可调度的充要条件以及不同静态有限优先级分配间转换时的几个重要性质,指出了系统优先级从低到高分配策略的优越性,定义了饱和任务组与饱和分配的概念,证明了在任务集合静态优先级可调度的情况下,最少优先级分配比固定数目优先级分配更具一般性.最后提出一种最少优先级分配算法LNPA(least-number priority assignment).与现有算法相比,LNPA适用范围更广,且复杂度较低.
Abstract: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 staticpriority schedulable. Finally, a least-number priority assignment algorithm with low time complexity is presented and its efficiency is verified by the experimental results.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60373053, 60673121 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2003AA1Z2220 (国家高技术研究发展计划(863)); the State Education Ministry's Scientific Research Foundation for the Returned Overseas Chinese Scholars (国家教育部留学回国人员科研启动基金); the Research Collaboration between the Chinese Academy of Sciences and the Royal Society of the United Kingdom under Grant Nos.20030389, 20032006 (中国科学院与英国皇家学会联合资助项目); the Plan of Hundreds Scientists in the Chinese Academy of Sciences (中国科学院百人计划) Supported by the National Natural Science Foundation of China under Grant Nos.60373053, 60673121 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2003AA1Z2220 (国家高技术研究发展计划(863)); the State Education Ministry's Scientific Research Foundation for the Returned Overseas Chinese Scholars (国家教育部留学回国人员科研启动基金); the Research Collaboration between the Chinese Academy of Sciences and the Royal Society of the United Kingdom under Grant Nos.20030389, 20032006 (中国科学院与英国皇家学会联合资助项目); the Plan of Hundreds Scientists in the Chinese Academy of Sciences (中国科学院百人计划)
Foundation items:
Reference text:

邢建生,王永吉,刘军祥,曾海涛,NASRO Min-Allah.一种静态最少优先级分配算法.软件学报,2007,18(7):1844-1854

XING Jian-Sheng,WANG Yong-Ji,LIU Jun-Xiang,ZENG Hai-Tao,NASRO Min-Allah.A Static Priority Assignment Algorithm with the Least Number of Priority Levels.Journal of Software,2007,18(7):1844-1854