next up previous contents
Next: Fair Share Up: Dynamische Scheduling-Verfahren Previous: Least Laxity First (LLF)   Inhalt


Proportional Share

Proportional Share steht für eine Klasse von Algorithmen, die jedem Thread einen Anteil an der verfügbaren Rechenzeit zuweisen, der proportional zu seiner Wichtigkeit ist.

Das Verfahren stammt aus dem Bereich der verteilten Multimediasysteme und der Netzwerke, wo Datenpakete mit einem festgelegten Anteil an der Übertragungsbandbreite ausgeliefert werden müssen. Es handelt sich dabei meist um sogenannte weiche Echtzeitbedingungen, die sich dadurch auszeichnen, daß das Überschreiten einer Deadline zwar unerwünscht, aber nicht fatal ist.

Waldspurger und Weihl vergeben an jeden Thread eine Anzahl Lose, je wichtiger der Thread, desto mehr Lose bekommt er. Im Fall des Lottery-Scheduling ([WaWe94]) wird vom Scheduler eine Zufallszahl erzeugt, die einer Losnummer entspricht. Der Thread, der das Los mit dieser Nummer hat, wird als nächster ausgeführt. Mit diesem Verfahren pendelt sich der Anteil an der Prozessorleistung zwar im Laufe der Zeit auf den gewünschten Wert ein, ein Thread kann aber sehr lange nicht ausgeführt werden, so daß man die Einhaltung von Deadlines nicht garantieren kann.

Ein anderer Algorithmus der Klasse Proportional Share ist das Stride-Scheduling, wie es in [WaWe95] beschrieben wird. Dabei wird zu jedem Thread ein Stride bestimmt, der umgekehrt proportional zu seiner Wichtigkeit ist. Der Thread muß jedesmal sooft warten, wie sein Stride angibt, bevor er einmal ausgeführt wird. Konkret heißt das, jedem Thread ist ein rückwärtslaufender Zähler zugeordnet. Der Thread mit dem niedrigsten Zählerstand wird ausgeführt und sein Zähler um seinen Stride erhöht.


next up previous contents
Next: Fair Share Up: Dynamische Scheduling-Verfahren Previous: Least Laxity First (LLF)   Inhalt
Alexander Schulz
2000-06-18