Deadline Monotonic Scheduling
- Deadline Monotonic Scheduling
-
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.
Annahmen
Grundsätzliche Einschränkungen
Die theoretische Betrachtung von Echtzeit-Schedulingverfahren erfordert einige grundsätzliche Einschränkungen, um die Komplexität der Analyse handhaben zu können.
- Prozesse können zu jedem Zeitpunkt unterbrochen werden
- der Overhead für Prozesswechsel wird mit 0 Zeiteinheiten angenommen
- notwendige Ressourcen (ausgenommen CPU-Zeit) sind unbegrenzt vorhanden
- alle Prozesse sind unabhängig (intuitiv: Die Prozesse können in beliebiger Reihenfolge ausgeführt werden)
- die Last aller Prozesse zusammen muss ≤1 sein
Annahmen für periodische Prozesse
- alle Prozesse haben Deadlines kleiner oder gleich ihrer Perioden
Annahmen für sporadische Prozesse
- alle Prozesse haben Deadlines kleiner oder gleich ihrer Minimal Inter-Arrival-Zeiten (Minimum zwischen zwei Ankunftszeiten desselben Prozesses)
Verfahren
Analog zu Rate Monotonic Scheduling (RMS) wird bei DMS stets der Prozess der höchsten Priorität ausgeführt. Die Prioritäten werden dabei reziprok zur relativen Periodenlänge vergeben. Das Verfahren ist präemptiv - beim Eintreffen eines neuen Prozesses mit höherer Priorität wird der aktuelle Prozess zugunsten des neuen unterbrochen. Um aperiodische Jobs handhaben zu können, wird für diese ein fiktiver periodischer Prozess mit der Minimal Inter-Arrival-Zeit als Periode angenommen.
Mächtigkeit
DMS ist unter den Schedulingverfahren mit festen Prioritäten das mächtigste Verfahren. Es handelt sich um eine Verallgemeinerung von Rate Monotonic Scheduling, wobei mit RMS nur ein Scheduling einer Teilmenge von mit DMS ausführbaren Prozessmengen möglich ist. Im Spezialfall, dass für alle Prozesse relative Deadline und Periodenlängen gleich sind, gilt DMS = RMS.
Literatur
Quellen
Wikimedia Foundation.
Schlagen Sie auch in anderen Wörterbüchern nach:
Deadline-monotonic scheduling — Deadline monotonic priority assignment is a priority assignment policy used with fixed priority pre emptive scheduling. With deadline monotonic priority assignment, tasks are assigned priorities according to their deadlines; the task with the… … Wikipedia
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 — (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… … Deutsch Wikipedia
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 — 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
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
Earliest Deadline First Scheduling — Pour les articles homonymes, voir EDF (homonymie). Algorithmes d ordonnancement EDF • Rate monotonic … Wikipédia en Français
Earliest deadline first scheduling — Pour les articles homonymes, voir EDF (homonymie). Earliest deadline first scheduling ( échéance proche = préparation en premier ) est un algorithme d ordonnancement préemptif, à priorité dynamique, utilisé dans les systèmes temps réel. Il… … 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
