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: converting potentially inefficient procedure calls to a source of concurrency via asynchronous remote procedure calls (ARPC); and 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 until a feasible schedule is generated. 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 employs parallelism exploitation techniques to guarantee timeliness in almost fully predictable environments such as factory automation, aerospace, and avionics. It allocates the components of object-based periodic 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) and 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.