Bissoy.com
Doctors Medicines MCQs Q&A

Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?

Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes? Correct Answer X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)

Answer: Option 2

Explanation: 

Given

Process X will perform down operation on a, b, c

Process Y will perform down operation on b, c, d

Process Z will perform down operation on c, d, a

all the binary semaphores initialized to 1.

Option 1: X: P(a)P(b)P(c) Y: P(b)P(c)P(d) Z: P(c)P(d)P(a)

Consider the following sequence 

X: P(a)    // a = 0

Y: P(b)   // b = 0

Z: P(c)   // c = 0

X: P(b)   // unsuccessful down operation hence X will be blocked.

Y: P(c)   // again unsuccessful down operation hence Y will be blocked.

Z: P(d)   // d=0

Z: P(a)   // unsuccessful down operation hence Z will be blocked. Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Option 2: X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)

In this Order, you execute in any sequence deadlock not possible. Hence this is the correct Option.

Option 3: X: P(b)P(a)P(c) Y: P(c)P(b)P(d) Z: P(a)P(c)P(d)

X: P(b)   // b = 0 

Y: P(c)   // c = 0 

Z: P(a)   // a = 0 

X: P(a)   // unsuccessful down operation hence X will be blocked.

Y: P(b)   // again unsuccessful down operation hence Y will be blocked.

Z: P(c)   // unsuccessful down operation hence Z will be blocked. Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Option 4: X: P(a)P(b)P(c) Y: P(c)P(b)P(d) Z: P(c)P(d)P(a)

X: P(a)   // a = 0

Y: P(c)   // c = 0

Z: P(c)   // unsuccessful down operation hence Z will be blocked.

X: P(b)   // b = 0

Y: P(b)   // unsuccessful down operation hence Y will be blocked.

X: P(c)   //  unsuccessful down operation hence X will be blocked. Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Related Questions

A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?
Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is ?. Three semaphores empty, full and mutex are defined with respective initial values of 0, ? and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R, and S, in the code below can be assigned either empty or full. The valid semaphore operations are: wait ( ) and signal ( ). Producer: Consumer: do {         wait (P) ;         wait (mutex) ;         //Add item to buffer         signal (mutex) ;         signal (Q) ; } while (1) ; do {          wait (R) ;          wait (mutex) ;          //Consume item from buffer          signal (mutex) ;          signal (S) ; } while (1) ;   Which one of the following assignments to P, Q, R and S will yield the correct solution?
Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P. CODE SECTION P wait (a); count=count+1 ; if (count==n) signal (b) ; signal (a) ; wait (b) ; signal (b) ; CODE SECTION Q What does the code achieve?
The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0. Process P0 Process P1 Process P2 While (true) { Wait (S0); Print ‘0’ Release (S1); Release (S2); } Wait (S1); Release (S0); Wait (S2); Release (S0);   How many times will process P0 print ‘0’? 
Consider the following threads, T1, T2, and T3 executing on a single processor, synchronized using three binary semaphore variables, S1, S2, and S3, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time. T1 T2 T3 While(true) { Wait(S3); Print(“C”); Signal (S2); } While(true) { Wait(S1); Print(“B”); Signal (S3); } While(true) { Wait(S2); Print(“A”); Signal (S1); }   Which initialization of the semaphores would print the sequence BCABCABCA….?
Consider the following two C code segment. Y and X are one- and two-dimensional arrays of size n and n × n respectively, where 2 ≤ n ≤ 10. Assume that in both code segments, elements of y are initialized to 0 and each element X[i] [j] of array X is initialized to i + j. Further assume that when stored in main memory all elements of x are in same main memory page frame. Code segment 1:                 //initialize elements of y to 0                 //initialize elements X[i] [j] of X to i+j                       for (i = 0; i < n; i++)                                 Y[i] += X[0] [i]; Code Segment 2:                 //initialize elements of Y to 0                 //initialize elements X[i] [j] of X to i+j                        for (i = 0; i < n; i++)                                 Y[i] += X[i] [0]; Which of the following statements is/are correct? S1: Final contents of array Y will be same in both code segments S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory S3: Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory
A certain computation generates two arrays a and b such that a[i]=f(i) for 0 ≤ i < n and b[i] = g (a[i] ) for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below. Process X: private i; for (i=0; i
Two processes X and Y need to access a critical section. Consider the following synchronization construct used by both the processes Process ? /* other code for process ? */ while(true) { varP = true; while(varQ == true) { /* Critical Section */ varP = false; } } /* other code for process ?? */   Process ? /* other code for process ? */ while(true) { varQ = true; while(varP == true) { /* Critical Section */ varQ = false; } } /* other code for process ? */   Here, varP and varQ are shared variables and both are initialized to false. Which one of the following statements is true?
Consider the following multi-threaded code segment (in a mix of C and pseudocode), invoked by two processes P1 and P2, and each of the processes spawns two threads T1 and T2: int x = 0; // global Lock L1; // global main() { create a thread to execute foo(); // Thread T1 create a thread to execute foo(); // Thread T2 wait for the two threads to finish execution; print (x);} foo() { int y = 0; Acquire L1; x = x + 1; y = y + 1; Release L1; print (y); } Which of the following statement(s) is/are correct ?
Segment CD is shorter than Segment MN, Segment MN is shorter than Segment TR, Segment AB is shorter than Segment CD and Segment MN is shorter than Segment PQ. Which segment is the shortest?