Operating Systems · GATE CSE

Semaphore Questions in GATE: 5 Patterns You Should Recognize

Most semaphore questions in GATE reduce to five recurring ideas: tracking semaphore values, protecting shared data, enforcing order, spotting deadlock, and handling Producer-Consumer synchronization.

5 recurring patterns 27 GATE CSE PYQs Focused practice bank Direct question links
Start Here

Semaphore Questions Look Different. The Reasoning Repeats.

One question asks for a semaphore value. Another asks which output can occur. Another hides a deadlock inside the order of two waits. The surface changes, but the same small set of reasoning structures keeps returning.

The goal is simple: recognize the pattern before you start simulating processes.

The five patterns

01 Value, P/V + Blocking What is the semaphore value, and who must wait? 02 Mutual Exclusion + Correctness Does the semaphore actually protect the shared state correctly? 03 Ordering + Precedence What must happen before what? 04 Deadlock + Wait Ordering Can a process block while holding something another process needs? 05 Producer-Consumer Which semaphore represents space, items and mutual exclusion?
What This Guide Covers

This guide covers 27 semaphore-focused GATE CSE PYQs. Additional questions from GATE IT, ISRO, UGC NET, TIFR, IIITH PGEE, BARC and GO Classes DPPs are included for extra practice across the same five patterns.

Extra Similar Practice questions reinforce a pattern already covered in the GATE CSE set.

Quick Recognition

20-Second Pattern Finder

Find the strongest clue in the question and jump directly to the reasoning pattern you should try first.

Pattern 1 P/V counts or a semaphore trace Start with permit accounting and blocking. Pattern 2 Shared state, atomicity or starvation Check mutual exclusion, race behavior and progress. Pattern 3 Required output or execution order Translate the question into precedence constraints. Pattern 4 Multiple semaphores or nested waits Track what each process holds while waiting. Pattern 5 Producer, consumer, empty/full/mutex Assign a meaning to each semaphore first.
Pattern 01

Value, P/V and Blocking

What is the semaphore value, and who must wait?

How to recognize it

Look for an initial semaphore value followed by P(), V(), wait(), signal(), or a sequence of operations that changes the available permits.

Your first move

Do permit accounting first. Track how many successful waits can occur before blocking becomes unavoidable.

GATE CSE questions in this pattern

GATE CSE PYQWhat it tests
GATE CSE 1992 Q2(x)Final counting-semaphore value after P/V operations
GATE CSE 1998 Q1.31Counting-semaphore arithmetic
GATE CSE 2016 Set 2 Q49Largest initial value that still leaves a P operation blocked
Representative walkthrough

Representative idea: GATE CSE 2016 Set 2 Q49

Twenty P(S) operations create demand and twelve V(S) operations restore permits. The net excess demand is eight. Therefore, the largest initial value that still guarantees at least one blocked P(S) is seven. The key is recognizing permit accounting before thinking about scheduler interleavings.

Open direct PYQ
Common trap to remember

Check the semaphore convention used in the question. In some definitions, a negative semaphore value represents the number of waiting processes.

More practice for Pattern 1

Other exam practice
ISROISRO CSE 2016 Q45UGC NETUGC NET January 2017 Part 2 Q36UGC NETUGC NET December 2019 Part 2 Q24
GO Classes DPP practice
GO DPPDPP 335: Semaphore Operation TraceGO DPPDPP 335: Counting Semaphores
Pattern 02

Mutual Exclusion and Correctness

Does the semaphore actually protect the shared state correctly?

How to recognize it

Look for shared variables, binary versus counting semaphores, atomicity, starvation, busy waiting, Readers-Writers, or a proposed semaphore implementation.

Your first move

Ask how many processes may enter, whether the protected update is atomic, and whether the solution guarantees progress as well as mutual exclusion.

GATE CSE questions in this pattern

GATE CSE PYQWhat it tests
GATE CSE 1997 Q6.8Broken P/V usage and maximum processes in the critical section
GATE CSE 2013 Q34Counting semaphore allows concurrent non-atomic updates
GATE CSE 2021 Set 1 Q46Multiple waits, limited permits and race behavior
GATE CSE 2023 Q28Binary versus counting semaphore around shared updates
GATE CSE 1987 Q8aReaders-Writers protocol using semaphores
GATE CSE 2000 Q20Readers-Writers, busy waiting and starvation
GATE CSE 2008 Q63Implement a counting semaphore using binary semaphores
GATE CSE 1990 Q1-viiWhy semaphore operations must be atomic
GATE CSE 2006 Q61Implement semaphore operations using an atomic primitive
Representative walkthrough

Representative idea: GATE CSE 2023 Q28

A binary semaphore initialized to one admits one thread at a time. A counting semaphore initialized above one can admit multiple threads together. If the shared read-modify-write operation is not atomic, those admitted threads can still race. The presence of a semaphore does not automatically mean mutual exclusion.

Open direct PYQ
Common trap to remember

Mutual exclusion, deadlock freedom, starvation freedom and bounded waiting are different properties. Proving one does not automatically prove the others.

More practice for Pattern 2

Other exam practice
GATE ITGATE IT 2007 Q56ISRO / UGC NETISRO CSE 2007 Q42 / UGC NET June 2010 II Q37UGC NETUGC NET June 2025 Part 2 Q63TIFRTIFR CSE 2012 Part B Q10BARCBARC 2026 Q37
GO Classes DPP practice
GO DPPDPP 335: Semaphore PropertiesGO DPPDPP 337: Reader-WriterGO DPPDPP 337: Readers-Writers ProblemGO DPPDPP 357: Semaphore Atomicity
Pattern 03

Ordering and Precedence

What must happen before what?

How to recognize it

Look for required output sequences, possible execution orders, semaphore initializations, or a conversion between process code and a precedence graph.

Your first move

Draw the dependency graph first. Read signal as 'unlocks' and wait as 'cannot pass until'.

GATE CSE questions in this pattern

GATE CSE PYQWhat it tests
GATE CSE 1993 Q22Convert precedence constraints into semaphore synchronization
GATE CSE 1995 Q19Convert P/V synchronization into a precedence graph
GATE CSE 2003 Q80Force a repeating output sequence
GATE CSE 2003 Q81Restrict possible output patterns
GATE CSE 2010 Q45Possible executions and printed outputs
GATE CSE 2013 Q39Enforce a producer-before-consumer style dependency
GATE CSE 2022 Q9Initialize semaphores to enforce BCABC...
GATE CSE 2026 Set 2 Q41Possible output patterns with two binary semaphores
Representative walkthrough

Representative idea: GATE CSE 2022 Q9

For a repeating BCABC... sequence, identify the required dependencies: B before C, C before A, and A before the next B. Then choose the initial semaphore values that allow only the first required event to begin.

Open direct PYQ
Common trap to remember

Do not enumerate every scheduler interleaving before extracting the forced order. Most ordering questions become much simpler as a partial-order graph.

More practice for Pattern 3

Other exam practice
GATE ITGATE IT 2005 Q42
GO Classes DPP practice
GO DPPDPP 335: Binary SemaphoreGO DPPDPP 335: Semaphore Ordering
Pattern 04

Deadlock and Wait Ordering

Can a process block while holding something another process needs?

How to recognize it

Look for multiple semaphores, nested waits, different acquisition orders, or a process waiting while still holding a semaphore.

Your first move

At every wait, write what the process is already holding and identify which process can perform the signal needed to release it.

GATE CSE questions in this pattern

GATE CSE PYQWhat it tests
GATE CSE 2000 Q1.21Circular wait among binary semaphores
GATE CSE 2004 Q48Semaphore acquisition order and deadlock
GATE CSE 2013 Q16Ordering multiple semaphore acquisitions
GATE CSE 2014 Set 2 Q31Producer-Consumer wait ordering creates deadlock
GATE CSE 2024 Set 2 Q36Blocking while holding a semaphore needed by another thread
Representative walkthrough

Representative idea: GATE CSE 2024 Set 2 Q36

One thread can acquire s1 and then block on s2 while still holding s1. The other thread needs s1 before it can reach the signal on s2. Each side therefore waits for progress that the other cannot make.

Open direct PYQ
Common trap to remember

Deadlock does not need to look exactly like wait(A), wait(B) versus wait(B), wait(A). The circular dependency may be indirect.

More practice for Pattern 4

Other exam practice
GATE ITGATE IT 2006 Q55UGC NETUGC NET June 2013 Part 3 Q60IIITH PGEEIIITH PGEE 2026 Q65
GO Classes DPP practice
GO DPPDPP 336: Producer-Consumer
Pattern 05

Producer-Consumer

Which semaphore represents space, items and mutual exclusion?

How to recognize it

Look for a bounded buffer, producer, consumer, empty, full, mutex, insertion or removal.

Your first move

Assign the semantic role of each semaphore before reading the options: empty means free slots, full means available items, and mutex protects shared buffer state.

GATE CSE questions in this pattern

GATE CSE PYQWhat it tests
GATE CSE 2002 Q20Identify P/V operations for full and empty slots
GATE CSE 2018 Q40Interpret empty, full and mutex roles
Representative walkthrough

Representative idea: GATE CSE 2002 Q20

If a bounded buffer begins empty, full starts at zero and empty starts at the buffer capacity. The producer consumes an empty slot before insertion and creates a full slot afterward. The consumer performs the reverse.

Open direct PYQ
Common trap to remember

Acquire availability before mutex. Holding mutex while waiting for an empty or full slot can prevent the process that would create that condition from entering.

More practice for Pattern 5

Other exam practice
GATE ITGATE IT 2004 Q65GATE ITGATE IT 2008 Q53ISROISRO CSE 2023 Q75
GO Classes DPP practice
GO DPPDPP 336: Bounded BufferGO DPPDPP 336: Bounded Buffer PropertiesGO DPPDPP 336: Producer SynchronizationGO DPPDPP 338: Producer-Consumer Semaphores
Bonus Practice Bank

15 Focused Questions From Other Indian Exams

These questions test the same five reasoning patterns in different wording. The strongest additions are part of the focused practice set; a few clearly marked Extra Similar Practice questions are retained because they are valid semaphore drills even when their reasoning overlaps with an existing GATE pattern.

5GATE IT
3ISRO / cross-listed
4UGC NET
3TIFR / IIITH / BARC
Direct questionPatternWhy it belongs
GATE IT
GATE IT 2004 Q65		 Pattern 5 Producer-Consumer with full, empty and mutex
GATE IT
GATE IT 2005 Q42		 Pattern 3 Minimum binary semaphores for alternating precedence
GATE IT
GATE IT 2006 Q55		 Pattern 4 Producer-Consumer wait ordering and deadlock
GATE IT
GATE IT 2007 Q56		 Pattern 2 Readers-Writers using mutex and wrt
GATE IT
GATE IT 2008 Q53		 Pattern 5 Producer and consumer synchronized by binary semaphores
ISRO / UGC NET
ISRO CSE 2007 Q42 / UGC NET June 2010 II Q37		 Pattern 2 Purpose of semaphores and contention
ISRO
ISRO CSE 2016 Q45		 Pattern 1 Counting-semaphore arithmetic using P and V
ISRO
ISRO CSE 2023 Q75		 Pattern 5 Primitive that makes a consumer wait on an empty buffer
UGC NET
UGC NET January 2017 Part 2 Q36		 Pattern 1 Negative semaphore value and number of waiting processes
UGC NET
UGC NET December 2019 Part 2 Q24		 Pattern 1 Counting-semaphore arithmetic drill
UGC NET
UGC NET June 2025 Part 2 Q63		 Pattern 2 Spinlock semaphores and busy waiting
TIFR
TIFR CSE 2012 Part B Q10		Pattern 2Blocked-set semaphore: mutual exclusion versus starvation under arbitrary wake-up
UGC NET
UGC NET June 2013 Part 3 Q60
Extra Similar Practice
Pattern 4Classic opposite semaphore acquisition order and deadlock
IIITH PGEE
IIITH PGEE 2026 Q65
Extra Similar Practice
Pattern 4Deadlock-free execution with binary semaphores; similar reasoning to a GATE deadlock pattern
BARC
BARC 2026 Q37
Extra Similar Practice
Pattern 2Basic mutual-exclusion drill on the initial semaphore value
GO Classes Practice

13 Focused DPP Questions

The selected DPPs stay tightly aligned to semaphore reasoning: value and blocking, mutual exclusion and correctness, ordering, deadlock, semaphore-based Readers-Writers, and Producer-Consumer.

DPP 3355 selected questions
DPP 3364 selected questions
DPP 3372 selected questions
DPP 3381 selected question
DPP 3571 selected question
Optional Tracker

Practice Checklist

Want a single place to track what you have solved? Open the checklist below. The marking control is native HTML, so it does not depend on custom JavaScript.

Open the complete 55-resource checklist
27 GATE CSE PYQs + 15 other Indian exam questions + 13 GO DPPs.
IIITH PGEEPattern 4
IIITH PGEE 2026 Q65

Deadlock-free execution with binary semaphores; similar reasoning to a GATE deadlock pattern

Extra Similar Practice
Review pattern
Practised
BARCPattern 2
BARC 2026 Q37

Basic mutual-exclusion drill on the initial semaphore value

Extra Similar Practice
Review pattern
Practised
Self Check

Can You Recognize the Pattern?

Five short scenarios. Do not solve the numerical details. Identify the reasoning family first.

Scenario 1 of 5
A semaphore starts at 4. Several P() and V() operations occur, and the question asks how many processes are blocked.
Choose the pattern you would try first.
Correct. The main task is semaphore-value accounting and blocking. Review Pattern 1
Not quite. Best first match: Pattern 1: Value, P/V + Blocking. The main task is semaphore-value accounting and blocking. Review Pattern 1
Not quite. Best first match: Pattern 1: Value, P/V + Blocking. The main task is semaphore-value accounting and blocking. Review Pattern 1
Not quite. Best first match: Pattern 1: Value, P/V + Blocking. The main task is semaphore-value accounting and blocking. Review Pattern 1
Not quite. Best first match: Pattern 1: Value, P/V + Blocking. The main task is semaphore-value accounting and blocking. Review Pattern 1
Scenario 2 of 5
A counting semaphore initialized to 2 surrounds a non-atomic update to a shared integer.
Choose the pattern you would try first.
Not quite. Best first match: Pattern 2: Mutual Exclusion + Correctness. The key issue is whether multiple threads can enter and race on the shared update. Review Pattern 2
Correct. The key issue is whether multiple threads can enter and race on the shared update. Review Pattern 2
Not quite. Best first match: Pattern 2: Mutual Exclusion + Correctness. The key issue is whether multiple threads can enter and race on the shared update. Review Pattern 2
Not quite. Best first match: Pattern 2: Mutual Exclusion + Correctness. The key issue is whether multiple threads can enter and race on the shared update. Review Pattern 2
Not quite. Best first match: Pattern 2: Mutual Exclusion + Correctness. The key issue is whether multiple threads can enter and race on the shared update. Review Pattern 2
Scenario 3 of 5
Three processes print A, B and C. You must choose semaphore values that force a specific repeating sequence.
Choose the pattern you would try first.
Not quite. Best first match: Pattern 3: Ordering + Precedence. The target output should be translated into precedence constraints. Review Pattern 3
Not quite. Best first match: Pattern 3: Ordering + Precedence. The target output should be translated into precedence constraints. Review Pattern 3
Correct. The target output should be translated into precedence constraints. Review Pattern 3
Not quite. Best first match: Pattern 3: Ordering + Precedence. The target output should be translated into precedence constraints. Review Pattern 3
Not quite. Best first match: Pattern 3: Ordering + Precedence. The target output should be translated into precedence constraints. Review Pattern 3
Scenario 4 of 5
P holds s1 and blocks on s2. Q needs s1 before it can signal s2.
Choose the pattern you would try first.
Not quite. Best first match: Pattern 4: Deadlock + Wait Ordering. This is a hold-and-wait cycle that can create deadlock. Review Pattern 4
Not quite. Best first match: Pattern 4: Deadlock + Wait Ordering. This is a hold-and-wait cycle that can create deadlock. Review Pattern 4
Not quite. Best first match: Pattern 4: Deadlock + Wait Ordering. This is a hold-and-wait cycle that can create deadlock. Review Pattern 4
Correct. This is a hold-and-wait cycle that can create deadlock. Review Pattern 4
Not quite. Best first match: Pattern 4: Deadlock + Wait Ordering. This is a hold-and-wait cycle that can create deadlock. Review Pattern 4
Scenario 5 of 5
A bounded buffer uses empty, full and mutex, and you must choose the correct wait/signal order.
Choose the pattern you would try first.
Not quite. Best first match: Pattern 5: Producer-Consumer. The question is fundamentally about Producer-Consumer semaphore roles. Review Pattern 5
Not quite. Best first match: Pattern 5: Producer-Consumer. The question is fundamentally about Producer-Consumer semaphore roles. Review Pattern 5
Not quite. Best first match: Pattern 5: Producer-Consumer. The question is fundamentally about Producer-Consumer semaphore roles. Review Pattern 5
Not quite. Best first match: Pattern 5: Producer-Consumer. The question is fundamentally about Producer-Consumer semaphore roles. Review Pattern 5
Correct. The question is fundamentally about Producer-Consumer semaphore roles. Review Pattern 5
Reference Table

The 27-Question GATE CSE Master Map

Every GATE CSE question in the focused semaphore set has one primary home. Questions that overlap multiple ideas are placed under the pattern that gives the best first attack.

PatternDirect GATE Overflow links
1. Value, P/V + Blocking1992 Q2(x) 1998 Q1.31 2016 Set 2 Q49
2. Mutual Exclusion + Correctness1997 Q6.8 2013 Q34 2021 Set 1 Q46 2023 Q28 1987 Q8a 2000 Q20 2008 Q63 1990 Q1-vii 2006 Q61
3. Ordering + Precedence1993 Q22 1995 Q19 2003 Q80 2003 Q81 2010 Q45 2013 Q39 2022 Q9 2026 Set 2 Q41
4. Deadlock + Wait Ordering2000 Q1.21 2004 Q48 2013 Q16 2014 Set 2 Q31 2024 Set 2 Q36
5. Producer-Consumer2002 Q20 2018 Q40
Final Takeaway

Do Not Memorize Semaphore Solutions. Learn 5 Ways of Thinking.

When you see a semaphore question, first decide whether it is about value and blocking, mutual exclusion and correctness, ordering, deadlock, or Producer-Consumer. Once that classification is right, the solution path is usually much shorter.

Count permits before simulating processes.
A semaphore around code does not automatically imply mutual exclusion.
Translate output questions into precedence constraints.
Track what a process is holding when it blocks.
Give empty, full and mutex separate meanings.
Operating Systems · Semaphore Pattern Guide · 5 focused patterns Aditya Rathod · Team GO Classes