| ||||||||||||||||||||||||||||||||||||||||||||||||||
A Comprehensive Framework for Specifying Clairvoyance, Constraints and Periodicity in Real-Time Scheduling
LDCSEE, West Virginia University, Morgantown, WV, USA
There are two principal modes in which real-time scheduling differs from scheduling in conventional models: (i) execution time variability and (ii) existence of complex timing constraints between jobs. There is a third issue that indirectly depends upon the non-constant nature of execution times, namely the degree of clairvoyance permitted by the application. Finally, there also exist the issues of periodicity and the presence of inter-period constraints; these issues need to be explicitly accounted for, in an analytic fashion. In traditional scheduling models, it is usual to assume fixed values for job execution times. This essentially means that a job will take exactly the same time to execute, in every instance of its invocation. From a real-time perspective, this assumption is both unrealistic and dangerous, in that it may lead to constraint violation at runtime. With a view towards enhancing the fault-tolerance of the system, the execution times of jobs are modeled through convex sets; doing so permits the capturing of situations that cannot be modeled otherwise. For instance, by monitoring the execution time of a job, over a number of independent runs, one can identify its safety interval with a high degree of confidence. The product of the safety intervals, over all the jobs in the system, forms a convex set. The second feature unique to real-time systems, is the presence of temporal relationships that constrain job execution. For instance, consider the pair of requirements: (i) job J1 should conclude 10 units before job J2 commences and (ii) job J2 commences within 12 units of job J1 concluding. These requirements cannot be modeled through precedence graphs, which by definition, are directed and acyclic. However, they can be easily modeled through simple, difference constraints. In hard real-time scheduling, it is important to guarantee the schedulability of the system a priori, since the violation of a constraint could lead to catastrophic consequences. However, in the presence of variable execution times and complex timing constraints, the definition of schedulablity is not obvious. In this context, it is necessary to mention the dispatchability problem; the dispatcher is concerned with strategies to assign jobs on the time line, once the scheduler has declared the job-set to be feasible. The nature of the schedulability query is determined by whether or not the dispatcher can use the execution times of jobs in the computation of the schedule. Observe that there are three possibilities, namely (i) the dispatcher never knows the execution time of a job, (ii) the dispatcher knows the execution time of a job after it has finished execution and (iii) the dispatcher knows the execution time of a job, even before it has commenced execution. Thus, depending upon the nature of the application involved, there are three different schedulability specifications, namely zero-clairvoyant (static), partially clairvoyant (parametric) and totally clairvoyant (co-static). Each specification affords a different level of flexibility and has different dispatching concerns. This paper presents the framework, called the E-T-C scheduling model, which explicitly accommodates execution time variability, complex timing constraints and different schedulability queries. This enables the specification of a wide range of real-time scheduling problems that occur in practical settings. This paper also discusses the relationships between flexibility and complexity in the proposed model. Each aspect of the model is motivated through examples from real-world design. The E-T-C model is itself a single period framework, in that all constraints are necessarily intra-period. This framework is extended to formulate the E-T-C-P scheduling framework, which explicitly accounts for inter-period constraints. The strengths of these two frameworks lie in their abilities to abstract the essentials of a number of real-time situations. In addition, decoupling the constraint system from the schedulability query greatly enhances the flexibility of the specification process. Although the primary purpose of this paper is to elaborate on scheduling problems only, it also discusses the problems of real-time dispatchability and optimization in clairvoyant scheduling.
Received 9 February 2004. revised 17 December 2004.