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

In summary, the ABA problem is caused by the value being used to check the state of a shared structure not actually being unique (i.e. the structure could have changed but the value compared still looks the same.)


ABA problem: during synchronization, the locations are read twice and tricked into thinking that "nothing has changed" although its possible that in between the reads, additional work could have been done and fools the first thread into thinking nothing has changed, thus corrupting the structure.

thread 0) POP(): old_top = A, new_top = B.

thread 1) POP(): old_top = A, new_top = B.

thread 1) // complete pop A, and set head to B

thread 1) PUSH(D): old_top = B, new_top = D

thread 1) // complete push D, and set head to D

thread 1) PUSH(A): old_top = D, new_top = A

thread 1) // complete push A, and set head to A

thread 0) // complete pop A and set new_top to B, head is now B ***

** Note that t0 still sees old_top = A, new_top = B, so it sets the new_top to B assuming that the information hasn't changed, but it doesn't realize that there was work done before and completely loses the information of the previous operations. As a result the stack structure is corrupted because we lose the work done by t1 of push(D).


ABA problem happens in one while loop iteration. cross-iteration doesn't yield this problem since the new top is fetched in each iteration.


ABA problem happens when the shared linked list's value is modified by one locally, but compared using another thread which looks like the value compared has stayed the same.


From wikipedia:

A common case of the ABA problem is encountered when implementing a lock-free data structure. If an item is removed from the list, deleted, and then a new item is allocated and added to the list, it is common for the allocated object to be at the same location as the deleted object due to optimization. A pointer to the new item is thus sometimes equal to a pointer to the old item which is an ABA problem.


To insert a node into the linked list, we first allocate memory through the "malloc" function. To delete the node, we use the "free" function. The ABA problem in this case would be similar to first freeing a node and then a subsequent malloc returns the same memory address which was freed in one of the previous delete operations.


Another way to think about the ABA problem is making an incorrect decision about safety based on a shallow notion of equality


The ABA problem can be solved if another mechanism is involved to ensure that memory not being available to threads and reused too early before no threads are holding reference to that memory.


The ABA problem happens because, whether the top changes doesn't guarantee whether the stack changes. Even if the top remains the same, the stack may have changed already.


A non-CS example of the ABA problem is if you're driving and stopped at a red light. Then, you turn to talk to a friend and then later turn back to see that the light is still red. You think that the light hasn't changed but, while you were turned, the light actually turned green and back to red.