Presents an optimal solution to the problem of allocating communicating periodic tasks to heterogeneous processing nodes (PNs) in a distributed real-time system. The solution is optimal in the sense of minimizing the maximum normalized task response time, called the system hazard, subject to the precedence constraints resulting from intercommunication among the tasks to be allocated. Minimization of the system hazard ensures that the solution algorithm allocates tasks so as to meet all task deadlines under an optimal schedule, whenever such an allocation exists. The task system is modeled with a task graph (TG), in which computation and communication modules, communication delays and intertask precedence constraints are clearly described. Tasks described by this TG are assigned to PNs by using a branch-and-bound (B&B) search algorithm. The algorithm traverses a search tree whose leaves correspond to potential solutions to the task allocation problem. We use a bounding method that prunes, in polynomial time, nonleaf vertices that cannot lead to an optimal solution, while ensuring that the search path leading to an optimal solution will never be pruned. For each generated leaf vertex, we compute the exact cost using the algorithm developed by Peng and Shin (1993). The lowest-cost leaf vertex (one with the least system hazard) represents an optimal task allocation. Computational experiences and examples are provided to demonstrate the concept, utility and power of the proposed approach.

Preemptive (resume) scheduling of cooperative tasks that have been preassigned to a set of processing nodes in a distributed system, when each task is assumed to consist of several modules is discussed. During the course of their execution, the tasks communicate with each other to collectively accomplish a common goal. Such intertask communications lead to precedence constraints between the modules of different tasks. The objective of this scheduling is to minimize the maximum normalized task response time, called the system hazard. Real-time tasks and the precedence constraints among them are expressed in a PERT/CPM form with activity on arc (AOA), called the task graph (TG), in which the dominance relationship between simultaneously schedulable modules is derived and used to reduce the size of the set of active schedules to be searched for an optimal schedule. Lower-bound costs are estimated, and are used to bound the search. An example of the task scheduling problem and some computational experiences are presented.>

Using two branch-and-bound (B&B) algorithms, an optimal solution is proposed to the problem of allocating (or assigning with the subsequent scheduling considered) periodic tasks to a set of heterogeneous processing nodes (PNs) of a distributed real-time system. The allocation objective is to minimize the maximum normalized task response time, called the system hazard, subject to precedence constraints among the tasks to be allocated. First, the task system is modeled with a task graph, which describes computation and communication modules as well as the precedence constraints among them. Second, the exact system hazard of a complete assignment is determined so that an optimal assignment can be derived. This exact cost is obtained by optimally scheduling the modules assigned to each PN with a B&B algorithm guided by the dominance relationship between simultaneously schedulable modules. Third, to reduce the amount of computation needed for an optimal assignment, a lower-bound system hazard that is obtainable with a polynomial time algorithm is derived.>

In a distributed system that implements real-time control, computational tasks are distributed over different nodes for execution to improve response time and system reliability. To model system behavior, tasks in each node are first decomposed into activities. The activities and precedence constraints among them are then modeled by a generalized stochastic Petri net (GSPN). Finally, a sequence of homogeneous continuous-time Markov chains (CTMC's) is built from the GSPN to model the concurrent task execution in the system.