Betriebssystemtheorie/ Scheduling/ Jobs


Einleitung

Bearbeiten

Jobs sind Aufgaben, die das System erledigen muss. Sie lassen sich grob in zwei Gruppen aufteilen.

Periodischer Job
Diese Jobs befinden sich ständig im System und müssen zu festen Zeiten ausgeführt werden. Hierbei kann es sich zum Beispiel um einen Thread handeln, der in regelmäßigen Abständen einen externen Sensor überprüft.
Sporadischer Job
Ein sporadischer (oder aperiodischer) Job taucht zu einem Zeitpunkt auf und kann nach der Ausführung entfernt werden. Ein Thread, der zufällig auftretende Interrupts verarbeitet, fällt in diese Kategorie.

Periodische Jobs

Bearbeiten

Periodische Jobs werden in regelmäßigen Zeitabständen immer wieder ausgeführt. Sie lassen sich durch die folgenden Eigenschaften beschreiben.

Phase
Nicht all Jobs starten direkt nach dem Start des Systems. Die Phase gibt den ersten Zeitpunkt an, an dem der Job auftritt.
Periode
Die Periode gibt die Zeit an, die zwischen zwei Auftritten des Jobs vergeht.
Ausführungsdauer
Die Dauer ist die Zeit, die der Job zum Erledigen seiner Aufgabe benötigt. Ist die Dauer größer als die Periode, ist der Job nicht ausführbar.
Deadline
Die Deadline bezeichnet den Zeitpunkt, an dem der Job spätestens beendet sein muss. Der späteste Zeitpunkt der Deadline eines periodischen Jobs ist das Ende der aktuellen Periode, da er sonst mit seinem Nachfolger in der Folgeperiode kollidieren würde.

In einem System, das nur periodische Jobs enthält, benötigt man keinen Scheduler, beziehungsweise der Algorithmus des Schedulers ist so einfach, dass komplizierte theoretische Betrachtungen entfallen. Alle Jobs mit ihren Parametern sind bekannt. Ist es also möglich, im voraus einen gültigen Plan für den Scheduler zu erstellen, ist auch die Ausführung möglich. Der Scheduler enthält eine Tabelle, die den zuvor ausgearbeiteten Plan darstellt. Die Aktivierung erfolgt zu festen Zeitpunkten. Wird er aktiviert, muss er lediglich die Tabelle nach dem aktuellen Zeitpunkt durchsuchen und den aufgeführten Job ausführen. Das Scheduling wiederholt sich nach einer festen Zeitspanne. Man nennt dies Hyperperiode.

Hyperperiode
Eine Hyperperiode beschreibt die Zeit, nach der sich der Plan für das Scheduling wiederholt. Sie ist das kleinste gemeinsame Vielfache aller Perioden der im System vertretenen Jobs.

Ein System, das periodische Jobs enthält, nennt man zeit-gesteuertes System. Aufgrund der Einschränkung, dass alle Jobs im voraus bekannt sein müssen, sind Systeme mit periodischen Jobs vor allem in Bereichen sinnvoll, die regelmäßig die gleichen Aufgaben erfüllen müssen und deren Verhalten nicht allzu komplex ist. Die Hardware-nahe Steuerung von Maschinen, Motoren oder Triebwerken sind typische Einsatzgebiete.

Sporadische Jobs

Bearbeiten

Im Gegensatz zu periodischen Jobs treten sporadische Jobs an beliebigen Zeitpunkten auf. Sie sind durch folgende Eigenschaften gekennzeichnet.

Release-Zeit
Die Release-Zeit gibt den frühesten Zeitpunkt an, an dem ein Job ausgeführt werden kann.
Ausführungsdauer
Wie bei den periodischen Jobs gibt die Ausführungsdauer die Zeit vom Ausführen bis zum Beenden des Jobs an.
Deadline
Entsprechend der Definition für periodische Jobs, bezeichnet die Deadline den Zeitpunkt, an dem ein Job spätestens beendet sein muss.

Das Scheduling von sporadischen Jobs wurde intensiv erforscht und es wurden viele Algorithmen entwickelt. Diese sind vor allem abhängig von der verwendeten Ressource und unterscheiden sich in verschiedenen Details. Die bekanntesten sind im Kapitel Algorithmen beschrieben. Da das Auftreten sporadischer Jobs im voraus nicht bekannt ist, müssen alle Algorithmen zur Laufzeit des Systems ausgeführt werden.

Ein System mit sporadischen Jobs, nennt man ereignis-gesteuertes System. Scheduler für sporadische Jobs finden sich vor allem in komplexen Systemen, die zum Teil auch auf Benutzereingaben reagieren müssen. Dazu zählen beispielsweise PC-Betriebssysteme, Flugzeugsteuerungen und Radarsysteme.

Äquivalenz

Bearbeiten

Beide, zeit- und ereignis-gesteuerte Systeme, sind äquivalent. Man kann also ein System durch das jeweils andere ersetzen.

Um ein zeit-gesteuertes System auf einem ereignis-gesteuerten System zu implementieren, benötigt man einen periodischen Timer, dessen Auftreten die Frequenz der Zeit-steuerung modelliert. Umgekehrt kann man ein ereignis-gesteuertes System auf einem zeit-gesteuerten System bauen, indem man zu Beginn jeder Periode die Ereignisse im System durch einen periodischen Job abfragt und die zugehörigen sporadischen Jobs freischaltet.