一种静态优先级保序饱和分配算法  

Saturated Assignment Algorithm with Ordered Static Priority

作　　者：伍微[1] 倪少杰[1] 刘小汇[1] 

机构地区：[1]国防科技大学电子科学与工程学院,长沙410073

出　　处：《计算机科学》2009年第12期41-45,共5页Computer Science

基　　金：新世纪优秀人才支持计划(NCET-04-0995)资助

摘　　要：在通信、雷达、导航以及各种消费类电子产品等领域,嵌入式实时调度已逐渐成为电子电气系统的控制核心,成本与性价比都是设计者需要考虑的重要内容。实际应用中,系统能够支持的优先级数目是有限的,当任务数目多于系统优先级数目时,RM,DM等优先级非受限最优算法尽管已经不再适用,但是仍然可以作为任务的自然优先级来辅助系统设计。利用自然优先级先验知识,提出一种保序饱和分配算法,用于任意截止期模型的最优保序分配。进一步的研究表明,当所有任务周期不小于其相对截止时间时,DM保序饱和分配是最少优先级分配。本算法复杂度低,可调度的判定总次数等于任务总数,远低于AGP和LNPA。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 concems 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-num-ber priority assignment）.

关 键 词：实时系统 有限优先级 优先级分配 饱和分配 截止期单调 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]