Scheduling with Slack Time.
Abstract
We study in this paper a problem concerning the scheduling of a set of jobs on a single processor computer system. In our model, a job consists of a periodic stream of identical requests. That is, a job J(i) demands periodically C(i) units of computation time in every T(i) units of time. We shall use J(1), J(2), ..., J(n) to denote the jobs, T(1), T(2), ...T(n) to denote the request periods, and C(1), C(2),..., C(n) to denote the computation times. (Throughout our discussion, we shall assume T(1) < or = T(2) < or = ...< or = T(n) for convenience in notations). That is, a job J(i) is completely characterized by an ordered pair of numbers (C(i), T(i)). By scheduling a set of jobs we mean to determine, at any time instant, the particular request to which the processor should be devoted. In our model, the criterion of scheduling is to satisfy each request prior to its deadline, which is the arrival time of the next request of the same job. A set of jobs is said to be schedulable by a certain scheduling algorithm if such a criterion can be met. Throughout our discussion, we assume that the preemptive scheduling discipline is employed. That is, the execution of a job can be interrupted by the execution of another job.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1974
- Accession Number
- ADA102226
Entities
People
- Arthur I. Liestman
- Chung Laung Liu
- Jane W. Liu
Organizations
- University of Illinois Urbana–Champaign