Even without inserting D, this way of interleaving is still problematic because A may contain a different value the second time.
jrgallag
Restating my question from lecture: can we use Load Linked/Store Conditional on the value of top to avoid the ABA problem? Prof. Kayvon's intuition was that this wouldn't work, but we couldn't come up with a reason why.
I did a little research on this issue, and it seems like this is possible in theory, but in practice most implementations of LL/SC are not sufficient:
"However, for practical architectural reasons, none of the architectures that support LL/SC (Alpha, MIPS, PowerPC) support VL or the ideal semantics of LL/SC as defined above. None allows nesting or interleaving of LL/SC pairs, and most prohibit any memory access between LL and SC. Accordingly, the restricted semantics of LL/SC supported in practice offer no or little help with preventing the ABA problem."
In our example, we would need to interleave LL/SC instructions to allow concurrent access without locks.
The ABA problem is caused in this case because the CAS uses "top is equal to old value" to indicate nothing has changed, while in fact the stack has changed despite that top is equal to the same value as before. Thus despite that the stack has changed, the CAS proceeds successfully, which is unintended and results in corrupting the stack.
stl
An example of the ABA problem is when a thread reads a shared variable and sees it's A, another thread comes in and makes changes to that variable and ultimately changes that variable back to A, and then the first thread comes back in, sees the value A and assumes that nothing has been changed so it proceeds with the CAS, when in fact it shouldn't have been able to do the CAS. With lock-free data structures, this can happen if some item is removed, and another is added in and has the same address as the removed item, the pointer to the new object will be equal to the pointer of the old object.
yikesaiting
I agree with @stl. To go further, we need some invariant attributes to tell us whether 'nothing has happened to this data structure' in the previous time.
qqkk
This problem occurs because CAS only checks the element on the top. If it remains same, program will think no operation happened and CAS will succeed. However in reality, even if the top element is the same, the elements below top still might be changed already.
Even without inserting D, this way of interleaving is still problematic because A may contain a different value the second time.
Restating my question from lecture: can we use Load Linked/Store Conditional on the value of top to avoid the ABA problem? Prof. Kayvon's intuition was that this wouldn't work, but we couldn't come up with a reason why.
I did a little research on this issue, and it seems like this is possible in theory, but in practice most implementations of LL/SC are not sufficient:
"However, for practical architectural reasons, none of the architectures that support LL/SC (Alpha, MIPS, PowerPC) support VL or the ideal semantics of LL/SC as defined above. None allows nesting or interleaving of LL/SC pairs, and most prohibit any memory access between LL and SC. Accordingly, the restricted semantics of LL/SC supported in practice offer no or little help with preventing the ABA problem."
In our example, we would need to interleave LL/SC instructions to allow concurrent access without locks.
Source: IBM Research
The ABA problem is caused in this case because the CAS uses "top is equal to old value" to indicate nothing has changed, while in fact the stack has changed despite that top is equal to the same value as before. Thus despite that the stack has changed, the CAS proceeds successfully, which is unintended and results in corrupting the stack.
An example of the ABA problem is when a thread reads a shared variable and sees it's A, another thread comes in and makes changes to that variable and ultimately changes that variable back to A, and then the first thread comes back in, sees the value A and assumes that nothing has been changed so it proceeds with the CAS, when in fact it shouldn't have been able to do the CAS. With lock-free data structures, this can happen if some item is removed, and another is added in and has the same address as the removed item, the pointer to the new object will be equal to the pointer of the old object.
I agree with @stl. To go further, we need some invariant attributes to tell us whether 'nothing has happened to this data structure' in the previous time.
This problem occurs because CAS only checks the element on the top. If it remains same, program will think no operation happened and CAS will succeed. However in reality, even if the top element is the same, the elements below top still might be changed already.