GATE CS 2008 Q63 — Concurrency and Synchronization

To determine the initial values of the binary semaphores $x_b$ and $y_b$, let us analyze their roles in the implementation of the counting semaphore operations:

1. Role of $x_b$:

   The variable $s$ is a shared integer representing the semaphore count. In both $P(s)$ and $V(s)$, the operations on $s$ (such as decrementing, incrementing, and checking its value) must be executed atomically to prevent race conditions.

   The binary semaphore $x_b$ is used to provide mutual exclusion (acting as a mutex) around these critical sections. Since a process must be allowed to enter the critical section initially, the mutex $x_b$ must be initialized to $1$.

2. Role of $y_b$:

   The binary semaphore $y_b$ is used to block processes when the resource count $s$ is less than $0$.

   When a process calls $P(s)$ and finds $s < 0$, it releases the mutex $x_b$ and then executes $P_b(y_b)$ to block itself. For the process to successfully block at $P_b(y_b)$, the semaphore $y_b$ must be unavailable initially. Thus, $y_b$ must be initialized to $0$.

   When another process calls $V(s)$ and increments $s$ such that $s \le 0$, it signals $V_b(y_b)$ to wake up one of the blocked processes.

Therefore, the initial values of $x_b$ and $y_b$ are $1$ and $0$ respectively.