A data-flow model of real-time systems
Supoj Sutanthavibul · 1991
We present an AND-OR data-flow model for a class of real-time systems in which input data arrive at fixed rates. There is no explicit timing constraint except that the loss of data, whether coming from external sources or generated within the system, is not allowed. Data loss may occur even if the processor is underutilized: whenever a node in the data-flow graph generates data twice from two successive computations, and the latter data overwrite the former before they are used by other nodes, then data loss has occurred. For the basic AND data-flow model, we demonstrate that the nonpreemptive uniprocessor-scheduling problem is NP-hard. However if preemption is allowed, there exist optimal schedulers which are efficient enough to be used on-line. To determine whether a preemptive schedule exists, one just computes the processor utilization factor of the system. When the OR nodes are added, we show that the utilization-factor determination problem is NP-hard. But the scheduling problem remains essentially the same. We also investigate the issues associated with the distributed systems. We demonstrate that the problem of mapping the data-flow graph onto a simple configuration of two connected processors to minimize the communication load is NP-complete, assuming the processor demands of the nodes are identical. The nonpreemptive schedulings of messages, in general, are NP-hard. In relation to the preemptive message scheduling, we study the case in which the messages make at most two hops in unidirection ring networks. We discover a technique for collapsing messages into a single message called the deputy message. We present an optimal scheduling algorithm for a case in which the periodicities of the double-hop messages are multiples of the period of their deputy message. One of our goals is to develop the AND-OR data-flow model as a methodology for designing real-time systems. Toward this goal, we apply our model to an actual real-time message processing system. We discover some shortcomings of the model but we are able to address them successfully. The application of the model has proved that our model has practical value.