1
$\begingroup$

suppose Threads 1 and 2 are executing concurrently with shared integer variables A, B, and C. Thread 1 executes:A=4, B=5, C=B-A; Thread 2 executes: A=3, B=6, C=A+B;

I'm trying to find what can the possible values of C be after execution of this fragment when synchronization is not implemented.

I know if there is no synchronization then the reads see writes that occur later in the execution order and it will be counter intuitive ( execution will be happens-before consistency)

I am confused what can be the possible values of C. Can the possible values for C be 1,2,3,8,9,10 after substituting the all possible values for A & B from both thread 1 and thread 2 for C=B-A & C=A+B

$\endgroup$
2
  • 1
    $\begingroup$ What do you think? Can you come up with executions supporting your set of possible values? Can you show that no other possible values are possible? $\endgroup$ Apr 2, 2014 at 17:33
  • $\begingroup$ @YuvalFilmus. I came up with thread 1 executed A=4, B=5, C becomes B-A = 1, thread 2 executed A=3, B=6, C=A+B= 9, likewise in execution A=4, B=6 ,C=B-A=2;A=3, B=5, C=B-A =2; $\endgroup$
    – robert
    Apr 2, 2014 at 20:08

1 Answer 1

1
$\begingroup$

Hint: Let $C = B \pm A$ be the final instruction being executed. Clearly $A \in \{3,4\}$ and $B \in \{5,6\}$, and this shows that $C \in \{1,2,3,8,9,10\}$. For the other direction, show that by carefully scheduling both threads, you can choose which of $C = B \pm A$ is executed last, and choose the value that $A$ and $B$ get prior to that instruction being executed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.