An Improved Rate Monotonic Schedulability Test Algorithm
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    One of the key issues in real-time theory is the schedulable analysis of a given task set with fixed priority. All the proposed schedulability test methods can be classified into two types: polynomial time methods and exact methods. Polynomial time methods use a sufficient schedulability condition, and several least upper bounds of the processor utilization under ideal assumptions have been developed. Exact methods based on the necessary and sufficient schedulability condition guarantee that the test result for every task set is correct. However, the pseudo-polynomial complexity of the exact tests is too complex to be executed online for large task sets. This paper presents a novel ISTA (improved schedulability test algorithm) for analyzing the schedulability of periodic task sets under Rate Monotonic priority assignment. A pruning theorem for the Task_i space is derived, the schedulability correlation among tasks and its effect on the schedulability test are investigated, and the related theorems are proven. Based on the above results, a new improved pseudo-polynomial schedulability test algorithm is developed, and several comparative simulation experiments among the three methods are conducted. Extensive simulations show that the average schedulability test performance as a function of number of the tasks can be significantly improved.

    Reference
    Related
    Cited by
Get Citation

刘军祥,王永吉,Matthew Cartmell.一种改进的RM可调度性判定算法.软件学报,2005,16(1):89-100

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:November 28,2003
  • Revised:May 09,2004
  • 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