Q.

1 The following two functions P1 and P2 that share a variable B with an initial value of 2 execute
concurrently.
P1 () P2 ()

{ {
C = B – 1; D = 2 * B;
B = 2 * C;
B = D – 1;
}
}
The number of distinct values that B can possibly take after the execution is _________.
[GATE 2000 : IIT Kharagpur]
Q.2 Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D
that has been initialized to 100
P1 P2 P3
: : :
: : :
D=D+20 D = D – 50 D = D + 10
: : :
: : :
The processes are executed on a uniprocessor system running a time – shared operating system .If the
minimum and maximum possible values of D after the three process have completed are X of Y
respectively, then the value of Y-X is _________.
[GATE 2019 : IIT Madras]
Q.3 A critical region is:
(A) One which is enclosed by a pair of P and V operations on semaphores.
(B) A program segment that has not been proved bug-free.
(C) A program segment that often causes unexpected system crashes.
(D) A program segment where shared resources are accessed.
[GATE 1987 : IIT Bombay]
Q.4 Processes P1 and P2 use critical flag in the following routine to achieve mutual exclusion. Assume that
critical flag is initialized to FALSE in the main program.
get_exclusive_access ( )
{
if (critical _flag == FALSE) {
critical_flag = TRUE ;
critical_region () ;
critical_flag = FALSE; }
}
Consider the following statements.
i. It is possible for both P1 and P2 to access critical region concurrently.
ii. This may lead to a deadlock
Which of the following holds?
(A) (i) is false and (ii) is true (B) Both (i) and (ii) are false
(C) (i) is true and (ii) is false (D) Both (i) and (ii) are true
[GATE 2007 : IIT Kanpur]
Q.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?
(A) This is a correct two- process synchronization solution.
(B) This solution violates mutual exclusion requirement.
(C) This solution violates progress requirement.
(D) This solution violates bounded wait requirement.
[GATE 2016 : IISc Bangalore]
Q.6 Consider the method 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.
Method used by P1 Method used by P2
While (S1==S2); While (S1! = S2);
Critical section Critical section
S1 = S2; S2 = not (S1);

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.
[GATE 2010 : IIT Guwahati]

Q.7 Two processes X and Y need to access a critical section. Consider the following synchronization construct
used by both the processes.
Process X Process Y/*
/* other code for process X*/ /*other code for process Y
while (true){ while (true){
varP = true; varQ = true;
while (varQ == true) while (varP == true)
{ {
/* Critical Section */ /* Critical Section */
varP = false; varQ = false;
}} }}

Here, varP and varQ are shared variables and both are initialized to false. Which one of the following
statements is true?
(A) The proposed solution prevents deadlock but fails to guarantee mutual exclusion
(B) The proposed solution guarantees mutual exclusion but fails to prevent deadlock
(C) The proposed solution guarantees mutual exclusion and prevents deadlock
(D) The proposed solution fails to prevent deadlock and fails to guarantee mutual exclusion
[GATE 2010 : IIT Guwahati]
Q.8 The enter _CS () and leave _CS () function 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 are TRUE?
(A) I only (B) I and II (C) II and III (D) IV only
[GATE 2009 : IIT Roorkee]
Q.9 At a particular time of computation the value of a counting semaphore is 7. Then 20P operations and
15V operations were completed on this semaphore. The resulting value of the semaphore is;
(A) 42 (B) 2 (C) 7 (D) 12
[GATE 1992 : IIT Delhi]
Q.10 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) operation are issued in some order. The largest
initial value of S for which at least one P(S) operation will remain blocked is _________.]
[GATE 2014 : IIT Kharagpur]
Q.11 Given below is a program which when executed spawns two concurrent processes :
semaphore X : = 0 ;
/* Process now forks into concurrent processes P1 & P2 */

P1: repeat forever P2: repeat forever

V (X) ; P(X) ;
Compute ; Compute ;
P(X) ; V(X) ;

Consider the following statements about processes P1 and P2:

I. It is possible for process P1 to starve.
II. It is possible for process P2 to starve.
Which of the following holds?
(A) Both I and II are true (B) I is true but II is false
(C) II is true but I is false (D) Both I and II are false
[GATE 2005 : IIT Bombay]
Q.12 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 the
memory, and then terminates. Each of the processes Y and Z reads X from memory, decrements by two,
stores it to memory, and 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
[GATE 2013 : IIT Bombay]
Q.13 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?
(A) It ensures that no process executes CODE SECTION Q before every process has finished CODE
SECTION P.
(B) It ensures that at most two processes are in CODE SECTION Q at any time.
(C) It ensures that all processes execute CODE SECTION P mutually exclusively.
(D) It ensures that at most n − 1 processes are in CODE SECION P at any time.
[GATE 2020 : IIT Delhi]
Q.14 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 (S1); wait (S2);
wait (S0); release (S0); release (S0);
print ‘0’;
release (S1);
release(S2);
}

How many times will process P0 print ‘0’?

(A) Atleast twice (B) Exactly twice (C) Exactly thrice (D) Exactly once
[GATE 2008 : IISc Bangalore]
s

Common Data for

Questions 15 & 16

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: Process Q:
while (1) { while (1) {
W: Y:
print ‘0’; print ‘1’
print ‘0’; print ‘1’
X:
Z:
}
}

Synchronization statements can be inserted only at point W, X, Y and Z.

Q.15 Which of the following will always lead to an output staring with 001100110011?
(A) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
(B) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0
(C) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
(D) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S initially 1, and T initially 0
[GATE 2003 : IIT Madras]
Q.16 Which of the following will ensure that the output string never contains a substring of the form 01nor 10n
where n is odd?
(A) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
(B) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
(C) P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1
(D) V(S) at W, V(T) at X, P(S) at Y, P(T) at Z, S and T initially 1.
[GATE 2003 : IIT Madras]
Q.17 Two concurrent processes P1 and P2 use four shared resources R1, R2, R3 and R4, as shown below.

P1 P2

Compute: Compute;
Use R1; Use R1;
Use R2; Use R2;
Use R3; Use R3;.
Use R4; Use R4;

Both processes are started at the same time, and each resource can be accessed by only one process at a
time The following scheduling constraints exist between the access of resources by the processes:
P2 must complete use of R1 before P1 gets access to R1
P1 must complete use of R2 before P2 gets access to R2.
P2 must complete use of R3 before P1 gets access to R3.
P1 must complete use of R4 before P2 gets access to R4.
There are no other scheduling constraints between the processes. If only binary semaphores are used to
enforce the above scheduling constraints, what is the minimum number of binary semaphores needed?
(A) 1 (B) 2 (C) 3 (D) 4
[GATE 2005 : IIT Bombay]
Q.18 Three concurrent processes X, Y and Z execute three different code segments that access 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?
(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)
[GATE 2013 : IIT Bombay]
Q.19 The atomic fetch-and-set x, y instruction unconditionally sets the memory location x to 1 and fetches the
old value of x in y without allowing any intervening access to the memory location x. Consider the
following implementation of P and V function 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?
(A) The implementation may not work if context switching is disabled in P
(B) Instead of using fetch- and- set, a pair of normal load/ store can be used
(C) The implementation of V is wrong.
(D) The code does not implement a binary semaphore.
[GATE 2006 : IIT Kharagpur]
Q.20 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 ( ).
Producer : Consumer :
do { do {
wait (P); wait (R);
wait (mutex); wait (mutex);
/ / Add item to buffer / / Consume item from buffer
signal (mutex); signal (mutex);
signal(Q); signal(S);
} while (1); } while (1);

Which one of the following assignments to P, Q, R and S will yield the correct solution?
(A) P : full, Q : full, R : empty, S : empty
(B) P : empty, Q : empty, R : full, S : full
(C) P : full, Q : empty, R : empty, S : full
(D) P : empty, Q : full, R : full, S : empty
[GATE 2018 : IIT Guwahati]
Q.21 The semaphore variables full, empty and mutex are initialized to 0, n and 1, respectively. Process
P1 repeatedly adds one item at a time to a buffer of size n, and process P2 repeatedly removes one item
at a time from the same buffer using the programs given below. In the programs, K, L, M and N are
unspecified statements.
P1 P2
while (1) { while (1) {
K; M;
P(mutex); P(mutex);
Add an item to the buffer; Remove an item from the buffer;
V(mutex); V(mutex);
L; N;
} }

The statements K, L, M and N are respectively

(A) P(full), V(empty), P(full), V(empty)
(B) P(full), V(empty), P(empty), V(full)
(C) P(empty), V(full), P(empty), V(full)
(D) P(empty), V(full), P(full), V(empty)
[GATE 2004 : IIT Delhi]
Q.22 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 (); remove FromBuffer ();
semSignal (s); semSignal (s);
semSignal (n) consume ();
} }
} }
Which one of the following is TRUE?
(A) The producer will be able to add an item to the buffer, but the consumer can never consume it.
(B) The consumer will remove no more than one item from the buffer.
(C) Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.
(D) The starting value for the semaphore n must be 1 and not 0 for deadlock- free operation.
[GATE 2014 : IIT Kharagpur]
Q.23 A solution to the Dining Philosophers Problem which avoids deadlock is
(A) Ensure that all philosophers pick up the left fork before the right fork.
(B) Ensure that all philosophers pick up the right fork before the left fork.
(C) Ensure that one particular philosophers picks up the left fork before the right fork, and that all other
philosophers pick up the right fork before the left fork.
(D) None of the above.
[GATE 2014 : IIT Kharagpur]
Q.24 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) mod 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
[GATE 2014 : IIT Kharagpur]
Q.25 Synchronization in the classical readers and writers problem can be achieved through use of
semaphores. In the following incomplete code for readers-writers problem, two binary semaphores
mutex and wrt are used to obtain synchronization
wait (wrt)
writing is performed
signal (wrt)
wait (mutex)
readcount = readcount + 1
if readcount = 1 then S1
S2
reading is performed
S3
readcount = readcount - 1
if readcount = 0 then S4
signal (mutex)
The values of S1, S2, S3, S4, (in that order) are
(A) signal (mutex), wait (wrt), signal (wrt), wait (mutex)
(B) signal (wrt), signal (mutex), wait (mutex), wait (wrt)
(C) wait (wrt), signal (mutex), wait (mutex), signal (wrt)
(D) signal (mutex), wait (mutex), signal (mutex), wait (mutex)
[GATE 2006 : IIT Kharagpur]
Q.26 Consider the following proposed solution for the critical section problem. There are n processes:
P0 ......................Pn−1 . In the code, function pmax returns an integer not smaller than any of if arguments.
For all i, t[i] is initialized to zero.
Code for P1
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);
While one of the following is TRUE about the above solution?
(A) At most one process can be in the critical section at any time
(B) The bounded wait condition is satisfied
(C) The progress condition is satisfied
(D) It cannot cause a deadlock
[GATE 2016 : IISc Bangalore]
Q.27 Each process Pi, i = 1……….9 is coded as follows
Repeat
P(mutex)
{
critical section
}
v(mutex)
forever
The code for P10 is identical except that it uses V(mutex) in place of P(mutex). What is the largest
number of processes that can be inside the critical section at any moment?
(A) 1 (B) 2 (C) 3 (D) None
[GATE 1997 : IIT Madras]
Q.28 Consider the following pseudocode, where S is a semaphore initialized to 5 in line#2 and counter is a
shared variable initialized to 0 in line#1. Assume that the increment operation in line#7 is not atomic.
int counter = 0;
Semaphore S = init(5);
Void parop(void){
wait(S);
wait(S);
counter++;
signal(S);
signal(S);
}
If live threads execute the function parop concurrently, which of the following program behavior(s)
is/are possible?
(A) The value of counter is 0 after all the threads successfully complete the execution of parop.
(B) The value of counter is 1 after all the threads successfully complete the execution of parop.
(C) There is a deadlock involving all the threads.
(D) The value of counter is 5 after all the threads successfully complete the execution of parop.
[GATE 2021 : IIT Bombay]
Q.29 Consider a computer system with multiple shared resource types, with one instance per resource type.
Each instance can be owned by only one process at a time. Owning and freeing of resources are done by
holding a global lock (L). The following scheme is used to own a resource instance:
function OWNRESOURCE (Resource R)
Acquire lock L // a global lock
if R is available then
Acquire R
Release lock L
else
if R is owned by another process P then
Terminate P, after releasing all resources owned by P
Acquire R
Restart P
Release lock L
end if
end if
end function
Which of the following choice(s) about the above scheme is/are correct?
(A) The scheme ensures that deadlocks will not occur.
(B) The scheme violates the mutual exclusion property.
(C) The scheme may lead to live-lock.
(D) The scheme may lead to starvation.
[GATE 2021 : IIT Bombay]
 Common Data for
Questions 30 & 31

Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in
the set arrive at the barrier and waits for all other 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 function.
Consider the following C implementation of a barrier with line numbers shown on the 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.
Q.30 The above implementation of barrier is incorrect. Which one of the following is true?
(A) The barrier implementation is wrong due to the use of binary semaphore S
(B) The barrier implementation may lead to a deadlock if two barrier invocation are used in immediate
succession
(C) Lines 6 to 10 need not be inside a critical section.
(D) The barrier implementation is correct if there are only two processes instead of three.
[GATE 2006 : IIT Kharagpur]
Q.31 Which one of the following rectifies the problem in the implementation?
(A) Lines 6 to 10 are simply replaces by process _arrived
(B) 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)
(C) Context switch is disabled at the beginning of the barrier and re-enabled at the end.
(D) The variable process _left is mad private instead of shared.
[GATE 2006 : IIT Kharagpur]
Q.32 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 wake up a process waiting on s;
Assume that Pb and Vb the wait and signal operations on binary semaphores X b and Yb are used to
implement the semaphore operations P(s) and V(s) as follows :
P(s): Pb(xb); V(s): Pb(xb);
s = s – 1; s = s + 1;
if (s < 0) if (s <= 0) Vb(yb);
{ Vb(xb);
Vb(xb);
Pb(yb);
}
else Vb(xb);
The initial values of xb and yb are respectively
(A) 0 and 0 (B) 0 and 1 (C) 1 and 0 (D) 1 and 1
[GATE 2008 : IISc Bangalore]
Q.33 Consider the following solution to the producer-consumer problem suing a buffer of size 1. Assume that
the initial value of account is 0. Also assume that the testing of count and assignment to count are atomic
operations. [GATE 1999 : IIT Bombay]
Show that in this solution it is possible that both the processes are sleeping at the same time.
Producer: Consumer:
Repeat Repeat
Produce an item; if count = 0 then sleep;
if count = 1 then sleep; Remove item from buffer;
place item in buffer. count = 0;
count = 1; Wakeup(Producer);
Wakeup(Consumer); Consume item;
Forever Forever;
Q.1 A critical section is a program segment.
(A) Which should run in certain specified amount of time
(B) Which avoids resources are accessed
(C) Where shared resources are accessed
(D) Which must be enclosed by a pair of semaphore operations, P and V
[GATE 1996 : IISc Bangalore]
Q.2 When several processes access the same data concurrently and the outcome of the execution depends on
the particular order in which the access takes place is called ________
(A) dynamic condition (B) race condition
(C) essential condition (D) critical condition
[GATE 1996 : IISc Bangalore]
Q.3 Mutual exclusion can be provided by the __________
(A) mutex locks (B) binary semaphores
(C) Semaphore only (D) Spin lock
[GATE 1996 : IISc Bangalore]
Q.4 Process synchronization can be done on __________
(A) hardware level (B) software level
(C) both hardware and software level (D) none of the mentioned
GATE 1996 : IISc Bangalore]
Q.5 Consider Peterson’s algorithm for mutual exclusion between two concurrent processes i and j. The
program executed by process i is shown below.
Repeat
flag [i] = true;
turn = j;
while (P) do no-op;
Enter critical section, perform actions,
Then exit critical section
flag [i] = false;
Perform other non- critical section action.
until false;
For the program to guarantee mutual exclusion, the predicate P in the while loop should be
(A) flag [j] = true and turn = i
(B) flag [j] = true and turn = j
(C) flag [i] = true and turn = j
(D) flag [i] = true and turn = i
[GATE 2001 : IIT Kanpur]
Q.6 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?
/* 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 */
(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.
[GATE 2007 : IIT Kanpur]
Q.7 A Counting semaphore was initialized to 10. Then 6P (Wait) operations and 4V (Signal) operations were
completed on this semaphore. The resulting value of the semaphore is _____.
(A) 0 (B) 8 (C) 10 (D) 12
[GATE 1998 : IIT Delhi]
Q.8 Consider two processes P1 and P2 accessing the shared variables X and Y protected by two binary
semaphores SX and SY and respectively, both initialized to 1. P and V denote the usual semaphore
operators, where P decrements the semaphore value, and V increments the semaphore value. The
pseudo-code of P1 and P2 is as follows :
P1 :
where true do{
L1: ……………………..
L2: ……………………..
X = X + 1;
Y = Y – 1:
V(SX);
V(SY);
}
P2 :
where true do
{
L3: ……………………..
L4: ……………………..
Y = Y + 1;
X = X – 1:
V(SY);
V(SX);
}
In order to avoid deadlock, the operators at L1 , L2 , L3 and L4 are respectively .
(A) P ( SY ) , P ( S X ) ; P ( S X ) , P ( SY ) (B) P ( S X ) , P ( SY ) ; P ( SY ) , P ( S X )
(C) P ( S X ) , P ( S X ) ; P ( SY ) , P ( SY ) (D) P ( S X ) , P ( SY ) ; P ( S X ) , P ( SY )
[GATE 2004 : IIT Delhi]
Q.9 Select the correct statements regarding mutex lock to prevent race condition:
(A) A process must acquire the lock before entering a critical section
(B) A process need not acquire the lock before entering a critical section;
(C) It releases the lock when it exits the critical section;\
(D) A process must acquire the lock when it exits the critical section
[GATE 2004 : IIT Delhi]
Q.10 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 processes are shown below.
Process X: Process Y:
private i; private i;
for(i=0;i<n; i++) for(i = 0; i<n; i++)
{ {
a[i] = f(i); entry Y (R,S);
exit X (R,S); b[i] = g(a[i]);
} }
Which one of the following represents the CORRECT implementation of Exit X and Entry Y?

(A) ExitX(R, S) { (B) ExitX(R, S) {

P(R); V(R);
V(S); V(S);
} }

EntryY (R, S) { EntryY(R, S) {

P(S); P(R);
V(R); P(S);
} }

(C) ExitX(R, S) { (D) ExitX(R, S) {

P(S); V(R);
V(R); P(S);
} }
EntryY(R, S) { EntryY(R, S) {
V(S); V(S);
P(R); P(R);
} }
[GATE 2013 : IIT Bombay]
Q.11 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 1 and returns the old value of X. It is used in the pseudo code
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
(A) fails as L can overflow
(B) fails as L can take on a non-zero value when the lock is actually available
(C) work correctly but may starve some processes
(D) works correctly without starvation
[GATE 2012 : IIT Delhi]
Q.12 Consider the following two-process synchronization solution
Process 0 Entry: loop while (turn == 1); (critical section) Exit: turn = 1;
Process 1 Entry: loop while (turn == 0); (critical section) Exit: turn = 0;
The shared variable turn is initialized to zero. Which one of the following is TRUE?
(A) This is a correct two-process synchronization solution.
(B) This solution violates mutual exclusion requirement.
(C) This solution violates progress requirement.
(D) This solution violates bounded wait requirement.
[GATE 2016 : IISc Bangalore]
Q.13 Fill in the boxes below to get a solution for the readers-writers problem, using a single binary
semaphore, mutex (initialized to 1) and busy waiting. Write the box numbers (1, 2 and 3), and their
contents in your answer book.

L1 L2

int R = 0, W = 0; Writer () {
Reader () { wait (mutex);
wait (mutex); if () { _________ (3)
if (W == 0) { signal (mutex);
R = R + 1; goto L2;
 ______________(1) }
} W=1;
else { signal (mutex);
 ______________(2) ...../*do the write*/
goto L1; wait( mutex);
} W=0;
..../* do the read*/ signal (mutex);
wait (mutex); }
R = R - 1;
signal (mutex);
 Objective & Numerical Answer Type Questions
1 3 2 80 3 D 4 C 5 C
6 A 7 A 8 A 9 B 10 7
11 A 12 D 13 A 14 A 15 B
16 C 17 B 18 B 19 A 20 C
21 D 22 C 23 C 24 B 25 C
26 A 27 D 28 B,C,D 29 A,C,D 30 B
31 B 32 C 33 *
Practice Questions
1 C 2 B 3 A,B,D 4 C 5 B
6 D 7 B 8 D 9 A,C 10 C
11 B 12 C 13 *

Practice Questions
*13 The first and second blank must be signal(mutex); The third blank is if(R>=1 or W=1)

❖❖❖❖