Tutorium 13

Gruppen 5 und 7
Samuel Teuber
propa@teuber.dev
https://teuber.dev/propa

Verwirrung bei Tutorien Terminen

Übungsblätter

  • Fragen?
  • Probleme?
  • Zu schwierig?

Übungsblatt 11

Aufgabe 1: Amdahlsches Gesetz

  • Verschiedene Threads:
    • Lesend: Beliebig viele gleichzeitig; Jeweils 2 sec.
    • Schreibend: Alleine; Jeweils 3 sec.
  • 10% Schreiber; 90% Leser

Obere Grenze für Beschleunigung auf 4-Kern-Prozessor?

$$ S(P) = \frac{1}{(1-P)+\frac{P}{N}} $$
$$ P = \frac{2*0.9}{2*0.9+3*0.1} \approx 0.86 $$
$$ S(P) \approx 2.82 $$

Aufgabe 2: Producer/Consumer

Sorry...

Aufgabe 3: Synchronisation

Reminder: Buddy-System, Immer eine*r der beiden Buddies muss anwesend sein

Sehr grobgranulare Synchronisation:

public synchronized boolean tryTakeVacation(String name, Month month) {
    // ....
    if (employee.isOnVacation(month)) return true;
    if (buddy.isOnVacation(month)) return false;
    employee.setVacationState(month, true);
    return true;
}

Problem?

Nur ein einziger Aufruf im ganzen Unternehmen gleichzeitig möglich!

Synchronized weglassen?

Nein, da sonst Race Condition!

Aufgabe 3: Synchronisation

Reminder: Buddy-System, Immer eine*r der beiden Buddies muss anwesend sein

synchronized(employee) {
    if (employee.isOnVacation(month) return true;
    synchronized (buddy) {
        if (buddy.isOnVacation(month) return false;
        employee.setVacationState(month, true);
    }
}

Problem?

Deadlock! Lösung?

Aufgabe 3: Synchronisation

Reminder: Buddy-System, Immer eine*r der beiden Buddies muss anwesend sein

EmployeeVacationRecord outerMonitor;
EmployeeVacationRecord innerMonitor;
if (employee.getName().compareTo(buddy.getName()) < 0) {
    outerMonitor = employee;
    innerMonitor = buddy;
} else {
    outerMonitor = buddy;
    innerMonitor = employee;
}

Optimale Lösung?

Monitorobjekt für die Buddies:

employee.getMonitorObject()

Aufgabe 4: Barriere

public interface IBarrier {
    void await() throws InterruptedException;
    void freeAll();
}

Reentrant?

public class Barrier implements IBarrier {
    private final int maxThreads;
    private int threadsInCurrentWaitingPhase = 0;
    private int currentWaitingPhase = 1;
    public Barrier(int maxThreads) {
        this.maxThreads = maxThreads;
    }
    @Override
    public synchronized void await() throws InterruptedException {
        final int myPhase = currentWaitingPhase;
        ++threadsInCurrentWaitingPhase;
        if (threadsInCurrentWaitingPhase == maxThreads) {
            freeAll();
        }
        while (currentWaitingPhase == myPhase) {
            this.wait();
        }
    }
    @Override
    public synchronized void freeAll() {
        ++currentWaitingPhase;
        threadsInCurrentWaitingPhase = 0;
        this.notifyAll();
    }
}

Aufgabe 5:

public class HappensBefore {
    public static boolean ping = false;
    public static final int maxRuns = 100;
    public static void main(String[] args) {
        Thread pingThread = new Thread(()-> {
            for(int i = 0; i < maxRuns; i++) {
                while(ping) {}
                ping = true;
                System.out.println("Ping - Round " + i);
            }
        });
        Thread pongThread = new Thread(()-> {
            for(int i = 0; i < maxRuns; i++) {
                while(!ping) {}
                ping = false;
                System.out.println("Pong - Round " + i);
            }
        });
        pingThread.start();
        pongThread.start();
    }
}

Warum bleibt das Programm manchmal hängen?

Aufgabe 6: Primzahltest

private static class State {
    private int currentNumber = 1;
    private int result = 0;
    private final int target;
    State(int target) {
        this.target = target;
    }
    synchronized int nextNumber() {
        return currentNumber < target ? ++currentNumber : -1;
    }
    synchronized void addToResult(Integer count) {
        this.result += count;
    }
    int getResult() {
        return result;
    }
}

Aufgabe 6: Primzahltest

|public static int countPrimes(final int until, final int threads) {
|    final State state = new State(until);
|    Set<CompletableFuture<Void>> futures = new HashSet<>();
|    for (int i = 0; i < threads; ++i) {
|        futures.add(CompletableFuture.supplyAsync(() -> {
|            int currentNumber = 0;
|            int partialCount = 0;
|            while (currentNumber != -1) {
|                if (PrimeTester.isPrime(currentNumber))
|                    ++partialCount;
|                currentNumber = state.nextNumber();
|            }
|            return partialCount;
|        }).thenAccept(state::addToResult));
|    }
|    for (CompletableFuture<Void> future : futures) {
|        try {
|            future.get();
|        } catch (InterruptedException | ExecutionException e) {
|            e.printStackTrace();
|            return -1;
|        }
|    }
|    return state.getResult();
|}

Design by Contract

Java Modelling Language (JML)

  • Formale Spezifikation von Methoden
  • z.B. durch Angabe von Vor- und/oder Nachbedingungen

Warum?

public static int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1
        else if (midVal > key)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}

JML: Verwendung

  • Dynamische Überprüfung zur Laufzeit: assertions
    • Für Fehlersuche
  • Statische Überprüfung
    • Garantiert Eigenschaften der Software

Vor- und Nachbedingungen

Syntax: Kommentare mit @ beginnend

  • Jede Bedingung: Gewöhnliche Java-Expression vom Typ boolean
    • Nur Expressions ohne Seiteneffekte
  • Zusätzliche Boolsche Operatoren:
    • ==> Implikation
    • <==> Äquivalenz
    • <=!=> XOR
  • Neue Schlüsselwörter (nur für Nachbed.):
    • \old(expr) Wert von expr vor Methode
    • \result Rückgabewert
public int x;
public int y;
public int z;
/*@ requires y!=0
  @ ensures \old(y)+1 == y
  @ ensures x == \old(y)
  @*/
public void doStuff() {
    x = y++;
    z = 10/x;
}

Quantoren

  • Ersatz für Schleifen
  • (\forall C x; B; R)
    • ergibt: $\forall x \in C: (B \implies R)$
  • (\exists C x; B; R)
    • ergibt $\exists x \in C: (B \land R)$

"Generalized Quantifiers"

  • (\sum C x; B; R)
  • (\product C x; B; R)
  • (\max C x; B; R)
  • (\min C x; B; R)
  • (\num_of C x; B; R)

Diesmal R numerischer Ausdruck

Sortieren spezifizieren

/*@
  @ requires arr != null;
  @ ensures (\forall int i; 0<=i && i<(arr.length-1); arr[i]<=arr[i+1])
  @ ensures arr.length == \old(arr.length)
  @ ensures (\forall int k; 0<=k && k<\old(arr.length);
  @            (\numof int i; 0<=i && i<arr.length;
  @                          arr[i] == \old(arr[k])) ==
  @            (\numof int j; 0<=j && j<arr.length;
  @                          \old(arr[j]) == \old(arr[k])))
  @*/
void sort(int[] arr){/*...*/}

Parameter und Attribute

  • Standardmäßig nicht null
  • nullable:
    /*@ nullable @*/ List<Integer> list
  • Welche Parameter sind veränderbar?
    • assignable für veränderbare Parameter
    • assignable \nothing

Klasseninvarianten

  • Nach jedem Konstruktoraufruf
  • Vor/Nach jedem Methodenaufruf
    • Während Aufruf verletzbar
  • Ähnlich: Schleifen-Invarianten
class IntegerSet {
    byte[] a; /* The arraya is sorted*
    /*@
      @ invariant (\forall int i;
      @                 0 <= i && i < a.length-1;
      @                 a[i]< a[i+1]);
      @*/
}

Seiteneffekte

//...
public int doSth() {
    this.i+=10;
    return this.j;
}
/*@ requires a > 0
  @ ensures doSth() = \old(a)
  @*/
public void doSthElse(int a) {/*...*/}
//...

Geht das?

Nein! Denn doSth hat Seiteneffekte.

Jede Funktion, die aus JML aufgerufen wird darf keine Seiteneffekte haben!

public /*@ pure @*/ int getBalance() {/*..*/}
public static int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1
        else if (midVal > key)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}
  • Trusting Trust (Ken Thompson)
  • Wem vertrauen wir bei der Spezifikation?

Liskovsches Substitutionsprinzip

Barbara Liskov

Subtype Requirement:
Let $\Phi(x)$ be a property provable about objects $x$ of type $T$.
Then $\Phi(y)$ should be true for objects $y$ of type $S$ where $S$ is a subtype of $T$.

  • Schwächere Vorbedingungen
  • Stärkere Nachbedingungen

Aktoren

        _
      /-/ `\
>\   |@@    |-_______
\ \__/      |        `\
 \____/"\__/         | h
        |        \   | h
        | |\______\  |
        |_|        |_|

Actor-Model

Aktoren (Threads oder Prozesse) kommunizieren per Nachrichten

Wie MPI, aber:

  • Nachrichten immer asynchron
  • Aktoren werden zur Laufzeit von anderen Aktoren erzeugt
  • Aktoren dienen zur Abstraktion (können untersch. Code ausführen)

Aktoren

Everything is an actor

Verhalten auf Nachricht:

  • Nachricht(en) versenden
  • Aktor(en) instanziieren
  • Zustand ändern
    • Kann auch Verhalten auf nächste Nachricht verändern
    • Nur eigener Zustand veränderbar

Nachrichten

  • Werden an mailing address gesendet
  • Nachrichten werden in mailbox gespeichert
  • Werden sequentiell abgearbeitet

Fault Tolerance

  • Aktor initialisiert (Kind-)Aktoren
    • Delegiert Arbeit an Kind-Aktoren
    • Kann Kind-Aktoren neustarten wenn notwendig
  • Aktoren können bel. auf Maschinen verteilt werden

Implementierungen

  • Erlang
  • Akka
  • Akka.NET

Beispiel in Akka (Teil 1)

public class HelloWorld extends AbstractActor {

    @Override
    public void preStart() {
        // create the greeter actor
        final ActorRef greeter =
            getContext().actorOf(Props.create(HelloWorldActor.class), "greeter");
        // tell it to perform the greeting
        greeter.tell("printHello", getSelf());
    }

    @Override
    public void createReceive() {
        return receiveBuilder()
            .match(String.class,
                message -> message.equals("shutdown"),
                this::shutdown)
            .matchAny(message -> unhandled(message))
            .build();
    }

    private void shutdown(String message) {
        getContext().stop(getSelf());
    }
}

Beispiel in Akka (Teil 2)

public class HelloWorldActor extends AbstractActor{

    @Override
    public Receive createReceive() {
        return receiveBuilder()
            .match(String.class,
                message -> message.equals("printHello"),
                this::handleStringMessage)
            .matchAny(message -> unhandled(message))
            .build();
    }

    private void handleStringMessage(String message) {
        System.out.println("Hello World!");
        getSender().tell("shutdown",getSelf());
    }
}