11. Anlage
 
zurück
11.4.1 Prioritäten paralleler Prozesse


Mit den in der Anlage "Echtzeitsysteme" definierten Sprachelementen können parallelen Prozessen Prioritäten zugewiesen werden. Eine Priorität wird durch einen ganzzahligen Wert dargestellt, der die Dringlichkeit der Ausführung und Beendigung eines parallelen Prozesses anzeigt. Die Priorität reflektiert somit die zeitliche Charakteristik eines parallelen Prozesses. Wenn mehrere parallele Prozesse im Zustand "bereit" sind und in den Zustand "aktiviert" übergehen können, so kann die aktuelle Ausführungsreihenfolge der parallelen Prozesse durch Zuweisung einer eindeutigen Priorität zu jedem parallelen Prozeß bestimmt werden.
Ein paralleler Prozeß ist im Zustand "bereit", wenn er noch nicht im Zustand "beendet" ist, nicht im Zustand "blockiert" ist, d. h. nicht auf die Ausführung einer geschützten Operation, eines Rendezvous oder einer Verzögerungsanweisung wartet und genügend Betriebsmittel (Prozessor, Speicher) zur Ausführung zur Verfügung stehen.

Bewerben sich zwei oder mehrere parallele Prozesse um die Ausführung auf einem Prozessor, so wird derjenige bereite parallele Prozeß mit der höchsten Priorität zuerst ausgeführt.
Prioritäten können auch zur Festlegung der Warteschlangen von Eingangsaufrufen und zur Bestimmung von Alternativen einer Auswahlanweisung (select_statement <BNF>) benutzt werden.
Es wird auf folgende Themen im Zusammenhang mit Prioritäten eingegangen:

Basisprioritäten

Jedem parallelen Prozeß und geschützten Objekt (protected_type_declaration <BNF>) kann eine Priorität zugewiesen werden. Dazu ist im vordefinierten Paket "System" der "integer"-Untertyp "any_priority" definiert. Die Untertypen "priority" und "interrupt_priority" zusammen füllen den Wertebereich von "any_priority" ohne Überlappungen aus. Der Wertebereich von "priority" muß mindestens 30 sein, und es gibt immer mindestens einen Wert für "interrupt_priority".

Untersuchungen bei der Koordinierung von parallelen Prozessen mit Hilfe des Rate-Monotonic-Algorithmus zeigen, daß zur Koordinierung von 32 und mehr parallelen Prozessen annähernd 32 Stufen von Prioritäten benötigt werden. Gewisse Hardwarearchitekturen erlauben lediglich 32 Prioritätsstufen. Um effiziente Bit-Vektoroperationen auf 32-Bit-Maschinen zu erlauben, wo ein Bit reserviert werden muß, wurde die Anzahl der Prioritätstufen auf 31 reduziert, wobei eine Prioritätsstufe für "interrupt_priority" reserviert ist. Daher kommt auch der Wertebereich von "priority" von 30 zustande.
Die initiale Basispriorität eines parallelen Prozesses kann durch das Pragma "Priority" spezifiziert werden. Für geschützte Objekte, die als Interrupt-Handler verwendet werden, kann mit Hilfe des Pragmas "Interrupt_Priority" die Priorität gesetzt werden.

Syntax:

pragma Priority(expression);
pragma Interrupt_Priority[(expression)];

Sowohl für das Pragma "Priority" als auch für das Pragma "Interrupt_Priority" ist der Typ des Parameters "integer".

Falls das Pragma "Priority" fehlt, ist die Basispriorität eines parallelen Prozesses identisch mit der Basispriorität des parallelen Prozesses, der sie kreiert. Fehlt auch im Haupt(-Unter)programm das Pragma "Priority", so ist die Basispriorität des parallelen Prozesses gleich der Priorität des umgebenden parallelen Prozesses "System.Default_Priority".


task type T (P: Any_priority) is
pragma Priority (P);
...

Die Basispriorität wird in diesem Beispiel durch eine Diskriminante gesetzt, aber sie kann natürlich auch eine Konstante sein.
Das Paket "Ada.Dynamic_Priorities" stellt Unterprogramme zur Verfügung, mit denen man die Basispriorität eines parallelen Prozesses verändern bzw. die Basispriorität eines parallelen Prozesses abfragen kann. Dynamische Prioritäten werden z. B. dann benötigt, wenn ein dynamischer Scheduling-Algorithmus implementiert werden soll wie z. B. das Earliest Deadline Scheduling.

Fred: T (10); --- initiale Basispriorität von 10
...
Set_Priority (Priority => 15, Task_Id => Fred´Identity);

Sowohl bei der Prozedur "Set_Priority" als auch bei der Funktion "Get_Priority" ist der
Eingangsparameter auf die Identität des aktuellen laufenden parallelen Prozesses voreingestellt. Daher würde ein Ausdruck der Form:

Get_Priority > Get_Priority (Irgendein_Paralleler_Prozeß)

dann den Wert "true" ergeben, wenn der aktuelle parallele Prozeß eine höhere Basispriorität als
"Irgendein_Paralleler_Prozeß" hat.


Priority Ceiling Protocol

Ein generelles Problem bei der Zuteilung von parallelen Prozessen auf einen Prozessor mit Hilfe von Prioritäten ist das Risiko einer Prioritäteninversion (priority inversion). Eine Prioritäteninversion tritt dann auf, wenn ein paralleler Prozeß mit einer hohen Priorität durch einen parallelen Prozeß mit einer niedrigeren Priorität, die ein gemeinsames Betriebsmittel benutzen, blockiert wird.

Zur Erklärung des Begriffs Prioritäteninversion nehmen wir an, daß drei parallele Prozesse H, M und L mit den Prioritäten hoch, mittel und niedrig um einen Prozessor konkurrieren. Die parallelen Prozesse H und L teilen sich ein Betriebsmittel P, das in ein geschütztes Objekt eingekapselt ist.
Nun ist folgende Ausführungsreihenfolge möglich:
  • L wird dem Prozessor zugeteilt und benutzt das Betriebsmittel P.
  • M wird bereit und unterbricht L, während L das Betriebsmittel P benutzt.
  • H wird bereit und unterbricht M.
  • H versucht, das Betriebsmittel P zu benutzten, bekommt aber keinen Zugriff, da L exklusiven Zugriff darauf hat. Deshalb wird H suspendiert.
  • Der nächstniedrigere parallele Prozeß M fährt mit der Ausführung fort.
Das Ergebnis ist, daß H durch L blockiert wird, obwohl H höhere Priorität hat.
Zur Vermeidung der Prioritäteninversion muß eine Form der Prioritätenvererbung (priority inheritance)
benutzt werden. Das Konzept der Prioritätsvererbung existierte schon in Ada 83 beim Rendezvous zwischen parallelen Prozessen. In Ada 95 wird es erweitert, um die Anzahl der Prioritätsinversionen bei geschützten Operationen zu beschränken.

Zur Erklärung der Prioritätsvererbung wird die Unterscheidung zwischen Basispriorität und aktiver Priorität eines parallelen Prozesses eingeführt. Bei der Interaktion eines Prozesses mit einem
Prozeß, der eine höhere Priorität besitzt, erbt der Prozeß die höhere Priorität und behält diese
höhere Priorität (aktive Priorität) während der Ausführung.

Prioritätenvererbung tritt in folgenden Fällen auf:
  • bei der Aktivierung eines Prozesses, wobei der zu aktivierende Prozeß die Priorität des aktivierenden Prozesses erbt,
  • während eines Rendezvous, wobei der den Eingangsaufruf (entry_call_statement <BNF>) akzeptierende Prozeß die Priorität des rufenden Prozesses erbt,
  • während der Ausführung einer geschützten Aktion auf ein geschütztes Objekt (protected_type_declaration <BNF>), wobei der parallele Prozeß die Priorität des geschützten Objektes erbt.
Es existieren verschiedene Modelle der Prioritätenvererbung. Die Anlage "Echtzeitsysteme" stellt die Prioritätenvererbung nach Ceiling-Werten (priority ceiling inheritance) zur Verfügung. Zur Realisierung des Priority Ceiling Protocols gibt es das Pragma "Locking_Policy" (Ceiling_Locking).

Zuerst wird eine Ceiling-Priorität für jedes geschützte Objekt (protected object) definiert. Diese Priorität repräsentiert die maximale Priorität desjenigen parallelen Prozesses, der dieses geschützte Objekt aufruft. Jedesmal, wenn ein paralleler Prozeß innerhalb des geschützen Objektes aktiv ist, tut er dies mit der Ceiling-Priorität des geschützten Objektes.

Sowohl den geschützten Objekten als auch allen anderen parallelen Prozessen muß eine Ceiling-Priorität zugewiesen werden. Hierzu wird das Pragma "Priority" verwendet. Wird die Option "ceiling_locking" vereinbart und fehlt das Pragma "Priority" in einem geschützten Objekt, so wird der Wert "priority’last" als Ceiling-Priorität für das geschützte Objekt angenommen. Fehlt das Pragma "Locking_Policy", so hängt der Locking-Mechanismus und somit die Bedeutung des Pragmas "Priority" eines geschützten Objekts vom Ada-Übersetzer ab. Die Option "ceiling_locking" für das Pragma "Locking_Policy" muß von jedem Ada-Übersetzer, der der Anlage "Echtzeitsysteme" konform ist, unterstützt werden.

Das Priority Ceiling Protocol von geschützten Objekten hat folgende Vorteile:
  • Die Anzahl der Prioritäteninversionen kann nach oben hin begrenzt werden.
  • Es erlaubt eine effiziente Implementierung des Sperrens von geschützten Objekten.
  • Es verhindert eine Verklemmung (deadlock) in einer Einprozessorarchitektur.
Prozessorzuteilungsstrategien

Der Prozeß, bei dem bestimmt wird, welcher bereite parallele Prozeß einem Prozessor zugeteilt wird, wird als Prozessorzuteilung (Task Dispatching) bezeichnet.

Im Gegensatz hierzu umfaßt der mehr allgemeinere Begriff "Prozeßkoordination" (Task Scheduling) die Bestimmung der anderen Faktoren wie z. B. welche parallelen Prozesse im logischen Sinne zur Ausführung wählbar sind, welche parallelen Prozesse auf welchem Prozessor ausführbar sind und welche aktive Priorität jeder parallele Prozeß hat.

Die Anlage "Echtzeitsysteme" fordert, daß bereite parallele Prozesse mit hoher aktiver Priorität den Vorzug bekommen vor parallelen Prozessen mit niedrigerer aktiver Priorität. Die Prozessor- zuteilung von parallelen Prozessen mit gleicher aktiver Priorität hängt von der Prozessor- zuteilungsstrategie ab und wird durch ein Konfigurationspragma spezifiziert.

Mit Hilfe des Pragmas "Task_Dispatching_Policy" kann eine Zuteilungsstrategie "fifo_within_priority" spezifiziert werden.

Syntax:

pragma Task_Dispatching_Policy(policy_identifier );

Dieses Konfigurationspragma spezifiziert eine Zuteilungsstrategie, bei der ein paralleler Prozeß unterbrochen wird, falls der parallele Prozeß sich selbst blockiert oder ein höherpriorisierter paralleler Prozeß zur Ausführung bereit ist.

Parallele Prozesse mit gleicher Priorität werden in FIFO-Ordnung (First In First Out) in eine Warteschlange eingereiht. Sobald parallele Prozesse bereit sind, werden sie am Ende der Warteschlange für die betreffende Priorität eingereiht. Wird ein paralleler Prozeß jedoch unterbrochen, so wird er am Anfang der Warteschlange für die betreffende Priorität eingereiht.

Ein paralleler Prozeß, der eine Verzögerungsanweisung ausführt, geht in den Zustand blockiert über, um danach wieder zur Ausführung zu gelangen. Daher würde eine Verzögerungsanweisung in einem parallelen Prozeß dazu führen, daß der parallele Prozeß unterbrochen und ein anderer paralleler Prozeß mit gleicher Priorität ausgeführt wird. Wenn kein anderer paralleler Prozeß mit gleicher Priorität bereit ist, wird der parallele Prozeß nach Beendigung seiner Verzögerungsanweisung weiter ausgeführt.

Es können außer "fifo_within_priority" weitere implementierungsabhängige Zuteilungsstrategien definiert sein. Ist kein Pragma "Task_Dispatching_Policy" angegeben, so ist die Zuteilungsstrategie implementierungsabhängig.

Wird die Option "fifo_within_priority"-Option gewählt, so muß auch die "ceiling_locking"-Option spezifiziert werden. Beide Optionen repräsentieren ein durchgängiges Konzept zur Implementierung von Echtzeitsystemen.

Strategien für Eingangsaufrufe

Die Strategie bei der Auswahl des nächsten Eingangsaufrufs aus der Warteschlange eines parallelen Prozesses oder eines geschützten Objekts kann durch das Pragma Queuing_Policy spezifiziert werden.

Syntax:

pragma Queuing_Policy(policy_identifier);

Es existieren zwei vordefinierte Strategien für dieses Pragma: fifo_queuing und priority_queuing.
Eine Ada-Implementierung kann weitere Strategien für dieses Pragma definieren.

In Ada 83 war als Strategie bei der Auswahl des nächsten Eingangsaufrufs stets fifo_queuing vorgesehen, was zu einer Prioritäteninversion führen konnte. Um die Abwärtskompatibilität mit Ada 83 zu erreichen, ist die Default-Option des Pragmas Queuing_Policy in Ada 95 auch fifo_queuing.
Bei der Wahl der fifo_queuing-Option werden die Eingangsaufrufe aus der Warteschlange in der Reihenfolge ihres Ankommens ausgewählt, unabhängig von der Priorität des aufrufenden parallelen Prozesses.

Bei der Wahl der priority_queuing-Option wird immer derjenige Eingangsaufruf aus der Warteschlange ausgewählt, dessen rufender paralleler Prozeß die höchste Priorität hat.

Existieren mehrere parallele Prozesse mit der gleichen Priorität, so wird derjenige parallele Prozeß zuerst bedient, dessen Eingangsaufruf zuerst in die Warteschlange der Eingangsaufrufe eingereiht
wurde.

Existiert ein geschütztes Objekt mit mehreren offenen Eingängen mit nicht leeren Warteschlangen oder besitzt eine selektive Eingangsanweisung (select_alternative <BNF>) verschiedene offene Eingangsalternativen mit nichtleeren Warteschlangen, so wird die Warteschlange mit der höchsten Priorität ausgewählt.

Werden mehrere geschützte Eingänge mit der gleichen Priorität aufgerufen, so wird derjenige Eingang zuerst bedient, der in der geschützten Deklarationsreihenfolge zuerst auftritt. Im Fall von mehreren Annahmealternativen mit einem Aufruf dieser Priorität wird die Alternative, die zuerst in der selektiven Annahmeanweisung auftritt, bedient.

Die aktive Priorität des rufenden parallelen Prozesses wird dazu verwendet, um den parallelen Prozeß an der korrekten Position in der prioritätengeordneten Warteschlange für Eingangsaufrufe zu plazieren.

Ändert sich die aktive Priorität, während der rufende parallele Prozeß suspendiert wird, dann hat dies keinen Einfluß auf die Warteschlange. Wird jedoch die Basispriorität durch das Pragma Set_Priority verändert, dann wird der parallele Prozeß logisch aus der Warteschlange der Eingangsaufrufe entfernt und an einer neuen Stelle innerhalb der Warteschlange entsprechend der neuen Priorität plaziert (aber hinter parallele Prozesse mit der gleichen Priorität).


 
zurück
 Index   Ada Tour - Dokumentation  
© 2003 Förderverein Ada Deutschland e.V.