This is really neat! The only modification of shared memory in each function is being protected by compare_and_swap. It should be noted that we are indeed reading from shared memory without any sort of guard (the assignment to old_top), but the C&S makes sure that this doesn't cause any issues on the write.

I know this an old lecture issue, but I generally get confused by C&S and how that is fully atomic. Does anyone have examples/a good explanation of that? And how that allows this to still be lock-free?

I think the compare_and_swap(v1, v2, n) = ret means if v1 == v2, then n is set to v1 and old value of v1 is returned.

@brianamb, compare and swap is generally implemented in hardware or as an instruction in part of the the processor's instruction set. For example, in x86-64, it is implemented using the CMPXCHG instruction (see https://www.felixcloutier.com/x86/cmpxchg for more details). Atomicity comes naturally from having compare-and-swap implemented as single instruction.

This is a great example of how a small instruction like CAS can be critical to the implementation of higher level and more complex abstractions. It's also an example of why the overhead of a more sophisticated implementation may be a reasonable tradeoff: the spin lock can generate a lot of traffic between CPU cores during periods of contention, and if there is always contention, then there is no guarantee that a waiting thread will eventually get its turn.

I wonder how this implementation would affect run-time since we essentially have a thread stalling. Would it be better if we allow the thread to do other work while it waits? Is it possible to do so?

@A bar cat I think that in a uniprocessor setting, a CAS is kind of unnecessary because there are better ways to implement this. If we move to a multiprocessor implementation, then it seems like a unavoidable situation that you will get some runtime issues, since it is essentially checking constantly for a value to change.