Scheduling and Allocation in Multiprocessor Systems

Abstract

The problem of allocation has always been one of the fundamental issues of building applications in multiprocessor systems. For real-time applications, the allocation problem should directly address the issues of task and communication scheduling. In this context, the allocation of tasks has to fully utilize the available processors and the scheduling of tasks has to meet the specified timing constraints. Clearly, the execution of tasks under the allocation and schedule has to satisfy the precedence, resources, and synchronization constraints. Traditionally time constraints for real-time tasks have been specified in terms of ready time and deadlines. Many application tasks have relative timing constraints in which the constraints for the execution of a task are defined in terms of the actual execution instances of prior tasks. In this dissertation we consider the allocation and scheduling problem of the periodic tasks with relative timing requirements. We take a time-based scheduling approach to generate a multiprocessor schedule for a set of periodic tasks. A simulated annealing algorithm is developed as the overall search algorithm for a feasible solution. Our results show that the algorithm performs well and finds feasible allocation and scheduling. We also investigate how to exploit the replication technique to increase the schedulability and performance of the systems. In this dissertation, we adopt the computation model in which each task may have more than one copy and a task may start its execution after receiving necessary data from a copy of each of its predecessors. Based on this model, replication techniques are developed to increase the schedulability of the applications in real-time systems and to reduce the execution cost of the applications in non-real-time systems.