Consider the following two threads of a process, to be run concurrently in a sha
ID: 3805295 • Letter: C
Question
Consider the following two threads of a process, to be run concurrently in a shared memory (all variables are shared between the two threads): Assume the following: 1. a single-core system 2. load and store are atomic (i.e. they start and finish without interruption) 3. x is initialized to 0 before either thread starts, and 4. x must be loaded into a register before being incremented (and stored back to memory afterwards). The following questions consider the final value of x after both threads have completed. State the upper and lower bounds of value of x when both threads have completed. Explain your answer. Suppose we replace 'x = x + 2' in Thread B with an atomic double increment operation atomicIncr2(x) that cannot be preempted while being executed. What are ALL possible final values of x? Explain.Explanation / Answer
Ans:
(1a)upper_bound
-->Each x=x+1 statement can either do nothing (if erased by Thread B) or increase x by 1.
Each x=x+2 statement can either do nothing (if erased by Thread A) or increase x by 2.
Since there are 5 of each type, and since x starts at 0, x is >= 0 and x <= (5*1)+(5*2)=15
lower_bound
-->Every store into x from either Thread A or B is >= 0, and once x becomes >= 0, it stays at >= 0.
The only way for x=1 is for the last x=x+1 statement in Thread A to load a zero and store a
one. However, there are at least four stores from Thread A previous to the load for the last
statement, meaning that it couldn’t have loaded a zero.
(1b)Final values are 5, 7, 9, 11, 13, or 15. The x=x+2 statements can be “erased” by being
between the load & store of the x=x+1 statement. However since the "x=x+2" statements
are atomic, the x=x+1 statements can never_be “erased” because the load and store phases
of x=x+2 cannot be separated. Therefore final_value is at least 5 (from Thread-A) with from
0 to 5 successful updates of x=x+2.