I'm still confused why D is missing here. Can anyone explain it to me?
ericwang
In this example, the CAS compares old_top with current top and reset new top.
The old_top is set to A, which supposed to protect the current top from other modifications. Ideally, if other threads interrupt and modify the stack top, new top will not match old_top. So CAS fails. Then in the loop, this thread will reset old_top and try CAS again.
However, when the interrupt threads remove A first, and then add it back along with other nodes (the D), the top of the stack will still be A. So in the original pop thread, the CAS successes an the top is reset. But notice that the assumption that no modification happens before CAS is not true. D is inserted. The original pop thread doesn't realize that, and it resets the top to B directly.
In memory, D still exists. But no pointers in the stack structure is pointing to it. So it is missing.
cgjdemo
Thread 0 wants to do pop and the top element is A. Before the completion of this pop, Thread 1 pop A, push D and push A. Then Thread 0 begin the CAS and find out that the top element is A so Thread 0 think that the next element is still B, which is not true since the structure of the stack is now different. So Thread 0 set the top to be B, which unexpectedly removes D.
arjunh
Can anyone give an intuitive explanation of the ABA problem? A real-world example would be nice!
iZac
ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and "value is the same" is used to indicate "nothing has changed". However, another thread can execute between the two reads and change the value, do other work, then change the value back, thus fooling the first thread into thinking "nothing has changed" even though the second thread did work that violates that assumption.
A real world example:
Natalie is waiting in her car at a red traffic light with her children. Her children start fighting with each other while waiting, and she leans back to scold them. Once their fighting stops, Natalie checks the light again and notices that it's still red. However, while she was focusing on her children, the light had changed to green, and then back again. Natalie doesn't think the light ever changed, but the people waiting behind her are very mad and honking their horns now.
Another similar problematic situation is when threads are pushing non-distinct elements onto the stack.
rokislt10
This seems like the kind of subtle issue that causes terrible exploitable security issues. Especially since it is hard to detect, systems that use this flawed implementation would be vulnerable to intentional memory corruptions.
Faust
Another real world example of the ABA problem is when someone plants a bug in somebody's cell phone. Tom may be look at his phone, turn away to talk to his friend, and look at his cell phone and think nothing has changed. However, when Tom was talking to his friend, Elizabeth may have inserted a bug into his phone. When Jack looks back at his cell phone, he may think nothing has changed, but in reality, Elizabeth has altered the "value" of the phone.
Sherry
Example: L is playing WOW in her room, her mom goes to her room and check if L is studying (per 10 mins). Each time her mom comes in, L switches WOW to Visual Studio. Therefore, L's mom believes L is a very hardworking person.
HCN
If the stack stores distinct pointers that point to values, then will there be an ABA problem?
I'm still confused why D is missing here. Can anyone explain it to me?
In this example, the CAS compares old_top with current top and reset new top.
The old_top is set to A, which supposed to protect the current top from other modifications. Ideally, if other threads interrupt and modify the stack top, new top will not match old_top. So CAS fails. Then in the loop, this thread will reset old_top and try CAS again.
However, when the interrupt threads remove A first, and then add it back along with other nodes (the D), the top of the stack will still be A. So in the original pop thread, the CAS successes an the top is reset. But notice that the assumption that no modification happens before CAS is not true. D is inserted. The original pop thread doesn't realize that, and it resets the top to B directly.
In memory, D still exists. But no pointers in the stack structure is pointing to it. So it is missing.
Thread 0 wants to do pop and the top element is A. Before the completion of this pop, Thread 1 pop A, push D and push A. Then Thread 0 begin the CAS and find out that the top element is A so Thread 0 think that the next element is still B, which is not true since the structure of the stack is now different. So Thread 0 set the top to be B, which unexpectedly removes D.
Can anyone give an intuitive explanation of the ABA problem? A real-world example would be nice!
ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and "value is the same" is used to indicate "nothing has changed". However, another thread can execute between the two reads and change the value, do other work, then change the value back, thus fooling the first thread into thinking "nothing has changed" even though the second thread did work that violates that assumption.
A real world example:
Natalie is waiting in her car at a red traffic light with her children. Her children start fighting with each other while waiting, and she leans back to scold them. Once their fighting stops, Natalie checks the light again and notices that it's still red. However, while she was focusing on her children, the light had changed to green, and then back again. Natalie doesn't think the light ever changed, but the people waiting behind her are very mad and honking their horns now.
Source: Wiki
Another similar problematic situation is when threads are pushing non-distinct elements onto the stack.
This seems like the kind of subtle issue that causes terrible exploitable security issues. Especially since it is hard to detect, systems that use this flawed implementation would be vulnerable to intentional memory corruptions.
Another real world example of the ABA problem is when someone plants a bug in somebody's cell phone. Tom may be look at his phone, turn away to talk to his friend, and look at his cell phone and think nothing has changed. However, when Tom was talking to his friend, Elizabeth may have inserted a bug into his phone. When Jack looks back at his cell phone, he may think nothing has changed, but in reality, Elizabeth has altered the "value" of the phone.
Example: L is playing WOW in her room, her mom goes to her room and check if L is studying (per 10 mins). Each time her mom comes in, L switches WOW to Visual Studio. Therefore, L's mom believes L is a very hardworking person.
If the stack stores distinct pointers that point to values, then will there be an ABA problem?