Process-Synchronization
Question 1 |
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.
wait (a); count = count+1; if (count==n) signal (b); signal (a); wait (b); signal (b);
What does the code achieve?
It ensures that all processes execute CODE SECTION P mutually exclusively. | |
It ensures that at most two processes are in CODE SECTION Q at any time. | |
It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
| |
It ensures that at most n-1 processes are in CODE SECTION P at any time.
|
Question 2 |
A critical section is a program segment
which should run in a certain specified amount of time | |
which avoids deadlocks | |
where shared resources are accessed | |
which must be enclosed by a pair of semaphore operations, P and V |
Question 3 |
The concurrent programming constructs fork and join are as below:
fork
N = 2 M = 2 fork L3 fork L4 S1 L1:join N S3 L2:join M S5 L3:S2 goto L1 L4:S4 goto L2 next:
Theory Explanation. |
Question 4 |
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 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?
1 | |
2 | |
3 | |
None of the above |
repeat
{
V(mutex)
C.S.
V(mutex)
}
forever
Now, let me say P1 is in CS then P1 is in CS
then P10 comes and executes CS (upon mutex).
Now, P2 comes (down on mutex).
Now P10 moves out of CS (again binary semaphore will be 1).
Now P3 comes (down on mutex).
Now P10 comes (upon mutex).
Now P4 comes (down mutex).
⁞
So, if we take P10 'in' and 'out' of CS recursively, all 10 processes can be in CS at same time using binary semaphore only.
Question 5 |
When the result of a computation depends on the speed of the processes involved there is said to be
cycle stealing | |
rare condition | |
a time lock | |
a deadlock |
Speed of processes corresponds to ordering of processes.
Question 6 |
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
0 | |
8 | |
10 | |
12 |
S = 10
Now 6P operations and uv operations were completed on this semaphore. So final value of S will be
S = 10 - 6 + 4 = 8
Question 7 |
(a) A certain processor provides a 'test and set' instruction that is used as follows:
TEST register, flag
This instruction atomically copies flag to register and sets flag to 1. Give pseudo-code for implementing the entry and exit code to a critical region using this instruction.
(b) Consider the following solution to the producer-consumer problem using a buffer of size 1. Assume that the initial value of count is 0. Also assume that the testing of count and assignment to count are atomic operations.
Producer: Repeat Produce an item; if count = 1 then sleep; place item in buffer. Count = 1; Wakeup(Consumer); Forever Consumer: Repeat if count = 0 then sleep; Remove item from buffer; Count = 0; Wakeup(Producer); Consume item; Forever;
Show that in this solution it is possible that both the processes are sleeping at the same time.
Theory Explanation. |
Question 8 |
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:
Thrashing | |
Deadlock | |
Starvation, but not deadlock | |
None of the above |
Question 9 |
(a) 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.
int R = 0, W = 0; Reader () { L1: wait (mutex); If (W ==0) { R = R +1; ▭______(1) } else { ▭______(2) goto L1; } …./* do the read */ wait (mutex) R = R – 1; signal (mutex); } Writer () { L2: wait(mutex); If (▭) {______(3) signal (mutex); goto L2; } W=1; signal (mutex); …./*do the write*/ wait(mutex) W = 0; signal (mutex);
(b) Can the above solution lead to starvation of writers?
Theory Explanation is given below. |
(ii) Signal (mutex)
(iii) R ⇒ 1 (or) W == 1
(b) In CS, atleast one of the reader is always present. That means writer can't be enter into the critical section.
This leads to readers-writers problem may occur in the queue.
Question 10 |
Consider Peterson’s algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process 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 actions. until false;
For the program to guarantee mutual exclusion, the predicate P in the while loop should be.
flag[j]=true and turn=i | |
flag[j]=true and turn=j | |
flag[i]=true and turn=j | |
flag[i]=true and turn=i |
Question 11 |
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.
Question 12 |
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 ensure that the output string never contains a substring of the form 01n0 or 10n1 where n is odd?
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 and T initially 1 | |
P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1 | |
V(S) at W, V(T) at X, P(S) at Y, P(T) at Z, S and T initially 1 |
Question 13 |
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 14 |
Consider the solution to the bounded buffer producer/consumer problem by using general semaphores S, F, and E. The semaphore S is the mutual exclusion semaphore initialized to 1. The semaphore F corresponds to the number of free slots in the buffer and is initialized to N. The semaphore E corresponds to the number of elements in the buffer and is initialized to 0.
Producer Process Consumer Process Produce an item; Wait(E); Wait(F); Wait(S); Wait(S); Append the items to the buffer; Signal(S); Signal(S); Signal(F); Signal(E); Consume the item;
Which of the following interchange operations may result in a deadlock? 1. Interchanging Wait (F) and Wait (S) in the Producer process 2. Interchanging Signal (S) and Signal (F) in the Consumer process
1 only | |
2 only | |
Neither 1 nor 2 | |
Both 1 and 2 |
Now if Wait(S) in producer succeeds, then producer will wait for Wait(F) which is never going to succeed as consumer would be waiting for Wait(S). So deadlock, can happen.
If Signal(S) and Signal(F) are interchanged in consumer, deadlock won't happen. It will just give priority to a producer compared to the next consumer waiting.
Question 15 |
The wait and signal operations of a monitor are implemented using semaphores as follows. In the following,
x is a condition variable,
mutex is a semaphore initialized to 1,
x_sem is a semaphore initialized to 0,
x_count is the number of processes waiting on semaphore x_sem, initially 0, next is a semaphore initialized to 0,
next_count is the number of processes waiting on semaphore next, initially 0.
The body of each procedure that is visible outside the monitor is replaced with the following:
P(mutex); ⋮ body of procedure ⋮ if (next_count > 0) V(next); else V(mutex);Each occurrence of x.wait is replaced with the following:
x_count = x_count + 1; if (next_count > 0) V(next) else V(mutex); ------------------------------------------------------------ E1; x_count = x_count - 1;Each occurrence of x.signal is replaced with the following:
if (x_count > 0) { next_count = next_count + 1; ------------------- E2; P(next), next_count = next_count - 1; }For correct implementation of the monitor, statements E1 and E2 are, respectively,
P(x_sem), V(next) | |
V(next), P(x_sem) | |
P(next), V(x_sem) | |
P(x_sem), V(x_sem) |
x_count is incremented and decremented in x_wait, which shows that in between them wait(x_sem) must happen which is P(x_sem). Correspondingly V(x_sem) must happen in x_signal. So, D choice.
Question 16 |
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?
(i) is false and (ii) is true | |
Both (i) and (ii) are false | |
(i) is true and (ii) is false | |
Both (i) and (ii) are true |
Question 17 |
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
signal (mutex), wait (wrt), signal (wrt), wait (mutex) | |
signal (wrt), signal (mutex), wait (mutex), wait (wrt) | |
wait (wrt), signal (mutex), wait (mutex), signal (wrt) | |
signal (mutex), wait (mutex), signal (mutex), wait (mutex) |
S2: After readcount has been updated, UP on mutex.
S3: DOWN on mutex to update readcount.
S4: If readcount is zero, i.e., no reader is reading, UP on wrt to allow some writer to write.
Question 18 |
The following is a code with two threads, producer and consumer, that can run in parallel. Further, S and Q are binary semaphores equipped with the standard P and V operations.
semaphore S = 1, Q = 0; integer x; producer: consumer: while(true) do while(true) do P(S); P(Q); x = produce (); consume (x); V(Q); V(S); done doneWhich of the following is TRUE about the program above?
The process can deadlock | |
One of the threads can starve | |
Some of the items produced by the producer may be lost | |
Values generated and stored in ‘x’ by the producer will always be consumed before the producer can generate a new value |
(B) No starvation happen because there is alteration between Producer and Consumer.
(C) No items is lost.
Question 19 |
A critical region is
One which is enclosed by a pair of P and V operations on semaphores. | |
A program segment that has not been proved bug-free. | |
A program segment that often causes unexpected system crashes. | |
A program segment where shared resources are accessed. |