Abstract
In some hard real-time systems, relative timing constraints may be imposed on task executions, in addition to the release time and deadline constraints. Relative timing constraints such as separation or relative deadline constraints may be given between start or finish times of tasks (Gerber et al., 1995; Han and Lin, 1989; Han et al., 1992; Han and Lin, 1992; Han et al., 1996).
One approach in real-time scheduling is to find a total order on a set of N tasks in a scheduling window, and cyclically use this order at run time to execute tasks. However, in the presence of relative timing constraints, if the task execution times are nondeterministic with defined lower and upper bounds, it is not always possible to statically assign task start times at pre-runtime for a given task ordering (Gerber et al., 1995).
We develop a technique called dynamic cyclic dispatching as an extension of a parametric dispatching mechanism in (Gerber et al., 1995). An ordered set of N tasks is assumed to be given in a scheduling window and this schedule(ordering) is cyclically repeated at runtime in consecutive scheduling windows. Relative timing constraints between tasks may be defined across scheduling window boundaries as well as within one scheduling window. A task set is defined to be dispatchable if there exists any way in which the tasks can be dispatched with all their timing constraints satisfied. An off-line algorithm is presented to check the dispatchability of a task set and to obtain parametric lower and upper bound functions for task start times if the task set is dispatchable. These parametric bound functions are evaluated at runtime to obtain a valid time interval during which a task can be started. The complexity of this off-line component is shown to be O(n 2 N 3) where n is the number of tasks in a scheduling window that have relative timing constraints with tasks in the next scheduling window. An online algorithm can evaluate these bounds in O(N) time.
Unlike static approaches which assign fixed start times to tasks in the scheduling window, our approach allows us to flexibly manage the slack times at runtime without sacrificing the dispatchability of tasks. Also, a wider class of relative timing constraints can be imposed to the task set compared to the traditional approaches.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Carpenter, T., Driscoll, K., Hoyme, K., and Carciofini, J. 1994. Arinc 659 scheduling: Problem definition. Proceedings, IEEE Real-time Systems Symposium, San Juan, PR, December.
Cheng, S., and Agrawala, A. K. 1994. Scheduling of periodic tasks with relative timing constraints. Technical Report CS-TR-3392, UMIACS-TR-94-135, Department of Computer Science, University of Maryland, December.
Cheng, S., and Agrawala, A. K. 1995. Allocation and scheduling of real-time periodic tasks with relative timing constraints. Technical Report CS-TR-3402, UMIACS-TR-95-6, Department of Computer Science, University of Maryland, January.
Dantzig, G., and Eaves, B. 1973. Fourier-Motzkin elimination and its dual. Journal of Combinatorial Theory (A), 14: 288–297.
Dasarathy, B. 1985. Timing constraints for real-time systems: Constructs for expressing them, methods of validating them. IEEE Transactions on Software Engineering, SE-11(1): 80–86, January.
Gerber, R., Pugh, W., and Saksena, M. 1995. Parametric dispatching of hard real-time tasks. IEEE Transactions on Computers, 44(3), March.
Han, C., Hou, C., and Lin, K. 1996. Distance-constrained scheduling and its applications to real-time systems. IEEE Transactions on Computers, 45(7), July.
Han, C. C., and Lin, K. J. 1989. Job scheduling with temporal distance constraints. Technical Report UIUCDCSR-89-1560, Department of Computer Science, University of Illinois at Urbana-Champaign.
Han, C. C., and Lin, K. J. 1992. Scheduling distance-constrained real-time tasks. Proceedings, IEEE Real-time Systems Symposium, Phoenix, Arizona, December, pp. 300–308.
Han, C. C., and Lin, K. J. 1992. Scheduling real-time computations with separation constraints. Information Processing Letters, 12: 61–66, May.
Hong, S. H. 1995. Scheduling algorithm of data sampling times in the integrated communication and control systems. IEEE Transactions on Control Systems Technology, 3(2): 225–230, June.
Jahanian, F., and Mok, A. K. 1986. Safety analysis of timing properties in real-time systems. IEEE Transactions on Software Engineering, SE-12(9): 890–904, September.
Saksena, M., da Silva, J., and Agrawala, A. K. 1995. Design and implementation of Maruti-II. In Advances in Real-Time Systems, Son, S. H., ed. Prentice Hall.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Choi, S., Agrawala, A.K. Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Timing Constraints. Real-Time Systems 19, 5–40 (2000). https://doi.org/10.1023/A:1008133505376
Issue Date:
DOI: https://doi.org/10.1023/A:1008133505376