Rate Monotonic Scheduling

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, was auch als Serverprinzip bezeichnet wird.

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\limits_{i=1}^{n}\frac{C_i}{T_i} \le n \cdot (\sqrt[n]{2} -1)$

C_i ... Ausführungszeiten

T_i ... Periodenlängen

n ... Anzahl der Jobs

Mit zunehmender Anzahl von Jobs ($n \to \infty$) nähert sich die Schranke dem Wert $\ln 2 \approx 69{,}3\%$.

Wenn also die berechnete Auslastung u unter 69,3% liegt, sind die Jobs sicher einplanbar. Wenn die tatsächliche Auslastung größer als $n \cdot (\sqrt[n]{2} -1)$ 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 $u \le 1$. Unter dieser Bedingung ist RMS also optimal.

Siehe auch

• Deadline Monotonic Scheduling

Literatur

• Liu, Jane W. S.: Real-time systems. Prentice Hall, Upper Saddle River, NJ, 2000