Allocation and Scheduling of Real-Time Periodic Tasks with Relative Timing Constraints

View/ Open
Date
1998-10-15Author
Cheng, Sheng-Tzong
Agrawala, Ashok K.
Metadata
Show full item recordAbstract
Allocation problem has always been one of the fundamental issues of
building the applications in distributed computing systems (DCS). For
real-time applications on DCS, 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 other synchronization constraints
among them.
Recently, the timing requirements of the real-time systems
emerge that the relative timing constraints are imposed on the consecutive
executions of each task and the inter-task temporal relationships are
specified across task periods. In this paper we consider the allocation
and scheduling problem of the periodic tasks with such timing
requirements. Given a set of periodic tasks, we consider the least common
multiple (LCM) of the task periods. Each task is extended to several
instances within the LCM. The scheduling window for each task instance is
derived to satisfy the timing constraints. We develop a simulated
annealing algorithm as the overall control algorithm. An example problem
of the sanitized version of the Boeing 777 Aircraft Information Management
System is solved by the algorithm. Experimental results show that the
algorithm solves the problem in a reasonable time complexity.
(Also cross-referenced as UMIACS-TR-95-6)