Processor Utilization Bounds for Real-Time Systems With Precedence Constraints

被引：0
作者：
Hongchao (Stephanie) Liu
Xiaobo Sharon Hu
机构：
[1] University of Notre Dame,Department of Computer Science and Engineering
来源：
Design Automation for Embedded Systems | 2002年 / 7卷
关键词：
Precedence; real-time; utilization bound;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This paper presents a novel approach to computing tight upper bounds on the processor utilization for general real-time systems where tasks are composed of subtasks and precedence constraints may exist among subtasks of the same task. By careful analysis of preemption effects among tasks, the problem is formulated as a set of linear programming (LP) problems. Observations are made to reduce the number of LP problem instances required to be solved, which greatly improves the computation time of the utilization bounds. Furthermore, additional constraints are allowed to be included under certain circumstances to improve the quality of the bounds.
引用
收藏
页码：89 / 113
页数：24
相关论文
共 21 条
  • [1] Audsley N.(1993)Applying New Scheduling Theory to Static Priority Preemptive Scheduling Software Engineering Journal 8 284-292
  • [2] Burns A.(1995)New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems IEEE Transactions on Computers 44 1429-1442
  • [3] Richardson M.(1994)Timing Analysis for Fixed-Priority Scheduling of Hard Real-Time Systems IEEE Transactions on Software Engineering 20 13-28
  • [4] Tindell K.(1973)Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment Journal of the ACM 20 46-61
  • [5] Wellings A. J.(1996)Fixed-Priority Scheduling of Real-Time Systems Using Utilization Bounds Journal of Systems Software 33 57-63
  • [6] Burchard A.(2000)Fixed Priority Scheduling of Tasks with Arbitrary Precedence Constraints in Distributed Hard Real-Time Systems Journal of Systems Architecture 46 991-1004
  • [7] Liebeherr J.(1998)Performance Estimation for Real-Time Distributed Embedded Systems IEEE Transactions on Parallel and Distributed Systems 9 1125-1136
  • [8] Oh Y.(undefined)undefined undefined undefined undefined-undefined
  • [9] Son S. H.(undefined)undefined undefined undefined undefined-undefined
  • [10] Harbour M. G.(undefined)undefined undefined undefined undefined-undefined
123