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

Semaphore \(A\) is initialized to 1, so the block from Wait(A) to Signal(A) behaves as a mutual-exclusion lock. Only one of P1, P2, P3 can be inside this block at any instant, so the three processes enter it strictly one after another (in some order decided by the scheduler), never concurrently.

Step 1: What happens inside the locked block. Whichever process enters the lock first (call it the 1st entrant) executes Print(*), then X = X+1 makes \(X=1\), so the condition \(X==2\) is false - it prints only a single '*' and calls Signal(A).

Step 2: The process that sees X = 2. The process that enters the lock second (the 2nd entrant) executes Print(*), then X becomes \(2\), so the condition is true: it prints '*' immediately followed by '$' inside the same locked block, then calls Signal(B) and only afterwards Signal(A). Because both prints happen inside one uninterrupted critical section, no character from any other process can ever appear between this '*' and this '$'.

Step 3: The last process. The 3rd entrant finds \(X=3\), so it prints only '*' and never '$'. It cannot even acquire \(A\) until the 2nd entrant has called Signal(A) - and that call happens only after the 2nd entrant has already printed both its '*' and its '$'. So across every possible interleaving, the relative order of the four characters from the locked block is fixed as \[ *,\ *,\ \$,\ * \] Sequences such as three stars followed by the dollar (i.e. '***$') can never occur, because the dollar is tied structurally to the middle entrant.

Step 4: The role of B. Semaphore \(B\) starts at 0 and is signalled for the first time only by the 2nd entrant, immediately after it prints '$'. After that, Wait(B)/Signal(B) acts like a token being passed among the processes: whichever process currently receives the token prints '#' and hands the token on via Signal(B). This produces exactly three '#' prints, always one after another (never overlapping each other), and always starting only after '$' has already appeared.

Step 5: Interleaving the third star with the # chain. The 1st entrant reaches Wait(B) very early, right after printing its own '*' and releasing \(A\), so it is usually already waiting when \(B\) is first signalled - meaning the '#' chain can start immediately, even before the 3rd entrant has managed to acquire \(A\) and print its star, since passing the B token and acquiring the A lock are independent activities carried out by different processes. Hence the lone remaining '*' from the 3rd entrant may legally appear before the '#' chain begins, after exactly one '#', or after exactly two '#'s - the exact position depends purely on scheduling.

Step 6: Checking each option.

• '**$*###' - star, star, dollar (fixed order kept), then the 3rd star before any '#', then the full # chain. Achievable.
• '**$#*##' - fixed '**$' prefix kept, one '#' completes, then the 3rd star, then the remaining two '#'s. Achievable.
• '**$##*#' - fixed '**$' prefix kept, two '#'s complete, then the 3rd star, then the last '#'. Achievable.
• '***$###' - this needs three stars printed before the dollar. This is impossible, since the dollar is always printed by the 2nd entrant strictly before the 3rd entrant can even acquire \(A\).

So the patterns that can actually occur are the first three options.

Final answer: [**$*###, **$#*##, **$##*#] are possible outcomes.