A Static Priority Assignment Algorithm with the Least Number of Priority Levels
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:June 10,2006
  • Revised:January 23,2007
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063