Timeline Scheduling (TL)

Das einfachste Beispiel eines Schedulers für periodische Tasks ist der sogenannte Time Line Scheduling Algorithmus. Die Grundidee dieses Algorithmus besteht darin, ausgehend von der Summe aller Ausführungszeiten $\sum_{i=1}^{n} C_{i}$ aller zu bearbeitenden Ereignisse $E$ ein periodisches Intervall (den minor cycle) zu finden, das groß genug ist, alle Ereignisse aus $E$ zu bearbeiten. Gibt es solch ein Intervall (einen minor cycle), dann ist sichergestellt,daß alle ankommenden Ereignisse immer bearbetet werden können.

Figure 4.1: Beispieldaten für Timeline-Daten

Beispiel (siehe für die Werte das Bild 4.1, für den Schedulingplan das Bild 4.2): ausgehend von einer Ereignismenge $E$, deren Ereignisse $e_{i}$ mit den Häufigkeiten $f_{i}$ [Hz] auftreten kann man dann mittels $T_{i}=1/f_{i}$ die Perioden der Ereignisse ermitteln. Man ermittelt dann nach der Methode des größten gemeinsamen Teilers (greatest common divisor (GCD)) den kleinsten Zyklus (minor cycle), für den gilt:

$$\sum_{i=1}^{n} C_{i} \le minorCycle$$

Im Beispiel wäre minorCycle 20ms und $\sum_{i=1}^{n} C_{i} = 6+4+2 = 12 ms$. Dies bedeutet, dass alle drei Tasks innerhalb des minorCycle ausgeführt werden können. Der Größere Zyklus (major cycle) wird mit der Methode des Kleinsten Gemeinsamen Vielfachen (KGV) (Least Common Multiple, LCM) ermittel. Der majorCycle gibt an, wie groß das Intervall mindestens sein muss, bis es wieder zur Wiederholung aller Ereignisse kommt. Im Beispiel ist der majorCycle = 200 ms.

Figure 4.2: Beispieldiagramm für Timeline-Daten

Für die Abarbeitung innerhalb des TimeLine Schedulings ist zu beachten, daß die Anordnung der Tasks jeweils zu Beginn des minor cycles für alle Tasks im Bereich dieses minor cycles geklärt wird (vgl. Bild 4.3). Damit ist keine Präemption und damit kein Kontextswitch notwendig. Für weitere Details zum TL-Scheduling sei auf [11]:SS.76ff verwiesen.

Figure 4.3: Schedulingalgorithmus für Timeline Algorithmus