Third IEEE International Conference on Engineering of Complex Computer Systems (ICECCS '97)
Precedence constraints in hard real-time distributed systems
Lake Como, ITALY
September 08-September 12
ISBN: 0-8186-8126-8
J. Orozco, Dep. Inf. Electr., Univ. Nacional del Sur, Bahia Blanca, Argentina
R. Cayssials, Dep. Inf. Electr., Univ. Nacional del Sur, Bahia Blanca, Argentina
J. Santos, Dep. Inf. Electr., Univ. Nacional del Sur, Bahia Blanca, Argentina
E. Ferro, Dep. Inf. Electr., Univ. Nacional del Sur, Bahia Blanca, Argentina
Hard real-time multitask-multiprocessor systems are one of the more important species of the taxonomic genus of distributed systems. The assignment of m preemptible periodic tasks to be executed in a set of n processors (interconnected through a communications network) is a NP-complete problem that must meet several constraints: time, allocation, resources, communication and precedence. The first three are processor-dependent and the fourth is network-dependent, but all of them can be verified as the assignment process goes on. Precedence constraints, instead, can be best verified when a tentative assignment, meeting the first four constraints, is obtained. In this paper, a formally proved method is presented to validate tentative assignments. In order to solve the problem of jitter in data arrivals, timed release counters are proposed.
Index Terms:
real-time systems; precedence constraints; hard real-time distributed systems; multitask-multiprocessor systems; taxonomic genus; NP-complete problem; tentative assignment; formally proved method; tentative assignments
Citation:
J. Orozco, R. Cayssials, J. Santos, E. Ferro, "Precedence constraints in hard real-time distributed systems," iceccs, pp.33, Third IEEE International Conference on Engineering of Complex Computer Systems (ICECCS '97), 1997