Process Synchronisation Questions and Answers

Q: Producer:Consumer:do{ wait(P); wait(mutex); //Add item to buffer signal(mutex); signal(Q);}while(1);do{ wait(R); wait(mutex); //Consume item from buffer signal(mutex); signal(S);}while(1);Which one of the following assignments to P, Q, R and S will yield the correct solution?

The correct assignment is P: full, Q: empty, R: empty, S: full.Note the unusual naming in this question: full counts the free slots (it starts at N) and empty counts the filled slots (it starts at 0). The producer must wait for a free slot, so P is full, and after adding an item it announces a filled slot, so Q is empty. The consumer waits for a filled slot, so R is empty, and after removing an item it frees a slot, so S is full.In option B and option D the producer waits on empty, which is 0 at the start, so it blocks before producing anything; in D the consumer also waits on full and could consume from an empty buffer. In option A the producer signals full after adding, creating free slots that do not exist, while the consumer waits forever on empty.

Q: Consider the following proposed solution for the critical section problem. There are \(n\) processes: \(P_{0} \ldots P_{n-1}\). 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[n-1])+1; c[i]=0; for every j \(\ne\) i in {0,...,n-1} { while (c[j]); while (t[j] != 0 && t[j]\(\lt\)=t[i]); } Critical Section; t[i]=0; Remainder Section;} while (true);Which one of the following is TRUE about the above solution?

The true statement is At most one process can be in the critical section at any time.This is a simplified bakery algorithm. A process picks a ticket larger than every current ticket, and before entering waits for each other process that is choosing a ticket (c[j]) and for each process holding a nonzero ticket no larger than its own. Two processes can never both pass the second wait for each other, because each would need the other's ticket to be zero or strictly larger. So mutual exclusion holds.The other properties fail. Two processes can compute pmax at the same moment and get equal tickets. Then each sees t[j] equal to t[i], satisfies t[j] \(\lt\)= t[i], and waits for the other forever: a deadlock. That breaks deadlock-freedom and progress. The real bakery algorithm avoids this by breaking ties with process ids, which this version omits; with processes able to deadlock, bounded waiting is not guaranteed either.

Q: 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.T1:a = a + 1;b = b + 1;T2:b = 2 * b;a = 2 * a;Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?

The possible results are (a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3).Each thread's two statements run in order, giving six interleavings. What matters is whether each update to a comes before or after the other thread's update to a, and the same for b:a: a + 1 then 2a gives 4; 2a then a + 1 gives 3.b: b + 1 then 2b gives 4; 2b then b + 1 gives 3.T1 updates a before b and T2 updates b before a. If T1's a-update comes after T2's a-update, T2 has already finished, so T1's b-update is also last: (3, 3). Otherwise a = 4 and b can be either. So (4, 4), (4, 3) and (3, 3) occur, but (3, 4) cannot, which rules out options B and C. Values of 2 would require an update to be lost, impossible with atomic statements.

Q: 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?

The solution violates the progress requirement.This is strict alternation. Mutual exclusion holds: turn is either 0 or 1, and each process can enter only when turn has its own value, so both can never be inside together. Bounded waiting also holds, because after a process leaves it hands the turn to the other, so neither can enter twice while the other waits.Progress fails. Suppose Process 0 runs its critical section and sets turn = 1, and Process 1 has no wish to enter. If Process 0 now wants to enter again, it must wait for Process 1 to take its turn, which may never happen. A process outside its critical section is blocking another from entering, which is exactly what the progress requirement forbids.

Q: Consider the two functions incr and decr shown below.incr(){wait(s);X = X+1;signal(s);}decr(){wait(s);X = X-1;signal(s);}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?

The minimum values are V1 = 12 and V2 = 7.I-1. A binary semaphore initialised to 1 lets only one thread into the critical section at a time, so every update is applied in full and the result is the same in every run:\[ V_{1} = 10 + 5 - 3 = 12 \]I-2. A counting semaphore initialised to 2 lets two threads update X together, so one update can overwrite another (X = X+1 is a read, an add and a write). To make X as small as possible: a decr thread reads X = 10 and pauses inside. Meanwhile the five incr threads pass one by one through the second slot, raising X to 15. The paused decr then writes 9, wiping out all five increments. The other two decr threads run normally: 8, then 7.No run can end below 7, because the three decrements can lower X by at most 3 from 10. So V2 = 7. 15 and 7 as V1 are impossible under mutual exclusion, and 8 is reachable but is not the minimum.

Q: P and Q are amongst the five synchronization objects supported by windows.P blocks access to a resource until some other thread or process signals that it may be used. Q prevents a block of code being used by more than one thread at a time.What is P and Q ?

P is an Event object and Q a critical section object.A Windows event object blocks threads waiting on it until another thread or process signals it, so it fits P, 'blocks access ... until some other thread or process signals that it may be used'. A critical section object lets only one thread of a process at a time execute a protected block of code, which matches Q.A waitable timer is signalled when a set time arrives, not by another thread, so it does not fit Q. A semaphore limits access to a count of users, and although a mutex also gives mutual exclusion, it does not fit P, which is signalled rather than owned and released.

Direction for [ Question No: 1 To 1 ] :

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{ wait(P); wait(mutex); //Add item to buffer signal(mutex); signal(Q); }while(1);	do{ wait(R); wait(mutex); //Consume item from buffer signal(mutex); signal(S); }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

Exam Year(s)

GATE CS - 2018,

Answer: C

The correct assignment is P: full, Q: empty, R: empty, S: full.

Note the unusual naming in this question: full counts the free slots (it starts at N) and empty counts the filled slots (it starts at 0). The producer must wait for a free slot, so P is full, and after adding an item it announces a filled slot, so Q is empty. The consumer waits for a filled slot, so R is empty, and after removing an item it frees a slot, so S is full.

In option B and option D the producer waits on empty, which is 0 at the start, so it blocks before producing anything; in D the consumer also waits on full and could consume from an empty buffer. In option A the producer signals full after adding, creating free slots that do not exist, while the consumer waits forever on empty.

Discuss in Forum

Consider the following proposed solution for the critical section problem. There are \(n\) processes: \(P_{0} \ldots P_{n-1}\). 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[n-1])+1; c[i]=0;
    for every j \(\ne\) i in {0,...,n-1} {
        while (c[j]);
        while (t[j] != 0 && t[j]\(\lt\)=t[i]);
    }
    Critical Section;
    t[i]=0;
    Remainder Section;
} while (true);

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

Exam Year(s)

GATE CS - 2016,

Answer: A

The true statement is At most one process can be in the critical section at any time.

This is a simplified bakery algorithm. A process picks a ticket larger than every current ticket, and before entering waits for each other process that is choosing a ticket (c[j]) and for each process holding a nonzero ticket no larger than its own. Two processes can never both pass the second wait for each other, because each would need the other's ticket to be zero or strictly larger. So mutual exclusion holds.

The other properties fail. Two processes can compute pmax at the same moment and get equal tickets. Then each sees t[j] equal to t[i], satisfies t[j] \(\lt\)= t[i], and waits for the other forever: a deadlock. That breaks deadlock-freedom and progress. The real bakery algorithm avoids this by breaking ties with process ids, which this version omits; with processes able to deadlock, bounded waiting is not guaranteed either.

Discuss in Forum

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.

T1:
a = a + 1; b = b + 1;

T2:
b = 2 * b; a = 2 * a;

Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 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)

Exam Year(s)

GATE CS - 2024,

Answer: A

The possible results are (a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3).

Each thread's two statements run in order, giving six interleavings. What matters is whether each update to a comes before or after the other thread's update to a, and the same for b:

a: a + 1 then 2a gives 4; 2a then a + 1 gives 3.
b: b + 1 then 2b gives 4; 2b then b + 1 gives 3.

T1 updates a before b and T2 updates b before a. If T1's a-update comes after T2's a-update, T2 has already finished, so T1's b-update is also last: (3, 3). Otherwise a = 4 and b can be either. So (4, 4), (4, 3) and (3, 3) occur, but (3, 4) cannot, which rules out options B and C. Values of 2 would require an update to be lost, impossible with atomic statements.

Discuss in Forum

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.

Exam Year(s)

GATE CS - 2016,

Answer: C

The solution violates the progress requirement.

This is strict alternation. Mutual exclusion holds: turn is either 0 or 1, and each process can enter only when turn has its own value, so both can never be inside together. Bounded waiting also holds, because after a process leaves it hands the turn to the other, so neither can enter twice while the other waits.

Progress fails. Suppose Process 0 runs its critical section and sets turn = 1, and Process 1 has no wish to enter. If Process 0 now wants to enter again, it must wait for Process 1 to take its turn, which may never happen. A process outside its critical section is blocking another from entering, which is exactly what the progress requirement forbids.

Discuss in Forum

Consider the following threads, T₁, T₂, and T₃ executing on a single processor, synchronized using three binary semaphore variables, S₁, S₂, and S₃, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time.

T₁	T₂	T₃
while(true){ wait(S₃); print("C"); signal(S₂); }	while(true){ wait(S₁); print("B"); signal(S₃); }	while(true){ wait(S₂); print("A"); signal(S₁); }

Which initialization of the semaphores would print the sequence BCABCABCA....?

A.\(S_{1} = 1;\ S_{2} = 1;\ S_{3} = 1\)
B.\(S_{1} = 1;\ S_{2} = 1;\ S_{3} = 0\)
C.\(S_{1} = 1;\ S_{2} = 0;\ S_{3} = 0\)
D.\(S_{1} = 0;\ S_{2} = 1;\ S_{3} = 1\)

Exam Year(s)

GATE CS - 2022,

Answer: C

The initialization is \(S_{1} = 1;\ S_{2} = 0;\ S_{3} = 0\).

The sequence must start with B, so only T2, which waits on \(S_{1}\), may run first: \(S_{1} = 1\) and the others 0. Then T2 prints B and signals \(S_{3}\), which lets only T1 print C; T1 signals \(S_{2}\), which lets only T3 print A; T3 signals \(S_{1}\) and the cycle repeats. At every moment exactly one semaphore is 1, so the order BCA is forced.

In the other options more than one semaphore starts at 1. With \(S_{2} = 1\), T3 could print A first; with \(S_{3} = 1\), T1 could print C first; and option D, with \(S_{1} = 0\), cannot print B first at all.

Discuss in Forum

Consider the two functions incr and decr shown below.

incr(){ wait(s); X = X+1; signal(s); }

decr(){ wait(s); X = X-1; signal(s); }

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

Exam Year(s)

GATE CS - 2023,

Answer: C

The minimum values are V1 = 12 and V2 = 7.

I-1. A binary semaphore initialised to 1 lets only one thread into the critical section at a time, so every update is applied in full and the result is the same in every run:

\[ V_{1} = 10 + 5 - 3 = 12 \]

I-2. A counting semaphore initialised to 2 lets two threads update X together, so one update can overwrite another (X = X+1 is a read, an add and a write). To make X as small as possible: a decr thread reads X = 10 and pauses inside. Meanwhile the five incr threads pass one by one through the second slot, raising X to 15. The paused decr then writes 9, wiping out all five increments. The other two decr threads run normally: 8, then 7.

No run can end below 7, because the three decrements can lower X by at most 3 from 10. So V2 = 7. 15 and 7 as V1 are impossible under mutual exclusion, and 8 is reachable but is not the minimum.

Discuss in Forum

P and Q are amongst the five synchronization objects supported by windows.

P blocks access to a resource until some other thread or process signals that it may be used. Q prevents a block of code being used by more than one thread at a time.

What is P and Q ?

A.Event object, Waitable timer
B.Event object, critical section object
C.Semaphore, waitable timer
D.Mutex, critical section object

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: B

P is an Event object and Q a critical section object.

A Windows event object blocks threads waiting on it until another thread or process signals it, so it fits P, 'blocks access ... until some other thread or process signals that it may be used'. A critical section object lets only one thread of a process at a time execute a protected block of code, which matches Q.

A waitable timer is signalled when a set time arrives, not by another thread, so it does not fit Q. A semaphore limits access to a count of users, and although a mutex also gives mutual exclusion, it does not fit P, which is signalled rather than owned and released.

Discuss in Forum

Loading…

Topics

Subject Categories

Tags: Process Synchronisation Questions and Answers || Process Synchronisation MCQ Questions and Answers || Process Synchronisation GK Questions and Answers || Process Synchronisation GK MCQ Questions || Process Synchronisation Multiple Choice Questions and Answers || Process Synchronisation GK || GK on Process Synchronisation || Operating Systems Questions and Answers || Operating Systems MCQ Questions and Answers || Operating Systems GK Questions and Answers || GK on Operating Systems

Process Synchronisation Questions and Answers

Direction for [ Question No: 1 To 1 ] :

Topics

Subject Categories

About Us

Stay informed about all important Dates & Notifications