Multicore & Synchronization

Which describes the ABA problem that affects lock-free data structures built with CAS?

  1. ATwo threads A and B can only run alternately
  2. BWhen a value changes from A to B and back to A, CAS fails to notice the change and succeeds
  3. CTwo locks A and B are taken in opposite orders
Show answer and explanation

Answer: B. When a value changes from A to B and back to A, CAS fails to notice the change and succeeds

Suppose a linked list's head pointer is A. While one thread reads A and prepares a CAS, other threads remove A, do work involving B, and reinsert a node at the same address A. The CAS succeeds because the value is still A, but the list has already changed and its structure is corrupted. It is prevented by pairing the pointer with a modification counter compared together, or by using LR/SC.

  • A. It is not about execution order.
  • B. Correct. It is a weakness of CAS comparing values only.
  • C. That causes deadlock.
Practice this topic Back to topic

More Multicore & Synchronization questions

  1. What does a fetch-and-add instruction, such as RISC-V amoadd.w or x86 lock xadd, do?
  2. Which describes a spinlock?
  3. In which situation is a spinlock least suitable?
  4. Why does a spinlock usually wait with ordinary reads and use an atomic instruction only when the lock looks free (test-and-test-and-set), instead of retrying the atomic write directly?
  5. Which correctly compares a mutex (a lock that sleeps while waiting) with a spinlock?