Here when thread 0 is about to do the initial pop, its local values of old_top is A and new-top is B. Suppose lets say at this point just before popping, it got swapped out and thread 1 starts executing. Thread 1 further goes on to pop A and then Push D and push the A back again. Now lets say thread 0 is context switched again. Now from thread 0's view the old_top is still A and hence the compare and swap passes. This leads to B replacing A and hence we effectively end up losing D all together.
p.s. Important thing to note is do not consider A, B, C as values but rather the address location of these nodes.
This comment was marked helpful 0 times.
black
Yes, it's important to remember the assumption that A and B are both addresses. It means when Thread 1 pushed A back into stack, Thread 0 though it's still the same node. Counter of number of pop is one solution of this situation. But I think in most cases, programmers prefer to pass a new copy of the value or object into stack, rather than the reference. So, I think's this situation won't happen much, hopefully!
This comment was marked helpful 0 times.
retterermoore
Why would the fact that they're passing values rather than references solve the problem? It seems like we could still have lots of problems, for instance both threads get A when they call pop in parallel, whereas your program would probably want one thread to get A and one thread to get the next element in the stack. I also don't think the problem referred to in the slides is fixed by passing values, only the problem where A could get a different value passed to it.
This comment was marked helpful 0 times.
benchoi
A helpful story that illustrates the ABA problem (in real life!) can be found on Wikipedia!
This comment was marked helpful 2 times.
iamk_d___g
I think the main reason why ABA problem occurs is that we only get a promise "the head isn't changed", which doesn't ensure anything happens beyond the scope. But a lock on the list ensures no concurrent operation will be performed while some process is holding it.
Here when thread 0 is about to do the initial pop, its local values of old_top is A and new-top is B. Suppose lets say at this point just before popping, it got swapped out and thread 1 starts executing. Thread 1 further goes on to pop A and then Push D and push the A back again. Now lets say thread 0 is context switched again. Now from thread 0's view the old_top is still A and hence the compare and swap passes. This leads to B replacing A and hence we effectively end up losing D all together.
p.s. Important thing to note is do not consider A, B, C as values but rather the address location of these nodes.
This comment was marked helpful 0 times.
Yes, it's important to remember the assumption that A and B are both addresses. It means when Thread 1 pushed A back into stack, Thread 0 though it's still the same node. Counter of number of pop is one solution of this situation. But I think in most cases, programmers prefer to pass a new copy of the value or object into stack, rather than the reference. So, I think's this situation won't happen much, hopefully!
This comment was marked helpful 0 times.
Why would the fact that they're passing values rather than references solve the problem? It seems like we could still have lots of problems, for instance both threads get A when they call pop in parallel, whereas your program would probably want one thread to get A and one thread to get the next element in the stack. I also don't think the problem referred to in the slides is fixed by passing values, only the problem where A could get a different value passed to it.
This comment was marked helpful 0 times.
A helpful story that illustrates the ABA problem (in real life!) can be found on Wikipedia!
This comment was marked helpful 2 times.
I think the main reason why ABA problem occurs is that we only get a promise "the head isn't changed", which doesn't ensure anything happens beyond the scope. But a lock on the list ensures no concurrent operation will be performed while some process is holding it.
This comment was marked helpful 0 times.