Is there a way to find out number of different values that a shared variable can take in concurrent computing, in general, without listing all the possibilities and then counting the ones that are different (like done in two examples below)?

I know that, it is possible to count number of ways in which atomic operation(s) of n different threads can be interleaved. It is also possible to find those values. For example,

  1. The number of ways in which statements(s) of the two threads can be interleaved is 6 and the number of values that shared variable $B$ can take is 3, they are 85, 75, and 110. (Note that despite their unitary appearance, a program statement (READ B or WRITE B) is actually composite) enter image description here Image taken from Principles of Computer System Design An Introduction Part 2 by Saltzer and Kaashoek
  2. The number of different values shared variable c can take in this concurrent execution of two threads is 5. Since Thread 1 code has conditionals, I am not sure about the number of ways in which operation(s) of the two threads can be interleaved. Is the value equal to $\frac{4!}{2!2!}$?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.