Title: The uniprocessor scheduling of sporadic real-time tasks
Abstract: Within the context of real-time computer systems, the concept of sporadic tasks was introduced to model external interrupts; i.e., events external to the computer system. Clearly one cannot guarantee service for interrupts that occur arbitrarily frequently. However, when the environment places restrictions on the occurrence of these events, it may be possible to schedule service for all such events. We study existing models for sporadic task systems, and introduce new ones. We compare these models in terms of accuracy (i.e., how accurately they model the sporadically recurring tasks actually encountered in real-time application systems) and tractability (i.e., the resource complexity of (i) determining whether a task system specified by the model is schedulable, and (ii) on-line algorithms for scheduling real-time task systems specified by the model). We design several new algorithms for feasibility-testing and on-line scheduling of sporadic task systems. These algorithms exhibit significant improvements in behavior over existing ones.
In order that they may degrade gracefully under emergency conditions, it is important that on-line scheduling algorithms perform well under conditions of overload. However, we prove that no on-line algorithm can guarantee a processor utilization greater than 1/4 under overload. We look beyond the paradigm of deterministic computation in our search for solutions to this potential bottleneck. We present randomized algorithms that offer significantly better performance guarantees. Further, we quantify the advantages of using faster hardware in real-time systems. Apart from the obvious advantage of being able to do more in a shorter amount of time (and thus being less likely to go into overload in the first place), we prove that the performance of systems using faster hardware improves dramatically vis-a-vis systems using slower hardware if overload does occur. Our results yield some very satisfactory methods for preventing performance degradation under conditions of overload.
Publication Year: 1993
Publication Date: 1993-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 8
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot