chapter

Concurrency, Synchronization and Deadlocks PYQs for GATE CS

Solve 12+ Concurrency, Synchronization and Deadlocks previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

2026 Slot Set2 PYQ

Consider 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); Assume that any of the three processes can start to execute first and context switching can happen between these processes at any arbitrary time and in any arbitrary order. Which of the following patterns is/are possible to be generated as an outcome of the execution of these three processes?

Question 2

2026 Slot Set1 PYQ

Consider a system consisting of k instances of a resource R, being shared by 5 processes. Assume that each process requires a maximum of two instances of resource R and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance. The minimum value of k for the system to be deadlock-free is ________. (answer in integer)

Question 3

2026 Slot Set1 PYQ

With respect to deadlocks in an operating system, which of the following statements is/are FALSE?

Question 4

2025 Slot Set2 PYQ

P = {P_{1}, P_{2}, P_{3}, P_{4}} consists of all active processes in an operating system. R = {R_{1}, R_{2}, R_{3}, R_{4}} consists of single instances of distinct types of resources in the system. The resource allocation graph has the following assignment and claim edges. Assignment edges: R_{1} \to P_{1}, R_{2} \to P_{2}, R_{3} \to P_{3}, R_{4} \to P_{4} (the assignment edge R_{1} \to P_{1} means resource R_{1} is assigned to process P_{1}, and so on for others) Claim edges: P_{1} \to R_{2}, P_{2} \to R_{3}, P_{3} \to R_{1}, P_{2} \to R_{4}, P_{4} \to R_{2} (the claim edge P_{1} \to R_{2} means process P_{1} is waiting for resource R_{2}, and so on for others) Which of the following statement(s) is/are CORRECT?

Question 5

2024 Slot Set2 PYQ

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). The threads execute the code shown below. // code of T1 wait(s1); x = x+1; print(x); wait(s2); signal(s1); // code of 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?

Question 6

2024 Slot Set1 PYQ

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. \begin{array}{c@{\qquad\qquad}c} \mathrm{T1} & \mathrm{T2}\\ a = a + 1; & b = 2 * b;\\ b = b + 1; & a = 2 * a; \end{array} Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?

Question 7

2023 PYQ

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?

Question 8

2022 PYQ

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 T2 T3 while(true){wait(S3); print(“C”); signal(S2); } while(true){wait(S1); print(“B”); signal(S3); } while(true){wait(S2); print(“A”); signal(S1); } Which initialization of the semaphores would print the sequence BCABCABCA\dots.?

Question 9

2022 PYQ

Which of the following statements is/are TRUE with respect to deadlocks?

Question 10

2021 Slot Set2 PYQ

Consider 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);} Which of the following statement(s) is/are correct?

Free preview ends here

Login to view the complete previous-year questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Concurrency, Synchronization and Deadlocks PYQs for GATE CS

Solve 12+ Concurrency, Synchronization and Deadlocks previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Atomic vs Non-Atomic Execution Boundaries

Concurrent execution means multiple threads share the CPU by taking turns. A context switch can happen at any moment. An operation is atomic if it executes completely without any possibility of interruption. For example, reading a single boolean flag is typically atomic. However, a statement like x = x + 1 is not atomic. It compiles to three machine instructions: load x into a register, increment the register, and store the register back to memory. If a context switch occurs after the load but before the store, another thread can read the old value of x, leading to lost updates.

Explain this more simply

Imagine two people writing in the same physical ledger. If you read the current balance, walk away to get a calculator, and return to write the new balance, someone else might have changed the balance while you were gone. Your calculation is now based on stale data. Atomicity means reading, calculating, and writing in one uninterrupted motion.

Go one level deeper

On modern architectures, even seemingly simple operations like x = y can be non-atomic if the variables are not naturally aligned in memory or exceed the processor word size. True atomicity requires hardware support, such as atomic instructions or memory barriers, which this topic assumes are absent unless explicitly stated.

Decomposing High-Level Statements into Machine Steps

To analyze concurrent outcomes accurately, we must decompose high-level statements into their constituent machine-level steps. Consider the statement a = a + 1. This is not a single event.

A context switch can occur after any of these three steps. When multiple threads execute similar statements, the interleaving of these granular steps determines the final state.

Load: Read the current value of a from memory into a local register (e.g., R1 = a).
Modify: Perform the arithmetic operation on the register (e.g., R1 = R1 + 1).
Store: Write the new value from the register back to memory (e.g., a = R1).

Explain this more simply

Think of the register as a temporary scratchpad. Thread 1 writes a number on its scratchpad, but before it can copy that number to the main whiteboard, the teacher calls Thread 2. Thread 2 looks at the whiteboard, sees the old number, and does its own math. The scratchpad of Thread 1 is isolated and does not affect Thread 2 until the store step happens.

Go one level deeper

In compiler optimization, a variable might be kept in a register across multiple statements. However, for exam-level interleaving analysis, we assume the standard naive compilation where each high-level statement independently performs its own load, modify, and store sequence unless specified otherwise.

Concurrency, Synchronization and Deadlocks: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Operating System · 2026_Set2 MSQ

Consider 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);

Assume that any of the three processes can start to execute first and context switching can happen between these processes at any arbitrary time and in any arbitrary order.

Which of the following patterns is/are possible to be generated as an outcome of the execution of these three processes?

A.
**$*###
B.
**$#*##
C.
**$##*#
D.
***$###

Question 2 · Operating System · 2026_Set1 NAT

Consider a system consisting of

k

instances of a resource

R

, being shared by 5 processes. Assume that each process requires a maximum of two instances of resource

R

and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance.

The minimum value of

k

for the system to be deadlock-free is ________. (answer in integer)

Question 3 · Operating System · 2026_Set1 MSQ

With respect to deadlocks in an operating system, which of the following statements is/are FALSE?

A.
Banker’s algorithm is used to prevent deadlocks
B.
Deadlock formation can be prevented by ensuring that the hold and wait condition is not allowed
C.
An assignment edge in a resource allocation graph is marked from a process to a resource
D.
A safe state guarantees that all processes can finish without formation of a deadlock

Question 4 · Operating System · 2025_Set2 MSQ

P = {P_{1}, P_{2}, P_{3}, P_{4}}

consists of all active processes in an operating system.

R = {R_{1}, R_{2}, R_{3}, R_{4}}

consists of single instances of distinct types of resources in the system.

The resource allocation graph has the following assignment and claim edges.

Assignment edges:

R_{1} \to P_{1}, R_{2} \to P_{2}, R_{3} \to P_{3}, R_{4} \to P_{4}

(the assignment edge

R_{1} \to P_{1}

means resource

R_{1}

is assigned to process

P_{1}

, and so on for others)

Claim edges:

P_{1} \to R_{2}, P_{2} \to R_{3}, P_{3} \to R_{1}, P_{2} \to R_{4}, P_{4} \to R_{2}

(the claim edge

P_{1} \to R_{2}

means process

P_{1}

is waiting for resource

R_{2}

, and so on for others)

Which of the following statement(s) is/are CORRECT?

A.
Aborting $P_{1}$ makes the system deadlock free.
B.
Aborting $P_{3}$ makes the system deadlock free.
C.
Aborting $P_{2}$ makes the system deadlock free.
D.
Aborting $P_{1}$ and $P_{4}$ makes the system deadlock free.

Question 5 · Operating System · 2024_Set2 MSQ

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). The threads execute the code shown below.

Which of the following outcomes is/are possible when threads T1 and T2 execute concurrently?

A.
T1 runs first and prints 1, T2 runs next and prints 2
B.
T2 runs first and prints 1, T1 runs next and prints 2
C.
T1 runs first and prints 1, T2 does not print anything (deadlock)
D.
T2 runs first and prints 1, T1 does not print anything (deadlock)

Question 6 · Operating System · 2024_Set1 MCQ

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.

\begin{array}{c@{\qquad\qquad}c} \mathrm{T1} & \mathrm{T2}\\ a = a + 1; & b = 2 * b;\\ b = b + 1; & a = 2 * a; \end{array}

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)$

Question 7 · Operating System · 2023 MCQ

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

Question 8 · Operating System · 2022 MCQ

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	T2	T3
`while(true){ wait(S3); print(“C”); signal(S2); }`	`while(true){ wait(S1); print(“B”); signal(S3); }`	`while(true){ wait(S2); print(“A”); signal(S1); }`

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

A.
S1 = 1; S2 = 1; S3 = 1
B.
S1 = 1; S2 = 1; S3 = 0
C.
S1 = 1; S2 = 0; S3 = 0
D.
S1 = 0; S2 = 1; S3 = 1

Question 9 · Operating System · 2022 MSQ

Which of the following statements is/are TRUE with respect to deadlocks?

A.
Circular wait is a necessary condition for the formation of deadlock.
B.
In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.
C.
If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.
D.
In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

Question 10 · Operating System · 2021_Set2 MSQ

Consider 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);}

Which of the following statement(s) is/are correct?

A.
Both P1 and P2 will print the value of x as 2.
B.
At least one of P1 and P2 will print the value of x as 4.
C.
At least one of the threads will print the value of y as 2.
D.
Both T1 and T2, in both the processes, will print the value of y as 1.

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Concurrency, Synchronization and Deadlocks PYQs for GATE CS

Atomic vs Non-Atomic Execution Boundaries

Decomposing High-Level Statements into Machine Steps

Concurrency, Synchronization and Deadlocks: Solved Questions with Step-by-Step Explanations (10 Problems)

More previous year questions (pyqs) in this unit