Previous | Next --- Slide 26 of 37
Back to Lecture Thumbnails

In effect, this lock-free stack just make sure that the thread will check whether the stack has been changed from the time when this thread read it until modify it. If changed, then re-execute the operation, otherwise just complete the execution.


Slide 21 says 'An algorithm that uses locks is blocking regardless of whether the lock implementation uses spinning or pre-emption'. Does that mean if I use lock to implement compare_and_swap, the stack implementation of this slide becomes a blocking algorithm?


I suppose so, but the convention is that CAS is a hardware instruction (or an atomic set of instructions).


Note that a lock-free stack isn't the most interesting because there isn't much concurrency (reads and writes occur in the same place on the stack). Anyways, so this code looks at the top, keeps the current state of the top. Performs its operations, and then commits by rewriting the top. It performs CAS, and if the top is the same, it believes that the stack has not been modified. However, this is not always true! Consider this: we pop the top pointer, pop some more elements, put elements back on, and then put the top pointer back. This is the ABA problem. The state of the stack seems the same, but it is not.


Without CAS, we could encounter the problems with inserting and deleting from linked list on previous slides.