Question

Consider the two functions incr and decr below. Five threads each call incr once and three threads each call decr once on the same shared variable \(X\) (initially \(10\)). There are two semaphore implementations:

I-1: \(s\) is a binary semaphore initialized to \(1\).
I-2: \(s\) is a counting semaphore initialized to \(2\).

Let \(V_1, V_2\) be the values of \(X\) at the end of all threads for I-1 and I-2, respectively. Which choice gives the minimum possible values of \(V_1, V_2\)?

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

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

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

Hint:

With a counting semaphore \(=2\), at most two threads race at once. The best way to minimize the final value is to let each decrement overwrite a concurrent increment (making a pair worth \(-1\)), and make the leftover increments collide with each other (worth \(+1\)). You cannot reduce all five increments because only three decrements exist and at most two threads can overlap at any instant.

Answer 1

The Correct Option is D

To determine the minimum possible values of \(V_1\) and \(V_2\), we need to analyze the semaphore implementations and the operations between the threads calling the incr and decr functions.

1. Semaphore Implementation I-1: A binary semaphore initialized to 1.
   • This semaphore allows only one thread to execute the critical section at any given time. Hence, the threads operate in a strictly serialized manner.
   • Since there are 5 threads calling incr and 3 threads calling decr, let's determine the net effect:
     • Each call to incr adds 1 to \(X\), resulting in \(5 \times 1 = 5\).
     • Each call to decr subtracts 1 from \(X\), resulting in \(-3 \times 1 = -3\).
     • Net effect on \(X\): \(5 - 3 = 2\).
   • Starting from \(X = 10\), the final value \(V_1 = 10 + 2 = 12\).
2. Semaphore Implementation I-2: A counting semaphore initialized to 2.
   • This semaphore allows up to two threads to execute the critical section concurrently.
   • Consequently, two threads might alter the shared variable \(X\) simultaneously. This increases potential interleaving scenarios.
   • In the worst-case scenario where any combination of incr and decr execution could happen concurrently:
     • Simultaneously occurring increments and decrements might cancel each other out.
     • The maximum concurrent decrements are 3 (from 3 threads), leading to a potential minimum effect of \(-3\) on \(X\) when interleaved exclusively after some increments.
     • Resultantly, if decrements dominate with minimal independent increments' contribution, \(X\) decreases potentially by 2, resulting in \(X = 8\).
   • Therefore, the final minimum value for \(V_2 = 8\).

Therefore, the minimum possible values of \(V_1\) and \(V_2\) are 12 and 8, respectively. Hence the correct answer is 12, 8.