Parallel Exam 3

What is the primary problem with locks?

Something might happen to the thread holding the lock.

What does it mean for an operation to be atomic?

No in between states can be seen.

What does it mean for an atomic operation to be lock-free?

The atomic operation is supported directly by the hardware.

Atomic types

• atomic_flag

• atomic

atomic_flag

The only atomic type guaranteed to be lock-free

What are the two methods of an atomic_flag?

• .clear()

• .test_and_set()

What does .test_and_set() do to an atomic_flag?

It sets the flag and returns the previous value.

• If the value was 0, it sets the flag to 1 but returns 0.

• If the value was 1, it does not reset the flag but returns 1.

What does .clear() do to an atomic_flag?

It clears the bit of the atomic_flag

Explain i.compare_exchange_weak(e,v)/i.compare_exchange_strong(e,v).

If (e == current value of i){

	i = v;

}

else{

	e = i;

}

What is the difference between i.compare_exchange_weak(e,v) and i.compare_exchange_strong(e,v)?

Weak is allowed to fail even when the value matched (spurious failure). Strong is required to succeed when the values match.

What does correctness require?

• Safety

• Liveness

What is safety?

Bad things never happen.

What is liveness?

Good things will eventually happen.

Safety is defined in terms of __________.

Safety is defined in terms of linearizability.

What does it mean for the execution of a parallel algorithm to be linearizable?

The execution is equivalent to some sequential execution history.

When is a data structure implementation linearizable?

When every possible history obtainable with that object is linearizable.

What are the requirements for an algorithm to be linearizable?

Each operation must appear to happen instantaneously at some point between its call and its return.

What is the linearization point?

The point between when no effect of an operation is visible and all of the effects of an operation are visible.

How can we prove the safety of an algorithm?

Identify the linearization point.

The linearization point is always an _______ instruction.

The linearization point is always an atomic instruction.

What are the different definitions of liveness?

• Obstruction-free:

  • every thread is guaranteed to complete even if all other threads were suddenly suspended

  • Not possible with mutexes; if a thread suspends while holding the mutex then I am stuck

  • Cannot be dead-locked

• Lock-free: some thread is guaranteed to complete in a fixed number of steps

  • Guaranteed to make progress

  • Cannot be live-locked

• Wait-free: every thread is guaranteed to complete in a fixed number of steps

  • No other thread can get in my way

  • Cannot suffer starvation

  • Very hard to obtain, and often unnecessary

When is it desirable to have wait-free liveness?

real-time systems that need a guarantee that the algorithm will complete in a fixed amount of time.

What is non-blocking? and does it guarantee any of the definitions of liveness?

• the absence of mutexes

• it does not guarantee any of the definitions of liveness

What is the ABA problem?

• You have A --> M --> N

• t1 wants to pop off A, but t2 makes it to the stack before t1 and pops off A and adds B, resulting in B --> M --> N

• t3 comes and creates a new node; the memory management system gives t3 the memory of discarded node A, resulting in A(with new data) --> B --> M --> N

• t1 finally gets a turn at accessing the stack. The problem is that t1’s oldHead variable in the pop() method has M as the next node, not B; so, A is popped off, head is assigned oldHead->next, which is M, and node B is forgotten.

Sequentially consistent ordering

All of the threads see the operations in the same order. They all agree on some ordering of operations. All processors agree on the order that operations occur, regardless of whether they appeared in the order that we wanted them to occur. When stuff happens ALL of the threads will agree

Relaxed

Each thread sees changes to variables at different times.

Release-Acquire

When thread1 releases memory, the thread that acquires the atomic will also see all of the changes that thread1 made to non-atomic variables.