0
$\begingroup$

This question is from Patterson and Hennessy's Computer Organization and Design.

Consider the following portions of two different programs running at the same time on four processors in a symmetric multicore processor (SMP). Assume that when this code is run, both $x$ and $y$ are 0.

Core 1: $x = 2$;

Core 2: $y = 2$;

Core 3: $x = x + 1$;

Core 4: $z = x + y$;

What are all the possible resulting values of $x$, $y$, and $z$? You will need to examine all possible interleaving of instructions.

The given answer is, for $(x, y, z)$: $(3, 2, 5), (3, 2, 4), (3, 2, 3), (3, 2, 2), (3, 2, 0), (2, 2, 4), (2, 2, 3), (2, 2, 2), (2, 2, 1), (2, 2, 0).$

I understand how $x$ is either 2 or 3 and why $y$ is forced to be 2, but I don't know how $z$ takes those values.

$\endgroup$
  • 3
    $\begingroup$ Welcome to CS.SE! What have you tried? What are your thoughts? What values do you think $z$ can take on? What approaches have you considered, for figuring out the answer, and what happened when you tried following those approaches? Please edit your question to show your thoughts. We expect you to make every effort to solve it on your own before asking, and to show us in the question what you've tried/considered. $\endgroup$ – D.W. Dec 17 '15 at 21:16
  • $\begingroup$ See also stackoverflow.com/q/31838588/781723. $\endgroup$ – D.W. Dec 17 '15 at 22:33
  • 4
    $\begingroup$ What's the memory model? $\endgroup$ – Raphael Dec 17 '15 at 23:07
  • $\begingroup$ Which values of z confuse you (and why) and which make sense? $\endgroup$ – djechlin Dec 18 '15 at 0:19
  • 2
    $\begingroup$ @user43335, I suspect you should be able to delete the post (if you wish) as there are no answers... though in this situation another solution is to write an answer to your own question, if you think anyone else might be in the same situation in the future. $\endgroup$ – D.W. Dec 18 '15 at 4:46
1
$\begingroup$

x has 4 possible values throughout the execution of the program, but only two after execution is finished. x could be x = 2, or x = 0 + 1, or x = 2 + 1, or x = 0. If x = 0 + 1 executes first, then x = 2 executes second and x will be 2, but if x = 2 executes first, then x will be 3. But z could either receive 0, 1, 2, or 3 for x. Y is only ever either 0 or 2, with 2 being the value at the end always. So you have z = 3 + 2, z = 2 + 2, z = 1 + 2, z = 0 + 2, z = 3 + 0, z = 2 + 0, z = 1 + 0, or z = 0 + 0.

$\endgroup$
  • $\begingroup$ You are assuming that x = x + 1 is an atomic operation, which is very unlikely to be true. Usually x = x + 1 will be implemented as "read x, add 1 to the value read, write the sum to x". It is quite possible that the assignment x = 2 happens between reading x = 0 and writing x = 1. $\endgroup$ – gnasher729 Dec 5 '16 at 8:44

Your Answer

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

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