Modified rate-monotonic algorithm for scheduling periodic jobs with deferred deadlines
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 19 (12) , 1171-1179
- https://doi.org/10.1109/32.249662
Abstract
[[abstract]]The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. This paper describes a semi-static priority-driven algorithm for scheduling periodic jobs with deferred deadlines: each job is assigned two priorities, the higher one for old requests and the lower one for the current request. This algorithm is called the modified rate-monotonic algorithm and is based on the well-known rate-monotonic algorithm. We show that the modified rate-monotonic algorithm is optimal when the deadline of every job is deferred by max (1, γ-1) periods or more, where γ is the ratio between the longest period and the shortest period. When the deadline of each job is deferred by one period of the job, any set of n independent jobs whose total utilization is equal to or less than [1+n(21/n-1)]/2 can be feasibly scheduled by this algorithm. This bound approaches 0.845 when n approaches infinity.[[fileno]]2030218010013[[department]]資訊工程學Keywords
This publication has 6 references indexed in Scilit:
- The rate monotonic scheduling algorithm: exact characterization and average case behaviorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Analysis of a synchronization and scheduling discipline for real-time tasks with preemption constraintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Fixed priority scheduling of periodic task sets with arbitrary deadlinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1990
- On the complexity of fixed-priority scheduling of periodic, real-time tasksPerformance Evaluation, 1982
- On a Real-Time Scheduling ProblemOperations Research, 1978
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973