Synchronization Problem Solving

1. The GATE Challenge: A Problem-Solving Session

The best way to prepare for the GATE exam is to solve problems that mirror its style and difficulty. I've selected a series of PYQs that test different facets of synchronization. For each problem, I encourage you to pause, analyze the code and the question, formulate your own solution, and then watch the guided explanation to verify your approach and learn the optimal way to break down the problem.

Let's begin.

Problem 1: Starvation Analysis

We concluded our last lesson by identifying starvation in the Readers-Writers problem. Let's start with a GATE question that directly tests your ability to spot potential starvation in a concurrent program.

Challenge:
Consider two concurrent processes, P1 and P2, synchronized using a binary semaphore X initialized to 0. The pseudocode is given below.

• P1: repeat forever { V(X); compute; P(X); }
• P2: repeat forever { P(X); compute; V(X); }

Which of the following statements is/are true?

1. It is possible for process P1 to starve.
2. It is possible for process P2 to starve.

Take a moment to trace the execution. Consider different interleavings. Can one process run repeatedly while blocking the other?

Now, let's watch the solution.

The key insight here is that since the scheduler can preempt a process at any time, we must look for execution sequences that allow one process to loop indefinitely while the other remains blocked. In this case, both P1 and P2 could potentially starve each other.

Problem 2: Race Conditions and Shared Variables

A fundamental type of synchronization problem involves predicting the possible final values of a shared variable when accessed by concurrent processes without proper locking.

Challenge:
Two processes, P1 and P2, share a variable B with an initial value of 2. They execute concurrently.

• Process P1:

  C = B - 1;
  B = 2 * C;
  

• Process P2:

  D = 2 * B;
  B = D - 1;
  

(Assume C and D are local variables for P1 and P2, respectively).

What are the distinct possible final values of B after both processes complete execution?

Think about the different ways the instructions from P1 and P2 can be interleaved. What happens if P1 runs completely, then P2? What if P2 runs first? What if they are interleaved statement by statement?

Let's see the detailed breakdown.

This type of problem highlights why atomicity is critical. Since the high-level language statements are not atomic, interleavings at the instruction level can produce a range of results (2, 3, and 4), not just the results from sequential execution.

Problem 3: Enforcing Execution Order

Another classic problem type involves setting up semaphores to force processes to execute in a specific, repeating sequence.

Challenge:
Consider three threads, T1, T2, and T3, synchronized by three binary semaphores, S1, S2, and S3. The threads print C, B, and A respectively.

• T1: wait(S2); print("C"); signal(S1);
• T2: wait(S1); print("B"); signal(S3);
• T3: wait(S3); print("A"); signal(S2);

What should be the initial values of S1, S2, and S3 to ensure the output sequence is always "BCA BCA BCA ..."?

To solve this, work backward from the desired starting action. Which thread must run first? What semaphore value is required to allow that thread to run while blocking the others?

Once you have your answer, check the explanation.

The correct initialization is S1=1, S2=0, S3=0. This allows T2 to execute first, which then signals S3, allowing T3, which signals S2, allowing T1, which signals S1, starting the cycle over again.

Problem 4: Multi-Concept Analysis (MSQ)

GATE often features Multiple Select Questions (MSQs) that require you to evaluate several properties of a given code snippet. These can be tricky because you need to check for multiple behaviors like race conditions, deadlocks, and specific outcomes.

Challenge:
Consider the following pseudocode where s is a semaphore initialized to 5, and counter is a shared variable initialized to 0. The counter++ operation is not atomic.

// Five threads execute this function concurrently
void per_op() {
    wait(s);
    wait(s);
    counter++; // Not atomic
    signal(s);
    signal(s);
}

Which of the following behaviors is/are possible?
(A) The value of counter is 5 after all threads complete.
(B) The value of counter is 1 after all threads complete.
(C) The value of counter is 0 after all threads complete.
(D) A deadlock involving all threads occurs.

Analyze each option independently. For (A), (B), and (C), can you construct an execution trace that results in that value? For (D), can you find a scenario where all threads block forever?

This problem is an excellent example of how GATE combines concepts. You need to understand semaphore mechanics, race conditions from non-atomic operations, and deadlock conditions all at once. The possible answers are (A), (B), and (D).

Conclusion

In this lesson, we put theory into practice by tackling a range of GATE-level synchronization problems. You've now seen how questions are framed and the analytical techniques required to solve them correctly and efficiently.

Key Takeaways:

• Trace Systematically: For questions about correctness or outcomes, methodically trace the execution under different interleavings. Consider sequential execution first, then various preemptions.
• Identify the Core Concept: Is the question about a race condition (shared variable values), starvation/deadlock (fairness/progress), or execution order (synchronization puzzle)? Recognizing the pattern helps you apply the right analysis.
• Non-Atomicity is Key: When a problem states an operation like x++ is "not atomic," it's a direct hint to look for race conditions by breaking it down into load, increment, store steps.
• Think Adversarially for Deadlock: To find a deadlock, look for a "worst-case" preemption schedule where each process acquires one resource and then gets blocked waiting for another.

You have now completed the module on synchronization. You have a solid foundation for analyzing and solving complex concurrency problems.

In our next lesson, we will officially begin the Deadlock module. We will move beyond the synchronization mechanisms themselves and focus on the problems that can arise from resource locking. We will start by defining the four necessary conditions for deadlock to occur and see how they can be modeled with Resource Allocation Graphs.