Scheduling Real-Time Computations With Temporal Distance and Separation Constraints and With Extended Deadlines

Abstract

In hard real-time systems, computations not only must be functionally correct but also must meet their strict timing constraints. To guarantee the timing requirements are satisfied, effective scheduling algorithms must be used. Different real-time applications have different timing requirements. Therefore, different timing constraints must be defined for different real-time applications. Also, different scheduling algorithms need to be designed for different real-time systems to effectively and efficiently schedule the computations to meet their timing constraints. We propose new real-time scheduling problems to model real-time systems in which computations have relative timing constraints. For relative timing constraints, we mean that a computation's ready time or deadline is relative to the actual start time (or finishing time) of some other computation. The Job Scheduling with Distance Constraints problem requires certain pairs of jobs to be scheduled within some given distance of each other. The Job Scheduling with Separation Constraints problem requires two related jobs to be scheduled no smaller than the separation constraint between them. We analyze the scheduling problems with these kinds of relative timing constraints and design several scheduling algorithms for some of them. We also propose new real-time scheduling problems to model real-time systems in which computations have more than one deadline. In the Scheduling with Extended Deadline problem, computations can be delayed after their first (primary) deadlines but must be finished before their second (extended) deadlines. We study two variations of this problem. In the first model, the system receives a penalty for each computation that does not finish its execution before its primary deadline. In the second model, there is an extra overhead for each computation that can not be finished before its primary deadline. We discuss the scheduling issues of the problems under these two models and design some algorithms for scheduling real-time computations with extended deadlines.