...
The following sequence of operation occurs.:
Thread | Queue Before | Operation | Queue After |
|---|
T1
| head -> A -> B -> C -> tail
| Enters queue_dequeue() function
head = A, tail = C
next = B
after executing data = next->data;
This thread gets preempted | head -> A -> B -> C -> tail
|
T2
| head -> A -> B -> C -> tail
| Removes node A | head -> B -> C -> tail
|
T2
| head -> B -> C -> tail
| Removes node B | head -> C -> tail
|
T2
| head -> C -> tail
| Enqueues node A back into the queue | head -> C -> A -> tail
|
T2
| head -> C -> A -> tail
| Removes node C | head -> A -> tail
|
T2
| head -> A -> tail
| Enqueues a new node D
After enqueue operation, thread 2 gets preempted | head -> A -> D -> tail
|
T1
| head -> A -> D -> tail
| Thread 1 starts execution
Compares the local head = q->head = A (true in this case)
Updates q->head with node B (but node B is removed) | undefined {} |
...
In this compliant solution, mtx_lock() is used to lock the queue. When thread 1 locks on the queue to perform any operation, thread 2 cannot perform any operation on the queue, which prevents the ABA problem.
...
See the FireEye Anti-Malware and Anti-Botnet Security tool as an example.
...
