GATE CSE Concurrency and Synchronization PYQs
Concurrency and Synchronization is consistently evaluated through rigorous interleaving analysis, semaphore tracing, and correctness verification of mutual excl… Read the guide
- Questions
- 18
- Asked
- since 2012
- Total marks
- 32
- Marks / paper
- 1.3
18 GATE CSE Concurrency and Synchronization PYQs with solutions, from Operating Systems. Browse all GATE CSE PYQs.
Questions
Every official paper that asked this topic, newest first.
- GATE CSE 2026 Set 2 · Q51Consider three processes P1, P2, and P3 running identical code, as shown in the pseudocode below. A and B are two binary semaphores initialized to 1 and 0, respectively. X is a shared variable initialized to 0. Each line in the pseudocode is executed atomically.
Pseudocode of P1, P2, and P3
Wait(A); Print(*); X = X+1; If (X == 2) { Print($); Signal(B); } Signal(A); Wait(B); Print(#); Signal(B);…MSQ2 marksMediumSolve - GATE CSE 2024 Set 1 · Q40Consider the following two threads T1 and T2 that update two shared variables and . Assume that initially . 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;<code>b = b +…MCQ2 marksMediumSolve - GATE CSE 2024 Set 2 · Q46Consider a multi-threaded program with two threads
T1andT2. The threads share two semaphores:s1(initialized to 1) ands2(initialized to 0). The threads also share a global variablex(initialized to 0). The threads execute the code shown below.// code of T1 wait(s1); x = x+1; print(x); wait(s2); signal(s1);…MSQ2 marksMediumSolve - GATE CSE 2023 · Q38Consider the two functions
incranddecrshown below.incr(){ wait(s); X = X+1; signal(s); } decr(){ wait(s); X = X-1; signal(s); }There are 5 threads each invokingincronce, and 3 threads each invokingdecronce, on the same shared…MCQ2 marksMediumSolve - GATE CSE 2022 · Q19Consider the following threads, , , and executing on a single processor, synchronized using three binary semaphore variables, , , and , operated upon using standard
wait()andsignal(). The threads can be context switched in any order and at any…MCQ1 markEasyDiagramSolve - GATE CSE 2021 Set 1 · Q46Consider the following pseudocode, where is a semaphore initialized to 5 in line#2 and
counteris 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. }…MSQ2 marksMediumSolve - GATE CSE 2021 Set 2 · Q42Consider the following multi-threaded code segment (in a mix of C and pseudo-code), invoked by two processes P1 and P2, and each of the processes spawns two threads T1 and T2:
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);}…MSQ2 marksMediumSolve - GATE CSE 2020 · Q34Each of a set of processes executes the following code using two semaphores
aandbinitialized to 1 and 0, respectively. Assume thatcountis 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…MCQ2 marksMediumSolve - GATE CSE 2016 Set 1 · Q50Consider the following proposed solution for the critical section problem. There are processes: . In the code, function
pmaxreturns 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);…MCQ2 marksHardSolve - GATE CSE 2016 Set 2 · Q48Consider the following two-process synchronization solution.
Process 0 Process 1 --------- --------- Entry: loop while (turn == 1); Entry: loop while (turn == 0); (critical section) (critical section) Exit: turn = 1; Exit: turn = 0;…MCQ2 marksMediumSolve - GATE CSE 2016 Set 2 · Q49Consider a non-negative counting semaphore . The operation decrements , and increments . During an execution, 20 operations and 12 operations are issued in some order. The largest initial value of for which at least one operation will remain blocked is…NAT2 marksMediumSolve
- GATE CSE 2015 Set 1 · Q9The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.
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 ___________.NAT1 markMediumSolve - GATE CSE 2015 Set 3 · Q10Two processes and need to access a critical section. Consider the following synchronization construct used by both the processes
Here,
varPandvarQare shared variables and both are initialized to false. Which one of the following statements is true?MCQ1 markMediumDiagramSolve - GATE CSE 2014 Set 2 · Q31Consider the procedure below for the *Producer-Consumer* problem which uses semaphores:
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(); } }…MCQ2 marksMediumSolve - GATE CSE 2013 · Q16Three concurrent processes , , and execute three different code segments that access and update certain shared variables. Process executes the operation (i.e., wait) on semaphores , and ; process executes the operation on semaphores , and ;…MCQ1 markMediumSolve
- GATE CSE 2013 · Q34A shared variable , initialized to zero, is operated on by four concurrent processes as follows. Each of the processes and reads from memory, increments by one, stores it to memory, and then terminates. Each of the processes and reads from memory, decrements by…MCQ2 marksHardSolve
- GATE CSE 2013 · Q39A certain computation generates two arrays
aandbsuch that for and for . Suppose this computation is decomposed into two concurrent processes and such that computes the arrayaand …MCQ2 marksMediumSolve - GATE CSE 2012 · Q32Fetch_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…MCQ2 marksMediumSolve
What GATE tests in Concurrency and Synchronization
Concepts, patterns, formulas and traps distilled from past papers.
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.
Core concepts
- Mutual Exclusion, Progress, and Bounded Waiting criteria
- Binary semaphores vs Counting semaphores mechanics
- Hardware atomic primitives (Fetch-and-Add, Test-and-Set) and spinlocks
- Barrier synchronization (Turnstile/Rendezvous) using shared counters and semaphores
- Producer-Consumer bounded-buffer synchronization and semaphore ordering pitfalls
- Deadlock conditions (Circular Wait, Hold-and-Wait) in multi-semaphore acquisitions
- Race conditions and non-atomic Read-Modify-Write instructions (LOAD, INCR, STORE)
- Process address space separation vs Thread shared memory (heap/global) and per-thread private stack
- Mutual Exclusion requirement
- Progress requirement (freedom from outside interference)
- Bounded Waiting requirement
- Strict Alternation protocol and its limitation
- Counting semaphore semantics (P/wait decrements, V/signal increments)
- Permit balance and thread blocking conditions
Recurring question patterns
Shared Variable Extremum / Distinct Values Under Interleaving
Commonmixed2 marks2024, 2023, 2021, 2015Threads 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
CommonMSQ2 marks2026, 2024, 2022Multiple 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
CommonMCQ2 marks2016, 2015, 2014, 2012A 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)
OccasionalMCQ2 marks2020, 2013Snippets 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
RareMSQ2 marks2021Code 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
CommonMCQ2 marks2016Given 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
CommonNAT2 marks2016Given 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.
Formulas GATE uses
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.
Examiner traps in Concurrency and Synchronization
- Assuming separate OS processes share global variables when they actually maintain isolated address spaces.
- Swapping the order of mutex semaphore `wait(mutex)` and counting semaphore `wait(empty/full)`, leading to nested wait deadlock.
- Forgetting that local variables inside functions called by threads are allocated on per-thread stacks and are not shared.
- Missing deadlock scenarios when all N threads perform the first of two consecutive `wait()` operations on a shared counting semaphore.
- Overlooking that a preempted thread storing an early computed value completely overwrites all increments/decrements committed in the interim.
- Assuming Bakery-style ticket algorithms guarantee progress without strict tie-breaking by process ID.
- Confusing the violation of Progress with a violation of Bounded Waiting or Mutual Exclusion in strict alternation solutions.
- Formulating non-strict vs strict inequalities for semaphore blocking (e.g., using S0 + NV ≤ NP instead of S0 + NV < NP when at least one process must remain blocked).
- Assuming a fixed interleaving order when the problem specifies operations occur 'in some order' (requiring analysis of the best-case/worst-case permit availability).
How questions are asked
- Trace and identify all reachable print string patterns (MSQ)
- Find the minimum and maximum possible final value of a shared variable (MCQ/NAT)
- Determine correct semaphore initialization values for a target execution trace (MCQ)
- Analyze a synchronization snippet for Mutual Exclusion and Deadlock violations (MCQ/MSQ)
- Find the deadlock-free acquisition order of multiple semaphores (MCQ)
- Count the total number of distinct final values under all statement interleavings (NAT/MCQ)
- Pseudocode synchronization requirement evaluation (MCQ/MSQ)
- Semaphore permit threshold computation (NAT)
Paper trends
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
Difficulty notes
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.