On-line scheduling of real-time distributed computers with complex communication constraints

摘要

We consider the scheduling of periodic tasks running on distributed computers. Every execution of a task must meet its deadline. Response time analysis of the tasks is used to prove the schedulability of hard real-time distributed systems according to the on-line priority rules that schedule the processors and the network. Its main advantage is to take into account the precedence dependencies of the schedules of the tasks on the processors and the messages sent on the network(s). Past works have addressed the issue of tasks related by asynchronous communication constraints with the senders and the receivers working at the same rate. We study more general relations among tasks when the rates of dependent tasks are not equal. We call such relations generalized communication constraints. Usually distributed systems are scheduled using a synchronization protocol and an on-line scheduling algorithm by processor. We present a graph theoretical approach to this schedulability analysis. Our algorithm transforms complex communication relations into classical ones, so that the classical scheduling analysis can be fully applied. That transformation is independent of the architecture of the distributed systems and no assumption is made on the synchronization protocol considered.