DDSCHED: A distributed dynamic real-time scheduling algorithm

Abstract

Modern real-time systems need enormous computing power, for which a uniprocessor system is often inadequate. This work is directed at developing a task scheduling algorithm for distributed systems with the goal of achieving flexibility through dynamic scheduling of tasks in a distributed and adaptive manner. In this paper we present a dynamic soft real-time task scheduling algorithm named DDSCHED for distributed systems. The two main components of DDSCHED are a local scheduler and a distributed scheduling scheme. The local scheduler is designed based on the earliest deadline first (EDF) policy and the concept of window. The implementation uses an efficient data structure to reduce the time complexity from O(n²) for the basic EDF algorithm to O(n log n). The distributed scheduling scheme is based on a focus-based heuristic algorithm and a bidding-based algorithm. Our algorithm takes care of the network delays.