FS23

3. FJ

a)

When we don’t have the code initialising the FJ Pool, make sure to overwrite any array contents with 0.
Do not immediately matMul[i][j] += ...

b)

Exponential Speedup ist definiert als $\Omega (n/\log n)$.

5. Locks

a)

Deadlock Def:
“Circular waiting/blocking (no instructions are executed/CPU time is used) between threads, so that the system (union of all threads) cannot make any progress anymore.”

b)

Deadlock vs. livelock
“In a deadlock the state of the system does not change. In a livelock, the state of the system changes continuously but without progress being made.”

c)

A deadlock doesn’t need to be full “circular dependency waiting”, it can also be a state where everyone is asleep → spurious wakeup could solve it.

Here, we just put all threads to sleep by exploiting Notify Order.

6

b)

Proof Linearizability ⇒ SC

Proof:

• A history $H$ being linearizable is defined as $H$ (with dropped pending invocations or added responses) being equivalent to a legal sequential history $S$ s.t. ${\to }_H\subset {\to }_S$.
• This implies that $H$ is equivalent to a legal sequential history which is the definition of sequential consistency.