Week 14

Mark one ADVANTAGE and one DISADVANTAGE of STM (Software Transactional Memory, as opposed to Hardware Transactional Memory)

• worse performance

• better performance

• can be used flexibly, without support from the hardware

• more work for the programmer

What does the programmer have to pay attention to when using shared mutable state with reference-based STMs (e.g. scala-stm)?

• variables must be volatile

• special reference variables/objects must be used for the shared state

• the program should not directly modify the shared state by itself

• the programmer must remember to add accesses to the read/write set

• when using `retry`, one must specify all variables for which updates should be detected

Atomic registers can be used to implement CAS

• True

• False

Answer explanation

We know from the lecture that atomic registers have consensus number 1. If we could implement CAS with atomic registers, we then could use that to solve 2-thread (or n-thread) consensus, a contradiction.

The following code is a correct consensus protocol for 2 threads

• True

• False

Answer explanation

An execution is possible where both threads read i == -1 one after the other. Then they both return their own inputs, which may differ.

• True

• False

Answer explanation

False, the implementation is blocking. If a thread stops executing while holding the lock, the other thread can execute infinitely many steps without finishing, contradicting wait-freedom.

• True

• False

• True

• False

Answer explanation

The construction of a consensus protocol for 2 threads using a queue was shown in the lecture (or see page 107 of the book). What should be surprising is that this is a correct protocol even if the queue is only lock-free. It turns out that any lock-free consensus protocol is also wait-free. Since there is a finite number of threads and a single consensus call from each thread, we can argue that any single call will be wait-free: while the call by a thread A is pending, a call by some thread is guaranteed to finish in a finite number of steps by lock-freedom. After this finite number of steps, we can again apply lock-freedom and know that some other call will finish in a finite number of steps. At the latest, the call on thread A will finish after all other threads have completed their calls.

• True

• False

Answer explanation

This was a question in last year's exam.

Match the entries on the left with the MPI operations on the right. (Top to bottom, NO SPACES)