Modified rate-monotonic algorithm for scheduling periodic jobs withdeferred deadlines |
| |
Authors: | Wei Kuan Shih Liu J.W.S. Liu C.L. |
| |
Affiliation: | Dept. of Comput. Sci., Illinois Univ., Urbana, IL ; |
| |
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. The authors describe 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. It is shown 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(21n/-1)]/2 can be feasibly scheduled by this algorithm. This bound approaches 0.845 when n approaches infinity |
| |
Keywords: | |
|
|