Bestimmung der Anteile

In diesem Abschnitt soll genauer betrachtet werden, welche Rahmenbedingungen gelten müssen, damit man mit Hilfe der drei Klassen auch Threads erlauben kann, deren Deadline kürzer ist als ihre Periode, ohne den schlechtesten Fall annehmen zu müssen und sie mit $P_i=\frac{C_i}{D_i}$ einzurechnen. Das würde eine schlechte Auslastung des Prozessors bedeuten, da der Thread diese Rechenzeit nur sehr selten nutzt.

Die Voraussetzungen aus Abschnitt 2.5.1 bleiben weitestgehend erhalten, mit der Ausnahme, daß ein Thread mit D_i<T_i zugelassen wird. Das Verfahren funktioniert nur solange, wie die Summe aller Prozentsätze innerhalb der Klasse genau unter 100% liegt.

Threads der Klasse maximal können bei der Betrachtung vernachlässigt werden, da es für sie nicht kritisch ist, wenn sie für kurze Zeit keine Rechenzeit bekommen. Zusätzliche Threads in der Klasse genau (mit T_i=D_i) ergeben nur einen konstanten Offset, das heißt, man hat weniger Gesamtrechenzeit zur Verfügung. Zusätzliche Threads in der Klasse minimal müssen sich alle Ressourcen teilen, so daß man sie für den Moment auch als einen Thread betrachten kann, der alle Resourcen alleine braucht. Wir betrachten daher nur zwei Threads, einen in der Klasse genau (G) und einen in der Klasse minimal (M).

Abbildung: Zeitlicher Verlauf der Threads M und G. Gepunktete Linien stellen P_i dar.

Es gibt zwei prinzipielle Herangehensweisen, um den Prozentsatz für den Thread mit der kurzen Deadline zu berechnen. Zum einen müssen die anderen Threads noch ihre benötigte Rechenzeit $P_M*T_M=\frac{C_M}{T_M}T_M=C_M$ bekommen. Zunächst sei $T_G\le T_M$, wie in Abbildung 2.10 gezeigt wird. Dann muß bei einer Prozessorauslastung von 100%, also für P_M=1-P_G, gelten:

$$\left( 1 - \frac{C_G}{D_G}\right) D_G + 1 \left( T_M-D_G \right) = C_M$$ D_G-C_G+T_M-D_G = C_M

T_M-C_G = C_M (1)

Der zweite Weg führt über die Gewinne und Verluste an Rechenzeit, die der Thread T_M erfährt. Während der Thread mit der kurzen Deadline aktiv ist, verliert der andere Thread

$$\int\limits_{0}^{D_G}\frac{C_M}{T_M}-1+\frac{C_G}{D_G}dt$$

Im Gegenzug gewinnt er während des Rests seiner Laufzeit

$$\int\limits_{D_G}^{T_M}P_G dt$$

das entspricht dem Bereich oberhalb der gepunkteten Linie in Abbildung 2.10. Gleichsetzen dieser beiden Ausdrücke führt ebenfalls auf Gleichung 2.1.

Damit müssen die beiden Threads mit den folgenden Prozentsätzen angegeben werden:

$$\begin{eqnarray*} P_M=\frac{C_M}{T_M}\\ P_G=1-\frac{C_M}{T_M}= 1-\frac{T_M-C_G}{T_M}\\ P_G=\frac{C_G}{T_M} \end{eqnarray*}$$

Mit $P_G+P_M\le 1$, was aus Abbildung 2.10 auch intuitiv klar wird.

Abbildung: Zeitlicher Verlauf der Threads M und G für T_G>T_M.

Wenn T_G>T_M gilt, dann kann es pasieren, daß in eine Periode von M mehrere Ausführungen von G fallen, wie es in Abbildung 2.11 zu sehen ist. Wenn T_G ein ganzzahliges Vielfaches von T_M ist, erhöhen sich die Verluste zwischen 0 und D_G um den gleichen Faktor, um den sich der Zugewinn in der restlichen Zeit erhöht. Es muß daher gelten:

$$\begin{eqnarray*} P_G=\frac{C_G}{T_G} \end{eqnarray*}$$

Dabei ist zu beachten, daß jetzt das kleinere T_G zur Berechnung des Prozentsatzes herangezogen wird und nicht T_M.

Wenn T_G>T_M ist, aber T_G kein ganzzahliges Vielfaches von T_M ist, muß der Thread G einen höheren Prozentsatz zugewiesen bekommen, da ein weiterer Peak von G auftreten kann, ohne daß M ausreichend Zeit hat, diesen auszugleichen. Im schlechtesten Fall, bei dem die Deadline von M mit der von G zusammenfällt, gilt:

$$\begin{eqnarray*} P_G=\left(1+\left\lfloor\frac{T_M}{T_G}\right\rfloor^{-1}\right)\frac{C_G}{T_G} \end{eqnarray*}$$

Ist P_G wie oben angegeben gewählt, können alle Threads ihre Deadlines einhalten, auch wenn man die Prozessorauslastung damit einschränkt. Damit erreicht man aber immer noch eine höhere Auslastung des Prozessors als mit $P_G=\frac{C_G}{D_G}$. Dem Scheduler muß natürlich weiterhin $\frac{C_G}{D_G}$ angegeben werden, aber die Summe dieser Werte darf 100% übersteigen.

Wenn mehrere Threads in der Klasse minimal vorhanden sind, müssen die Verluste aller Threads aufsummiert und P_G so gewählt werden, daß alle diese Verluste ausgeglichen werden. Das führt dann zwar zu komplexeren Berechnungen, der benötigte Prozentsatz bleibt aber weiterhin berechenbar.