09-01-2014, 12:22 PM
How Different are Offline and Online Scheduling
Offline and Online Scheduling.pdf (Size: 57.21 KB / Downloads: 90)
INTRODUCTION
The heated debate on whether offline or online scheduling (e.g., [2], [1], and
[3]) is preferable for real-time systems has taken attention away from the question
how the two are actually defined and what their essential differences are. Results
and arguments in the debate are typically based on a conglomerate of assumptions,
system design issues, and particular views of scheduling rather than the actual cores
of the ways to schedule themselves. We do not wish to get involved into the “TT’
vs. ET” debate, rather have a look the related scheduling paradigms to determine
what their differences are. We conclude they are much smaller than perpertuated
clichees.
One of the central choicesfor scheduler design is that of the activation paradigm,
i.e., when are events recognized, who initiates activities, when are these decisions
taken? In conventional systems, the event triggered approach is prevalent, in which
occurrences of events initiate activities in the system immediately. In time triggered
systems, activities are iniated at predefined points in time [2].
Online Scheduling
In event triggered systems, events invoke an online sched-
uler, which takes a decision based on a set of pre defined rules, e.g., represented
as priorities. An offline schedulability test can be used to show that, if a set of
rules is applied to a given task set at runtime, all tasks will meet their deadlines.
Major representative lines of such algorithms are based on fixed priorities, e.g, rate
monotonic or dynamic priorities.
Conclusion
Mixing system design issues and actual scheduling of TT and ET,
offline and online scheduling appear very different. Separating activation paradigm,
i.e., when is the scheduler invoked, from the actual scheduling reveals a different
situation: the essential steps of (i) offline analysis and feasibility test, either via proof
that no infeasible situation can occur or by constructing a complete schedule, (ii)
determination of scheduling rules, whether in explicit forms, e.g., EDF, or implicit
as scheduling table, and (iii) runtime execution according to these rules, are the
same, albeit in different forms.