High yield ●●●

🔒 Synchronization & Concurrency

Why it matters: Semaphore programs and critical-section solutions are tested every year: does it ensure mutual exclusion, deadlock freedom, what outputs are possible.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 5 done.

Formulas

Critical-section requirements
mutual exclusion + progress + bounded waiting
Binary semaphore
init 1; P(S) before the critical section, V(S) after
Bounded buffer
empty = n, full = 0, mutex = 1
Counting semaphore value
initial value − (P completed) + (V completed) ≥ 0; if negative in the textbook form, |value| = number of blocked processes
Peterson entry
flag[i] = true; turn = j; while (flag[j] && turn == j);

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Does this solution guarantee mutual exclusion / progress / bounded waiting?
Try the bad interleaving: both set flags, or both check before either sets.
★★★
Semaphore code: possible outputs or final value
Track the semaphore value, which processes block, and which orders of P and V are possible.
★★★
Producer-consumer / readers-writers / philosophers variants
Find the missing or misplaced P or V, or the deadlock caused by the wrong order.
★★★
Minimum or maximum value of a shared variable
Interleave the load, add and store steps to find the extreme result.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

10 real questions from the official GATE CSE papers (2012 to 2024), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

10 questions · 0 correct of 0 attempted · marks 0 / 18

Year:
GATE 2024 CS1 · Q40MCQ2 marks
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?
GATE 2024 CS2 · Q46MSQ2 marks
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). T1:
wait(s1);
x = x + 1;
print(x);
wait(s2);
signal(s1)
T2:
wait(s1);
x = x + 1;
print(x);
signal(s2);
signal(s1)
Which of the following outcomes is/are possible when threads T1 and T2 execute concurrently?

One or more options may be correct. Select all that apply, then submit.

GATE 2023 · Q38MCQ2 marks
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?
GATE 2022 · Q19MCQ1 mark
Consider the following threads, T1, T2, and T3 executing on a single processor, synchronized using three binary semaphore variables, S1, S2, and S3, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time. T1:
while (true) {
  wait(S3);
  print("C");
  signal(S2);
}
T2:
while (true) {
  wait(S1);
  print("B");
  signal(S3);
}
T3:
while (true) {
  wait(S2);
  print("A");
  signal(S1);
}
Which initialization of the semaphores would print the sequence BCABCABCA....?
GATE 2021 Set 1 · Q46MSQ2 marks
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.
1  int counter = 0;
2  Semaphore S = init(5);
3  void parop(void) {
5      wait(S);
6      wait(S);
7      counter++;
8      signal(S);
9      signal(S);
10 }
If five threads execute the function parop concurrently, which of the following program behavior(s) is/are possible?

One or more options may be correct. Select all that apply, then submit.

GATE 2020 · Q34MCQ2 marks
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?
GATE 2019 Set 2 · Q23NAT1 mark
Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100. P1: D = D + 20; P2: D = D − 50; P3: 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 processes have completed execution are X and Y respectively, then the value of Y − X is ______.
GATE 2018 · Q40MCQ2 marks
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:
do {
  wait(P);
  wait(mutex);
  /* add item to buffer */ signal(mutex);
  signal(Q);
}  while (1);
Consumer:
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?
GATE 2013 Code A · Q34MCQ2 marks
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?
GATE 2012 Code A · Q32MCQ2 marks
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.
AcquireLock(L) {
  while (Fetch_And_Add(L, 1)) L = 1;
}
ReleaseLock(L) {
  L = 0;
}
This implementation

Common traps

Spinlock vs mutex: a spinlock never sleeps, so on a single CPU it wastes the whole quantum.
Test-and-set gives mutual exclusion but not bounded waiting on its own.
A semaphore signal is remembered; a condition-variable signal with no waiter is lost.
Do not confuse deadlock (nobody can proceed) with starvation (someone is unlucky forever).