GATE CS 2024 Set 2 — Question 46

Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.

MSQ+2 / -0MediumSemaphoresProcess SynchronizationOperating System

Operating System → Process Synchronization → Semaphores

Last updated 20 August 2026

Question

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?

Correct answer (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) Solution The semaphore s1 acts as a mutex protecting the critical sections of both threads. s2 is a synchronization semaphore. Case 1: T1 executes first. 1. T1 executes wait(s1) . s1 becomes 0. T1 enters its critical section. 2. T1 increments x to 1 and prints 1. 3. T1 executes wait(s2) . Since s2 is 0, T1 blocks and waits for s2 to be signaled. T1 still holds s1 (s1=0). 4. T2 tries to execute wait(s1) . Since s1 is 0, T2 blocks and waits for s1. 5. Result: T1 is waiting for s2 (signaled by T2), and T2 is waiting for s1 (signaled by T1). This is a deadlock. T1 has printed 1, T2 has printed nothing. This corresponds to option (C). Case 2: T2 executes first. 1. T2 executes wait(s1) . s1 becomes 0. T2 enters its critical section. 2. T2 increments x to 1 and prints 1. 3. T2 executes signal(s2) . s2 becomes 1. 4. T2 executes signal(s1) . s1 becomes 1. 5. T2 finishes. 6. Now T1 can execute wait(s1) . s1 becomes 0. 7. T1 increments x to 2 and prints 2. 8. T1 executes wait(s2) . Since s2 is 1 (signaled by T2), s2 becomes 0 and T1 proceeds. 9. T1 executes signal(s1) . 10. Result: T2 prints 1, then T1 prints 2. This corresponds to option (B). Option (A) is impossible because if T1 runs first, it deadlocks and never releases s1, so T2 cannot run to print 2. Option (D) is impossible because if T2 runs first, it releases s1 and signals s2, allowing T1 to complete, so no deadlock occurs. Thus, both (B) and (C) are possible outcomes. Turn this into a strength. Explore AI-powered practice and doubt support with Success Tracker.

Review answer and solution without JavaScript

Interactive answer checking needs JavaScript. The published solution is available below.

Correct answer (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) Solution The semaphore s1 acts as a mutex protecting the critical sections of both threads. s2 is a synchronization semaphore. Case 1: T1 executes first. 1. T1 executes wait(s1) . s1 becomes 0. T1 enters its critical section. 2. T1 increments x to 1 and prints 1. 3. T1 executes wait(s2) . Since s2 is 0, T1 blocks and waits for s2 to be signaled. T1 still holds s1 (s1=0). 4. T2 tries to execute wait(s1) . Since s1 is 0, T2 blocks and waits for s1. 5. Result: T1 is waiting for s2 (signaled by T2), and T2 is waiting for s1 (signaled by T1). This is a deadlock. T1 has printed 1, T2 has printed nothing. This corresponds to option (C). Case 2: T2 executes first. 1. T2 executes wait(s1) . s1 becomes 0. T2 enters its critical section. 2. T2 increments x to 1 and prints 1. 3. T2 executes signal(s2) . s2 becomes 1. 4. T2 executes signal(s1) . s1 becomes 1. 5. T2 finishes. 6. Now T1 can execute wait(s1) . s1 becomes 0. 7. T1 increments x to 2 and prints 2. 8. T1 executes wait(s2) . Since s2 is 1 (signaled by T2), s2 becomes 0 and T1 proceeds. 9. T1 executes signal(s1) . 10. Result: T2 prints 1, then T1 prints 2. This corresponds to option (B). Option (A) is impossible because if T1 runs first, it deadlocks and never releases s1, so T2 cannot run to print 2. Option (D) is impossible because if T2 runs first, it releases s1 and signals s2, allowing T1 to complete, so no deadlock occurs. Thus, both (B) and (C) are possible outcomes.

Continue learning with Success Tracker

A step still unclear? Work through it with support

Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.

AI-powered practice· Unlimited practice on eligible plans

PYQs with solutions: Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
Practice that adapts: Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
AI doubt support: Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.

Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.

Start with a free account View plans and allowances

This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.

GATE CS 2024 Set 2 — Question 46

Question

Correct answer

Solution

A step still unclear? Work through it with support

More questions on Process Synchronization