Nebenläufige Programmierung in Ada

16.05.2013 10:10 Uhr Johannes Kanig, Jose Ruiz

Die Programmiersprache Ada verfügt über spezielle Konstrukte zur nebenläufigen Programmierung. Mit Tasks lassen sich sequenzielle Instruktionen formulieren, die zur Laufzeit nebeneinander, bei mehreren Prozessoren auch gleichzeitig ausgeführt werden.

Die meisten Rechner und Smartphones haben heute mehr als einen Prozessorkern. Es ist daher naheliegend, diese durch die Anwendungssoftware zu nutzen. Viele Probleme lassen sich nur schwer in eine Reihe sequentieller Schritte auflösen – auch hier ist es effizienter, sequenzielle Teilaufgaben sowie deren Kommunikation zu beschreiben und die Aufgabe der Zusammenführung dem Compiler zu überlassen.

Hier setzt die "nebenläufige Programmierung" an: Der Programmierer beschreibt nicht eine einzige sequenzielle Abfolge von Arbeitsschritten, sondern mehrere, sowie die Kommunikation, die zwischen diesen Prozessen erfolgen kann. Abhängig vom Problem bietet sich nebenläufige Programmierung auch an, wenn nur ein Prozessor zur Verfügung steht: nämlich immer dann, wenn mehrere unabhängige Aufgaben zu erledigen sind und eine künstlich festgelegte Reihenfolge der Aufgaben unerwünscht ist.

Die nebenläufige Programmierung gilt als deutlich komplexer als die sequenzielle. Neue Arten von Programmierfehlern wie Race Conditions und Deadlocks muss der Entwickler zusätzlich zu den aus der sequenziellen Programmierung bekannten berücksichtigen. Zwei weitere Begriffe sind in diesem Zusammenhang wichtig: Von verteilter Programmierung spricht man, wenn das Programm auf mehreren Maschinen laufen soll und die Kommunikation demzufolge über das Netzwerk erfolgt. Von Echtzeitprogrammierung hingegen, wenn neben dem funktionalen Aspekt – berechnet das Programm das richtige Ergebnis, stürzt es auch nicht ab? – auch Timing-Aspekte – wann gibt das Programm das Ergebnis aus, wie schnell reagiert es auf Eingaben? – eine Rolle spielen. Zu den wenigen Programmiersprachen, die direkt diese Paradigmen unterstützen, gehört neben Erlang und Go auch Ada.

Zentraler Aspekt – Tasks

Das grundlegende Konzept der nebenläufigen Programmierung in Ada ist der Task: Er bildet eine Reihe sequenzieller Instruktionen, zum Beispiel Berechnungen oder Funktionsaufrufe. Ein sequenzielles Ada-Programm hat genau einen Task, nämlich den, der das Main-Programm ausführt. Zusätzlich kann der Programmierer weitere, dann nebenläufig ausgeführte Tasks definieren. "Parallel" wäre hier nicht der passende Begriff, denn wirklich gleichzeitig werden diese Tasks nur ausgeführt, wenn auch mehrere Prozessoren zur Verfügung stehen. Ist das nicht der Fall, entscheidet die Laufzeitumgebung beziehungsweise das Betriebssystem, einen Task zu unterbrechen und einen anderen rechnen zu lassen.

In Ada ist jeder Task sowohl zu deklarieren als auch zu definieren. Ein Task lässt sich auf drei verschiedene Arten erstellen: zuerst als ein einfacher Task, der direkt ausgeführt wird, sobald der Programmfluss auf diese Task-Definition trifft. Die Deklaration besteht einfach aus dem Schlüsselwort task und dem Namen des Task. Die Definition ist ähnlich einer Funktionsdefinition, aber mit dem Schlüsselwort task body:

task Paternoster;
task body Paternoster is
 ... lokale Definitionen des Task: Typen, Variablen, Funktionen, ...
begin
 ... Der Code des Task
end Paternoster;

Es lässt sich auch ein Task-Typ definieren; das ist immer nützlich, wenn mehrere ähnliche Tasks laufen sollen. Der eigentliche Task wird dann als Variablendeklaration eingeführt:

task type Person;
task body Person is ... wie zuvor ... end Person;
   P : Person;

Die beiden ersten Varianten ermöglichen das Erstellen statischer Tasks: Es steht von vornherein fest, wie viele Tasks wann existieren. Die dritte Variante ermöglicht die dynamische Erzeugung von Tasks:

X := New Person;

Das folgende Codebeispiel zeigt zwei Tasks, die mit Variante 1 und 2 definiert wurden und die nebenläufig ausgeführt werden: einen Paternoster und einen Fahrgast.

shared:

   Low : constant Float := 0.0;
   High : constant Float := 100.0;
   Position : Float := Low;

left Side:

   task Paternoster;
   task body Paternoster is
      type State is (Up, Down);
      Direction : State := Up;
      Step : constant Float := 0.1;
   begin
      loop
         Position :=
            (if Direction = Up then Position + 0.1 else Position - 0.1);
         Direction :=
            (if Position >= High then Down
             elsif Position <= Low then Up
             else Direction);
      end loop;
   end Paternoster;

right Side:

   task type Person;
   task body Person is

      Start : constant Float := Ada.Numerics.Float_Random.Random (Float_Gen);

      procedure Jump is
      begin
         if abs (Float(Start) - Position) > 1.0 then
            raise Program_Error;
         end if;
      end Jump;

   begin
      loop
         if abs (Float(Start) - Position) < 0.1 then
            Jump;
         end if;
      end loop;
   end Person;

   P : Person;

An diesem Beispiel kann man gut sehen, warum die nebenläufige Programmierung angenehm sein kann: Der Code der Fahrstuhlsteuerung kümmert sich nur um den Fahrstuhl und kann andere Aspekte – zum Beispiel die Person – außer Acht lassen. In einer Endlosschleife, die typisch für die nebenläufige Programmierung ist, setzt der Code einfach die Fahrstuhlposition auf einen neuen Wert.

Es ist sinnvoll, den Fahrstuhl als einfachen Task zu definieren: Es gibt in dieser Simulation nur einen Fahrstuhl, und er läuft die ganze Zeit. Es ist ebenfalls sinnvoll, die Person als Task-Typ zu definieren, denn auch wenn es in dem ersten größeren Beispiel nicht der Fall ist, kann man sich natürlich mehrere Fahrgäste vorstellen.

Streng genommen gibt es im Beispiel sogar drei Tasks und nicht nur zwei: den Fahrstuhl, die Person und den "Main"-Task, der das Main-Programm aufruft und in jedem Ada-Programm existiert, auch wenn keine anderen Tasks definiert werden. Im Beispiel führt dieser Task aber nichts anderes aus, als die anderen Tasks zu starten und auf ihre Beendigung zu warten.

Noch ein Aspekt des Fahrgast-Tasks ist wichtig: Die Person möchte auf den Paternoster aufspringen, aber nur, wenn die Position nah genug (10 cm) vom Ausgangspunkt der Person ist. Während des Sprungs wird noch einmal der Abstand überprüft. In einem sequenziellen Programm wäre die Überprüfung völlig unnötig. Hier aber zeigt sie eines der fundamentalen Probleme der Nebenläufigkeit. Der Paternoster-Task kann, während der Person-Task noch entscheidet zu springen, die Position des Fahrstuhls entscheidend verändern und so den Sprung in den Fahrstuhl zu einem Sprung ins Leere umwandeln.

Der typische Programmierfehler im ersten Beispiel ist eine sogenannte Race Condition. Das Problem ist, dass die beiden Tasks die einfache Variable Position verwenden, um miteinander zu kommunizieren. Die Information fließt hier in eine Richtung: Der Paternoster-Task schreibt die jeweils aktuelle Position in die Variable, und der Person-Task liest sie aus, um sich zum Sprung zu entscheiden. Kurz nachdem diese Entscheidung getroffen wurde, kann der Paternoster-Task aber schon wieder die Position ändern. Die Entscheidung basiert somit auf einem veralteten Wert.

Ada bietet zwei Mechanismen der sicheren Kommunikation zwischen Tasks: eine Form der synchronen und eine der asynchronen Kommunikation.

Protected Objects

Geschützte Objekte und Typen

Das Problem des Paternoster-Beispiels war, dass sich die Position des Fahrstuhls ändern lässt, während ein Task sie kritisch benutzt. Die Lösung des Problems besteht darin, den Zugriff auf solche kritische Ressourcen zu beschränken. Dafür gibt es in verschiedenen Systemen unterschiedliche Lösungen wie Mutexes oder Semaphoren. Ada verwendet dafür das "geschützte Objekt" (protected object). Man kann es sich als ein Objekt im Sinne der Objektorientierung vorstellen, also als private Daten zusammen mit Prozeduren, die diese manipulieren. Ein Prozeduraufruf eines geschützten Objekts läuft prinzipiell wie ein normaler Aufruf ab, mit einem Unterschied: Zu jedem Zeitpunkt kann nur eine Prozedur des Objekts laufen. Läuft bei einem Aufruf schon eine Prozedur des gleichen Objekts in einem anderen Task, wird der aufrufende Task geblockt und wartet, bis der aktuelle Aufruf fertig ist.

Der Sinn geschützter Objekte ist die sichere Kommunikation zwischen Tasks. Diese nennt man asynchron, denn im Prinzip entscheidet jeder Task selbst, wann er auf das Objekt zugreifen möchte – auch wenn manchmal zu warten ist. Wie für Tasks ist zwischen Deklaration und Definition eines geschützten Objekts zu unterscheiden. Die Deklaration sieht wie folgt aus:

protected Elevator is
<Operationsdeklarationen>
private
    <Variablendeklarationen>
end Elevator;

Wie für Tasks kann man auch einen protected type definieren und dann Objekte dieses Typs deklarieren. Die Definition eines geschützten Objekts gibt im Wesentlichen die Implementierungen der Operationen an:

protected body Elevator is
 ...
end Elevator;

Ein geschütztes Objekt kann drei Arten von Operationen definieren. Diese können potenziell den aufrufenden Task so lange blockieren, bis sich die Operation wirklich ausführen lässt:

Funktionen dürfen private Daten lesen, aber nicht schreiben, und lassen sich gleichzeitig mit anderen Funktionen des gleichen Objekts ausführen;
Prozeduren dürfen private Daten lesen und schreiben, aber nicht gleichzeitig mit anderen Operationen ausgeführt werden.
Entries verhalten sich so wie Prozeduren. Zusätzlich haben sie eine Eingangsbedingung, die mit dem Schlüsselwort when angegeben wird. Ist diese zum Zeitpunkt des Aufrufs falsch, wird der Entry zusätzlich so lange geblockt, bis die Bedingung wahr wird.

Im folgenden längeren Codebeispiel wurde ein Fahrstuhl als geschütztes Objekt implementiert. Zu jedem Zeitpunkt kann nur eine Person fahren, den Fahrstuhl nutzen, um von Etage A nach Etage B zu fahren, und dann aussteigen. Diese Exklusivität wird hier erreicht, indem die Funktion Step_In ein Flag setzt, das weitere Aufrufe von Step_In so lange blockiert, bis Step_Out aufgerufen wird.

left side:

   task body Person is

      From : Floor := ...;
      To : Floor;
   begin
      Elevator.Step_In (From, Id);
      delay 2.0;
      Elevator.Step_Out (To, Id);
   end Person;
   
right side:
   protected Elevator is
      entry Step_In (F : Floor; Id : Integer);
      procedure Step_Out (F : Floor; Id : Integer);
   private
      Running : Boolean := False;
      From    : Floor;
   end Elevator;

   protected body Elevator is
      entry Step_In (F : Floor ; Id : Integer) when not Running is
      begin
         Running := True;
      end Step_In;

      procedure Step_Out (F : Floor ; Id : Integer) is
      begin
         Running := False;
      end Step_Out;
   end Elevator;

Bereitschaft für ein Rendezvous

Die andere wichtige Form der Kommunikation zwischen Ada-Tasks ist die synchrone Kommunikation mit einem Rendezvous. Tasks können so wie geschützte Objekte Entries bereitstellen, die außerhalb der Tasks so ähnlich wie Prozeduren aussehen und aufgerufen werden. Anders als bei einem Prozeduraufruf ist ein Rendezvous aber von beiden Seiten zu veranlassen: Ein Task muss mit dem Schlüsselwort accept die Bereitschaft eines Rendezvous für einen bestimmten Entry signalisieren, und ein anderer Task muss diesen Entry auch aufrufen. Tritt zunächst nur eines der beiden Ereignisse ein, wird dieser Task so lange blockiert, bis das andere Ereignis geschieht. Das erinnert an ein Client-Server-Modell: Der Client, der aufrufende Task, wird so lange blockiert, bis der Server, der anbietende Task, auch bereit ist, diese Art von Entry anzunehmen. Andersherum wird der Server so lange warten, bis auch tatsächlich ein Client den Service in Anspruch nimmt. Wenn dann endlich beide bereit sind, passiert das sogenannte Rendezvous.

Für den Client eines Rendezvous gibt es nur wenige Möglichkeiten, das Blockieren zu vermeiden: So kann man einen Timeout für die Wartezeit angeben oder testen, ob der Server für ein bestimmtes Rendezvous empfänglich ist. In den anderen Fällen blockiert der Client so lange, bis der Server bereit ist. Dagegen gibt es für den Server eine Reihe von Möglichkeiten, das Blockieren zu vermeiden. So kann der Server mit einem select-Statement auf mehrere Entries gleichzeitig warten; sind mehrere Clients für ein Rendezvous verfügbar, wird einer von ihnen ausgewählt. Das select-Statement erlaubt es auch, eine bestimmte Aktion auszuführen, wenn gerade kein Client da ist, auf bestimmte Entries nur zu warten, wenn eine Bedingung erfüllt ist, oder aufzuhören zu warten, wenn der Task nicht mehr gebraucht wird.

In folgendem Codebeispiel ist vor allem der Elevator-Task interessant: Er bietet, wie man es von einem Fahrstuhl erwarten kann, drei Entries an: den Ruf des Fahrstuhls mit Richtungsangabe, das Betreten an einer bestimmten Etage mit Angabe der Zieletage und das Verlassen des Fahrstuhls. Zum Betreten und Verlassen des Fahrstuhls ist es klar, dass beide Parteien – die Person und der Fahrstuhl – dazu bereit sein müssen, es ist daher natürlich, das als Rendezvous zu programmieren. Bei dem Ruf ist das weniger klar, aber auch hier wurde der Einfachheit halber ebenfalls ein Rendezvous verwendet.

left side
   task Elevator is
      ...
   begin
      loop
         select
            accept Call (Floor : Floor_Type; Dir : Dir_Type) do
               Calls (Floor) :=
                  (if Floor = Floor_Type'First then Up
                   elsif Floor = Floor_Type'Last then Down
                   else Merge (Calls (Floor), Dir));
            end Call;
         or when Door_Is_Open and then Num_People /= Capacity => 
               accept Step_In (Current_Floor) (To : Floor_Type) do
                  Num_People := Num_People + 1;
                  Calls (To) := Both;
               end Step_In;
         or when Door_Is_Open and then Num_People /= 0 =>
               accept Step_Out (Current_Floor) do
                  Num_People := Num_People - 1;
               end Step_Out;
         else
            Update_State;
            delay 0.1;
         end select;
      end loop;
   end Elevator;

right side:
   task Person is
   begin
      Elevator.Call (From, Dir);
      Elevator.Step_In (From) (To);
      Elevator.Step_Out (To);
   end Person;

Der Code des Fahrstuhl-Tasks wartet nun auf eines der drei möglichen Ereignisse: Ruf beziehungsweise Betreten und Verlassen auf der aktuellen Etage unter bestimmten Bedingungen – die Tür ist offen, es ist noch Platz im Fahrstuhl. Das wird mit einem select-Statement erreicht. Als Rendezvous-Aktion werden dabei jeweils die Anzahl der Fahrgäste aktualisiert und der Wunsch eines neuen Fahrgasts registriert. Nur wenn keines dieser Ereignisse auftritt, aktiviert der Fahrstuhl seine Zustandsmaschine, die zum Beispiel die Tür schließt oder die Etage wechselt.

Der Person-Task sieht im Wesentlichen so aus, wie man es erwartet (siehe das obige Beispiel): Die Person ruft den Fahrstuhl, steigt ein und wieder aus. Alle drei Aufrufe sind Rendezvous-Aufrufe und daher potenziell – wie im wirklichen Leben – mit Warten verbunden.

Die Beispiele zeigen, dass nebenläufige Programmierung Vorteile bietet, wenn mehrere gleichzeitig ablaufende Prozesse (in Ada: Tasks) zu beschreiben sind; in den Beispielen waren das der Fahrstuhl und die Fahrgäste. Potenziell würden die Programme auf Multiprozessorsystemen schneller laufen, auch wenn das nicht das Ziel der Beispiele war. Gleichzeitig ist aber in der nebenläufigen Programmierung auf die Kommunikation zwischen Tasks zu achten. Ada bietet hier Mechanismen der asynchronen Kommunikation (geschützte Objekte) und synchronen Kommunikation (mit Rendezvous) an.

Echzeitsysteme

Unterstützung für Echtzeitsysteme mit Ravenscar

Ada unterstützt auch die Entwicklung von Echtzeitsystemen. Hier ist es entscheidend zu wissen, wie lange eine bestimmte Berechnung braucht und wie lange ein Task auf den Zugriff auf ein geschütztes Objekt warten muss. Wenn bestimmte Programmfeatures sowie dynamische Tasks oder dynamische geschützte Objekte verwendet werden, lässt sich das nicht mehr ohne weiteres bestimmen. Auch das hier vorgestellte Rendezvous ist problematisch.

Daher wurde ein Profil für Ada entwickelt, das sogenannte Ravenscar-Profil, das solche problematischen Konstruktionen ausschließt. Ravenscar ist seit 2005 Teil des offiziellen Ada-Standards. Bleibt man in den von Ravenscar gesteckten Grenzen, was ein Ada-Compiler überprüfen kann, kann man sicher sein, dass solche Timing-Analysen möglich sind und das Scheduling der Tasks immer geht. Für Echtzeitsysteme ist das ein echtes Plus.

Ada und andere: Erlang und Go

Ada ist nicht die einzige Sprache, die eine eingebaute Unterstützung für die parallele Programmierung anbietet. Die Programmiersprache Erlang gibt es seit Ende der 80er-Jahre, sie bietet wie Ada die Möglichkeit, nebenläufige Prozesse zu beschreiben. Die Kommunikation läuft über den Message-Passing-Mechanismus. Er ist dem hier beschriebenen Rendezvous ähnlich, ist aber asynchron: Die Aufrufe oder "Nachrichten" werden so lange gepuffert, bis sie der empfangene Prozess gelesen hat. Das scheint mehr ein kosmetischer Unterschied und ließ sich in Ada leicht mit einem geschützten Objekt erreichen. Das Alleinstellungsmerkmal von Erlang ist die gute Unterstützung verteilter Systeme sowie das "hot swapping", also das Update der Software zur Laufzeit. Ada unterstützt zwar auch verteilte Systeme, aber unabhängig vom hier vorgestellten Tasking-System. Zum anderen gibt es in Erlang keine geschützten Objekte: Jeder Erlang-Prozess hat seine eigenen Variablen, und die Kommunikation kann nur über Message Passing erfolgen. Das führt zu einem funktionalen Programmierstil, der zwar sauber, aber zum Teil auch umständlich sein kann. Ada folgt hier dem gängigen imperativen Stil.

Viel jünger als Ada und Erlang ist das 2009 von Google vorgestellte Go. Die sogenannten Go-Routinen sind deutlich flexibler als Ada-Tasks oder Erlang-Prozesse: Jeder beliebige Ausdruck, zum Beispiel ein Funktionsaufruf, lässt sich zu jedem beliebigen Zeitpunkt parallel starten. Die Kommunikation zwischen Go-Routinen erfolgt mit (optional gepufferten) Kanälen. Go-Kanäle lassen sich leicht in Ada mit einem geschützten Objekt imitieren, und auch die Go-Routinen bringen Go hauptsächlich einen syntaktischen Vorteil – während in Go das Schlüsselwort go ausreicht, ist in Ada ein eigener Task zu definieren. Der Umgang mit Go wird noch durch den verfügbaren Garbage Collector erleichtert.

Auch bezüglich Erlang und Go gilt, dass jede Programmiersprache ihre Nische hat: Go wurde für
– nicht unbedingt kritische – Server-Applikationen entwickelt. Erlang zielt auf verteilte Systeme mit Update-Möglichkeit während des Betriebs. Der Markt von Ada sind in der Regel Embedded-Systeme, die sicherheitskritisch sind und oft Echtzeitanforderungen haben. Hier hat Ada durch die klare Syntax, viele Laufzeitüberprüfungen, die Abwesenheit eines Garbage Collector und schließlich auch durch das Ravenscar-Profil die Nase vorn.

Dr. Johannes Kanig und Dr. Jose Ruiz
sind Senior Software Engineers bei AdaCore. (ane [1])

URL dieses Artikels:
https://www.heise.de/-1862433

Links in diesem Artikel:
[1] mailto:ane@heise.de