A Scheduling Strategy for Tasks with Precedence and Conditional Execution

概要

論文の詳細を見る
A program in a computer system can be divided into program segments, or tasks. Tasks typically have precedence relations among them. Execution flow control constructs in programming languages, such as IF and CASE statements, cause conditional task execution. In other words, a task may dispatch one sequence of tasks in one condition and the other sequence of tasks in the other condition. When there are such conditional task sequence executions in a time-critical system, we need to consider schedules for all possible combinations of task sequences in order to guarantee the deadlines assigned to the task set. The number of schedules we need to consider increases exponentially with the number of conditional task sequences. In order to solve this difficulty, we adopt a three-stage scheduling strategy which has been proposed for VLSI design. First, the original task precedence relation with conditional execution is transformed into a task precedence relation without conditional execution. Then, the transformed task set is scheduled. Finally, the schedule of the transformed task set is transformed back to a schedule of the original task set. In this paper, several transformation algorithms are proposed for the first-stage. The perfomance of the algorithms are compared through simulations.
一般社団法人情報処理学会の論文
1995-09-15