Scheduling of Overload-Tolerant Computation and Multi-Mode Communication in Real-Time Systems
Real-time tasks require sufficient resources to meet deadline constraints. A component should provision sufficient resources for its workloads that consist of tasks to meet their deadlines. Supply and demand bound functions can be used to analyze the schedulability of workloads. The demand-bound function determines the maximum required computational units for a given workload and the supply-bound function determines the minimum possible resources supplied to the workload. A component will experience an overload if it receives fewer resources than required. An overload will be transient if it only occurs for a short period. Most work concentrates on designing components that avoid overloads by over-provisioning resources although some computational units such as control system components can tolerate transient overloads. Components that permit short, bounded, and transient overloads can utilize the resources more efficiently than by avoiding this over provisioning.
First, this dissertation presents the design of an efficient periodic resource model for scheduling computation of components that can tolerate transient overloads under the earliest deadline first (EDF) scheduling policy. We propose a periodic resource model for overload-tolerant components that addresses three problems: (1) characterize overloads and determine metrics of interest (i.e., delay), (2) derive a model to compute periodic resource supply for a given workload and worst-case tolerable delay, and (3) find a periodic resource supply for given control system specifications with a worst-case delay. The derived periodic resource supply can be used to derive an overload-tolerant component interface. Overload-tolerant real-time components can connect each other in a distributed manner and thus require communication scheduling for reliable and guaranteed transmissions. Moreover, applications may require multi-mode communication for efficient data transmission.
Second, this dissertation discusses communication schedules for multi-mode distributed components. Since distributed multi-mode applications are prone to suffer from delays incurred during mode changes, good communication schedules have low average mode-change delays. A key problem in designing multi-mode communication in real-time systems is the generation of schedules to move away the complexity of schedule design from the developer. We propose a mechanism to generate multi-mode communication schedules using optimization constraints associated with timing requirements. We illustrate a workflow from specifications to the generation of communication schedules through a real-time video monitoring case-study. Experimental analysis for the case-study demonstrates that schedules generated using the proposed method reduce the average mode-change delay compared to a randomized algorithm and the well-known EDF scheduling policy.
Finally, this thesis discusses synthesis of schedules for computation and communication to achieve not only performance but also separation of concerns for reducing complexity and increasing safety. To integrate overload-tolerant components using real-time communication, we derive specifications of component interfaces using the characterization of overloads and the proposed periodic resource model. The generation of communication schedules uses the specifications of interfaces which include timing requirements of possible transient overloads. A walk-through case-study explains the steps necessary to generate communication schedules using component interfaces. The interfaces provide safety through isolation of transient overload-tolerant components and the generated communication schedules provide high performance as a result of their low average mode-change delay.