imported>Aka: Halbgeviertstrich, Links normiert, Kleinkram

2023-08-21T10:21:13Z

Halbgeviertstrich, Links normiert, Kleinkram

Neue Seite

{{lang|en|'''Rate Monotonic Scheduling'''}} (deutsch etwa ‚ratenmonotone Einplanung‘; kurz: ''RMS'') ist ein [[Prioritätsscheduling]]-Verfahren für unterbrechbare, periodische Jobs und wird häufig in [[Echtzeitsystem]]en eingesetzt. Die Prioritäten werden statisch anhand der Periodendauer eines Jobs festgelegt: je kürzer die Periodendauer eines Jobs, desto höher ist seine Priorität.

Aperiodische Jobs können mithilfe eines fiktiven periodischen Jobs ausgeführt werden, der diese bei Bedarf ausführt oder andernfalls keine Aktion durchführt. Diese Technik wird auch als Serverprinzip bezeichnet.

== Einplanbarkeit ==
Unter folgenden Bedingungen ist eine Menge von Jobs mittels Rate Monotonic Scheduling garantiert einplanbar:
* ''[[Hinreichende Bedingung#Hinreichende Bedingung|Hinreichende Bedingung]] nach Liu und Layland'': Ist die Auslastung <math>u</math> kleiner oder gleich einer Auslastungsschranke, ist die Job-Menge einplanbar. Die Schranke ist dabei nur von der Anzahl <math>n</math> der Jobs abhängig:
:<math>u = \sum\limits_{i=1}^{n}{\frac{C_i}{T_i}} \le n \cdot \left(\sqrt[n]{2} -1\right)</math>
::<math>C_i</math>: Ausführungszeiten
::<math>T_i</math>: Periodenlängen
::<math>n</math>: Anzahl der Jobs
:Mit zunehmender Anzahl von Jobs (<math>n \to \infty</math>) nähert sich die Schranke dem Wert ln 2 ≈ 0,693. Wenn also die berechnete Auslastung <math>u</math> unter 69,3 % liegt, sind alle Jobs sicher einplanbar. Wenn die tatsächliche Auslastung größer als <math>n \cdot \left(\sqrt[n]{2} -1\right)</math> ist, kann aber trotzdem ein Ablaufplan unter RMS existieren, mit dem kein Job seine Deadline verletzt.
* ''Hinreichende Bedingung'' ''"Hyperbolic Bound"'': Das ist eine strengere hinreichende Bedingung für die Einplanbarkeit als die von Liu und Layland:
:<math>\prod_{i=1}^n ({\frac{C_i}{T_i}} +1) \leq 2</math>
* ''Harmonische Periodendauern''. Wenn die Periodendauern Vielfache voneinander sind (harmonisch), sind die Jobs einplanbar, falls <math>u \le 1</math>. Unter dieser Bedingung ist RMS also optimal.

== Siehe auch ==
* [[Deadline Monotonic Scheduling]]
* [[Earliest Deadline First]]

== Literatur ==
* Liu, Jane W. S.: ''Real-time systems.'' Prentice Hall, Upper Saddle River, NJ, 2000
* E. Bini, G. C. Buttazzo and G. M. Buttazzo, "Rate monotonic analysis: the hyperbolic bound," in IEEE Transactions on Computers, vol. 52, no. 7, pp. 933–942, July 2003, [[doi:10.1109/TC.2003.1214341]].

[[Kategorie:Betriebssystemtheorie]]

Rate Monotonic Scheduling - Versionsgeschichte

imported>Aka: Halbgeviertstrich, Links normiert, Kleinkram