next up previous contents
Next: Laxity Percentage Up: Erweiterungen zu Guaranteed Percentage Previous: Erweiterungen zu Guaranteed Percentage   Inhalt

Globaler Zähler

Eine Möglichkeit zur Behandlung von Blockierungen wäre etwa, für jeden Thread einen zweiten Zähler mitlaufen zu lassen, der die Zugewinne und Verluste an Takten mitzählt, die während einer Blockierung auftreten. Das Ziel des Scheduling ist dann, diese Zähler auf 0 auszugleichen. Insbesondere müssen Threads, die einen hohen positiven Wert in diesem Zähler haben, mehr Rechenzeit bekommen, um die Verluste auszugleichen. Die dazu benötigte Rechenzeit wird bevorzugt von Threads mit negativem Zähler abgezogen, die schon mehr Rechenzeit bekommen haben, als es ihrem Anteil entspricht. Nach jedem Intervall wird dieser Zähler um den zugewiesenen Prozentsatz erhöht und mit jedem ausgeführten Befehl des Thread um eins erniedrigt.

Nun muß der Algorithmus aber zwischen Blockierungen und Wartezeiten, in denen der Thread einfach nichts zu tun hat, unterscheiden können. Sonst würde der Zähler während der Idle-Zeiten schnell steigen und das Bild verzerren. Dies könnte entweder durch ein weiteres Bit im Threadstatus geschehen, oder durch ein Rücksetzen des Zählers mit einem Prozessorbefehl oder automatisch, wenn ein Signal eintrifft, daß diesen Thread startet. Damit ist dieser Zähler nur innerhalb einer Periode gültig.

Threads mit kurzer Deadline könnte man dann mit einer zusätzlichen Priorisierung versehen, so daß dieser Thread immer ausgeführt wird, wenn er ausführbar ist. Oder man weist den Threads eine Prioritätenfolge zu, wobei der Thread mit der höchsten Priorität seine Rate zuerst erfüllt bekommt. Wenn die Summe aller Anteile dadurch 100% übersteigt, muß der Benutzer des Systems sicherstellen, daß der Thread mit der kurzen Deadline selten genug auftritt und kurz genug läuft, daß alle anderen Threads ihre Deadlines noch einhalten können.

Dabei ist wichtig, daß es nur einen solchen Thread gibt, da die Threads ihre Deadlines sonst nicht einhalten können, wenn sie sich zeitlich ungünstig überlappen.

Solange die Summe der Prozentsätze noch unter 100% liegt und keine Blockierungen auftreten, schreiten alle Threads gemäß ihrer zugewiesenen Rate fort. Das abgewandelte Verfahren verhält sich dann genau so wie das Original.


next up previous contents
Next: Laxity Percentage Up: Erweiterungen zu Guaranteed Percentage Previous: Erweiterungen zu Guaranteed Percentage   Inhalt
Alexander Schulz
2000-06-18