Multicore & Synchronization

What property does a lock-free algorithm have?

  1. AEven if some thread stops partway, at least one of the other threads can still make progress
  2. BEvery thread always finishes in a fixed number of steps
  3. CShared data is updated without any atomic instructions
Show answer and explanation

Answer: A. Even if some thread stops partway, at least one of the other threads can still make progress

With locks, if the holder is stalled by an interrupt or low priority, everyone else waits. A lock-free algorithm updates shared data directly with CAS or similar, arranged so that a thread fails and retries only when some other thread has succeeded. As a whole, some thread always makes progress. Building one correctly is hard, though, and pitfalls such as the ABA problem must be handled.

  • A. Correct. There is no thread that can stall everyone while holding a lock.
  • B. That is the stronger wait-free property.
  • C. It is built with atomic instructions such as CAS.
Practice this topic Back to topic

More Multicore & Synchronization questions

  1. Which describes a critical section?
  2. Which describes barrier synchronization in parallel programs?
  3. When 64 cores continuously update one shared counter with atomic instructions, adding cores does not speed things up. What is the main reason?
  4. Which describes a NUMA (non-uniform memory access) system?
  5. Under the first-touch policy common on Linux NUMA systems (a page is placed in the memory of the node where the thread first writing it runs), what should programmers watch out for?