Rate Monotonic Scheduling

Rate Monotonic Scheduling (deutsch etwa ‚ratenmonotone Einplanung‘; kurz: RMS) ist ein Prioritätsscheduling-Verfahren für unterbrechbare, periodische Jobs und wird häufig in Echtzeitsystemen 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 nach Liu und Layland: Ist die Auslastung ${\displaystyle u}$ kleiner oder gleich einer Auslastungsschranke, ist die Job-Menge einplanbar. Die Schranke ist dabei nur von der Anzahl ${\displaystyle n}$ der Jobs abhängig:

${\displaystyle u=\sum \limits _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n\cdot \left({\sqrt[{n}]{2}}-1\right)}$

${\displaystyle C_{i}}$: Ausführungszeiten

${\displaystyle T_{i}}$: Periodenlängen

${\displaystyle n}$: Anzahl der Jobs

Mit zunehmender Anzahl von Jobs (${\displaystyle n\to \infty }$) nähert sich die Schranke dem Wert ln 2 ≈ 0,693. Wenn also die berechnete Auslastung ${\displaystyle u}$ unter 69,3 % liegt, sind alle Jobs sicher einplanbar. Wenn die tatsächliche Auslastung größer als ${\displaystyle n\cdot \left({\sqrt[{n}]{2}}-1\right)}$ 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:

${\displaystyle \prod _{i=1}^{n}({\frac {C_{i}}{T_{i}}}+1)\leq 2}$

• Harmonische Periodendauern. Wenn die Periodendauern Vielfache voneinander sind (harmonisch), sind die Jobs einplanbar, falls ${\displaystyle u\leq 1}$. 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.