Process Synchronization
Questions
Q1. The time taken to switch between user and kernel modes of
execution be t1 while the time taken to switch between two processes
be t2.
• Which of the following is TRUE?
(A) t1 > t2
(B) t1 = t2
(C) t1 < t2
(D) nothing can be said about the relation between t1 and t2
Solution -C
Process switches or Context switches can occur in only kernel mode .
So for process switches first we have to move from user to kernel mode
. Then we have to save the PCB of the process from which we are
taking off CPU and then we have to load PCB of the required process .
At switching from kernel to user mode is done. But switching from user
to kernel mode is a very fast operation(OS has to just change single bit
at hardware level)
Thus T1< T2
Q2. 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?
(a) Mutual exclusion but not progress
(b) Progress but not mutual exclusion
(c) Neither mutual exclusion nor progress
(d) Both mutual exclusion and progress
Method Used by P1 Method Used by P2
while (S1 == S2) ; while (S1 != S2) ;
Critica1 Section Critica1 Section
S1 = S2; S2 = not (S1);
Solution -A
Principle of Mutual Exclusion: No two processes may be simultaneously present in
the critical section at the same time. That is, if one process is present in the critical
section other should not be allowed.
P1 can enter critical section only if S1 is not equal to S2, and P2 can enter critical
section only if S1 is equal to S2. Therefore Mutual Exclusion is satisfied.
Progress: no process running outside the critical section should block the other
interested process from entering critical section whenever critical section is free.
Suppose P1 after executing critical section again want to execute the critical section
and P2 doesn’t want to enter the critical section, then in that case P1 has to
unnecessarily wait for P2. Hence progress is not satisfied.
Q3. A counting semaphore was initialized to 10. Then 6 P (wait)
operations and 4 V (signal) operations were completed on this
semaphore. The resulting value of the semaphore is
(a) 0
(b) 8
(c) 10
(d) 12
Solution-B
• 6P => decrements the semaphore 6 times. Hence , the value becomes
4.
• 4V => increments the semaphore 4 times. Hence , the value becomes
8.
• Note: The positive value of counting semaphore indicates that those
many down (P) operations can be carried out successfully. The
negative value of counting semaphore indicates that the number of
blocked processes.
Q4. Let m[0]…m[4] be mutexes (binary semaphores) and P[0] …. P[4]
be processes.
Suppose each process P[i] executes the following:
wait (m[i]);wait (m[(i+1) mode 4]);
.........
release (m[i]); release (m[(i+1)mod 4]);
This could cause
(a) Thrashing (b) Deadlock
(c) Starvation, but not deadlock (d) None of the above
Solution-B
Deadlock occurs, if each process gets preempted after executing
wait(m[i]);
Q5. 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?
(a) I only
(b) I and II
(c) II and III
(d) IV only
Solution-A
The test-and-set instruction is an instruction used to write to a memory
location and return its old value as a single atomic (i.e., non-
interruptible) operation. Since it is an atomic instruction it guarantees
mutual exclusion.
Q6. Two processes, P1 and P2, need to access a critical section of code. Consider the following
synchronization construct used by the processes:
Here, wants1 and wants2 are shared variables, which are initialized to false. Which one of the
following statements is TRUE about the above construct?
(a) It does not ensure mutual exclusion.
(b) It does not ensure bounded waiting.
(c) It requires that processes enter the critical section in strict alternation.
(d) It does not prevent deadlocks, but ensures mutual exclusion.
/* P1 */ /* P2 */
while (true) { while (true) {
wants1 = true; wants2 = true;
while (wants2 == true); while (wants1==true);
/* Critical /* Critical
Section */ Section */
wants1=false; wants2 = false;
} }
/* Remainder section */ /* Remainder section */
Solution-D
• The code ensures the condition of mutual exclusion: Assume P1 is initiated. It sets
wants1=true. Now since wants2 = false, P1 exists from its while loop and enters
its critical section. Now suppose context switch takes place and P2 gets executed.
Now it sets wants2=true, and now enters the while loop and remains busy till P1
comes out of the critical section and sets wants1=false, because wants1=true( as
set by P1). So we can see that the mutual exclusion condition is satisfied.
• The code does not prevent deadlock: Assume that P1 starts its execution. It sets
wants1=true and then gets preempted. Now P2 starts its execution. P2 sets
wants2=true and suddenly gets preempted. Now P1 starts execution; it enters the
while loop and finds that wants2=true and remains busy in the while loop. Now
P1 gets preempted. P2 enters into execution; it enters the while loop and finds
that wants1=true remains busy in the while loop. Hence both P1 and P2 remains
busy forever.
Q7. 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?
(A) -2
(B) -1
(C) 1
(D) 2
Solution- D
Semaphore S is initialized to 2
Process W executes S=1, x=1 but it doesn't update the x variable.
Then process Y executes S=0, it decrements x, now x= -2 and
signal semaphore S=1
Now process Z executes s=0, x=-4, signal semaphore S=1
Now process W updates x=1, S=2
Then process X executes X=2
Q8. 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?
(A) I only
(B) I and II
(C) II and III
(D) IV only
Solution –A
The above solution is a simple test-and-set solution that makes sure
that deadlock doesn’t occur, but it doesn’t use any queue to avoid
starvation or to have FIFO order.
Q9. 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'?
(a) twice (b) once
(c) thrice
Process P0 Process P1 Process P2
while (true) wait (S1); wait (S2);
{ signal (S0); signal (S0);
wait (S0);
print (0);
signal (S1);
signal (S2);
}
Solution - A
• P0 will execute first because only S0=1. Hence it will print 0 (for the first time).
Also P0 releases S1 and S2. Since S1=1 and S2=1, therefore P1 or P2, any one of
them can be executed.
• Let us assume that P1 executes and releases S0 (Now value of S0 = 1). Note that
P1 process is completed.
• Now S0=1 and S2=1, hence either P0 can execute or P2 can execute. Let us check
both the conditions:-
1. Let us assume that P2 executes, and releases S0 and completes its execution.
Now P0 executes; S0=0 and prints 0 (i.e. second 0). And then releases S1 and S2.
But note that P1 and P2 processes has already finished their execution. Again if P0
tries to execute it goes into sleep condition because S0=0. Therefore, minimum
number of times '0' gets printed is 2.
Q 10 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 deadlockfree
order of invoking the P operations by the processes?
(A) X: P(a)P(b)P(c) Y:P(b)P(c)P(d) Z:P(c)P(d)P(a)
(B) X: P(b)P(a)P(c) Y:P(b)P(c)P(d) Z:P(a)P(c)P(d)
(C) X: P(b)P(a)P(c) Y:P(c)P(b)P(d) Z:P(a)P(c)P(d)
(D) X: P(a)P(b)P(c) Y:P(c)P(b)P(d) Z:P(c)P(d)P(a)
Solution - B
• Option A can cause deadlock. Imagine a situation process X has acquired a,
process Y has acquired b and process Z has acquired c and d. There is
circular wait now.
• Option C can also cause deadlock. Imagine a situation process X has
acquired b, process Y has acquired c and process Z has acquired a. There is
circular wait now.
• Option D can also cause deadlock. Imagine a situation process X has
acquired a and b, process Y has acquired c. X and Y circularly waiting for
each other.