Rate Monotonic Scheduling
aus Wikipedia, der freien Enzyklopädie
Rate Monotonic Scheduling (RMS) ist ein Prioritätsscheduling-Verfahren für unterbrechbare, periodische Jobs. Es wird häufig in Echtzeit-Systemen eingesetzt. Die Prioritäten werden statisch nach der Periodendauer eines Jobs festgelegt: je kürzer die Periodendauer eines Jobs, desto höher ist seine Priorität.
Aperiodische Jobs können innerhalb eines fiktiven periodischen Jobs ausgeführt werden.
[Bearbeiten] Einplanbarkeit
Unter welchen Bedingungen ist eine Menge von Jobs unter RMS garantiert einplanbar?
- Hinreichende Bedingung nach Liu und Layland. Ist die Auslastung u kleiner oder gleich einer Auslastungsschranke, ist die Job-Menge einplanbar. Die Schranke ist dabei nur von der Anzahl n der Jobs abhängig:
![u = \sum\frac{C_i}{T_i} \le n * (\sqrt[n]{2} -1)](../../../math/3/f/b/3fb66e220e36da8549fb56b8518e05bd.png)
(mit den Ausführungszeiten Ci und den Periodenlängen Ti, i = 1 bis n, n = Anzahl der Jobs).- Mit zunehmender Anzahl von Jobs nähert sich die Schranke dem Wert
. - Wenn also die berechnete Auslastung u unter 69,3% liegt, sind die Jobs sicher einplanbar. Wenn die tatsächliche Auslastung größer als u ist kann aber trotzdem ein Ablaufplan unter RMS existieren, mit dem kein Job seine Deadline verletzt.
- Harmonische Periodendauern. Wenn die Periodendauern Vielfache voneinander sind (harmonisch), sind die Jobs einplanbar, falls
. Unter dieser Bedingung ist RMS also optimal.
[Bearbeiten] Literatur
- Liu, Jane W. S., "Real-time systems", Prentice Hall, Upper Saddle River, NJ, 2000
