Prioritäten-Manager

Zunächst werden eventuelle Latenzen vom vorherigen Takt übernommen. Der Scheduler führt für jeden Thread die Anzahl der noch ausstehenden Latenzen mit.

Das Herzstück eines jeden Schedulers ist ein Vergleicherbaum, der den jeweils höchstpriorisierten Thread zurückliefert. Dieser Vergleicherbaum stellt den größten Aufwand in Laufzeit und Hardware-Verbrauch dar.

Verglichen werden von jedem Thread ein Wert, der zum einen aus den Parametern - etwa der Deadline - besteht, zum anderen gibt das höchstwertige Bit an, ob der Thread überhaupt ausgeführt werden darf. Somit werden ausführbare Threads schon bei diesem Vergleich bevorzugt.

Ein Thread darf nur dann ausgeführt werden, wenn er sich nicht in einer Latenz befindet, aktiv und nicht blockiert ist und wenn ein Bytecode oder Opcode zur Verfügung steht. Dies ist der Fall, wenn im Befehlsfenster noch genügend Daten vorhanden sind oder statt neu geholter Bytecodes noch Mikrobefehle ausgeführt werden können.

Ist der höchstpriorisierte Thread bestimmt, wird dieser über IdThreadTag an die Dekodierlogik weitergereicht oder IdInvalid auf high gesetzt, wenn er nicht ausgeführt werden darf. Zum Schluß werden noch die Latenzen heruntergezählt, da alle nicht ausgeführten Threads im Verlauf dieses Taktes einen Takt ihrer Latenz ,,abgesessen`` haben.

Die übrigen Teile sind jeweils vom verwendeten Schedulingverfahren abhängig.

• Feste Prioritäten (Fixed Priority Preemptive, FPP) Bei diesem Verfahren sind keine zusätzlichen Maßnahmen notwendig.
• Earliest Deadline First (EDF) übernimmt mit jeder Ankunft eines Signals die Deadline des zugehörigen Thread in eine Variable und zählt diese mit jedem Takt herunter. Somit liegt die Deadline desjenigen Thread am nächsten, der die kleinste Zahl in dieser Variablen stehen hat. Deshalb wird das höchstwertige Bit der Priorität, das anzeigt ob der Thread ausführbar ist, invertiert und der Thread mit dem kleinsten Wert ausgewählt.
• Guaranteed Percentage wird anhand von Intervallen gesteuert. Zu Beginn eines Intervalls wird ein Zähler auf die Intervallänge initialisiert und dann in jedem Takt heruntergezählt. Zudem wird der Anteil an Takten, den die Threads bekommen sollen, in remain gespeichert, die Kodierung für die Klasse, der er angehört, in klasse.

  Die Kodierung der Klassen ist aus Tabelle 4.2 ersichtlich.

  Da Threads der Klasse minimal zunächst mit solchen der Klasse genau verzahnt ausgeführt werden sollen, bekommen sie zu Beginn des Intervalls ebenfalls die Kennung genau und wechseln erst dann zu minimal, wenn sie ihren vorgegebenen Anteil Verbraucht haben (remain =0).

  Der Bitvektor klasse wird mit dem Bitvektor für die Resttakte zur Priorität zusammengefaßt. Um eine bessere Durchmischung zu erreichen, wäre es besser, statt der Resttakte den Quotient $\frac{Resttakte}{Anteil~in~Takten}$ zu verwenden, das würde aber eine Division erfordern, die in der zur Verfügung stehenden Zeit innerhalb eines Taktes nicht realisierbar ist. Das wäre lösbar, indem man in den Parametern noch einen zusätzlichen Wert mitgibt, der in etwa ld(Anteil) entspricht. Man könnte dann alle Anteile um sieben bit nach links und um diesen Wert wieder nach rechts schieben und bekäme wieder eine gute Mischung. Allerdings müssen dann die Vergleicher breiter werden,was die Kosten deutlich erhöht.

  Zusätzlich muß noch beachtet werden, daß Threads der Klassen kurz, genau und maximal nicht mehr ausgeführt werden dürfen, wenn sie ihren Anteil verbraucht haben. Um diese drei Klassen schnell erkennen zu können, haben sie eine 1 im ersten Bit der Kennung.

  Am Ende des Taktes wird die Zahl der verbleibenden Takte für den auszuführenden Thread und jeden, der gerade eine Latenz abwartet, um eins erniedrigt.

Tabelle: Kodierung der Klassen für Guaranteed Percentage

Code	Klasse
000	Nicht echtzeitfähig
001	Minimal
101	Maximal
110	Genau
111	Kurze Deadline