Rate Monotonic Scheduling

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)
Ci ... Ausführungszeiten
Ti ... 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

Literatur

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

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Rate-monotonic Scheduling — Algorithmes d ordonnancement EDF • Rate monotonic • Round robin LIFO • FIFO Le rate monotonic scheduling est un algorithme d ordonnancement …   Wikipédia en Français

  • Rate-monotonic scheduling — In computer science, rate monotonic scheduling [citation|first1=C. L.|last1=Liu|authorlink1=Chung Laung Liu|first2=J.|last2=Layland|title=Scheduling algorithms for multiprogramming in a hard real time environment|journal=Journal of the ACM|volume …   Wikipedia

  • Rate-monotonic scheduling — L ordonnancement à taux monotone (en anglais, rate monotonic scheduling) est un algorithme d ordonnancement temps réel en ligne à priorité constante. Il attribue la priorité la plus forte à la tâche qui possède la plus petite période. RMS est… …   Wikipédia en Français

  • Deadline Monotonic Scheduling — (DMS) bezeichnet in der Informatik ein Schedulingverfahren für harte Echtzeitsysteme, das zur Verwaltung von Prozessen fester Prioritäten dient. Unter den Schedulingverfahren mit festen Prioritäten ist es für beliebige Deadlines optimal.… …   Deutsch Wikipedia

  • Rate Monotonique — Rate monotonic scheduling Algorithmes d ordonnancement EDF • Rate monotonic • Round robin LIFO • FIFO Le rate monotonic scheduling est un algorithme d ordonnancement …   Wikipédia en Français

  • Scheduling (Informatik) — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Scheduling algorithm — In computer science, a scheduling algorithm is the method by which threads, processes or data flows are given access to system resources (e.g. processor time, communications bandwidth). This is usually done to load balance a system effectively or …   Wikipedia

  • Earliest deadline first scheduling — Earliest deadline first (EDF) scheduling is a dynamic scheduling algorithm used in real time operating systems. It places processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) the queue will be …   Wikipedia

  • Least slack time scheduling — Least Slack Time (LST) scheduling is a scheduling algorithm. It assigns priority based on the slack time of a process. Slack time is the amount of time left after a job if the job was started now. This algorithm is also known as Least Laxity… …   Wikipedia

  • Earliest Deadline First Scheduling — Pour les articles homonymes, voir EDF (homonymie). Algorithmes d ordonnancement EDF • Rate monotonic …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”