Grundbegriffe

Abhängig/Unabhängig

: Wenn ein Task $\tau_{i}$ von einem anderen Task $\tau_{j}$ abhängig ist, dann kann $\tau_{i}$ nur durch gleichzeitige/vorausgehende Ausführung dieses anderen Tasks $\tau_{j}$ abgearbeitet werden. Liegt solch eine Abhängigkeit nicht vor, dann ist der Task unabhängig. Unabhängige Tasks gelten als vollständig unterbrechbar (preemptable).

Ankunftszeit (arrival)

a$_{i}$. Wenn ein Ereignis eintritt, das nach der Ausführung eines Task verlangt

Antwortzeit

R$_{i}$: $R_{i} = f_{i} - r_{i}$

Auftretenszeit (request/ release)

r$_{i}$: Ab wann ein Task für die Ausführung zur Verfügung steht. In der Theorie ist $a_{i} = r_{i}$, bei realen Systemen ist $r_{i} > a_{i}$. Von der Auftretenszeit $r_{i}$ ist die Startzeit $s_{i}$ (siehe dort) zu unterscheiden. Wenn ein Task auftritt, dann spricht man auch von einer Instanz des Task.

Auftreten (Occurence)

: Wenn ein Ereignis (Event) auftritt, dann markiert es einen bestimmten Zeitpunkt, die Ankunftszeit (siehe dort). Das Auftreten kann regelmässig (periodisch) oder unregelmässig (aperiodisch) sein. Jedem auftretenden Ereignis ist ein Task (Task/Job) zugeordnet, der ausgeführt werden soll. Damit ein Task ausgeführt werden kann, muss er aktiviert werden. Dies ist der Aktivierungszeitpunkt (Release Time)

Ausführungszeit

C$_{i}$: Die Ausführungszeit wird als maximale Ausführungszeit betrachtet, d.h. das ist die worst-case execution time. Die tatsächliche Ausführung kann auch kürzer sein. Diese Differenzen zwischen maximaler und minimaler Ausführungszeit in der tatsächlichen Ausführung kann u.U. zu Problemen führen (siehe auch Ausführungs Jitter).

Ausführungs Jitter, absoluter (Absolute Execution Jitter)

AEJ$_{i}$: die höchste Abweichung der Ausführungszeiten zwischen allen Instanzen eines Task:

$$AFJ_{i} = max_{k}\mid (f{i.k}-s_{i.k})-(f_{i.k-1}-s_{i.k-1}) \mid$$

Ausführungs Jitter, relativer (Relative Execution Jitter)

RFJ$_{i}$: die höchste Abweichung der Ausführungszeiten zwischen zwei konsekutiven Instanzen eines Task:

$$RFJ_{i} = max_{k} (f{i.k}-s_{i.k})- min_{k} (f{i.k}-s_{i.k})$$

Beendigungszeit

f$_{i}$:

Beendigungszeit

f$_{i.j}$: Beendigungszeit der $j$-ten Instanz des Tasks $\tau_{i}$, das ist die Zeit, an der der Task/Job seine Ausführung beendet hat.

Beendigungs Jitter, absoluter (Absolute Finishing Jitter)

AFJ$_{i}$: die höchste Abweichung der Beendigungszeiten zwischen allen Instanzen eines Task:

$$AFJ_{i} = max_{k}\mid (f{i.k}-r_{i.k})-(f_{i.k-1}-r_{i.k-1}) \mid$$

Beendigungs Jitter, relativer (Relative Finishing Jitter)

RFJ$_{i}$: die höchste Abweichung der Startzeiten zwischen zwei konsekutiven Instanzen eines Task:

$$RFJ_{i} = max_{k} (f{i.k}-r_{i.k})- min_{k} (f{i.k}-r_{i.k})$$

Deadline, Absolute

d$_{i}$:

Deadline, Absolute

d$_{i.j}$: Absolute Deadline der $j$-ten Instanz des periodischen Tasks $\tau_{i}$ mit $d_{i.j} = \Phi_{i}+(j-1)T_{i}+D_{i}$ (Beispiel: Task $\tau_{3}$ startet bei Zeitpunkt $\Phi_{3}$ = 4 und tritt nun zum 5-ten Mal ($j$ = 5) auf mit einer Periode $T_{3}$ = 7 Zeiteinheiten und einer relativen Deadline $D_{3}$ = 2; dann ergibt sich $d_{3.5} = \Phi_{3}+(5-1)T_{3}+D_{3} = 4+(5-1)7+2 = 4+28+2 = 34$)

Deadline, relative

D$_{i}$: $D_{i} = d_{i} - r_{i}$

Erfüllbarer Task (feasible)

: Ein einzelner Task gilt als erfüllbar, wenn alle seine Instanzen innerhalb der Deadline beendet werden können. Eine Erfüllbare Taskmenge$\Gamma$ gilt als erfüllbar (feasible), wenn alle ihre tasks erfüllbar sind.

Hyperperiode

: $H$ Bei periodischen Tasks wiederholen sich die Konstellationen innerhalb der Hyperperiode $H = kgv(\cal{T})$ nach $H$-vielen Zyklen, wobei $kgv$ das kleinste gemeinsame Vielfache der Menge $\cal{T}$ der Perioden der beteiligten Tasks ist.

Kritische Instanz

: Der Zeitpunkt, bei dem das Auftreten eines Task die längste Antwortzeit (Response Time) nach sich zieht.

Kritische Zeitzone/ Kritisches Intervall

: Das Intervall zwischen einer kritischen Instanz und der Antwortzeit des zugehörigen Task

Laxity (or. Slack Time; Restzeit)

X$_{i}$: $X_{i} = d_{i} - a_{i} - C_{i}$ (Maximal verbleibende Zeit, um den Task bis zur Deadline zu beenden)

Periode

$T_{i}$: Periode des $i$-ten Tasks. Die Periode ist das Intervall zwischen zwei aufeinanderfolgenden Aktivierungen des gleichen Tasks.

Phase

$\Phi_{i}$: Die Phase des Tasks $\tau_{i}$ ist die erste Instanz $r_{i.1}$ des periodischen Tasks $\tau_{i}$

Prozessor Ausnutzungsfaktor (Processor Utilization Factor)$U$: Im Falle von periodischen Tasks steht einem Task $\tau_{i}$ mit einer Periode von $T_{i}$ der Prozessor maximal für die Zeit $T_{i}$ zur Verfügung. Wieviel Zeit der Task tatsächlich benötigt, hängt von seiner Ausführungszeit $C_{i}$ ab, also $C_{i}/T_{i}$. Wenn $C_{i}=T_{i}$ dann benötigt die Ausführungszeit die gesamte verfügbare Zeit. Bei n-vielen Tasks gilt

$$U = \sum_{i=1}{C_{i}/T_{i}}$$

Prozessor Ausnutzungsfaktor (Processor Utilization Factor),
obere Schranke (upper bound)$U_{ub}$: abhängig von einer bestimmten Taskmenge $\Gamma$ und einem Schedulingalgorithmus $A$ existiert eine maximale obere Schranke (upper bound) für den Ausnutzungsfaktor U, unterhalb von der die Menge $\Gamma$ erfüllbar ist und oberhalb nicht mehr, d.h. es muss gelten

$$U \le U_{ub}(\Gamma, A)$$

damit $\Gamma$ mit $A$ erfüllbar ist.

Prozessor Ausnutzungsfaktor (Processor Utilization Factor),
kleinste obere Schranke (least upper bound)$U_{lub}$: variiert man über alle möglichen Taskmengen $\Gamma_{i}$ dann kann man die kleinste obere Schranke definieren:

$$U_{lub}(A) = min_{\Gamma}(U_{ub}(\Gamma, A))$$

Wenn für eine bestimmte Taskmenge $\Gamma_{i}$ gilt, dass $U_{i} \le U_{lub}(A)$, dann ist diese Taskmenge ganz sicher mit $A$ erfüllbar. Andernfalls muss man dies im Einzelfall speziell klären.

Prozessor Ausnutzungsfaktor (Processor Utilization Factor),
Kleiner gleich 1 Wenn man eine Taskmenge $\Gamma$ mit n-vielen Tasks mit den Perioden $T_{i}$ hat sowie einen Prozessor mit verfügbaren Zeit 1, dann kan man sagen, dass mit $\sum_{i=1}^{n}{C_{i}/T_{i}}$ der Rechenbedarf der Tasks aus $\Gamma$ gegeben ist. Es soll gelten

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

Sei $T = \prod_{i=1}^{n} T_{i}$ das Produkt aller Perioden, dann gilt

$$\sum_{i=1}^{n}{TC_{i}/T_{i}} \le T$$

, das aber ist nichts anderes als

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

Restzeit (Lateness)

L$_{i}$: $L_{i} = f_{i} - d_{i}$

Startzeit

s$_{i}$:

Startzeit

s$_{i.j}$: Startzeit der $j$-ten Instanz des Tasks $\tau_{i}$, das ist die Zeit, an der der Task/Job seine Ausführung beginnt.

Startzeit Jitter, absoluter (Absolute Release Jitter)

ARJ$_{i}$: die höchste Abweichung der Startzeiten zwischen allen Instanzen eines Task:

$$ARJ_{i} = max_{k}\mid (s{i.k}-r_{i.k})-(s_{i.k-1}-r_{i.k-1}) \mid$$

Startzeit Jitter, relativer (Relative Release Jitter)

RRJ$_{i}$: die höchste Abweichung der Startzeiten zwischen zwei konsekutiven Instanzen eines Task:

$$RRK_{i} = max_{k} (s{i.k}-r_{i.k})- min_{k} (s{i.k}-r_{i.k})$$

Task/Job

$\tau_{i.j}$/$J_{i.j}$ Der Sprachgebrauch ist hier nicht ganz einheitlich. Sehr häufig bezeichnet man periodische Tasks als Tasks $\tau$ und aperiodische Tasks als Jobs $J$. $\tau_{i.j}$ bezeichnet dann die j-Instanz des Tasks $\tau_{i}$. Entsprechend für $J$.

Taskmenge

$\Gamma$:

Überschusszeit (Exceeding Time; Tardiness)

E$_{i}$: $E_{i} = max(0,L_{i})$ (Die Zeit, die ein Task nach seiner Deadline noch aktiv bleibt)

Unterbrechbar/ Präemptiv/ Preemptable

: Wenn ein Task unterbrechbar ist, dann kann ihre Ausführung an einem bestimmten Punkt angehalten werden, die gesamte Task wird zwischengespeichert (Kontextwechsel/ Contextswitch), und zu einem späteren Zeitpunkt kann die Task zurückgeholt und neu aktiviert werden. Bei realen Systemen kosten solche Kontextwechsel Verwaltungszeit/Administration Overhead.

Wert/ Priorität

v$_{i}$:

WCAO := Worst-Case Administration Overhead

: Die maximale Zeit, die die Verwaltung eines Tasks während seiner Ausführung kosten kann.