Voraussetzungen

Die folgenden Definitionen richten sich nach [SSRB98]. Ein Thread $\tau _i$ ist charakterisiert durch die Worst-Case-Laufzeit C_i eines Durchlaufes, die Periode T_i, mit der er aufgerufen wird, sowie seine relative Deadline D_i. Ein Job t_i,j ist die j-te Instanz des Threads $\tau _i$, die zum Zeitpunkt r_i,j startet und spätestens zur absoluten Deadline d_i,j = r_i,j + D_i beendet sein muß. Das heißt, jeder Thread benötigt innerhalb seiner Periode maximal seine Worst-Case-Laufzeit, der Rest der Rechenleistung des Prozessors steht für andere Threads zur Verfügung.

Die Auslastung des Prozessors durch einen Thread ist daher $\frac{C_i}{T_i}$, die durch eine Menge von n Threads folglich $\sum_{i=1}^{n}\frac{C_i}{T_i}$. Diese Summe darf in keinem Fall größer als 1 werden, sonst können die Threads nicht mehr auf dem Prozessor ausgeführt werden, ohne daß Deadlines verletzt werden. Wie nah man an den Wert 1 herankommt, hängt vom verwendeten Scheduling-Verfahren und von den Threads ab. Bei der Wahl des Verfahrens spielt auch die Anzahl der Threadwechsel und der dabei entstehende Overhead eine wichtige Rolle.

Wir gehen davon aus, daß alle Echtzeit-Threads periodisch sind und die Deadline gleich der Periode ist (D_i=T_i). Aperiodische Threads werden so behandelt, als wären sie periodisch, wobei ihre minimale Ankunftsrate als ihre Periode angenommen wird. Ein Thread wird nur inaktiv, wenn er einen Durchlauf beendet hat, das heißt insbesondere, daß es neben der CPU keine weiteren gemeinsam genutzten Ressourcen und keine gegenseitigen Abhängigkeiten gibt. Threads können zu jedem beliebigen Zeitpunkt unterbrochen werden.

Ein periodischer Thread ist also durch das Tripel (T_i,C_i,D_i) eindeutig beschrieben. Da die Deadline in den hier betrachteten Fällen immer gleich der Periode ist, können wir auf den dritten Parameter verzichten und einen Thread durch das Tupel (T_i,C_i) beschreiben.

Die letzte Voraussetzung für die theoretische Betrachtung ist, daß durch Unterbrechung eines Threads und Umschalten zu einem anderen (Thread-Wechsel) keine Kosten in Form von zusätzlich verbrauchter Rechenzeit entstehen. In einem normalen System ist diese Voraussetzung nicht haltbar, auf einem mehrfädigen Prozessor ist das jedoch tatsächlich möglich.

Der ungünstigste Fall für die Abarbeitung ist gegeben, wenn alle Threads zur gleichen Zeit das erste Mal aktiviert werden. Wir können ohne Beschränkung der Allgemeinheit diesen Zeitpunkt 0 nennen.

Abbildung 2.1: Ein Thread läuft exklusiv (T₀=3,C₀=1)

Abbildung 2.1 zeigt das Ablaufdiagramm eines periodischen Thread mit T₀=3 und C₀=1, wenn er exklusiv auf einem Prozessor läuft. Dabei markiert $\uparrow$ den Startzeitpunkt r_i,j eines Jobs, der durch einen Timer oder das Auftreten eines Ereignisses vorgegeben wird, $\downarrow$ seine Deadline d_i,j und die grauen Bereiche die Zeiträume, in dem die CPU dem Thread zur Verfügung steht. Bei $\updownarrow$ treffen die Deadline d_i,j und die Startzeit r_i,j+1 zusammen.