GATE CSE 2015 | Set 1 | Question: 9

Question

The following two functions $P1$ and $P2$ that share a variable $B$ with an initial value of $2$ execute concurrently.
$$\begin{array}{|l|l|}\hline  \text{P1() \{ } & \text{P2()\{} \\  \text{ C = B - 1;} & \text{ D = 2 * B; } \\  \text{ B = 2 * C;} & \text{ B = D - 1;} \\ \text{\}} & \text{\}} \\\hline \end{array}$$
The number of distinct values that $B$ can possibly take after the execution is______________________.

Comments

read question care fully it is asked for distict value of B not whole program distinct value this cane be the silly mistake i made this miskake during test

toatl 4 distinct value that is 1,2,3,4

and B having 3 distinct value that is 4,3,2

---

Similar question instead of two functions it is given two threads:

Operating System: GATE CSE 2024 | Set 1 | Question: 30

---

It's so Simple with cases :

Case 1 : P1 then P2 (executes serially). In this order B will be 3.

Case 2 : P2 then P1 (serially). In this order B will be 4.

Case 3 : when both P1, P2 read the same value B=2, but write one after the other.

 1) P1 writes first then P2. In this case P1's B value(B=2) will be overwrite by P2(B=3). So at last B will be 3.

 2) P2 writes first then P2. In this case P2's B value(B=3) will be overwrite by P1(B=2). So at last B will be 2.

hence B can be 2,3, or 4.

So 3 unique values of B possible.

Answer 1

$3$ distinct values $\{2,3,4\}$
$$\begin{array}{|ll | l| }\hline & \text{P1() \{ } & \text{P2()\{} \\  a. &\text{ C = B - 1;} & \text{ D = 2 * B; } \\b.&  \text{ B = 2 * C;} & \text{ B = D - 1;} \\& \text{\}} & \text{\}}\\\hline \end{array}$$

1. $P1_{a}\to P1_b \to P2_{a} \to P2_b \implies B = 3$
2. $P2_a\to P2_b \to P1_a \to P1_b  \implies B = 4$
3. $P1_a \to P2_a \to P2_b \to P1_b \implies B = 2$

Comments

P1 1st statement executed: B = 1

P2 1st statement executed B = 2

P2 2nd statement executed B = 1 (But before store operation, preemption)

P1 2nd statement complete B = 4

P2 2nd statement, remaining store operation done, B = 1

total 4 distinct values, 1, 2, 3, 4

---

there is also possible case of p2-p1-p2 whose value can be 7.Is this right? anyone can explain it?

---

@nikhil856 you are taking it in a wrong way . From third option he meant that execute first line of P1 and then execute entire P2 and then execute last line of P1.

@Lakshman Patel RJIT Sir @Arjun Suresh Sir please write the explanation for B = 2 in detail because from the answer it is inferring that we first execute P1 and then P2 and then again P1 which is not the case.

Answer 2

Let P1(){ A, B } and  P2(){ 1, 2 }

Now possible sequence and value of variables B, C and D are as follow -->

1. A B 1 2   {3,1,4}
2. A 1 B 2   {3,1,4}
3. A 1 2 B   {2,1,4}
4. 1 A B 2   {3,1,4}
5. 1 A 2 B   {2,1,4}
6. 1 2 A B   {4,2,4}

So Number of distinct values that B can possibly take after the execution is 3 {2,3,4}.

PS: Little bit long but error free method. 

Comments

Ok... but premitives of statements such as W(S1) ∩ W(S2) = { } itself is not satisfying. Then no scope of correct results.

---

S1 and S2 are sequential they don't need bernstien's condition i suppose. It is in sequence 1324 { considering 1, 2 belongs to p1 and 3,4 belongs to P2} that they violate concurrency conditions of bernstiens when 3 &2 are executed concurrently. This is my understanding and i want to clarify whether i'm thinking in right direction or not?

---

Nice Explanation !!

Some mathematical spices for the above solution (if anybody not getting )

1) Just apply combinatorial concept permutations where specific elements must maintain a fixed relative order.

$\binom{n}{k} = \frac{n!}{k!(n-k)!} \implies \binom{4}{2} = 6$

or 

2) Just Apply Division concept 

If you have multiple independent constrained groups of sizes $k_1, k_2, \dots$, you divide the total permutations by the factorial of each group's size:

$\text{Total Valid Permutations} = \frac{n!}{k_1! \times k_2! \times \dots}$

Answer 3

We have to calculate values of B for every possible case

Comments

i also used same approach, is threre any shortcut?

Answer 4

Order Of Execution : B  value

P1-P2: B = 3
P2-P1: B = 4
P1-P2-P1: B = 2
P2-P1-P2: B = 3

Total distinct values  {2,3,4}.

Comments

hi,

i am confused with last format i.e., p2-p1-p2

p2{b=3} p1{b=4} p2{b=7(bcz from the previous process execution b=4,d=4*2,b=d-1 ie.,8-1=7)so how it will be b having only 3 distinct numbers please answer for this!!!!!!!!!!!!!!!!!!!!!!!

---

Here P2 P1 P2 actually means P2 line1, P1 line1, P1 line2, P2 line2 ..

i.e  [P2: D],  premption, [ P1: C, B] ,preemption, [P2: B]

By this u will get 3

Answer 5

Observe closely, In both P1 and P2 writing to B is happening only at second(final) statement.

---

Case I: P2 value get's overwritten by P1 $\Rightarrow$ Only P1

It's like in effect only P1 executes. With B=2 as initial value, final value will be 2.

Case II: P1 value gets overwritten by P2 $\Rightarrow$ Only P2

With B=2 as initial value final value will be 3.

Case III: P2 executes first and writes the value which is read by P1 $\Rightarrow$ P2 then P1

P2 writes 3 as in Case II. With B=3 P1 writes final value 4.

Case IV: P1 executes first and writes the value which is read by P2 $\Rightarrow$ P1 then P2

P1 writes value 2 as in Case I which is same as initial value. So as in Case II P2 writes final value 3 with initial value 2.

---

So in effect there are only 3 possible values which are {2,3,4}. Answer: 3

Comments

I have done it using Permutation and Combination way. So we know that 6 possible cases are there in case of P1 and P2 to execute concurrently. Then all 6 cases were giving only 3 distinct values as mentioned below. Hence '3' is the answer.

Answer 6

Since no while loops are present, only 2 values are taken by B.

P1- P2 : 3

P2 - P1: 4

Answer: 2