Skip to content
Get started

How low can a racy counter go?

A shared integer c starts at 0. Two threads each execute c++ exactly 10 times, where each c++ is compiled to two separate steps: r = c (load into a private register) then c = r + 1 (store). The scheduler may interleave the steps of the two threads arbitrarily. What is the smallest possible final value of c?

Show hints (3)+
  1. A thread can load a value, sleep for a long time, then store a stale result.
  2. Try to make each thread overwrite almost all of the other's work once.
  3. For the lower bound, look at the load of the final iteration of whichever thread stores last.

Answer

Reveal answer →

2

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions