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

摘要：

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

关键词：实时系统、静态优先级调度、有限优先级、优先级分配、可调度判定、性价比

所属期刊栏目：18

分类号：TP316(计算技术、计算机技术)

资助基金：国家自然科学基金60373053;60673121;国家高技术研究发展计划863计划2003AA1Z2220;教育部留学回国人员科研启动基金;中国科学院国际合作项目20030389;20032006;中国科学院"百人计划"

在线出版日期：2007-08-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：1844-1854