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

	一种静态最少优先级分配算法
	邢建生 ; 王永吉 ; 刘军祥 ; 曾海涛
刊名	软件学报
	2007
卷号	18 期号:7 页码:1844-1854
关键词	实时系统静态优先级调度有限优先级优先级分配可调度判定性价比 real-time system static priority scheduling limited priority level priority assignment schedulability test performance/price ratio
ISSN号	1000-9825
其他题名	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适用范围更广,且复杂度较低.
收录类别	ei,wanfang,cscd,cnki
语种	中文
公开日期	2010-08-17
附注	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.
内容类型	期刊论文
源URL	[http://124.16.136.157/handle/311060/3258]
专题	软件研究所_互联网软件技术实验室 _期刊论文
推荐引用方式 GB/T 7714	邢建生,王永吉,刘军祥,等. 一种静态最少优先级分配算法[J]. 软件学报,2007,18(7):1844-1854.
APA	邢建生,王永吉,刘军祥,&曾海涛.(2007).一种静态最少优先级分配算法.软件学报,18(7),1844-1854.
MLA	邢建生,et al."一种静态最少优先级分配算法".软件学报 18.7(2007):1844-1854.