Static scheduling of pipelined periodic tasks in distributed real-time systems

Abstract

Many distributed real time applications involve periodic activities with end to end timing constraints that are larger than the periods. That is, a new instance of a periodic activity will come into existence before the previous instance has been completed. Also, such activities typically involve communicating modules in a distributed system where some modules may be replicated for resilience. For such activities, pipelined execution allows us to meet the various resource and timing constraints imposed on them. We discuss an approach to dealing with the pipelined execution of a set of periodic activities that have the above characteristics. It can be called a meta algorithm since it works in conjunction with another scheduling algorithm-one that creases the actual schedules. The idea is to exploit the existence of many such scheduling algorithms, which, however typically work with activities whose deadlines are equal to or less than their periods. Our meta algorithm invokes such a scheduling algorithm, perhaps multiple times, to generate a pipelined execution for the tasks. The effectiveness of the approach is shown via simulation studies.