Question

Consider three processes P1, P2, and P3 running identical code, as shown in the
pseudocode below. A and B are two binary semaphores initialized to 1 and 0,
respectively. X is a shared variable initialized to 0. Each line in the pseudocode is
executed atomically.
Pseudocode of P1, P2, and P3
Wait(A);
Print(*);
X = X+1;
If (X == 2)
{
Print($);
Signal(B);
}
Signal(A);
Wait(B);
Print(#);
Signal(B);
Assume that any of the three processes can start to execute first and context
switching can happen between these processes at any arbitrary time and in any
arbitrary order.
Which of the following patterns is/are possible to be generated as an outcome of the
execution of these three processes?

• A. **$*###
• B. **$#*##
• C. **$##*#
• D. ***$###

Hint:

A acts as a mutex, so entries into the critical section are strictly ordered; whichever process is second to enter always sees X=2 and prints its dollar sign immediately after its own star and before the third process can even acquire A - so a star-star-dollar-star pattern is forced and dollar can never follow all three stars. B then chains the three hash prints one at a time, and this chain can start and even finish before the third star is printed, since releasing A and passing B are independent.

Answer 1

The Correct Option is A, B, C

Think of this system as two independent mechanisms running side by side: a 'lock' mechanism built from semaphore \(A\), and a 'baton-passing' mechanism built from semaphore \(B\).

The lock mechanism (A): Since \(A\) starts at 1, only one process can be between Wait(A) and Signal(A) at a time. The three processes therefore take turns entering this locked region in some order - first, second, third. Each turn, the process prints a star. The shared counter \(X\) goes 0 to 1 to 2 to 3 across these three turns in strict order, so it is always the process taking the SECOND turn that sees \(X=2\) and, while still holding the lock, prints a dollar sign right after its star and also signals \(B\) for the very first time. Because this happens inside one indivisible locked turn, no other process can squeeze a character between that star and that dollar. The process taking the third turn only ever prints a plain star, and it physically cannot take its turn until the second-turn process has released the lock - which only happens after the dollar was printed. So among the four symbols coming from the lock (star, star, dollar, star), the order star-star-dollar-star is unavoidable; dollar can never slide past the third star.

The baton mechanism (B): \(B\) starts at 0 and only becomes available once the second-turn process signals it (right after printing the dollar). From then on, each process that grabs \(B\) prints a hash and passes \(B\) along by signalling it again, so the three hashes always come out one at a time, never simultaneously, and never before the dollar. However, since releasing the lock (finishing a turn on \(A\)) and picking up the baton (using \(B\)) are handled by different, unsynchronized process actions, the scheduler is free to let the hash-chain run partly or fully before the third star is printed, or interleave the third star anywhere inside that chain.

Testing the four candidate outputs:

'**$*###' - fixed prefix intact, third star slotted in before the hash chain starts. Possible.

'**$#*##' - fixed prefix intact, third star slotted in after just one hash. Possible.

'**$##*#' - fixed prefix intact, third star slotted in after two hashes. Possible.

'***$###' - this would require the dollar to appear only after all three stars, which directly contradicts the fact that the dollar-producing turn must finish (lock released) before the third turn can even begin. Not possible.

Conclusion: options showing '**$*###', '**$#*##' and '**$##*#' are all valid execution outcomes, while '***$###' can never happen.