Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » pfp » Lösungsversuch   (Übersicht)

Lösungsversuch

Aufgabe 1 - Wissensfragen

a)

  • volatile
  • synchronized

b)

  • p(n) ist der parallele Anteil
  • B_p ist der Speedup

c)

  • Entzug von Betriebsmitteln
  • globale Ordnung der Betriebsmittel

d)

  • Filteroperationen
  • Abbildungsoperationen (z. B. map)

Aufgabe 2 - Schreibtischlauf

a)

Ausgabe (MyThread1) Ausgabe (MyThread2)
Möglichkeit 1 y = 0 x = 1
Möglichkeit 2 y = 1 x = 0
y = 1 x = 1
y = 0 x = 0

Begründung: print des einen Threads kann vor Setzen des neuen Wertes im anderen Thread geschehen. Compiler kann außerdem unabhängige Code-Zeilen umsortieren, weshalb auch y = 0 / x = 0 möglich ist!

b)

Ausgabe (Main-Thread)
Möglichkeit 1 counter = 2
Möglichkeit 2 counter = 3

Begründung: counter wird garantiert 2x synchronisiert, also korrekt inkrementiert. Der zweite Zugriff auf counter in MyThread1 ist aber nicht mehr korrekt synchronisiert, da eine andere Marke verwendet wird. Deshalb kann es hier zu einer Lese-Ändere-Schreibe-Wettlaufsituation kommen.

c)

Ausgabe (MyThread1) Ausgabe (MyThread2)
Möglichkeit 1 T1 = done. T2 = done.
T1 = done. T2 =

Begründung: value ist nicht volatile, durch Sichbarkeitsprobleme kann es hier zu einem Deadlock kommen, nämlich gerade dann wenn MyThread2 nichts von der Änderung in MyThread1 mitbekommt.

Aufgabe 3 (Petri-Netze)

a)

b) Wenn irgendwann einmal wieder jede Transition (t1 - t4) schalten/feuern kann, dann ist ein Petri-Netz lebendig, wenn nicht, dann nicht. ;)

Beispiele für ein nicht lebendiges Petri-Netz:
- Eine Belegung [x, y, z] in einem Erreichbarkeitsgraphen aus dem keine Pfeile gehen (Deadlock)
- Zyklus in dem nicht alle möglichen Belegungen erreicht werden (Lifelock)

c)

Aufgabe 4 (Java - Counting)

  import java.util.concurrent.*;
  import java.util.concurrent.atomic.AtomicIntegerArray;
 
  public class Counting {
	final byte[] array;
	int threads;
	final AtomicIntegerArray globalCounts;
	final CyclicBarrier barrier;
 
	Counting(byte[] array, int threads) {
		this.array = array;
		this.threads = threads;
		this.globalCounts = new AtomicIntegerArray(256);
		this.barrier = new CyclicBarrier(threads + 1);
 
	}
 
	AtomicIntegerArray count() throws Exception {
		int step = array.length / threads;
		int start = 0;
		for (int i = 0; i < threads ; i++) {
			Thread cntThr;
			if ((start + step < array.length) && (i != threads - 1)) {
				cntThr = new CountingThread(start, start + step);
			} else {
				cntThr = new CountingThread(start, array.length);
			}
			cntThr.start();
			start += step;
		}
		barrier.await();
		return globalCounts;
	}
 
	class CountingThread extends Thread {
		private int begin, end;
		CountingThread(int begin, int end) {
			this.begin = begin;
			this.end = end;
		}
 
		public void run() {
			try {
				// local counting phase -- already implemented
				int[] count = new int[256];
				for (int i = begin; i < end; i++) {
					count[array[i] + 128]++;
				}
				// add values of count to globalCounts 3
				for (int i = 0; i < 256; i++) {
					globalCounts.addAndGet(i, count[i]);
				}
				barrier.await();
			} catch (Exception e) { /* handle exception */ }
		}
	}
  }


(ich glaube im oberen Code ist ein barrier.await() zu viel)
Alternativlösung:
1:

this.barrier = new CyclicBarrier(threads + 1);


2:

for (int i = 0; i < thread; i++) {
    int end = start + step;
    if (end >= array.length) end = array.length - 1;
 
    (new CountingThread(start, end)).start();
 
    start = end + 1;
    if (i != array.length - 1 && start >= array.length) {
        threads = i;
        barrier = new CyclicBarrier(i + 1);
        break;
    }
}


3:

for (int i = 0; i < count.length; i++) globalCounts.addAndGet(i, count[i]);


4 (nur oberes Feld):

barrier.await();



Aufgabe 5 (Scala - Listenoperationen)

a)

  def flatten : List[(Char, Char)] => List[Char] = {
      case Nil => List()
      case t :: ts => List(t._1, t._2) ::: flatten(ts)
  }

Alternativlösung:

def flatten : List[(Char, Char)] => List[Char] = {
    case Nil => Nil
    case (a, b) :: tailList => a :: List(b) ::: flatten(tailList)
}

b)

  def countPar : List[Char] => List[(Char, Int)] = cs => {
      for (c <- cs) yield (c, cs.par.filter(_ == c).size)
  }

c)

  def distinct : List[(Char, Int)] => List[(Char, Int)] = cs => {
      cs.foldLeft(List[(Char, Int)]())((ls, c) => if (ls.contains(c)) ls else c :: ls)
  }

Aufgabe 6 (Scala - Lauflängenkodierung)

a)

def decodeTuple: ((Char, Int)) => Stream[Char] = {
    case (c, 1) => Stream(c)
    case (c, k) => c #:: decodeTuple(c, k - 1)
}

b) Geht für decode(Stream()) und decode(Stream( ('a', 3) )).toList kaputt:

def decode: Stream[(Char, Int)] => Stream[Char] = {
    case null => Stream()
    case ts => decodeTuple(ts.head) #::: decode(ts.tail)
}

Alternativlösungen:

def decode: Stream[(Char, Int)] => Stream[Char] = {
  case Stream.Empty => Stream.Empty
  case ts => decodeTuple(ts.head) #::: decode(ts.tail)
}
def decode: Stream[(Char, Int)] => Stream[Char] = {
    case Stream.Empty => Stream.Empty
    case first #:: tailList => decodeTuple(first) #::: decode(tailList)
}