Unlocked Multi-threaded Variable Incrementation

You have two threads incrementing the same variable in parallel. Graph the possible outputs overtime.

Problem Statement

You have a class in Java, of which you have an instance. A method on this class is defined as: void foo() { while (true) print (x++); } where x is a member of the class, which is initialized to zero. You invoke this method once from each of the two threads t0 and t1. Graph the possible outputs of t0 and t1 over time.

Evaluation

  • Coming up with a meaningful representation of how the two threads write to console over time (25%)
  • Noting whether duplicate outputs are possible (25%)
  • Noting whether the output from one thread only increments or could also decrement (25%)
  • Concise explanation of how x++ is implemented and exactly how multiple threads are behaving inside it (25%)

References

Vlad, a software architect at Lionside, a Bay Area gaming startup, asked me this during an interview

Author
Amin Ariana
Published
September 2010