Precedence constraints in hard real-time distributed systems

OROZCO, J.; CAYSSIALS R.; SANTOS J.; FERRO E.

Como Italia

Conferencia; IEEE International Conference on Engineering of Complex Computer Systems; 1997

IEEE Computer Society Press

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 timed release counters are proposed.