ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary We consider a scheduling problem concerning a set of jobs {J 1, J 2,..., J n } in which the job J i requests C i units of computation time every T i units of time periodically. These jobs are to be executed by a timeshared single-processor computing system. It is assumed that the requests for each job arrive at the system at the beginning of the request periods and that deadline for completion of the requested computation in each period coincides with the beginning of the next period. For a set of jobs that is schedulable by a certain algorithm, the time span between the completion of a request and its deadline is referred to as the slack time of the request. It is shown here that when the set of jobs is scheduled according to the rate monotonic algorithm, the slack time of the first request of any job is no larger than the slack time of any subsequent request of that job. This result enables us to determine lower bounds to slack times of all requests.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00262974