A pre-run-time scheduling algorithm for object-based distributed real-time systems

The most important goal in hard real-time systems is to guarantee that all timing constraints are satisfied. Even though object-based techniques (which contain reusable software components) are used to manage the complexity in the software development process of such systems, execution efficiency may have to be sacrificed, due to the large number of procedure calls and contention for accessing software components. These issues are addressed by the following parallelizing techniques: (a) converting potentially inefficient procedure calls to a source of concurrency via asynchronous remote procedure calls (ARPC) (b) replicating (or cloning) software components to reduce the contention. The existing object-based scheduling algorithms construct an initial schedule and apply incremental parallelization techniques to modify the initial schedule till a feasible schedule is generated. But these algorithms are applicable for scheduling only multiple independent tasks. This paper describes a pre-run-time scheduling algorithm for a set of periodic object-based tasks having precedence constraints among them. The algorithm allocates the components of object-based periodic real-time tasks to the sites of a distributed system based on a clustering heuristic which takes into account the ARPC parallelism and load balancing, and schedules them on respective sites. The algorithm also finds a schedule for communication channel(s). Further, it clones the components of object-based periodic tasks, if contention occurs in accessing them. In addition to the above (periodicity and precedence) constraints, the tasks handled by our algorithm can have resource constraints among them. The experimental evaluation of the algorithm shows that the combination of the proposed clustering heuristic and cloning enhances schedulability.