GATE CSE 2023 | Question: 28

Question

Consider the two functions $\textsf{incr}$ and $\textsf{decr}$ shown below. 

incr(){             decr(){
    wait(s);            wait(s);
    X = X+1;            X = X-1;
    signal(s);          signal(s);
}                   }    

There are $5$ threads each invoking $\textsf{incr}$ once, and $3$ threads each invoking $\textsf{decr}$ once, on the same shared variable $\mathrm{X}$. The initial value of $\mathrm{X}$ is $10.$

Suppose there are two implementations of the semaphore $\text{s},$ as follows:

$\textbf{I-1:} \;\mathrm{s}$ is a binary semaphore initialized to $1.$
$\textbf{I-2:}\; \mathrm{s}$ is a counting semaphore initialized to $2.$

Let $\text{V1, V2}$ be the values of $\text{X}$ at the end of execution of all the threads with implementations $\textbf{I-1, I-2},$ respectively.

Which one of the following choices corresponds to the minimum possible values of $\text{V1, V2},$ respectively?

• A. $15,7$
• B. $7,7$
• C. $12,7$
• D. $12,8$

Comments

The code to prove the minimum possible is 8:

```

import itertools

array = ['i', 'i', 'i', 'i', 'i', 'd', 'd', 'd']

permutations = list(itertools.permutations(array))

mn = 1000

for i in permutations:

    count = 10

    for j in range(0, len(i), 2):

    sr = i[j] + i[j + 1]

    if sr == "ii":

    count += 1

    elif sr == "id":

    count -= 1

    elif sr == "dd":

    count -= 2

    if count < mn:

    mn = count

    

    print("Checking ", i, count)

print(mn)

```

---

@Deepak Poonia @Sachin Mittal 1 @GO Classes please check this. I'm getting D, also posted the code I used to check.

---

Got it 7 is possible

Answer 1

For I-1:

Initially, X = 10, s = 1 (mutual exclusion), and ‘s’ is in binary semaphore. So, after executing 5 incr() the value of X becomes 10 + 5 = 15, and after executing 3 decr() the value of X becomes 15 - 3 = 12.

For I-2:

Initially, X = 10, s = 2 (counting semaphore). This means, two processes can enter the critical section simultaneously. Let's say, the final values of X written by only the right-hand side function in each pass below-

// both read X = 10
pass1: incr1() & decr1()    // decr1() still in execution stage
                            // Final value of X = 11
pass2: incr2() & decr1()    // decr1() still in execution stage
                            // Final value of X = 12
pass3: incr3() & decr1()    // decr1() writes the final value
                            // Final value of X = 9
// both read X = 9
pass4: incr4() & decr2()    // decr2() writes the final value
                            // Final value of X = 8
// both read X = 8
pass5: incr5() & decr3()    // decr3() writes the final value
                            // Final value of X = 7

So, V1 and V2 become 12 and 7. The correct answer is Option C.

Answer 2

initial value of shared variable X is 10

we have 5 threads of INC()

and 

3 threads of DEC()

I1 uses binary semaphore so value of semaphore can be either 1 or 0

now in I1 semaphore is initialized with 1, and we can see when any thread will run (any thread of  INC() or DEC() )then firstly wait() is called so semaphore value will become 0 and hence no other thread of INC() or DEC() can run at the same time to access X and once currently running thread is over then only signal() is called so value of semaphore will become 1. so I1 guarantees Mutual Exclusion hence no two threads will be in critical section at a time so,final value of this solution will always be unique no matter in which order you execute it.

so value of V1 = 5 inc and 3 dec in X so V1=5-3+10=12.

In I2 counting semaphore is used that is initialized with 2,

here once any thread is under execution then it will firstly decrement semaphore value by 1 using wait(), now 

semaphore has current value as 1 so that means 1 more process can be at critical section at this time,

we want min value here by executing 5 INC() threads and 3 DEC() threads so 

(i).take one INC() thread and read current value of X that is 10, now preempt this and and take one DEC() thread and read current value of X that is 10 now semaphore = 0, so next thread will only come if any one of them will be completly executed and call signal() that will make semaphore as 1,

(ii)now just complete INC() thread and call next INC thread and do this untill all 5 INC() thread is over. so now suppose all 5 INC() threads are over and hence current value of X is 15, but when first time we  called a DEC() thread it read value 10 so do dec in it and update X so X became 9 similarly execute remaining 2 DEC() threads also one after another and they will make X=7.

So finally V2=7

final answer is V1=12,V2=7.