Drucken

Informatik für das Lehramt (B.Sc.)

Diese Seiten können nicht richtig dargestellt werden, da Sie Ihren Internet Explorer mit aktivierter Kompatibiltätsansicht verwenden. Wir empfehlen 'fu-berlin.de' aus der Liste der Websites mit aktivierter Kompatibilitätsansicht zu entfernen:

  1. Blenden Sie bitte in Ihrem Internet Explorer die Menüleiste ein, indem Sie entweder 'Alt' drücken oder in der Adressleiste mit der rechten Maustaste klicken und dann 'Menüleiste' auswählen.
  2. Klicken Sie auf 'Extras' und wählen das Menü 'Einstellungen der Kompatibilitätsansicht' aus.
  3. Wählen Sie unter 'Zur Kompatibilitätsansicht hinzugefügte Websites' 'fu-berlin.de' aus.
  4. Klicken Sie auf 'Entfernen'.

Nichtsequentielle Programmierung (4. Semester)

In einem klassischen Einführungsbeispiel der nichtsequentiellen Programmierung sind Alice und Bob zwei Nachbarn, welche sich einen gemeinsamen Garten teilen. Alice hat einen Hund und Bob eine Katze, die sich nicht zur gleichen Zeit in diesem Garten aufhalten dürfen. Um zu verhindern, dass das passiert, haben sowohl Alice als auch Bob einen Fahnenmast an ihren Häusern installiert, so dass sie dem Nachbarn signalisieren können, ob sie gerade das jeweilige Haustier in den Garten schicken möchten.

Alice und Bob führen folgende Aktionen durch: Sie schauen zur Flagge des anderen, um zu sehen, ob diese gehisst ist. Falls ja, warten sie bis die Flagge wieder verschwunden ist. Falls nein, hissen sie ihre eigene Flagge. Im Anschluss schicken sie das eigene Tier los.

Da diese Aktionen von Alice und Bob je nach Situation und Tagesform zu unterschiedlichen Zeitpunkten ausgeführt werden können, treten trotz des vermeintlich ausgeklügelten Systems der Flaggenmaste zwei schwerwiegende Probleme auf.

Wählen Sie in den zwei nachfolgenden Texten die richtige Lösung für die Lücken aus.

Anschließend können Sie nach einem Klick auf das Feld „Ergebnis“ herausfinden, ob Ihre Version des Lückentextes richtig war.

1. Problem

In dieser Situation kommt es zum Unglück: Hund und Katze werden trotz gesetzter Flaggen gleichzeitig in den Garten gelassen. Wie konnt das passieren?

Alice schaut zur anderen Flagge. Bob Bob hisst seine Flagge. Alice Alice Bob lässt die Katze in den Garten.

Im ersten Beispiel schauen zunächst beide Nachbarn zur Flagge des anderen und stellen fest, dass diese nicht gehisst ist. Wie abgesprochen, hissen sie daraufhin beide die eigene Flagge. Da sie allerdings nicht noch einmal nachschauen, haben sie nicht mitbekommen, dass der jeweils andere Nachbar in der Zwischenzeit auch die Flagge gehisst hat. Daher lassen sie beide ihre Tiere in den Garten und der schlimmste Fall tritt ein:

  1. Alice schaut zur anderen Flagge.
  2. Bob schaut zur anderen Flagge.
  3. Bob hisst seine Flagge.
  4. Alice hisst ihre Flagge.
  5. Alice lässt den Hund in den Garten.
  6. Bob lässt die Katze in den Garten.

In der nichtsequentiellen Programmierung nennt man den Garten den kritischen Abschnitt (Critical Section) eines Programms. Die Garantie niemals mit zwei Prozessen diesen Abschnitt zu betreten, heißt Gegenseitiger Ausschluss (Mutual Exclusion). Es handelt sich um die Grundlage, um mit mehreren Prozessen an den selben Resourcen zu arbeiten.

Klicken Sie auf Weiter, um zur nächsten Teilaufgabe zu gelangen.

2. Problem

Beim nächsten Versuch passen Alice und Bob besser auf. Sie verwerfen ihre vorige Abmachung und treffen eine neue Verabredung, nämlich immer erst nach der anderen Flagge zu schauen nachdem die eigene Flagge gehisst wurde. Wenn die jeweils andere Flagge gehisst ist, gewähren sie dem anderen den Vortritt und warten bis die Flagge heruntergenommen wurde. Doch auch hier landen sie in einer Zwickmühle: Beide warten auf den jeweils anderen Nachbarn und niemand kann das Haustier in den Garten lassen. Wie kam es zu dieser Situation?

Alice hisst ihre Flagge. Bob Alice Alice wartet auf Bob. Bob schaut zur anderen Flagge. Bob

Im zweiten Beispiel wurde versucht das erste Problem zu lösen. Dabei ist ein neues Problem aufgetreten. Der gegenseitige Ausschluss ist nun zwar gegeben, allerdings ist es möglich, dass die beiden Nachbarn auf die Aktion des anderen warten:

  1. Alice hisst ihre Flagge.
  2. Bob hisst seine Flagge.
  3. Alice schaut zur anderen Flagge.
  4. Alice wartet auf Bob.
  5. Bob schaut zur anderen Flagge.
  6. Bob wartet auf Alice.

Diese Situation wird Verklemmung (Deadlock) genannt. Da in diesem Beispielprogramm in einer Endlosschleife auf die Flagge des anderen gewartet werden würde, könnte sich dieses Programm niemals selbst aus der Situation befreien und müsste vom Betriebssystem beendet werden.

Wie hier zu sehen ist, gibt es bei der nichtsequentiellen Ausführung von Programmen eine Reihe von Problemen (dies waren nicht die einzigen!), welche gelöst werden müssen. Im Modul „Algorithmen und Programmierung IV: Nichtsequentielle Programmierung“ wird der Umgang mit diesen Problemen in Theorie und Praxis gelehrt.