Niklas @ ETHZ

HS20

3 min read

3. Pipelining

3 a)

Throughput: > im steady state immer!

Throughput = 1 / max_stage (die wo alle warten müssen)

6. Wait/Notify

a)

Be careful with too much synchronisation → that could lead to a deadlock here!

we only need to synchronise with this around the while (!foodTruck.isCustomersTurn(this)) as we need to wait().

The other stuff is already synchronised inside!

Release the lock on the FoodTruck, before synchronising on the customer → otherwise deadlock!!

7. ForkJoin

Pay attention here, this is in-place, thus the array is modified! We need to pass in the left, right values along.

map → only if independently on every element.
This is neither map nor reduce!

b)

The ForkJoin Framework keeps a DAG internally to keep track of the progress.
It has a sort of TaskParallelism

c)

Both ForkJoin and Executor coordinate Tasks → Threads, keep a list of running threads that are assigned work

ForkJoin → internal Queue + Work Stealing

8.

a) Definitions

Deadlock-Freedom: If threads are trying to enter the critical section, one of them must eventually get in.

Starvation Freedom: if any thread is trying to enter the critical section, it must eventually get in.

b) State-Space diagram

Modifications after

The modifications on a line of code run only after the diagram has gone from that state to the next!

c) N thread lock

Filter lock pseudocode implementation:

int[] level(#threads);
int[] lastToEnter(#threads);
 
lock(me) {
	for (i = 1 to #threads) {
		level[me] = i;
		lastToEnter[i] = me;
		while (lastToEnter[i] == me && there exists k =/= me with level[k] >= i) {
			wait; // pseudo for spinlock
		}
	}
}

wait until everyone in front of me has cleared

d) CAS lock

R = CASObject;
 
lock(me) {
	while (!R.CAS(false, true)) {
		// spin
	}
}
 
unlock(me) {
	R.set(false);
}

9 Linearizability

e)

In a shared memory system where all accesses to shared data are protected by a Global Lock

  • Linearizable
  • SC
  • Sequential → FALSE

Sequential

Methods calls do not interleave

Volatile Accesses:

  • Linearizable
  • SC
  • sequential → FALSE

Equivalent

A history is equivalent to another if the per-thread projections are the same.

11. WaitFree

a)

consensus:

  • valid
  • consistent
  • wait-free
    • finite number of it’s own steps

b) Consensus Protocol Lemma

All critical States on the same height → FALSE

Univalent

State who’s children all make the same decision.

Bivalent

State where children can still be both 0 or 1.

Critical State

A protocol state is critical if:

  • it is bivalent
  • if any thread moves, the protocol state becomes univalent (The art of multiprocessor programming p106)

13. Mixer

b) Pointer Tagging

Can Pointer-Tagging solve ABA in all cases?

No. Pointer-Tagging only makes the ABA problem much less probable. It uses a few bits of an address for a tag, and increments that tag each time the pointer is stored in a data structure. However the tag can overflow and revert to the initial value. (Lecture 22)

It’s also not always possible to use Pointer-Tagging: maybe no bits are available for a tag.

c) TAS Lock

Use TATAS
Use exponential back-off to prevent the “release storm”

Graph View