Kurs 20026 Programmierungs-Konzepte
Einsendeaufgaben zu Lerneinheit 1
Essende und denkende Filosofen (3 Punkte)
Das Problem der essenden und denkenden Filosofen wurde bereits 1971 von E. Dijkstra eingeführt und beschreibt ein Standardproblem im Bereich der verteilten DV-Systeme. Dabei sollen die Probleme der wechselseitigen Zuteilung von Ressourcen an die autonom handelnden Komponenten eines verteilten Systems veranschaulicht werden.
Man stelle sich vor, dass sich 6 Filosofen um einen runden Tisch mit dem Essen auf der Mitte dieses Tisches gruppiert haben. Sie können abwechselnd entweder nur denken oder essen. Es stehen weiterhin nur 6 Gabeln zur Verfügung. Also, jeweils zwischen 2 benachbarten Filosofen befindet sich eine Gabel. Zum Essen brauchen sie aber jeweils 2 Gabeln. D. h. durch die Tatsache, dass jeweils 2 benachbarte Filosofen sich eine Gabel in ihrer Mitte teilen, kann also zu einem Zeitpunkt höchstens der mittlere von 3 Filosofen essen.
Frage: Wie viele Filosofen können zur gleichen Zeit speisen? Begründen Sie bitte Ihre Antwort!
Aktivitäten (Threads) (12 Punkte)
Gisela und Klaus besitzen ein gemeinsames Konto mit 100 EUR Guthaben und wollen am gleichen Tag an verschiedenen Orten vom Konto Geld abheben. Dabei gehen sie wie folgt vor:
Gisela
Kontostand abfragen
60 EUR abheben
Klaus
Kontostand abfragen
70 EUR abheben
Auf dem Konto ist kein Dispositionskredit eingerichtet, d. h. dass nur bei ausreichendem Guthaben Geld abgehoben werden kann. Dabei soll angenommen werden, dass die Programmierer der Bankautomatensoftware gerade erst Java gelernt haben und noch nichts von kritischen Bereichen gehört haben.
Stellen Sie bitte fest, welchen Kontostand das gemeinsame Konto nach der Ausführung beider Aktivitäten haben kann. In welchem Fall erhalten Klaus und Gisela wieviel Geld? Welchen Betrag sehen sie bei der Kontostandsabfrage? Begründen Sie bitte Ihre Antworten!
Präzedenzgraph (15 Punkte)
Gegeben sei folgender arithmetische Ausdruck der Programmiersprache JAVA:
A = B * C++ + (-A--) * C / D
Folgende Befehle stehen zur Verfügung:
|
Befehl
|
Bedeutung
|
| L(A) | Liest Variable A |
| S(A) | Schreibt Variable A |
| Op(*) | Führt die Operation * (Multiplikation) aus |
Entsprechende Befehle gibt es für alle Variablen und Operationen. Für die Operation C = A + B sieht der Präzedenzgraph beispielsweise wie folgt aus:
a) Erstellen Sie bitte einen Präzedenzgraphen für den o. g. Ausdruck! (10 Punke)
b) Geben Sie an, wieviele Zeiteinheiten minimal benötigt werden, um diesen Ausdruck unter Ausnutzung aller Nebenläufigkeiten zu berechnen. Dabei wird für die Bearbeitung einer Aktion eine Zeiteinheit benötigt. (5 Punkte)