Studied by 0 people
Looks like no one added any tags here yet for you.
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.
