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:

Semaphore A lets only one process print its star, and possibly the dollar sign, at a time; semaphore B then releases the three hash marks in whatever order the scheduler wakes the waiting processes.

Answer 1

The Correct Option is A, B, C

Step 1: Notice A acts as a lock.
Semaphore \(A\) begins at \(1\), so only one of the three processes can be between its \(Wait(A)\) and its own later \(Signal(A)\) at any moment. This forces the three processes through that stretch of code one at a time, in some order picked by the scheduler; call them the first, second, and third to pass through.

Step 2: Write down what each one prints inside the lock.
The first one to pass through sets \(X\) to \(1\) and prints only a star. The second one sets \(X\) to \(2\), so it prints a star and then a dollar sign, and it also signals \(B\) once, all before releasing the lock. The third one sets \(X\) to \(3\) and prints only a star, finding the condition false again.

Step 3: Fix the unavoidable order of the first four prints.
The third star cannot appear until the second process releases the lock, which happens only after that same process has already printed its dollar sign. So the first four characters printed are always star, star, dollar, star, in that fixed order, whichever physical process plays which role. Any candidate pattern with all three stars ahead of the dollar sign is impossible right away.

Step 4: See how the hash marks get freed up.
\(B\) starts at \(0\), so the first process to reach \(Wait(B)\), right after it leaves the lock, finds \(B\) at \(0\) and waits there. The second process, right after printing the dollar sign, signals \(B\) once; since someone is already waiting, that signal wakes the FIRST process rather than being banked for later. The second process then tries its own wait on \(B\) and, finding the count back at \(0\), ends up waiting itself. From here on, every time a process finishes printing its hash mark, it signals \(B\) again, releasing whichever process is waiting next. So the three hash marks come out one at a time, each one triggered by the previous process finishing.

Step 5: See how the third star can slot in at different points.
The third process becomes free to enter the lock the moment the second process signals \(A\), which happens right after it has already printed the dollar sign. Whether the scheduler lets the third process run immediately, or instead runs one or two of the already unblocked hash printing processes first, is completely open, since arbitrary interleaving is allowed. This single choice, of when the third star gets slotted in relative to the chain of hash marks, is what produces the different valid patterns.

Step 6: Match the three allowed slots to the given options.
If the third star runs before any hash mark, the output reads star star dollar star hash hash hash, matching option (A). If exactly one hash mark comes out first, then the third star, then the remaining two hash marks, the output reads star star dollar hash star hash hash, matching option (B). If both remaining hash marks come out before the third star finally runs, the output reads star star dollar hash hash star hash, matching option (C).

Step 7: Explain why option (D) never happens.
Option (D) needs three stars printed before any dollar sign, but Step 3 already shows the dollar sign must come out right after the second star and strictly before the third. So (D) can never be produced.

Step 8: Conclude.
\[ \boxed{\text{Patterns (A), (B), and (C) are all reachable; (D) is not}} \]