Deadline Monotonic Scheduling

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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.

[Bearbeiten] Annahmen

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

Für periodische Prozesse:

alle Prozesse haben Deadlines kleiner oder gleich ihrer Perioden

bzw. für sporadische Prozesse:

alle Prozesse haben Deadlines kleiner oder gleich ihrer Minimal Inter-Arrival-Zeiten (Minimum zwischen zwei Ankunftszeiten desselben Prozesses)
(Liste noch nicht vollständig korrekt, bitte ergänzen)

[Bearbeiten] Verfahren

Analog zu Rate Monotonic Scheduling 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 der 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.

[Bearbeiten] 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 (RMS), wobei mit RMS nur ein Scheduling einer Teilmenge von mit DMS ausführbaren Prozessmengen möglich ist. Im Spezialfall, daß für alle Prozesse relative Deadline und Periodenlänge gleich sind, gilt DMS = RMS.