主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
邢建生,王永吉,刘军祥,曾海涛,NASRO Min-Allah.一种静态最少优先级分配算法.软件学报,2007,18(7):1844-1854
一种静态最少优先级分配算法
A Static Priority Assignment Algorithm with the Least Number of Priority Levels
投稿时间:2006-06-10  修订日期:2007-01-23
DOI:
中文关键词:  实时系统  静态优先级调度  有限优先级  优先级分配  可调度判定  性价比
英文关键词:real-time system  static priority scheduling  limited priority level  priority assignment  schedulability test  performance/price ratio
基金项目: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 (中国科学院百人计划)
作者单位
邢建生 中国科学院,软件研究所,互联网软件技术实验室,北京,100080
中国科学院,软件研究所,计算机科学国家重点实验室,北京,100080
中国科学院,研究生院,北京,100049 
王永吉 中国科学院,软件研究所,互联网软件技术实验室,北京,100080
中国科学院,软件研究所,计算机科学国家重点实验室,北京,100080 
刘军祥 中国科学院,软件研究所,互联网软件技术实验室,北京,100080
中国科学院,软件研究所,计算机科学国家重点实验室,北京,100080
中国科学院,研究生院,北京,100049 
曾海涛 中国科学院,软件研究所,互联网软件技术实验室,北京,100080
中国科学院,软件研究所,计算机科学国家重点实验室,北京,100080
中国科学院,研究生院,北京,100049 
NASRO Min-Allah 中国科学院,软件研究所,互联网软件技术实验室,北京,100080
中国科学院,软件研究所,计算机科学国家重点实验室,北京,100080
中国科学院,研究生院,北京,100049 
摘要点击次数: 2881
全文下载次数: 3080
中文摘要:
      随着实时系统越来越多地应用于各种快速更新系统,尤其是各种片上系统,如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 staticpriority schedulable. Finally, a least-number priority assignment algorithm with low time complexity is presented and its efficiency is verified by the experimental results.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利