A lock-free stack is speculative: we assume that we're able to change the stack, and right before we actually "commit" the change, we check if another thread has modified the stack. If another thread has, then we "fail", and try again (which is why we have the while(1) loop). Since the "commit" operation is an atomic compare_and_swap, we ensure we won't run into race conditions. This differs from a stack with locks because some thread is always capable of making progress (modifying the stack).
However, the implementation on this slide is actually incorrect (due to the ABA problem), which we can see on the next slide.
This comment was marked helpful 0 times.
pradeep
This lock-free implementation of stack is different from using a spin lock to push and pop elements. This is because if we had used a spinlock, the thread holding a spinlock could end up blocking other threads needing to push and pop in scenarios such as when it gets a page fault.
Whereas in this case even if this happens other threads can still execute their compare and swap operation and the thread that got a page fault, comes back and fails its compare and swap and tries again.
This comment was marked helpful 1 times.
rokhinip
@tomshen, In a way, your comment reminds me of how transactional memory works in an optimistic manner. We assume we can make the change and before we commit to it, we make another check in TM and it is analogous to the CAS here.
This comment was marked helpful 1 times.
ruoyul
Note this works because compare_and_swap is atomic meaning no other thread can sneak in between the check of "whether other thread was modified by other thread" and actually committing the new change, therefore no race condition!
A lock-free stack is speculative: we assume that we're able to change the stack, and right before we actually "commit" the change, we check if another thread has modified the stack. If another thread has, then we "fail", and try again (which is why we have the while(1) loop). Since the "commit" operation is an atomic
compare_and_swap, we ensure we won't run into race conditions. This differs from a stack with locks because some thread is always capable of making progress (modifying the stack).However, the implementation on this slide is actually incorrect (due to the ABA problem), which we can see on the next slide.
This comment was marked helpful 0 times.
This lock-free implementation of stack is different from using a spin lock to push and pop elements. This is because if we had used a spinlock, the thread holding a spinlock could end up blocking other threads needing to push and pop in scenarios such as when it gets a page fault. Whereas in this case even if this happens other threads can still execute their compare and swap operation and the thread that got a page fault, comes back and fails its compare and swap and tries again.
This comment was marked helpful 1 times.
@tomshen, In a way, your comment reminds me of how transactional memory works in an optimistic manner. We assume we can make the change and before we commit to it, we make another check in TM and it is analogous to the CAS here.
This comment was marked helpful 1 times.
Note this works because compare_and_swap is atomic meaning no other thread can sneak in between the check of "whether other thread was modified by other thread" and actually committing the new change, therefore no race condition!
This comment was marked helpful 0 times.