Loading previous year questions
18 Qs · since 2012 · 32 marks · 1.3 marks/paperMedium yield
Concurrency and Synchronization is consistently evaluated through rigorous interleaving analysis, semaphore tracing, and correctness verification of mutual exclusion algorithms. Ov… Guide
Wait(A);
Print(*);
X = X+1;
If (X == 2)
{
Print($);
Signal(B);
}
Signal(A);
Wait(B);
Print(#);
Signal(B);…a = a + 1;
<code>b = b +…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.
// code of T1
wait(s1);
x = x+1;
print(x);
wait(s2);
signal(s1);…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…wait() and signal(). The threads can be context switched in any order and at any…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)
4. {
5. wait(S);
6. wait(S);
7. counter++;
8. signal(S);
9. signal(S);
10. }…int x = 0; // global
Lock L1; // global
main() {
create a thread to execute foo(); // Thread T1
create a thread to execute foo(); // Thread T2
wait for the two threads to finish execution;
print (x);}
foo() {
int y = 0;
Acquire L1;
x = x + 1;
y = y + 1;
Release L1;
print (y);}…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…pmax returns an integer not smaller than any of its arguments. For all , t[i] is initialized to zero.
Code for :
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);…Process 0 Process 1
--------- ---------
Entry: loop while (turn == 1); Entry: loop while (turn == 0);
(critical section) (critical section)
Exit: turn = 1; Exit: turn = 0;…P1 ( ) {
C = B - 1;
B = 2 * C;
}P2 ( ) {
D = 2 * B;
B = D - 1;
}
The number of distinct values that B can possibly take after the execution is ___________.varP and varQ are shared variables and both are initialized to false. Which one of the following statements is true?semaphore n = 0;
semaphore s = 1;
void producer()
{
while(true)
{
produce();
semWait(s);
addToBuffer();
semSignal(s);
semSignal(n);
}
}
void consumer()
{
while(true)
{
semWait(s);
semWait(n);
removeFromBuffer();
semSignal(s);
consume();
}
}…a and b such that for and for . Suppose this computation is decomposed into two concurrent processes and such that computes the array a and …Topic guide
Concurrency and Synchronization is consistently evaluated through rigorous interleaving analysis, semaphore tracing, and correctness verification of mutual exclusion algorithms. Over the years, GATE tests whether candidates can systematically trace race conditions, identify potential deadlocks from mismatched semaphore wait/signal orders, and compute the bounds or exact sets of possible shared variable values under non-atomic operations. Recent papers heavily favor Multi-Select Questions (MSQs) requiring complete enumeration of all valid execution traces and program outcomes.
Shared Variable Extremum / Distinct Values Under Interleaving
common · mixed · 2 marks · 2024, 2023, 2021, 2015
Threads or processes execute non-atomic read-modify-write sequences (or arithmetic updates) on shared variables under binary or counting semaphores. The candidate must find the maximum/minimum possible final values, the number of distinct outcomes, or enumerate all possible resulting (x, y) tuples.
Semaphore-Based Execution Tracing and Possible Output Patterns
common · MSQ · 2 marks · 2026, 2024, 2022
Multiple processes or threads coordinate using binary/counting semaphores with specific initial values. Candidates trace the execution order, determine whether specific print/event sequences are possible, or find the correct semaphore initializations required to force a specific recurring sequence.
Synchronization Primitive Flaw and Deadlock Analysis
common · MCQ · 2 marks · 2016, 2015, 2014, 2012
A synchronization scheme (such as Producer-Consumer, lock-free/hardware primitive like Fetch_And_Add, or custom flag/Bakery algorithm) is provided with subtle flaws. The question asks whether Mutual Exclusion, Progress, Bounded Waiting, or Deadlock-freedom are violated.
Synchronization Pattern Recognition (Barrier, Pipeline Handshake, Resource Ordering)
occasional · MCQ · 2 marks · 2020, 2013
Snippets implementing classical coordination paradigms (e.g., barrier/rendezvous counters, lockstep producer-consumer handshake, Dijkstra resource hierarchy for deadlock prevention) are evaluated to identify their high-level functionality or correct implementation.
Process vs. Thread Memory Isolation with Synchronization
rare · MSQ · 2 marks · 2021
Code involves both multi-processing (fork/independent address spaces) and multi-threading with locks. Tests distinction between thread-shared global variables vs. process-private global memory vs. thread-local stack variables.
Critical Section Protocol Requirement Verification
common · MCQ · 2 marks · 2016
Given a concurrent pseudocode snippet for two processes sharing control variables (such as a turn or flag variable), determine which of the standard criteria (Mutual Exclusion, Progress, Bounded Waiting) are satisfied or violated.
Counting Semaphore Balance and Blocking Bounds
common · NAT · 2 marks · 2016
Given a total count of (wait) and (signal) operations executed in an arbitrary order on a counting semaphore, compute the extreme (maximum or minimum) initial semaphore value that guarantees or permits blocking of at least processes.
Total Valid Interleavings of Independent Thread Statements
Used to count all possible context-switched instruction sequences when threads execute atomic instructions respectively.
Lost Update Overwrite Bound (Counting Semaphore Concurrency)
Used when counting semaphore allows one thread to read the initial value and hold it while all opposite operations execute, overwriting all intermediate updates upon committing.
Dijkstra Resource Hierarchy Condition (Deadlock Prevention)
Used to verify whether an ordering of semaphore wait/P operations is guaranteed to be deadlock-free by ruling out circular wait.
Semaphore Blocking Condition
Determining the largest initial non-negative semaphore value such that at least one operation remains blocked when wait operations and signal operations are issued.
Net Available Permits After Execution
Tracking permit consumption and remaining capacity across sequences of and invocations.
Shift from single-correct MCQs analyzing algorithm correctness towards multi-select questions (MSQs) tracing all possible interleaved execution paths and identifying multiple valid output strings or deadlock states.
2026, 2024, 2021
Increased focus on counting semaphores enabling partial concurrency (e.g., initial value > 1), requiring candidates to analyze overwrite scenarios when multiple threads enter critical sections.
2023, 2021, 2013
Rise in discrete combinatoric interleaving problems where candidates evaluate statement permutations (e.g., binom(n+m, n)) to deduce reachable states.
2024, 2015
Questions are split between algorithmic reasoning on classic software synchronization primitives (e.g., strict alternation) and quantitative permit bounds via NATs on counting semaphores.
2016
Easy items involve direct execution tracing of 2-3 threads with binary semaphores to find a fixed periodic printing sequence. Medium items require multi-step interleaving analysis, calculating maximum/minimum final values under counting semaphores, or detecting deadlocks in multi-threaded/multi-process code (especially MSQs with multiple valid interleaving outcomes). Hard items involve subtle algorithmic flaws (such as missing tie-breakers in Bakery variants or concurrent lock overwrites with atomic instructions) requiring rigorous counterexample construction.