Real-Time Scheduling of Dynamically Reconfigurable Systems

The timing of sensor-based control systems is crucial. Critical servo-level periodic tasks that fail to meet their deadlines result in losing data or missing control cycles. This can lead to a loss in performance in the best case, and can cause serious damage to equipment or human injury in the worst case. It is therefore critical that the timing of these systems is predictable and controllable. A dynamically reconfigurable system can change in time without the need to halt the system. Such systems may have many sensors or actuators, only a subset of which are used at any time. Alternately the same hardware is used in a different configuration. In this paper we propose the maximum-urgency-first algorithm, which can be used to predictably schedule dynamically changing systems. We show that it is a significant improvement over the rate monotonic algorithm, which can only be used to schedule static systems. The maximum-urgency-first scheduler has been implemented as the default scheduler of CHIMERA II, a real-time operating system being used to control sensor-based control systems both at Carnegie Mellon University and elsewhere.