Process-Synchronization
Question 1 |
Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100.
The process are executed on a uniprocessor system running a time-shared operating system. If the minimum and maximum possible values of D after the three processes have completed execution are X and Y respectively, then the value of Y–X is _______.
10 | |
40 | |
60 | |
80 |

P2 reads D=100, preempted.
P1 executes D=D+20, D=120.
P3 executes D=D+10, D=130.
Now, P2 has D=100, executes
D = D-50 = 100-50 = 50
P2 writes D=50 final value. This is minimum.
Next,
P2 reads D=100, executes D = D-50, before that assume P1 & P3 has read D=100.
P2 makes D=50 & writes it.
P1 executes (D=100), D=D+20 & P3 executes D=D+10 gives maximum value D=130.
So, Y - X = 130 - 50 =80.
Question 2 |
Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is N. Three semaphores empty, full and mutex are defined with respective initial values of 0, N and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full 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().

Which one of the following assignments to P, Q, R and S will yield the correct solution?
P: full, Q: full, R: empty, S: empty | |
P: empty, Q: empty, R: full, S: full
| |
P: full, Q: empty, R: empty, S: full | |
P: empty, Q: full, R: full, S: empty |
Initial: mutex = 1
empty = 0
full = N

Question 3 |
A multithreaded program P executes with x number of threads and used y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:
x = 1, y = 2 | |
x = 2, y = 1 | |
x = 2, y = 2 | |
x = 1, y = 1 |
Here a non-reentrant process can’t own the same lock multiple times, so if the process tries to acquire an already owned lock, it will get blocked, and deadlock will happen.
From the above options x=1 (a single thread) and y=1 (a single lock) deadlock is possible when we consider the given situations in question.
Question 4 |
Consider the following proposed solution for the critical section problem. There are n processes: P0...P(n-1). In the code, function pmax returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero.
Code for Pi: do { c[i]=1; t[i] = pmax(t[0],...,t[n-1])+1; c[i]=0; for every j ≠ i in {0,...,n-1} { while (c[j]); while (t[j] != 0 && t[j]<=t[i]); } Critical Section; t[i]=0; Remainder Section; } while (true);
Which one of the following is TRUE about the above solution?
At most one process can be in the critical section at any time | |
The bounded wait condition is satisfied | |
The progress condition is satisfied | |
It cannot cause a deadlock |
Based on the above code option B, C and D are not satisfied.
We can see that while (t[j] != 0 && t[j] <= t[i]);
because of this condition deadlock is possible when t[j] = = t[i].
Because Progress == no deadlock as no one process is able to make progress by stopping other process.
Bounded waiting is also not satisfied.
In this case both deadlock and bounded waiting to be arising from the same reason as if t[j] = = t[i] is possible then starvation is possible means infinite waiting.
Mutual exclusion is satisfied.
All other processes j started before i must have a value of t[j]) < t[i] as function pMax() return an integer not smaller than any of its arguments.
So if anyone out of the processes j have positive value will be executing in its critical section as long as the condition t[j] > 0 && t[j] <= t[i] within while will persist.
And when this j process comes out of its critical section, it sets t[j] = 0; and next process will be selected in for loop.
So, when i process reaches to its critical section none of the processes j which started earlier before process i is in its critical section.
This ensures that only one process is executing its critical section at a time.
So, A is the answer.
Question 5 |
Consider the following two-process synchronization solution.
Process 0 Process 1 --------- --------- Entry: loop while (turn == 1); Entry: loop while (turn == 0); (critical section) (critical section) Exit: turn = 1; Exit: turn = 0;
The shared variable turn is initialized to zero. Which one of the following is TRUE?
This is a correct two-process synchronization solution. | |
This solution violates mutual exclusion requirement. | |
This solution violates progress requirement. | |
This solution violates bounded wait requirement. |
So False.
C) Progress means if one process does not want to enter the critical section then it should not stop other process to enter the critical section.
But we can see that if process 0 will not enter the critical section then value of turn will not become 1 and process 1 will not be able to enter critical section.
So progress not satisfied. True.
D) Bounded waiting solution as there is a strict alternation.
So, False.
Question 6 |
Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is _________.
7 | |
8 | |
9 | |
10 |
P(S) operation remain in blocked state therefore it will -1.
The negative value of the counting semaphore indicates the number of processes in suspended list (or blocked).
Take any sequence of 20P and 12V operations, at least one process will always remain blocked.
So, X - 20 + 12 = -1
Here P(S) = 20 and V(S) = 12
X = 7
Question 7 |
The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.
P1() { C = B – 1; B = 2*C; } P2() { D = 2 * B; B = D - 1; }
The number of distinct values that B can possibly take after the execution is
3 | |
4 | |
5 | |
6 |
If we execute P1 process after P2 process, then B = 4
If we did preemption between P1 & P2 processes, then B = 2 (Preemption have done from P1 to P2) or B = 3 (Preemption have done from P2 to P1). So, among 2 & 3 values, only one value will be saved in B. So, total no. of distinct values that B can possibly take after the execution is 3.
Question 8 |
Consider the procedure below for the Producer-Consumer problem which uses semaphores:
semaphore n=0; semaphore s=1; void producer() void consumer() { { while(true) while(true) { { produce(); semWait(s); semWait(s); semWait(n); addToBuffer(); removeFromBuffer(); semSignal(s); semSignal(); semSignal(n); consume(); } } } }
Which one of the following is TRUE?
The producer will be able to add an item to the buffer, but the consumer can never consume it. | |
The consumer will remove no more than one item from the buffer. | |
Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty. | |
The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation. |
Question 9 |
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.
AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1; } ReleaseLock(L){ L = 0; }
This implementation
fails as L can overflow | |
fails as L can take on a non-zero value when the lock is actually available | |
works correctly but may starve some processes | |
works correctly without starvation |
while (Fetch_And_Add (L,1))
L = 1; // A waiting process can be here just after
// the lock is released, and can make L = 1.
Assume P1 executes until while condition and preempts before executing L =1. Now P2 executes all statements, hence L = 0. Then P1 without checking L it makes L = 1 by executing the statement where it was preempted.
It takes a non-zero value (L=1) when the lock is actually available (L = 0). So option B.
Question 10 |
Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned.

Which one of the following statements describes the properties achieved?
Mutual exclusion but not progress
| |
Progress but not mutual exclusion | |
Neither mutual exclusion nor progress | |
Both mutual exclusion and progress |
Question 11 |
The following program consists of 3 concurrent processes and 3 binary semaphores.The semaphores are initialized as S0 = 1, S1 = 0, S2 = 0.

How many times will process P0 print '0'?
At least twice | |
Exactly twice | |
Exactly thrice | |
Exactly once |
S1=0
S2=0
P0 enters the critical section first,
prints (‘0’)
releases S1,S2(i.e., S1=1 & S2=1)
Now P1 & P2 both can enter critical section releases S0 & prints (‘0’)
This process continues, hence the number of zero’s printed ≥2.
Question 12 |
The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:
void enter_CS(X) { while test-and-set(X) ; } void leave_CS(X) { X = 0; }
In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements:
- I. The above solution to CS problem is deadlock-free.
II. The solution is starvation free.
III. The processes enter CS in FIFO order.
IV More than one process can enter CS at the same time.
Which of the above statements is TRUE?
I only | |
I and II | |
II and III | |
IV only |
It is not using any queue to avoid starvation and there is no use of FIFO.
In CS, only one process can enter.
So, Answer is option A.
Question 13 |
The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows:
P(s): s = s - 1; if (s < 0) then wait; V(s): s = s + 1; if (s <= 0) then wakeup a process waiting on s;
Assume that Pb and Vb the wait and signal operations on binary semaphores are provided. Two binary semaphores Xb and Yb are used to implement the semaphore operations P(s) and V(s) as follows:
P(s): Pb(Xb); s = s - 1; if (s < 0) { Vb(Xb) ; Pb(Yb) ; } else Vb(Xb); V(s): Pb(Xb) ; s = s + 1; if (s <= 0) Vb(Yb) ; Vb(Xb) ;
The initial values of Xb and Yb are respectively
0 and 0 | |
0 and 1 | |
1 and 0 | |
1 and 1 |
Yb must be '0' initially, because if Yb is '1' initially then two process can be in critical section at the same time.
So answer is Option (C).
Question 14 |
Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:
/* P1 */ while (true) { wants1 = true; while (wants2 == true); /* Critical Section */ wants1=false; } /* Remainder section */ /* P2 */ while (true) { wants2 = true; while (wants1==true); /* Critical Section */ wants2 = false; } /* Remainder section */
Here, wants1 and wants2 are shared variables, which are initialized to false. Which one of the following statements is TRUE about the above construct?
It does not ensure mutual exclusion. | |
It does not ensure bounded waiting.
| |
It requires that processes enter the critical section in strict alternation. | |
It does not prevent deadlocks, but ensures mutual exclusion. |
Now, if in P1
wants1 = true ;
executed and preempted and now if in P2
wants2 = true ;
executed.
Then the deadlock situation will be created because both will fall into infinite loop.
Question 15 |
The atomic fetch-and-set x, y instruction unconditionally sets the memory location x to 1 and fetches the old value of x n y without allowing any intervening access to the memory location x. consider the following implementation of P and V functions on a binary semaphore S.
void P (binary_semaphore *s) { unsigned y; unsigned *x = &(s->value); do { fetch-and-set x, y; } while (y); } void V (binary_semaphore *s) { S->value = 0; }
Which one of the following is true?
The implementation may not work if context switching is disabled in P | |
Instead of using fetch-and-set, a pair of normal load/store can be used | |
The implementation of V is wrong | |
The implementation of V is wrong |
B) If we use normal load and store instead of Fetch and Set, then there can be chance that more than one process sees S.value as 0 and then mutual exclusion will not be satisfied. So wrong.
C) Here we are setting S→value to 0, which is correct. This option that's why wrong.
D) Only one process can be in critical section at any time. So this option is wrong.
Question 16 |
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.
void barrier (void) { 1: P(S); 2: process_arrived++; 3. V(S); 4: while (process_arrived !=3); 5: P(S); 6: process_left++; 7: if (process_left==3) { 8: process_arrived = 0; 9: process_left = 0; 10: } 11: V(S); }
The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.
The above implementation of barrier is incorrect. Which one of the following is true?
The barrier implementation is wrong due to the use of binary semaphore S
| |
The barrier implementation may lead to a deadlock if two barriers in invocations are used in immediate succession
| |
Lines 6 to 10 need not be inside a critical section | |
The barrier implementation is correct if there are only two processes instead of three
|
Hence, it is leads to deadlock.
Question 17 |
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.
void barrier (void) { 1: P(S); 2: process_arrived++; 3. V(S); 4: while (process_arrived !=3); 5: P(S); 6: process_left++; 7: if (process_left==3) { 8: process_arrived = 0; 9: process_left = 0; 10: } 11: V(S); }
The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.
Which one of the following rectifies the problem in the implementation?
Lines 6 to 10 are simply replaced by process_arrived-- | |
At the beginning of the barrier the first process to enter the barrier waits until process_arrived becomes zero before proceeding to execute P(S).
| |
Context switch is disabled at the beginning of the barrier and re-enabled at the end.
| |
The variable process_left is made private instead of shared. |
Question 18 |
Consider two processes P1 and P2 accessing the shared variables X and Y protected by two binary semaphores SX and SY respectively, both initialized to 1. P and V denote the usual semaphone operators, where P decrements the semaphore value, and V increments the semaphore value. The pseudo-code of P1 and P2 is as follows:
P1 : While true do { L1 : ................ L2 : ................ X = X + 1; Y = Y - 1; V(SX); V(SY); } P2 : While true do { L3 : ................ L4 : ................ Y = Y + 1; X = Y - 1; V(SY); V(SX); }
In order to avoid deadlock, the correct operators at L1, L2, L3 and L4 are respectively
P(Sy), P(Sx); P(Sx), P(Sy)
| |
P(Sx), P(Sy); P(Sy), P(Sx)
| |
P(Sx), P(Sx); P(Sy), P(Sy)
| |
P(Sx), P(Sy); P(Sx), P(Sy)
|
P1 : line 1
P2 : line 3 (block require Sx)
P1 : line 2
P2 : line 4 (still in block state)
P1 : execute CS, the push up the value of Sx.
P2 : line 3 line 4 (block require Sy)
P1 : push up Sy
P2 : line 4 get Sy and enter into CS
P2 : start execution.
So option D is Answer.
Question 19 |
Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.
Process P: while (1) { W: print '0'; print '0'; X: } Process Q: while (1) { Y: print '1'; print '1'; Z: }
Synchronization statements can be inserted only at points W, X, Y and Z.
Which of the following will always lead to an output staring with '001100110011'?
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1 | |
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0 | |
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1 | |
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S initially 1, and T initially 0
|
Process P1 will be executed first and then Process P2 can be executed next.
At the process P: W=P(S)
X=V(T)
At the process Q: Y=P(T)
Z=V(S)
Here, S=1, T=0 then the process P executes first and then Q, and both can run on process alternate way start with P.