1
$\begingroup$

The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.

P1() {  

    C = B - 1;
    B = 2 * C;
}

P2(){  

    D = 2 * B; 
    B = D - 1; 
}

The set of distinct values that B can possibly take is ?
My understanding: Say P1 executes first , then B=2, after that P2 executes next then value of B=3. Again P1 executes and we get B value as 4, yet again B executes and we get B value as 7 etc. So does this mean B will take up infinitely many values? The order of my execution is P1-P2-P1-P2-P1.... Is this correct?

Improve this question
$\endgroup$
4
  • $\begingroup$ Each function is only executed once. The point of the exercise is that you cannot assume that either function executes completely in one go; you might first have the first line of P1, then the first line of P2, etc. $\endgroup$
    – Klaus Draeger
    Commented Jan 15, 2016 at 12:30
  • $\begingroup$ So concurrently executing means neither of the two functions can execute in one go , ever .But will preempt in between , right? So basically its non deterministic? $\endgroup$
    – bandit_king28
    Commented Jan 15, 2016 at 12:46
  • 1
    $\begingroup$ Yes, it is nondeterministic. $\endgroup$
    – Klaus Draeger
    Commented Jan 15, 2016 at 12:51
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented Jan 15, 2016 at 17:41

2 Answers 2

Reset to default
1
$\begingroup$

Label the four statements $$\begin{align} x &: C=B-1\\ y &: B=2C\\ z &: D=2B\\ w &: B=D-1 \end{align}$$ The only constraint is that $x$ must be executed before $y$ and $z$ must be executed before $w$, giving us six possible orders: $xyzw,xzyw,xzwy,zxyw,zxwy,xwzy$. Trace the execution of each of these possible orders and you'll find that $B$ can have a final value of $2$ (twice), $3$ (three cases), and $4$ (in one case).

For what it's worth, if P1 consists of $n$ assignments and P2 has $m$ assignments, the total possible orders is given by the binomial coefficient $\binom{n+m}{n}$, though that won't necessarily be the same as the number of possible final values of the shared variable $B$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Aren't you assuming that each of the statements you labelled is atomic, which would not be the case on any modern processor? $\endgroup$
    – gardenhead
    Commented Feb 1, 2016 at 21:33
  • $\begingroup$ @gardenhead Yup, the situation would be more complicated if the statements weren't atomic. My reading of the OP was that they were intended to be, since the translation to machine language would be more or less implementation-dependent. $\endgroup$
    – Rick Decker
    Commented Feb 1, 2016 at 21:55
1
$\begingroup$

Each of the two functions (P1 and P2) has two statements. Each statement is labelled as follows:

            function P1() {             function P2() {     
    T_0^0:    C = B – 1;        T_0^1:    D = 2 * B;        
    T_1^0:    B = 2 * C;        T_1^1:    B = D – 1;        
            }                           }

Assumptions:

  1. Every statement is atomic; it executes without pre-emption.
  2. There is one processor. When the processor is executing a statement it cannot be interrupted. After the statement executes, it can switch to executing any other statement that has not yet executed.
  3. Each of the functions executes once.

  4. Precedence constraints:

    o T_0^0 executes before T_1^0 executes.

    o T_0^1 executes before T_1^1 executes.

  5. The initial values of B, C and D are 2, 0 and 0 respectively.

To answer the question “what are the possible values of B?”

  1. List all possible execution sequences

    a. T_0^0  T_1^0  T_0^1  T_1^1

    b. T_0^0  T_0^1  T_1^0  T_1^1

    c. T_0^0  T_0^1  T_1^1  T_1^0

    d. T_0^1  T_1^1  T_0^0  T_1^0

    e. T_0^1  T_0^0  T_1^1  T_1^0

    f. T_0^1  T_0^0  T_1^0  T_1^1

  2. Compute the value of B for every execution sequence. To assist in this computation, an interactive, dynamic Petri Net model of the computation was created (see Figure 1): to execute a statement, click on a green square. An interactive, dynamic source code of the computation was also provided (see Figure 2): to execute a statement, click on a green rectangle. [For the PDF version of this reply, the figures are interactive, dynamic diagrams.]

Figure 1 enter image description here

Figure 2 Please see PDF version of this reply

Thus, the possible values of B, C and D are:

Computation Sequence                B   C   D   
T_0^0  T_1^0  T_0^1  T_1^1     3   1   4 
T_0^0  T_0^1  T_1^0  T_1^1     3   1   4 
T_0^0  T_0^1  T_1^1  T_1^0     2   1   4 
T_0^1  T_1^1  T_0^0  T_1^0     4   2   4 
T_0^1  T_0^0  T_1^1  T_1^0     2   1   4 
T_0^1  T_0^0  T_1^0  T_1^1     3   1   4
Improve this answer
$\endgroup$

Your Answer

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

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