Previous Year Questions: Process Synchronization | Operating System - Computer Science Engineering (CSE) PDF Download

Q1: Consider a multi-threaded program with two threads T1 and T2. The threads share two semaphores: s1 (initialized to 1) and s2 (initialized to 0). The threads also share a global variable x (initialized to 0). The threads execute the code shown below.  (2024 SET 2) 

Which of the following outcomes is/are possible when threads T1 and T2 execute concurrently?
(a) T1 runs first and prints 1, T2 runs next and prints 2
(b) T2 runs first and prints 1, T1 runs next and prints 2
(c) T1 runs first and prints 1, T2 does not print anything (deadlock)
(d) T2 runs first and prints 1, T1 does not print anything (deadlock)
Ans: (b, c)
Sol: In the initial, as you can see, both threads T1 and T2 are doing wait operations on S1. As initially, the value of S1 = 1, then only one thread can run.
If T1 runs first, then, it will get stuck on statement wait(S2) and this will lead to T2 not being able to run and getting blocked upon executing wait(S1). This will cause a deadlock.
Hence, options B and C are correct

Q2: Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a=b=1. Though context switching between threads can happen at any time, each statement of T1 or T2 is executed atomically without interruption.  (2024 SET 1) Which one of the following options lists all the possible combinations of values of a a and b b after both T 1  and T 2  finish execution?
 (a) (a=4, b=4) ;(a=3, b=3) ;(a=4, b=3)
(b) (a=3, b=4) ;(a=4, b=3) ;(a=3, b=3)
(c) (a=4, b=4) ;(a=4, b=3) ;(a=3, b=4)
(d) (a=2, b=2) ;(a=2, b=3) ;(a=3, b=4)
Ans: (a) 
Sol: Let's assume that the given statements are as A,B,C,D. we can execute these statements in any order and can preempt at any point in time.

• A: a= a + 1
• B: b = b +1
• C: b =2 x b
• D: a = a x 2

The possible execution sequences are as follows:

1. A, B, C, D
2. A, C, D, B
3. A, C, B, D
4. C, D,  A, B
5. C, A, B, D
6. C, A, D, B

Let's understand how different output is generated when we interchange the execution order.
1) A , B , C , D : in this sequence initial value of a = 1 , b = 1 .
when A is executed a update it's value as a = 2 , b = 1
when B is executed b update it's value as a = 2 , b = 2
when C is executed b update it's value as a = 2 , b = 4
when D is executed a update it's value as a = 4 ,
2) A , C , D , B : in this sequence initial value of a = 1 , b = 1 .
when A is executed a update it's value as a = 2 , b = 1
when C is executed b update it's value as a = 2 , b = 2
when D is executed b update it's value as a = 4 , b = 2
 when B is executed a update it's value as a = 4 , b = 3
3) A , C , B , D : in this sequence initial value of a = 1 , b = 1 .
 when A is executed a update it's value as a = 2 , b = 1
 when C is executed b update it's value as a = 2 , b = 2
 when B is executed b update it's value as a = 2 , b = 3
 when D is executed a update it's value as a = 4 ,b = 3
4) C , D , A , B : in this sequence initial value of a = 1 , b = 1 .
when C is executed a update it's value as a = 1 , b = 2
when D is executed b update it's value as a = 2 , b = 2
when A is executed b update it's value as a = 3 , b = 2
when B is executed a update it's value as a = 3 , b = 3
5) C , A , B , D : in this sequence initial value of a = 1 , b = 1 .
 when C is executed a update it's value as a = 3 , b = 2
when A is executed b update it's value as a = 2 , b = 2
 when B is executed b update it's value as a = 2 , b = 3
when D is executed a update it's value as a = 4 , b = 3
6) C , A , D , B : in this sequence initial value of a = 1 , b = 1 .
when C is executed a update it's value as a = 1 , b = 2
when A is executed b update it's value as a = 2 , b = 2
when D is executed b update it's value as a = 4 , b = 2
when B is executed a update it's value as a = 4 ,
We can see that the given program produces three different values of a ′ s . b ′ s as ( 4 , 4 ) , ( 4 , 3 ) , ( 3 , 3 ) Option ( A ) is correct.

Q3: Consider the two functions incr and decr shown below.  (2023 )

There are 5 threads each invoking incr once, and 3 threads each invoking decr once, on the same shared variable X. The initial value of X is 10.
Suppose there are two implementations of the semaphore s, as follows:
I-1: s is a binary semaphore initialized to 1.
I-2: s is a counting semaphore initialized to 2.
Let V1, V2 be the values of X at the end of execution of all the threads with implementations I-1, I-2, respectively.
Which one of the following choices corresponds to the minimum possible values of V1, V2, respectively?
(a) 15, 7
(b) 7, 7
(c) 12, 7
(d) 12, 8
Ans: (c)
Sol: For I-1:
Initially, X = 10, s = 1 (mutual exclusion), and ‘s’ is in binary semaphore. So, after executing 5 incr() the value of X becomes 10 + 5 = 15, and after executing 3 decr() the value of X becomes 15 - 3 = 12.
For I-2:
Initially, X = 10, s = 2 (counting semaphore). This means, two processes can enter the critical section simultaneously. Let's say, the final values of X written by only the right-hand side function in each pass below-
So, V1 and V2 become 12 and 7. The correct answer is Option C.

Q4: Consider the following threads, T ₁ , T ₂ , and T ₃  executing on a single processor, synchronized using three binary semaphore variables, S _{1 ,} S ₂ , and S ₃  , operated upon using standard w a i t ( ) wait() and signal(). The threads can be context switched in any order and at any time.  (2022)
Which initialization of the semaphores would print the sequence BCABCABCA ...?
(a) S₁=1; S₂ = 1; S₃ = 1
(b) S₁=1; S₂ = 1; S₃ = 0
(c) S₁=1; S₂ = 1; S₃ = 0
(d) S₁=0; S₂ = 1; S₃ =1
Ans: (c)
Sol:  Thread T₂ prints B. Thread T₁ prints C. Thread T₃ prints  A.
These three threads are executing on a single processor. We want these threads to be synchronized in such a way that we get the sequence B C A   B C A  B C A … printed.
The threads can be context switched in any order and at any time. But in whichever order they run, pre-empt, run again; the sequence that should be printed is  B C A   B C A  B C A ...
Hence, Logically, we want the threads to execute in the following order :  T₂, T₁, T₃,  T₂, T₁, T₃, T₂, T₁, T₃ 
First T₂ should be able to print. Hence, binary semaphore S₁ must be 1 initially.
Clearly, first T₁ Or T₃ should not be able to print, So, S₃ = 0, S₂ = 0 initially.
Also, with S₁ = 1, S₃=0, S₂ = 0 initially, we can verify that the sequence   B C A   B C A  B C A ...  is printed, as following
T₂ prints B, then wakes up  T₁.
T₁ prints C, then wakes up T₃.
T₃ prints A, then wakes up T2.
Same scenario repeats continuously.

Q5:  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:  (2021 SET 2)

Which of the following choice(s) about the above scheme is/are correct?
[MSQ]
(a) The scheme ensures that deadlocks will not occur
(b) The scheme may lead to live-lock
(c) The scheme may lead to starvation
(d) The scheme violates the mutual exclusion property
Ans: (a, b, c)
Sol: A system is in Deadlock when all the processes are in Waiting state. This is similar to a traffic jam where no vehicle moves.
A system is in Livelock when the processes do repeated work without any progress for the system (still no useful work). This is similar to a traffic jam where some vehicles reverses and then move forward hitting the same block again.
Now, both deadlock and livelock are mutually exclusive – at any point of time only one can happen in a system. But both of them imply no progress for system and hence starvation for the processes involved.
Now, coming to the given question, any process can kick out another process and then acquire the nedeed resource and this can go in a cyclic fashion ensuring a livelock. There is no possibility of a deadlock as at any time a process is free to kick out another process. Since there is a possibility of livelock, starvation possibility is also there. So, options A, B and C are TRUE.
A process is acquiring the resource owned by another process only after terminating the other process. Hence there is no violation of mutual exclusion property here.
Correct Answer: A;B;C.

Q6: Consider the following pseudocode, where Sis 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.  (2021 SET 1)

If five threads execute the function parop  concurrently, which of the following program behavior(s) is/are possible?
[MSQ]
(a) The value of countercounter is 5 after all the threads successfully complete the execution of parop.
(b) The value of countercounter is 1 after all the threads successfully complete the execution of parop.
(c) The value of countercounter is 0 after all the threads successfully complete the execution of parop.
(d) There is a deadlock involving all the threads.
Ans: (a, b, d)
Sol: The given code allows up to 2 threads to be in the critical section as the initial value of semaphore is 5 and 2 wait operations are necessary to enter the critical section ( [5 /2 ] = 2).
In the critical section the increment operation is not atomic. So, multiple threads entering the critical section simultaneously can cause race condition.
A. Assume that the 5 threads execute sequentially with no interleaving then after each thread ends the counter value increments by
1. Hence after 5 threads finish, counter value will be incremented 5 times from 0 to 5. Possible.
B. Let’s assume that a process used 2 waits and reads the counter value and didn’t update the value yet, all the other process let’s say the other processes executed sequentially incremented and stored the value as 4 but since the value isn’t written the first process yet the current value is overwritten by the first process as 1. Possible
C. There exists no pattern of execution in which the process increments the current value and completes while maintaining 0 as the counter value. Not possible
D. Assume that all the process use up the first wait operation, the semaphore value will now become zero and deadlock would’ve occurred. Possible
Correct Options: A,B,D

Q7: 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.  (2020)

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 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 SECTION P at any time
Ans: (a)
Sol:  Answer: A. It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
In short, semaphore 'a' controls mutually exclusive execution of statement count+=1 and semaphore 'b' controls entry to CODE SECTION Q when all the process have executed CODE SECTION P. As checked by given condition if(count==n) signal(b); the semaphore 'b' is initialized to 0 and only increments when this condition is TRUE. (Side fact, processes do not enter the CODE SECTION Q in mutual exclusion, the moment all have executed CODE SECTION P, process will enter CODE SECTION Q in any order.)
Consider this situation as the processes need to execute three stages- Section P, then the given code and finally Section Q.
It is evident that semaphores do not control Section P hence, There is no restriction in execution of P.
Now, we are given 2 semaphores 'a' and 'b' initialized to '1' and '0' respectively.
Take an example of 3 processes (hence n=3, count=0(initially) ) and lets say first of them has finished executing Section P and enters the
given code. It does following changes:-
1. will execute wait(a) hence making semaphore a=0
2. increment the count from 0 to 1 (first time)
3. If(count==n) evaluates FALSE and hence signal(b) is not executed. So semaphore b remains 0
4. signal(a) hence making semaphore a=1
5. wait(b) But since semaphore b is already 0, The process will be in blocked/waiting state.
First out of the three processes is unable to enter the CODE SECTION Q !
Now say second process completes CODE SECTION P and starts executing the given code. It can be concluded that it will follow the same sequence (5 steps) as mentioned above and status of variables will be:- count = 2 (still count<n), semaphore a=1, semaphore b=0 (no change)
Finally the last process finishes execution of CODE SECTION P.
It will follow same steps 1 and 2 making semaphore a=0 and count = 3
3. if(count==n) evaluates TRUE! and hence signal(b) is executed marking semaphore b = 1 FOR THE FIRST TIME.
4 and 5 will be executed the same way.
Now the moment this last process signaled b, the previously blocked process will be able to execute wait(b) and the very next moment execute signal(b) to allow other blocked/waiting process to proceed.
This way all the processes enter CODE SECTION Q after executing CODE SECTION P.

Q8: Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100.  (2019) 

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 __________.
(a) 50
(b) 80
(c) 100
(d) 130
Ans: (b)
Sol: D = 100
Arithmetic operations are not ATOMIC.
These are three step process:

1. Read
2. Calculate
3. Update

Maximum value:

• Run P₂ for read and Calculate. D = 100
• Run P₁ for read and calculate. D = 100
• Run P₂ update. D = 50
• Run P₁ update. D = 110
• Run P₂ read, calculate and update. D = 130

Maximum value:

• Run P₁ , P₂ , P₃ for Read and Calculate. D = 100
• Run P₁ update. D = 110
• Run P₃ update. D = 120
•  Run P₂ update. D = 50

Difference between Maximum and Minimum  = 130 - 50 =80.
 
Q9: 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().  (2018)

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
Ans: (c)
Sol: Empty denotes number of Filled slots.
Full number of empty slots.
So, Producer must dealing with Empty and Consumer deals with Full
Producer must checks Full i,e. decrease Full by 1 before entering and Consumer check with Empty decrease Full by 1 before entering
So, (C) must be answer.

Q10: 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 12V(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 ________.  (2016 SET 2)
(a) 8
(b) 7
(c) 12
(d) 20
Ans:  (b)
Sol: V(S): Signal will increment the semaphore variable, that is, S++.
P(S): Signal will decrement the semaphore variable., that is, S--.
Initial counting semaphore = x
Signal operation = 12 V
Wait operation = 20 P
Since at least 1 process in blocked state
Final counting semaphore (F) = -1
F ≥ x + 20P + 12V
-1 ≥ x + 20(- 1) + 12(+ 1)
∴ x ≤ 7
Therefore, largest value of initial semaphore count is 7

Q11: Consider the following two-process synchronization solution.  (2016 SET 2) 

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
Ans: (c)
Sol:  There is strict alternation i.e. after completion of process 0if it wants to start again. It will have to wait until process 1 gives the lock.
This violates progress requirement which is, that no other process outside critical section can stop any other  interested process from entering the critical section.
Hence the answer is that it violates the progress requirement.
The given solution does not violate bounded waiting requirement.
Bounded waiting is : There exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections after a process has made request to enter its critical section and before that request is granted.
Here there are only two processes and when process 0 enters CS, next entry is reserved for process 1and vice-versa (strict alteration). So, bounded waiting condition is satisfied here.
Correct Answer: C

Q12: Consider the following proposed solution for the critical section problem. There are n processes: P ₀ . . . P _{n − 1}. In the code, function p max returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero.  (2016 SET 1) 

Which 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
Ans: (a)
Sol: while (t [j] ! = 0 && t[j] <=t[i] ) ;
This ensures that when a process i reaches Critical Section, all processes j which started before it must have its t[j] = 0. This means no two process can be in critical section at same time as one of them must be started earlier.
is the issue here for deadlock. This means two processes can have same t value and hence
while (t[j] ! = 0 && t [j] <=t [i] ) ;
can go to infinite wait. (t [j] == t [i] ). Starvation is also possible as there is nothing to ensure that a request is granted in a timed manner. But bounded waiting (as defined in Galvin) is guaranteed here as when a process i starts and gets
t [i] value, no new process can enter critical section before i (as their t value will be higher) and this ensures that access to critical section is granted only to a finite number of processes (those which started before) before eventually process i gets access.
But in some places bounded waiting is defined as finite waiting (see one here from CMU) and since deadlock is possible here, bounded waiting is not guaranteed as per that definition.

Q13: Two processes X and Y need to access a critical section. Consider the following synchronization construct used by both the processes  (2015 SET 3)

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
Ans: (a)
Sol: When both processes try to enter critical section simultaneously, both are allowed to do so since both shared variables varP and varQ are true. So, clearly there is NO mutual exclusion. Also, deadlock is prevented because mutual exclusion is one of the necessary condition for deadlock to happen. Hence, answer is (A).

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

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.
Ans: (c)
Sol: 
A. False : Producer = P (let), consumer = C (let)  , once producer produce the item and put into the buffer. It will up the s and n to 1 , so consumer can easily consume the item. So, option (A) Is false.
Code can be execute in this way: P : 1 2 3 4 5 | C : 1 2 3 4 5 . So, consumer can consume item after adding the item to buffer.
B. Is also False, because whenever item is added to buffer means after producing the item, consumer can consume the item or we can say remove the item, if here statement is like the consumer will remove no more than one item from the buffer just after the removing one then it will be true (due n = 0then, it will be blocked ) but here only asking about the consumer will remove no more than one item from the buffer so, its false.
C. is true , statement says if consumer execute first means buffer is empty. Then execution will be like this.
C : 1 (wait on s, s = 0 now) 2 ( BLOCK n = − 1 ) |P : 1 2 (wait on s which is already 0 so, it now block). So, c wants n which is held by producer or we can say up by only producer and P wants s , which will be up by only consumer. (circular wait ) surely there is deadlock.
D. is false,  if n = 1 then, also it will not free from deadlock.
For the given execution: C : 1 2 3 4 5 1 2 (BLOCK) | P : 1 2 (BLOCK) so, deadlock.
(here, 1 2 3 4 5 are the lines of the given code)
Hence, answer is (C)

Q15: A certain computation generates two arrays a and b such that a[i]=f(i)for o ≤ i < n and b[i] = g (a[i] )for o ≤ 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.  (2013)

Which one of the following represents the CORRECT implementations of ExitX and EntryY?
(a) ExitX(R, S) { P(R); V(S); } EntryY(R, S) { P(S); V(R); }
(b) ExitX(R, S) { V(R); V(S); } EntryY(R, S) { P(R); P(S); }
(c) ExitX(R, S) { P(S); V(R); } EntryY(R, S) { V(S); P(R); }
(d) ExitX(R, S) { V(R); P(S); } EntryY(R, S) { V(S); P(R); }
Ans: (c)
Sol: A. X is waiting on R and Y is waiting on X. So, both cannot proceed.
B. Process X is doing Signal operation on R and S without any wait and hence multiple signal operations can happen on the binary semaphore so Process Y won't be able to get exactly n successful wait operations. i.e., Process Y may not be able to complete all the iterations.
C. Process X does Wait(S) followed by Signal(R) while Process Y does Signal(S) followed by Wait(R). So, this ensures that no two iterations of either X or Y can proceed without an iteration of the other being executed in between. i.e., this ensures that all n iterations of X and Y succeeds and hence the answer.
D. Process X does Signal(R) followed by Wait(S) while Process Y does Signal(S) followed by Wait(R). There is a problem here that X can do two Signal(R) operation without a Wait(R) being done in between by Y. This happens in the following scenario Process Y: Does Signal (S);Wait(R) fails; goes to sleep.
Process X: Does Signal(R); Wait(S) succeeds; In next iteration Signal(R) again happens;
So, this can result in some Signal operations getting lost as the semaphore is a binary one and thus Process Y may not be able to complete all the iterations. If we change the order of Signal(S) and Wait(R) in EntryY, then (D) option also can work.

Q16: 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?  (2013)
(a) -2
(b) -1
(c) 1
(d) 2
Ans: (d)
Sol: Since, initial value of semaphore is 2, two processes can enter critical section at a time- this is bad and we can see why.
Say, X and Y be the processes. X increments x by 1 and Z decrements x by 2 . Now, Z stores back and after this X stores back. So, final value of x is 1 and not − 1 and two Signal operations make the semaphore value 2 again. So, now W and Z can also execute like this and the value of x can be 2 which is the maximum possible in any order of execution of the processes
(If the semaphore is initialized to 1, processed would execute correctly and we get the final value of x as −2.)

Q17: 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?  (2013)
(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)
Ans: (b)
Sol:  For deadlock-free invocation, X, Y and Z  must access the semaphores in the same order so that there won't be a case where one process is waiting for a semaphore while holding some other semaphore. This is satisfied only by option B.
In option A, X  can hold a and wait for c while Z can hold c and wait for a
In option C, X can hold b and wait for c, while Y can hold c and wait for b
In option D, X can hold a and wait for c while Z can hold c and wait for a
So, a deadlock is possible for all choices except B.

Q18: 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.  (2012)

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) works correctly but may starve some processes
(d) works correctly without starvation
Ans: (b)
Sol: A process acquires a lock only when L = 0 . When L is 1 , the process repeats in the while loop- there is no overflow because after each increment to L , L is again made equal to 1 . So, the only chance of overflow is if a large number of processes (larger than sizeof(int)) execute the check condition of while loop but not L = 1 , which is  highly improbable.
Acquire Lock gets success only when Fetch_ And_ Add gets executed with L = 0. Now suppose P 1 acquires lock and make L = 1 . P 2 waits for a lock iterating the value of L between 1 and 2 (assume no other process waiting for lock). Suppose when P 1 releases lock by making L = 0 , the next statement P 2 executes is L = 1 . So, value of L becomes 1 and no process is in critical section ensuring L can never be 0 again. Thus, (B) choice.
To correct the implementation we have to replace Fetch_ And_ Add with Fetch_And_Make_Equal_1 and remove L = 1 in Acquire Lock ( L ) .

Q19: 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'?  (2010)

How many times will process P0 print '0'?
(a) At least twice
(b) Exactly twice
(c) Exactly thrice
(d) Exactly once
Ans: (a)
Sol: First P₀ will enter the while loop as S ₀ is 1. Now, it releases both S₁ and S₂ and one of them must execute next. Let that be P₁ . Now, P₀ will be waiting for P₁ to finish. But in the mean time P₂ can also start execution. So, there is a chance that before P₀ enters the second iteration both P₁ and P₂ would have done release ( S ₀ ) which would make S₁ 1 only (as it is a binary semaphore). So, P₀ can do only one more iteration printing ′ 0 ′ two times.
If P₂ does release ( S ₀ ) only after P₀ starts its second iteration, then P₀ would do three iterations printing ′ 0 ′ three times.
If the semaphore had 3 values possible (an integer semaphore and not a binary one), exactly three ′0′s would have been printed.  
Correct Answer: A, at least twice

Q20: 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.  (2010) 

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
Ans: (a)
Sol: Answer is (A). In this mutual exclusion is satisfied, only one process can access the critical section at particular time but here progress will not satisfied because suppose when S1 = 1 and S2 = 0 and process P1 is not interested to enter into critical section but P 2 want to enter critical section. P 2 is not able to enter critical section in this as only when P1 finishes execution, then only P2 can enter (then only S1 = S2 condition be satisfied).
Progress will not be satisfied when any process which is not interested to enter into the critical section will not allow other interested process to enter into the critical section. When P1wants to enter the critical section it might need to wait till P2 enters and leaves the critical section (or vice verse) which might never happen and hence progress condition is violated.