ON PERIODIC REAL-TIME SCHEDULING ALGORITHMS

The problem of scheduling a set of periodic-time-critical tasks on a single-processor computing system is investigated. A periodic-time-critical task is a computational procedure consisting of an infinite sequence of requests, arising periodically, each of which has a prescribed deadline. The objective here is to schedule the processing of the tasks such that all requests are completely executed by their prescribed deadlines. Existing results on independent periodic real-time scheduling are extended and generalized. The class of priority-driven algorithms is shown to be asymptotically optimal in time complexity. When tasks to be scheduled are dependent, an optimal algorithm and its characterization are devised and analyzed. A class of non-preemptive priority-driven algorithms for the scheduling of non-preemptive periodic-time-critical tasks is also developed. When additional restrictions are imposed on the request-periods of the tasks, optimal algorithms are devised and analyzed. Necessary and sufficient conditions that can guarantee a non-preemptive task set to be schedulable are obtained. Finally, we consider a non-deterministic scheduling system in which vital information describing the tasks to be scheduled is not completely known in advance. An optimal algorithm for the scheduling of a set of randomly arriving time-critical tasks in this environment is developed. The relationship of this non-deterministic model with independent periodic real-time scheduling systems is examined and analyzed