Kurs 20026 Programmierungs-Konzepte

Einsendeaufgaben zu Lerneinheit 3

Aufgabe 1 (10 Punkte)

Zwei Aktivitäten arbeiten auf einem gemeinsamen Zähler 'count':

int count = 20;
Thread a = ...
...
count++;
...


Thread b = ...
...
count--;
...

Wenn der Zugriff auf 'count' durch einen Semaphor oder Monitor geschützt ist, kann man entweder beobachten, dass 'count' zuerst um 1 erhöht wird, also den Wert 21 erhält, dann um 1 vermindert wird (und somit den Wert 20 erhält) oder umgekehrt. Wenn jedoch kein wechselseitiger Ausschluss beim Zugriff auf 'count' sichergestellt ist, können sich unterschiedliche Ergebnisse ergeben. Wir nehmen an, dass die 'count'-Anweisungen wie folgt in Maschinenanweisungen übersetzt werden:

...

...

LOAD count into register R

LOAD count into register R

ADD 1 to R

SUB 1 from R

STORE content of R in count

STORE content of R in count

...

...

Ohne Zugriffsynchronisation können die Maschinenanweisungen beider Aktivitäten miteinander verschachtelt ausgeführt werden.

Geben Sie zwei Ausführungsfolgen der Maschinenbefehle an, die dazu führen, dass der Wert von 'count' nach der Ausführung im einen Fall 21 und im zweiten Fall 19 ist.

Aufgabe 2 (9 Punkte)

Das nachstehende Programm in Pseudocode löst das Filosofenproblem mit Hilfe eines Monitors ohne Bedingungsvariablen, wobei wir wieder folgende Vereinbarung benutzen: left(i) = i, right(i) = (i-1) % 5

MONITOR fork
{
  int avail[5] = {2, 2, 2, 2, 2 }; // each phil has access to two forks available 
                                         
  void pickup_fork (int phil) // admissible arguments are the integers 0, ..., 4

  {
    avail[left(phil)]--;
    avail[right(phil)]--;
  }

  void putdown_fork (int phil)
  {
    avail[left(phil)]++:
    avail[right(phil)]++;
  }
}

a) Überlegen Sie sich, wie sich dieses Programm verhält und begründen Sie das Kernproblem dieser Lösung. (2 Punkte)

b) Schlagen Sie eine Änderung des Programms vor, die dieses Problem behebt, ohne Bedingungsvariablen oder Semaphore einzuführen. Beschreiben Sie, wie Ihre Lösung das in Teilaufgabe a genannte Kernproblem verhindert (7 Punkte)

Aufgabe 3 (6 Punkte)

Schreiben Sie ein Java-Programm, das die in den 'cobegin'-Anweisungen des Programms "processWordsConcurrently ()" aus Programm 7.1-1 angegebenen Anweisungen in eigenen Aktivitäten ausführt, so dass der gleiche Grad an Nebenläufigkeit erreicht wird.