Steuerung mit Intervallen

Eine weitere Möglichkeit, Threads mit kurzer Deadline einzuplanen, besteht darin, für jeden Thread das Intervall mit anzugeben, in dem er seinen Anteil bekommen muß. Damit ist festgelegt, wann ihm Rechenzeit entzogen werden darf, und wann das zu Verletzungen von Deadlines führen würde.

Gegeben seien (n-1) Threads $\tau_2\ldots \tau_n$ mit den Raten $P_2\ldots P_n$ in den Intervallen $I_2\ldots I_n$. Dazu kommt ein Thread $\tau_1$ mit D₁<T₁, für den wir zunächst annehmen, I₁ sei kürzer als alle anderen Intervalle. Er werde nur einmal innerhalb des längsten Intervalls aufgerufen. Ist $\sum_{i=1}^n P_i \le 1$, so kann der Thread auf jeden Fall angenommen werden. Anderenfalls muß man anderen Threads im System kurzfristig Rechenzeit entziehen, die man ihnen später in ihrem Intervall wieder zurückgibt.

Abbildung: Intervalle und Rechenzeitzuweisung für n=3

Abbildung 2.12 zeigt ein Beispiel für n=3. Der zusätzliche Bedarf von $\tau_1$, der den anderen Threads entzogen werden muß, ist

$$\int\limits_0^{I_1} \left(\sum_{i=1}^n P_i \right) -1 dt,$$

also der Teil, um den die Summe der P_i 100% überschreitet. $\tau_2\ldots \tau_n$ seien oBdA nach aufsteigender Intervallänge sortiert. Dann kann jedem Thread $\tau_k~(2\le k\le n)$ der Anteil

$$\int\limits_{I_{k-1}}^{I_k} 1-\sum_{i=2}^n P_i dt$$ (2)

innerhalb des Intervalls I_k-1 entzogen werden. Formel 2.2 beschreibt die Prozessorleistung, die $\tau_k$ zurückerhalten kann, wenn er für den Rest seines Intervalls die gesamte Restleistung des Prozessors erhält.

Maximal kann den Threads $\tau_2\ldots \tau_n$ also

$$\begin{eqnarray*} \int\limits_{I_1}^{I_2} 1-\sum_{i=2}^n P_i dt + \int\limits_{I... ...i=2}^n P_i dt\\ = \int\limits_{I_1}^{I_n} 1-\sum_{i=2}^n P_i dt \end{eqnarray*}$$

entzogen werden. Damit ist auch der Fall abgedeckt, daß I₁ nicht das kürzeste Intervall ist. Weiterhin bedeutet das insbesondere auch, das man die zusätzlich benötigte Rechenleistung direkt von dem Thread mit dem längsten Intervall abziehen kann.

Der neue Thread $\tau_1$ kann also genau dann angenommen werden, wenn er nicht mehr zusätzliche Rechenleistung braucht, als dem System maximal entzogen werden kann:

$$\begin{eqnarray*} \int\limits_0^{I_1} \left(\sum_{i=1}^n P_i \right) -1 dt \le \... ...2}^n\int\limits_0^{I_n}P_i dt+ \int\limits_0^{I_1}P_1 dt \le I_n \end{eqnarray*}$$

Da $\tau_1$ nur innerhalb seines Intervalls ausgeführt wird, also P₁=0 für t>I₁ gilt, folgt:

$$\sum_{i=1}^n\int\limits_0^{I_n}P_i dt \le I_n$$ (3)

Daraus ergibt sich folgender Scheduling-Algorithmus: Der neue Thread wird angenommen, falls die Ungleichung 2.3 erfüllt ist, sonst abgelehnt. Wenn $\tau_1$ aktiv ist (in dem Intervall I₁), wird dem Thread $\tau_n$ mit dem längsten Intervall die Rechenleistung entzogen, die $\tau_1$ zusätzlich benötigt. In der restlichen Zeit bekommt $\tau_n$ die gesamte Restleistung des Prozessors zugeschlagen. Damit ist auch der Fall abgedeckt, dass $\tau_1$ erst am Ende des Intervalls I_n aktiv wird.