Multicore & Synchronization

Learn about the MESI protocol, memory consistency models, atomic instructions such as CAS and LL/SC, locks and memory barriers, false sharing and data races with multiple-choice questions.

—Your accuracy
0 / 50Questions answered
Practice this topicAll questions in this topic, in random order Weak questionsRetry only the questions you last got wrong

Multicore & Synchronization: key points

In a multicore CPU, several cores on one chip share the same memory while each keeps its own caches. Coherence protocols such as MESI manage cache-line states so that no core keeps using stale data after another core writes it.

Beyond that, you need to understand memory consistency models, which define the order in which writes become visible to other cores, atomic instructions that let cores update values safely, and locks and memory barriers. This topic also covers pitfalls such as false sharing and data races, which make programs that look correct run slowly or misbehave.

All Multicore & Synchronization questions (50)

  1. Two cores each hold a copy of variable x in their own caches. After core 0 writes x, what problem could occur when core 1 reads x if there were no cache coherence mechanism?
  2. Which correctly lists the four states of the MESI cache coherence protocol?
  3. In the MESI protocol, what does it mean when a cache line is in the Modified (M) state?
  4. In the MESI protocol, what happens when a core writes to a line it holds in the Exclusive (E) state?
  5. In an invalidation-based coherence protocol, what happens when a core writes to a line in the Shared (S) state?
  6. In MESI, when core 1 tries to read a line that core 0 holds in the Modified (M) state, what generally happens?
  7. Which describes the snooping approach to cache coherence?
  8. Why do systems with many cores use directory-based coherence instead of snooping?
  9. Coherence protocols can be invalidation-based or update-based. Why do most CPUs use invalidation?
  10. Which describes false sharing in a multithreaded program?
  11. False sharing occurs with an array of per-thread counters such as "long cnt[8];". What is the most suitable fix?
  12. Which describes a data race?
  13. When two threads run the code above simultaneously, the final counter can be less than 200000. Why?
  14. Which describes an atomic instruction?
  15. What does the atomic CAS (compare-and-swap) instruction do?
  16. The code above doubles the shared variable counter using CAS(&p, expected, new). When does the CAS fail so the loop repeats?
  17. With an instruction pair such as RISC-V LR/SC (load-reserved / store-conditional), when does the SC fail?
  18. Which describes the ABA problem that affects lock-free data structures built with CAS?
  19. What does a fetch-and-add instruction, such as RISC-V amoadd.w or x86 lock xadd, do?
  20. Which describes a spinlock?
  21. In which situation is a spinlock least suitable?
  22. 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?
  23. Which correctly compares a mutex (a lock that sleeps while waiting) with a spinlock?
  24. Which is an example of deadlock?
  25. In a program using several locks, what is the most common way to prevent deadlock?
  26. What does a memory consistency model define?
  27. Which describes sequential consistency?
  28. The two threads above run simultaneously on different cores (assume no compiler reordering). Which outcome cannot occur under sequential consistency but can occur on real CPUs such as x86?
  29. What is a characteristic of the x86 memory consistency model (TSO, total store order)?
  30. Which statement is correct about weak memory consistency models such as those of Arm and RISC-V (RVWMO)?
  31. What is the role of a memory barrier (fence) instruction?
  32. In the code above, thread 1 prepares data and then signals with flag, and thread 2 waits for flag and then reads data. On a CPU with a weak memory model, what is needed for thread 2 to reliably read 42?
  33. Which statement is correct about memory operations with acquire and release semantics?
  34. In C, why is marking a flag variable shared between threads volatile not sufficient for synchronization?
  35. Why do C11 _Atomic and C++11 std::atomic let programmers specify a memory order?
  36. Which correctly compares coarse-grained locking (one lock for a whole large data structure) with fine-grained locking (separate locks for each part)?
  37. What property does a lock-free algorithm have?
  38. Which describes a critical section?
  39. Which describes barrier synchronization in parallel programs?
  40. When 64 cores continuously update one shared counter with atomic instructions, adding cores does not speed things up. What is the main reason?
  41. Which describes a NUMA (non-uniform memory access) system?
  42. 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?
  43. Which is NOT a reason a parallel program fails to scale as cores are added?
  44. When splitting loop iterations among threads, which division suits iterations whose costs vary widely?
  45. When several threads sum all elements of an array, which approach performs well?
  46. What is a characteristic of a reader-writer lock?
  47. What is the most suitable use of a counting semaphore?
  48. What is the difference between cache coherence and a memory consistency model?
  49. Which describes the idea of hardware transactional memory?
  50. When waiting on a condition variable until a queue becomes non-empty, why is the condition rechecked in a while loop rather than an if after waking?

Other topics in Computer systems