next up previous contents
Next: Proportional Share Up: Dynamische Scheduling-Verfahren Previous: Earliest Deadline First (EDF)   Inhalt


Least Laxity First (LLF)

Dieses Verfahren ist dem Earliest Deadline First sehr ähnlich, allerdings wird zur Auswahl des nächsten auszuführenden Threads nicht nur die Deadline betrachtet, sondern zusätzlich die Zeit, die der Thread bis zur Erfüllung seiner Aufgabe noch rechnen muß. Die höchste Priorität bekommt der Thread mit der geringsten Laxity li,j. Die Laxity ist die Zeit, die einem Prozess bis zu seiner Deadline noch übrigbleiben würde, wenn er ab sofort bis zu seiner Beendigung den gesamten Prozessor zur Verfügung hätte. Abbildung 2.5 verdeutlicht diesen Zusammenhang.

Abbildung 2.5: Definition der Laxity

Least Laxity First ist theoretisch besser als Earliest Deadline First, da früher erkannt wird, wenn eine Deadline nicht mehr eingehalten werden kann. Das Verfahren benötigt aber zusätzlichen Rechenaufwand und die Laufzeiten der Threads als zusätzliche Eingabewerte. Zudem werden deutlich mehr Kontextwechsel erzeugt.

Abbildung 2.6 zeigt das Ablaufdiagramm der drei Threads aus Abschnitt 2.5.3 unter Least Laxity First Scheduling.

Abbildung 2.6: Drei Threads unter Least Laxity First Scheduling


next up previous contents
Next: Proportional Share Up: Dynamische Scheduling-Verfahren Previous: Earliest Deadline First (EDF)   Inhalt
Alexander Schulz
2000-06-18