Non-Blocking Algorithms Flashcards
Non-Blocking Algorithms don’t use locks.
What are disatvantages of locks?
Name 3
1) Locks are pessimistic by design i.e. they assume the worst and enforce mutual exclusion
2) Severe performance issues: Even when uncontested, a lock acquisition must read and write from main memory. When the lock is contested, this degradation becomes much worse.
3) Locking is hard. A delayed thread might slow down all subsequent threads, deadlocks might occur,
interrupt handlers become much harder to implement correctly, etc.
What library do we use for atomic operations?
java.util.concurrent.atomic
Write down the code for testAndSet() and explain what it does.
checks if a value is what you excpect it to be
TestandSet() what does it do, and what does it have to do with atomicity? Think of a value in a operation
Test-and-set helps us fix that problem by checking that the value your overwriting is what you think it should be. In this case, you can check that the balance was the original value that you read. Since it’s atomic, it’s non-interruptible so no-one can pull the rug out from under you between the read and the write.
example increment
Say two threads execute a = a + 1 and say a starts with 100. What can go wrong? And what does TestandSet() say in this example?
Both threads could read a = 100 and increment by 1. So both threads will write-back 101 even tho it should be 102 after 2 increments.
With TestandSet a thread says “Set a to 101 but only if it currently has the value 100”. 1 thread will succeed but the other won’t. The other will retry the entire statement.
Why does TestandSet work? IMPORTANT
Because all operations are ATOMIC. No bad-interleavings happen during the check of the value.
Why is TestandSet faster than a Mutex (lock implementation)?
Even during collision, one thread isn’t blocked at all, and it’s faster for the other thread to just spin and retry than it would be to suspend itself in line for some mutex.
Write the code for compareAndSet(). What does it do?
What arguments does it take?
Takes two arguments: 1) expected value 2) update value + memory location of the value to be checked
If the current stored value is equal to the expected value, it updates it to the specied update value, otherwise the value is left unchanged. Finally, it returns a boolean value indicating whether the value was replaced or not.
What kind of operations are TAS and CAS?
Read-Modifly-Write operations
Give the definition of the ABA problem.
The ABA problem occurs when one activity fails to recognize that a single memory location was modied temporarily by another activity and therefore erroneously assumes that the overall state has not been changed.
Explain the ABA-Problem using the lock-free stack implementation with a Nodepool.
1) We try to pop(a) and observe that head == a and head.next == b
2) We then try to compareAndSet() head to b, because we pop(a)
3) At the same time another thread removes a and b and than pushes some other node c and a from the nodepool. (head than == a=
4) CompareAndSet would than observe head == a as expected and set head == b and delete a. b might not even be in the stack anymore
How do we solve the ABA problem? name 4
DCAS: We check if head and head.next are as expected.
Garbage Collection: Would eliminate the need for a NodePool (NodePool is neede because popped node just use space and are not used), but its very slow
Pointer Tagging: Each time a pointer is stored its tag bit is increased up to 32. Now 32 versions exist (ex. 32 versions of the same node) ABA is less likely but not gone
Hazard Pointers: We can associate an AtomicReferenceArray with the data structure where we temporarily store references which we’ve read and wish to write to in the future. Whenever we return a Node to the NodePool, we check whether its reference is stored in the hazarduous array. While this solution does work, the nal product of a NodePool doesn’t really improve performance when compared to regular memory allocation with a garbage collector.
What is TAS Test-And-Set useful for? And what kind of operation is it?
For implementing lock. Say Thread 1 wants to acquire the Lock it will check memory location to see if it is 0. if it is it will change it to 1 and return true. Which means we have acquired the lock.
When a second Thread tries to acquire the lock it will see the memory location as 1 and return false, therefore not acquiring the lock.
To realease the lock you simply change the value back to 0.
It it an atomic operation.
