6.7 Consider the following portions of two different programs running at the sam
ID: 3807499 • Letter: 6
Question
6.7 Consider the following portions of two different programs running at the same time on four processors in a symmetric multicore processor (SMP). Assume that before this code is run, both x and y are 0.
Core 1: x = 2;
Core 2: y = 2;
Core 3: w = x + y + 1;
Core 4: z = x + y;
6.7.1 [10] <§6.5> What are all the possible resulting values of w,x,y, and z? For each possible outcome, explain how we might arrive at those values. You will need to examine all possible inter-leavings of instructions.
6.7.2 [5] <§6.5> How could you make the execution more deterministic so that only one set of values is possible?
Explanation / Answer
6.7 ANSWER:
6.7.1:
As there are the 4 processors that are executing in the parallel, there are all-together 24 combinations which can be made.
As this is the case of interleaving, the execution of the program can jump from one processor to another processor at any time after
the instruction have been executed.
SInce the value of X and Y are zero before the program runs,the final values after the each combinations runs are as follows:-
Case -1: Execution steps (3,2,1,4) i.e Core-3 executes first and then second and forst and at last core-4.
a)When core-3 runs then the value of the x is updated i.e x=1.
b)core-2 runs the value of y becomes 2 i.e y=2.
c)core-1 runs the value of x again becomes 2 i,e x=2.
d)Core-4 runs the value of z becomes 4 because z=x+y i.e z=4.
Case-2: Execution steps (1,2,3,4)
a) Core-1 runs value of x=2
b)core-2 runs, value of y=2.
c)core-3 runs, value of x=3.
d) core-4 runs,value of z=5
Case-3: Execution steps (4,3,2,1)
a) core-4 runs,value of z=0 because the initial values of x and y before the program execution is '0'.
b) core-3 runs,tvalue of x=1.
c) core-2 runs, value of y=2.
d) core-1 runs,value of x updated i.e x=2.
Case-4: Execution steps (2,3,1,4)
a) Core-2 runs , the value of y=2.
b)COre-3 runs, the value of x=1.
c) Core-1 runs the value of the x updated i.e x=2.
d) core-4 runs, the value of z=4.
The values of X and Y are the updated values that are updated on the last run of the program.
Case-5 : Execution steps (3,4,2,1)
a) Core-3 runs, the value of x=1.
b)Core 4 runs , the value of z=1.
C) Core-2 executes, the value of y=2.
d)core-1 executes, the value of x updated i.e x=2.
Case-6: Execution steps(1,4,3,2)
a) core-1 executes , the value of x=2
b)core-4 executed, the value of z=2
c) core-3 executed, the value of x updated i.e x=3.
d) core-2 executed , the value of y=2.
Case-7: Execution steps(3,4,1,2)
a)core-1 executes,value of x=1.
b)core-2 executed,value of z=1.
c)core-3 executed,value of x updated i.e x=2.
d)core-2 executed, the value of y=2.
Case-8: Execution steps (2,4,1,3)
a)core-1 executed, the value of x=2.
b)core-4 executed,the value of z=2.
c)core-1 executed,the value of x=2(updated).
d)core-3 executed ,the value of x updated again i.e x=3.
Case-9: Execution steps(2,4,3,1)
a)core-2 executed , the value of y=2.
b)core-4 executed, the value of z=2.
c)core-3 executed,the value of x=1.
d)core-1 executed,the value of x=2.
Case-10: Execution steps (4,2,3,1)
a)core-4 executed,the value of z=0.
b)core-2 executed,the value of y=2.
c)core-3 executed,the value of x=1.
d)core-1 executed,the value of x=2.
Similarly we can carry out for the other combinations as well.
We can see that the value of X Y Z are different for the different combination of the executing processors, sometimes they could be the same.
But again, this is not guaranteed when there is interleaving of the processes.
6.7.2:
To make the execution more deterministic,one specific order of the execution should be decided.The result should be known so that the operation that are conflicting
can be carried out atomically so that it result in the one values for X,Y and Z.
Let as assume that all the processor have to run serially, i.e the Execution steps be like (1,2,3,4).
Thus, while executing one by one we will have the values of X,Y and Z equals to 3,2 and 5 respectively.
We can introduce the locking concept to prevent the anonymous execution of the processors.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.