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?
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?
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?
Show 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.
Updated On: Jul 22, 2026
- **$*###
- **$#*##
- **$##*#
- ***$###
Show Solution
Verified By Collegedunia
The Correct Option is A, B, C
Solution and Explanation
Step 1: Understand the role of semaphore A.
\(A\) starts at \(1\), so \(Wait(A)\) followed later by \(Signal(A)\) works exactly like a mutex lock around the block from \(Print(*)\) to \(Signal(A)\). Only one process can be inside this block at a time, and the three processes must pass through it strictly one after another, in some order decided by the scheduler.
Step 2: Track what happens inside the locked block.
Whichever process enters first prints one \(*\) and sets \(X=1\); since \(X\neq2\), nothing else happens before it releases \(A\). The second process to enter prints its own \(*\) and sets \(X=2\); this time the condition is true, so it prints \(\$\) and calls \(Signal(B)\) BEFORE it releases \(A\) with its own \(Signal(A)\). The third process to enter prints a final \(*\) and sets \(X=3\); the condition fails again.
Step 3: Fix the order of the first four printed characters.
Because the third process cannot even attempt \(Wait(A)\) until the second process has executed \(Signal(A)\), and the second process's \(\$\) is printed strictly before its own \(Signal(A)\), the very first four visible characters are always star, star, dollar, star, in exactly that order, no matter which physical process arrives first, second, or third. This immediately rules out any pattern where three stars appear before the dollar, such as option (D).
Step 4: Understand semaphore B and who blocks on it.
\(B\) starts at \(0\). The first process to finish the locked block reaches \(Wait(B)\) immediately after releasing \(A\), and since \(B=0\) at that point, it blocks. The second process, right after printing \(\$\), calls \(Signal(B)\); with a process already waiting, this wakes that first blocked process rather than letting anyone new through for free. The second process then tries its own \(Wait(B)\), and by then the count is back to \(0\), so the second process itself blocks too. Each later \(Signal(B)\), issued after a process prints its \(\#\), wakes whichever process is queued next.
Step 5: Show pattern (A), \(**\$*\#\#\#\), is achievable.
Let the scheduler run the third entrant immediately after the second's \(Signal(A)\), so the third star prints right away, giving \(**\$*\). At this point two processes are queued on \(B\), the first and second entrants, and the third entrant now also calls \(Wait(B)\) and blocks. As each queued process is woken in turn by the chain of \(Signal(B)\) calls, three \(\#\) prints follow one after another, giving \(**\$*\#\#\#\).
Step 6: Show pattern (B), \(**\$\#*\#\#\), is achievable.
Instead, let the scheduler run the already unblocked first entrant right after the second's \(Signal(A)\), so it prints its \(\#\) before the third entrant gets a turn, giving \(**\$\#\). Its own \(Signal(B)\) wakes the second entrant, but the third entrant can now also acquire \(A\) and print its star before the woken second entrant is actually scheduled to print. Choosing that interleaving gives \(**\$\#*\), and the remaining two processes then print their \(\#\)'s one after another, giving \(**\$\#*\#\#\).
Step 7: Show pattern (C), \(**\$\#\#*\#\), is achievable.
Let both the first entrant and, after being woken, the second entrant print their \(\#\)'s back to back before the scheduler ever lets the third entrant acquire \(A\), giving \(**\$\#\#\). The third entrant then finally runs, printing its star and later its own \(\#\), giving \(**\$\#\#*\#\).
Step 8: Rule out pattern (D).
As shown in Step 3, three stars can never appear before the dollar, so \(***\$\#\#\#\) can never occur.
Step 9: Final answer.
\[ \boxed{\text{(A), (B), and (C) are all achievable; (D) is not}} \]
\(A\) starts at \(1\), so \(Wait(A)\) followed later by \(Signal(A)\) works exactly like a mutex lock around the block from \(Print(*)\) to \(Signal(A)\). Only one process can be inside this block at a time, and the three processes must pass through it strictly one after another, in some order decided by the scheduler.
Step 2: Track what happens inside the locked block.
Whichever process enters first prints one \(*\) and sets \(X=1\); since \(X\neq2\), nothing else happens before it releases \(A\). The second process to enter prints its own \(*\) and sets \(X=2\); this time the condition is true, so it prints \(\$\) and calls \(Signal(B)\) BEFORE it releases \(A\) with its own \(Signal(A)\). The third process to enter prints a final \(*\) and sets \(X=3\); the condition fails again.
Step 3: Fix the order of the first four printed characters.
Because the third process cannot even attempt \(Wait(A)\) until the second process has executed \(Signal(A)\), and the second process's \(\$\) is printed strictly before its own \(Signal(A)\), the very first four visible characters are always star, star, dollar, star, in exactly that order, no matter which physical process arrives first, second, or third. This immediately rules out any pattern where three stars appear before the dollar, such as option (D).
Step 4: Understand semaphore B and who blocks on it.
\(B\) starts at \(0\). The first process to finish the locked block reaches \(Wait(B)\) immediately after releasing \(A\), and since \(B=0\) at that point, it blocks. The second process, right after printing \(\$\), calls \(Signal(B)\); with a process already waiting, this wakes that first blocked process rather than letting anyone new through for free. The second process then tries its own \(Wait(B)\), and by then the count is back to \(0\), so the second process itself blocks too. Each later \(Signal(B)\), issued after a process prints its \(\#\), wakes whichever process is queued next.
Step 5: Show pattern (A), \(**\$*\#\#\#\), is achievable.
Let the scheduler run the third entrant immediately after the second's \(Signal(A)\), so the third star prints right away, giving \(**\$*\). At this point two processes are queued on \(B\), the first and second entrants, and the third entrant now also calls \(Wait(B)\) and blocks. As each queued process is woken in turn by the chain of \(Signal(B)\) calls, three \(\#\) prints follow one after another, giving \(**\$*\#\#\#\).
Step 6: Show pattern (B), \(**\$\#*\#\#\), is achievable.
Instead, let the scheduler run the already unblocked first entrant right after the second's \(Signal(A)\), so it prints its \(\#\) before the third entrant gets a turn, giving \(**\$\#\). Its own \(Signal(B)\) wakes the second entrant, but the third entrant can now also acquire \(A\) and print its star before the woken second entrant is actually scheduled to print. Choosing that interleaving gives \(**\$\#*\), and the remaining two processes then print their \(\#\)'s one after another, giving \(**\$\#*\#\#\).
Step 7: Show pattern (C), \(**\$\#\#*\#\), is achievable.
Let both the first entrant and, after being woken, the second entrant print their \(\#\)'s back to back before the scheduler ever lets the third entrant acquire \(A\), giving \(**\$\#\#\). The third entrant then finally runs, printing its star and later its own \(\#\), giving \(**\$\#\#*\#\).
Step 8: Rule out pattern (D).
As shown in Step 3, three stars can never appear before the dollar, so \(***\$\#\#\#\) can never occur.
Step 9: Final answer.
\[ \boxed{\text{(A), (B), and (C) are all achievable; (D) is not}} \]
Was this answer helpful?
0
0
Top GATE CS Operating System Questions
- Processes \( P_1, P_2, P_3, P_4 \) arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times. Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?
- With respect to deadlocks in an operating system, which of the following statements is/are FALSE?
- Consider a system consisting of \(k\) instances of a resource \(R\), being shared by 5 processes. Assume that each process requires a maximum of two instances of resource \(R\) and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance.The minimum value of \(k\) for the system to be deadlock-free is __________. (answer in integer)
- Consider a hard disk with a rotational speed of 15000 rpm. The time to move the read/write head from a track to its adjacent track is 1 millisecond. Initially, the head is on track 0. The number of sectors per track is 400. The sector size is 1024 bytes. It is necessary to transfer data from 10 randomly located sectors in each of the following tracks in the order: 5, 12 and 7. The total time for the data transfer (in milliseconds) from the hard disk is _________. (rounded off to one decimal place)
- Consider the following program snippet. Assume that the program compiles and runs successfully. Further, assume that the fork() system call is always successful in creating a process.
int main () { int i; for (i = 0; i < 3; i++){ if (fork() == 0){ continue; } break; } printf("Hello!"); return 0; }The total number of times that the printf statement gets executed is ________.
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions