Lösungsvorschlag

a) falsch

b)

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

c) 1

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

Petri-Netz ist lebendig, da Summe aller Marken bei t0 → t2 → t3 → t4 → t1 unverändert bleibt. Alle Transitionen können immer wieder schalten!

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();
				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();
					// 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