ProcessSynchronization
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 timeshared 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 = D50 = 10050 = 50
P2 writes D=50 final value. This is minimum.
Next,
P2 reads D=100, executes D = D50, 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 producerconsumer 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 nonreentrant, i.e., if a thread holds a lock l, then it cannot reacquire 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 nonreentrant 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: P_{0}...P_{(n1)}. 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 P_{i}: do { c[i]=1; t[i] = pmax(t[0],...,t[n1])+1; c[i]=0; for every j ≠ i in {0,...,n1} { 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 satisﬁed  
The progress condition is satisﬁed  
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 twoprocess 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 twoprocess 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 nonnegative 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 ProducerConsumer 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 deadlockfree operation. 
Question 9 
Fetch_And_Add(X,i) is an atomic ReadModifyWrite 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 busywait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any nonzero 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 nonzero 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 nonzero 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 
S_{1}=0
S_{2}=0
P_{0} enters the critical section first,
prints (‘0’)
releases S_{1},S_{2}(i.e., S_{1}=1 & S_{2}=1)
Now P_{1} & P_{2} both can enter critical section releases S_{0} & 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 testandset instruction as follows:
void enter_CS(X) { while testandset(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 deadlockfree.
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 P_{b} and V_{b} the wait and signal operations on binary semaphores are provided. Two binary semaphores X_{b} and Y_{b} are used to implement the semaphore operations P(s) and V(s) as follows:
P(s): P_{b}(X_{b}); s = s  1; if (s < 0) { V_{b}(X_{b}) ; P_{b}(Y_{b}) ; } else V_{b}(X_{b}); V(s): P_{b}(X_{b}) ; s = s + 1; if (s <= 0) V_{b}(Y_{b}) ; V_{b}(X_{b}) ;
The initial values of X_{b} and Y_{b} are respectively
0 and 0  
0 and 1  
1 and 0  
1 and 1 
Y_{b} must be '0' initially, because if Y_{b} 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 fetchandset 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 { fetchandset 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 fetchandset, 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 reenabled at the end.
 
The variable process_left is made private instead of shared. 
Question 18 
Consider two processes P_{1} and P_{2} accessing the shared variables X and Y protected by two binary semaphores S_{X} and S_{Y} 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 pseudocode of P_{1} and P_{2} is as follows:
P_{1} : While true do { L_{1} : ................ L_{2} : ................ X = X + 1; Y = Y  1; V(S_{X}); V(S_{Y}); } P_{2} : While true do { L_{3} : ................ L_{4} : ................ Y = Y + 1; X = Y  1; V(S_{Y}); V(S_{X}); }
In order to avoid deadlock, the correct operators at L_{1}, L_{2}, L_{3} and L_{4} are respectively
P(S_{y}), P(S_{x}); P(S_{x}), P(S_{y})
 
P(S_{x}), P(S_{y}); P(S_{y}), P(S_{x})
 
P(S_{x}), P(S_{x}); P(S_{y}), P(S_{y})
 
P(S_{x}), P(S_{y}); P(S_{x}), P(S_{y})

P_{1} : line 1
P_{2} : line 3 (block require S_{x})
P_{1} : line 2
P_{2} : line 4 (still in block state)
P_{1} : execute CS, the push up the value of S_{x}.
P_{2} : line 3 line 4 (block require S_{y})
P_{1} : push up S_{y}
P_{2} : line 4 get S_{y} and enter into CS
P_{2} : 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 P_{1} will be executed first and then Process P_{2} 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.