FS19

Speedup, Gustafson’s, Amdahl’s

2.

Lower bound für wieviele Prozessoren gebraucht werden: “hat die Maschine mindestens!

$S_p=2=\frac{1}{f+\frac{1-f}{P}}$. Dann gilt $P\ge 3$.

Nicht auf das $\ge$ vergessen.

3.

Für ${\lim }_{P\to \infty }{S}_P$ mit $f>0$, gilt dass $S_P$ bounded ist!

${\lim }_{P\to \infty }{S}_p=\frac{1}{f+\frac{1-f}{P}}=\frac{1}{f}$ as ${\lim }_{P\to \infty }\frac{1-f}{P}=0$.

Pipelining

b)

Angenommen Pipeline leer, wie lange bis 100 Bilder durch sind.

Formel: latency (first element) + max(stage_time) * (n - 1).

Also in unserem Fall $160+50\ast 99=5110ms$.

Threads

Synchronized needed

We cannot call wait() or notify on the class’s Monitor without having the method synchronized.

Synchronized is very necessary here!

Wait/Notify

Do not forget the synchronized around the while (true) inner block!

Without it again, we cannot call wait().

The general pattern here is:

• while (true) for consumer (post office)
• set current = null
• increment current ticketnum
• notifyAll
• busywait until consumer is not null
• serve consumer

the consumer should also be synchronized and wait() with a while until it’s his turn, when he sets customer == this.

Do not forget synchronized(this) { ... } block!

Fork/Join

You need:

• new Task(...)
• then .compute() or .fork()
  • then .join() for the forked task
• finally recombine elements
  • make sure boundary cases are handled:
    • going over middle sep
    • combining left/right into one

For the correct splitting:

int mid = length / 2;
Task left = new Task(array, start, mid); // this is exclusive mid
Task right = new Task(array, start+mid, length - mid); // inclusive mid here

Make sure to correctly initialise Sequence → no length, initial len is 1, only using extend!

3)

We can of course split the work into 3 different segments and recombine (if easily splittable by 3) → just as efficient.

ForkJoinPool in which RecursiveTask is executed is just special ExecutorService and can handle an arbitrary amount of threads.

State Diagrams

b)

1. Deadlock
   1. only if a state has no outgoing edges is possible
2. Livelock
   1. only if there is a cycle in which both threads make no progress
      1. i.e. without entering the critical section
   2. “no cycle without having both threads enter the critical section”
3. Mutex
   1. No state every reaches [CS, CS, -]
4. Wait-Free
   1. wait-free = non-blocking + everyone makes progress
   2. only if failure or suspension of one thread cannot cause failure or suspension of another thread

→ here one thread being blocked means state never switches back to next == 1/0 and thus the other is also blocked.

Synchronization

9)

Mutex for $N$ can be implemented with:

• atomic registers (filter lock, bakery lock)
• locks
• CAS
• STM (only guarantees atomicity, but aborts everyone but one → optimistic concurrency control)

Wait-free consensus for $N$;

• atomic-registers → NO
• locks → NO
• CAS → YES

ABA problem occurs for:

• atomic registers
• CAS
  not for Locks or STM (because of global clock and timestamps)

10)

private int factor = 1;
private final AtomicBoolean full = new AtomicBoolean(false);
public void Update1(int multiplier) {
	while (!full.compareAndSet(false, true));
	factor *= multiplier; // CS
	full.set(false);
}

Lock-free? NO → uses Spinlock here.

• For lock-freedom it would have to be
  • non-blocking → it blocks on CAS
  • someone makes progress
• if one thread dies in the CS, all are blocked!

Mutex for 2 or $N$ threads → YES

private final AtomicInteger factor = new AtomicInteger(1);
boolean Update2(float multiplier, int retries) {
	while (retries >= 0) {
		int val = factor.get();
		int res = val * multiplier;
		if (factor.compareAndSet(val, res)) {
			return true;
		}
		--retries;
	}
	return false;
}

This code uses optimistic concurrency control.

Optimistic concurrency control

First fetching element, then doing some work on it and finally checking if the element was not modified before writing-back (atomically.
If the element was modified, restart.

Linearizability

a)

1. Linearizability ⇒ Sequential consistency

sequential consistency means it’s a legal history if we allow reordering threads arbitrarily, no matter what, just inter-thread PO has to be respected.
Linearizability demands that we cannot reorder non-overlapping sections!

2. Sequential ⇒ Linearizable
   1. FALSE, sequential is weaker

Sequential vs. linearizable counterexample 15.2.1 Comparing SC and Linearizability

3. sequential History is legal, if every teilhistorie is legal

   1. TRUE, by def.
      1. legal sequential history: for every $x$, $H|x$ is legal sequential history.

4. Komplette historie immer linearisierbar

   1. FALSE
   2. komplette historie = no pending invocations

5. Zwei historien equivalent wenn beide linearisierbar sind

   1. FALSE
   2. H, G equivalent wenn for all threads $H|{\text{thread}}_i$ = $G|{\text{thread}}_i$.

b)

1. H1 und H2 können nicht vom selben Programm erzeugt worden sein
   1. FALSE
   2. histories are equivalent for each thread (projections) as the calls match exactly, just the inter-thread order is different
2. H1 is linearisable
   1. false, we can check from the diagrams

History → Diagram

We can create the diagram from the history by drawing a line between matching invocations, i.e. q.w(2) -> q:void, etc…

3. H2 is a sequential history
   1. FALSE, sequential only when threads don’t interleave.
      1. final pending invocation is ok

Barriers and Synchronisation

a)

Inefficient: yes, busy waiting (not spinlock!) is inefficient.

b)

Within a synchronized, the even non-atomic statements like i++ are of course atomic. Thus it completes perfectly fine.

c)

Implement a barrier for any number of threads, that other threads can already enter while the rest are exiting.

Intuition:

• Hold threads while the barrier is draining, use a spinlock or wait()
• Count up, then down
  • when all are out, allow the next ones to proceed through.

public class Barrier {
    final int threads;
    private int i = 0;
    private boolean holding = false;
    
    public void synchronized await(){
        while(holding){
            wait();
        }
        
        i++;
        
        while(i < n && !holding){
            wait();
        }
        if(i==n){
            holding = true;
            notifyAll();
        }
        i--;
        
        if(i==0){
            holding = false;
            notifyAll();
        }
    }
}

Why no volatile? Having everything inside the synchronized block gives us the same properties as the volatile does. → unlocking/locking monitor is also a synchronization action.

Semaphores

a) Multi-Semaphore

Java-Monitore = java object monitors, just use synchronized.

synchronized void acquire(int n) {
  while (n > count)
    wait();
  count -= n;
}
 
synchronized void release(int k) {
  count += k;
  notifyAll();
}

b)

just set the multisemaphore to $3$ and then acquire 1 or 3 depending on either car or truck.