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