Lösungsvorschlag

a) falsch

b)

• falsch (nur Änderungen im synchronized-Block)
• falsch (nur, wenn sie die gleiche Marke haben wollen)
• richtig

c) Zählt man die Startbelegung S auch zum Petri-Netz, so ist ∞ die richtige Antwort, sonst 1

d)

e)

f)

a)

 S = ( 1, 0, 1, 1, 0 )

 M: 
  0   0   0   0   1
  2   0  -1  -1   0
  0   1  -1   0   0
 -1  -1   0   0   2
  0   0   3   1  -4
  
  EDIT: Die 1 in der ersten Zeile ist vermutlich falsch, t4 hat keinen Einfluss auf die Belegung in A. Meiner Meinung nach müsste die komplette Zeile nur aus 0en bestehen.

Petri-Netz ist nicht lebendig, da durch t0 → t3 → t3 ein Deadlock entsteht!

b)

import java.util.concurrent.*;
public class PointerDoubling {
	private static int[] next ;
	private static int[] rank;
	private static CyclicBarrier outer;
	private static CyclicBarrier inner;
	public static int[] calculateRanks (int [] next) 
		throws InterruptedException, BrokenBarrierException {
		PointerDoubling.next = next;
		rank = new int[next.length];
		outer = new CyclicBarrier(next.length + 1);
		inner = new CyclicBarrier(next.length);
		// TODO: 1
		Thread[] threads = new Thread[next.length];
		for (int i = 0; i < next.length; i++) {
			threads[i] = new Worker(i);
			threads[i].start();
		}
		outer.await();
		return rank;
	}
 
	public static class Worker extends Thread {
		private final int index;
		public Worker (int index) {
			this.index = index;
		}
 
		public void run () {
			try {
				// TODO: 2
				if (next[index] == -1) {
					rank[index] = 1;
				}
				// TODO: 4
				// inner.await(); -- not needed
				int distance = 1 ;
				while (distance < next.length) {
					int rankOfNext = 0;
					int nextOfNext = 0;
					if (next[index] > 0) {
						rankOfNext = rank[next[index]];
						nextOfNext = next[next[index]];
					}
					// TODO: 4
					// inner.await(); -- not needed
					// TODO: 3
					if (rankOfNext != 0) {
						rank[index] = rankOfNext + distance;
						next[index] = nextOfNext;
					} else {
						next[index] = nextOfNext;
					}
					// TODO: 4
					inner.await();
					distance *= 2;
				} // END OF while
				outer.await();
			} catch (Exception e) {
				e.printStackTrace();
			}
		} // END OF run
	} // END OF Worker
} // END OF PointerDoubling

if (index == 0) { Thread.sleep(1000); }

a) Vier, Rechenzeit wird Threads zufällig zugeteilt, weshalb die Reihenfolge von Inkrementieren und Schreiben nicht geklärt werden kann.

b) digits[2] == 0 | 1
Auch hier kann nicht vorausgesagt werden, ob erst inkrementiert oder erst geschrieben wird. Sicher ist jedoch, dass sich die Threads keine Kopie der Variablen halten und somit immer auf den zuletzt geschriebenen Wert zugreifen!

c) digits[3] == 9
Da Thread2 an barrier auf das Schreiben von Thread1 wartet, wird gewährleistet, dass sicher der zuvor gesetzte Wert geschrieben wird.

d) Alle Werte zwischen 2 und 8 sind möglich.

e) digits[5] == 5 | 7
Da nicht geklärt ist, welcher Thread nach barrier.await() zuerst Rechenzeit zugeteilt bekommt, entsteht eine Wettlaufsituation um dv5.