Scheduling mit festen Prioritäten (fixed priority preemptive)

Bei dieser Gruppe von Algorithmen wird jedem Thread eine feste Priorität zugewiesen, die während der gesamten Laufzeit des Threads konstant bleibt. Zu jedem Zeitpunkt wird derjenige Thread ausgeführt, der unter allen ausführbaren die höchste Priorität hat. Normalerweise vergibt man die Prioritäten so, daß die Threads eine umso höhere Priorität bekommen, je kürzer ihre Periode ist. Dieses Verfahren nennt man Rate-Monotonic (RM) ([LiLa73]). Wenn eine Menge von Threads überhaupt mit festen Prioritäten eingeplant werden kann, dann wird sie auch mit dieser Verteilung der Prioritäten fehlerfrei ablaufen. Daher ist Rate-Monotonic optimal in dieser Klasse von Algorithmen.

Ebenfalls in [LiLa73] wird nachgewiesen, daß man im schlechtesten Fall nur eine Prozessorauslastung von $n(2^\frac{1}{n}-1)$ erreichen kann, wobei n die Anzahl der laufenden Threads ist. Für die drei Beispiel-Threads aus Abschnitt 2.5.3 wären das also ca. 78%.

Die Schranke von Liu und Layland ist sehr pessimistisch, hängt aber nicht von den Parametern der einzelnen Threads ab, sondern nur von deren gesamter Prozessorauslastung. Alle weiteren Abschätzungen, ob eine Menge von Threads ohne eine Verletzung von Deadlines ausgeführt werden kann, wie sie zum Beispiel in [HaTy97] beschrieben werden, hängen von den Ausführungszeiten, den Startzeiten und den Deadlines ab. Die genaue Einordnung einer Menge von Threads ist zwar im Voraus möglich, wenn man alle Parameter kennt, jedoch im allgemeinen nicht in polynomialer Zeit. Zudem sind viele Parameter in einem dynamischen System nicht vorab bekannt.

Diese geringe Prozessorauslastung gilt als der größte Nachteil dieses Algorithmus. Sie ist nur akzeptabel, wenn es noch weitere Threads im System gibt, die keinen Echtzeitanforderungen genügen müssen und die verbleibende Rechenkapazität nutzen können, aber 22% sind dafür eigentlich schon zuviel.

Die Vorteile dieser Technik liegen in der einfachen Implementierbarkeit, dem geringen Hardwareaufwand und in seiner Stabilität. Im Falle einer Überlastung des Prozessors werden zwar nicht mehr alle, aber die wichtigsten Jobs innerhalb ihrer Deadlines ausgeführt, wenn diese die höchsten Prioritäten haben.

Abbildung 2.2 zeigt das Ablaufdiagramm der drei Threads aus Abschnitt 2.5.3 unter Rate-Monotonic Scheduling. Trotz der hohen Gesamtauslastung von über 95% funktioniert das Verfahren bei diesem Beispiel fehlerfrei. Würde der dritte Thread mit T₂=8 und C₂=2 laufen, so ginge es nicht mehr, obwohl die Prozessorauslastung auch dann noch kleiner als eins wäre.

Abbildung 2.2: Drei Threads unter Rate-Monotonic Scheduling