Solving Synchronization Problems in GATE

A Quick Refresher: The Three Pillars of Correctness

As you analyze the problems in this lesson, always evaluate the given solution or scenario against these three essential criteria. A correct synchronization solution must satisfy:

1. Mutual Exclusion: If one process is executing in its critical section, no other processes can be executing in their critical sections.
2. Progress: If no process is in its critical section and some processes wish to enter, then the selection of the next process to enter cannot be postponed indefinitely. This also implies that a process running in its non-critical section cannot prevent other interested processes from entering the critical section.
3. Bounded Waiting: There must be a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. This prevents starvation.

Let's dive into our first problem type.

Strategy 1: Analyzing Race Conditions for Final Values

A very common type of GATE question involves a shared variable being modified by multiple concurrent processes. Your task is to determine the range of possible final values for that variable. The key is to understand how different interleavings of instructions can lead to different outcomes.

A. Finding the Maximum and Minimum Value

To find the maximum possible value, you need to find an execution order where the operations that decrease the value are "lost" or nullified by a race condition. Conversely, to find the minimum value, you arrange the execution so that the increasing operations are lost.

Let's analyze a problem from a past GATE paper that exemplifies this.

Problem: A shared variable x, initialized to 0, is operated upon by four concurrent processes: W, X, Y, and Z.

• Processes W and X increment x by 1.
• Processes Y and Z decrement x by 2.
• A synchronization mechanism ensures that at most two processes can be in the critical section at any given time.

What is the maximum possible final value of x?

Think about how you would orchestrate the process execution to maximize x. You have two "slots" in the critical section. Which two processes would you send in first to create a race condition that favors a higher final value?

The video below provides a complete, step-by-step solution, explaining the logic for finding both the maximum and minimum values.

The core idea is to have an incrementer and a decrementer read the shared value simultaneously. Then, you let the decrementer write its result first, followed immediately by the incrementer writing its result. The incrementer's write will overwrite the decrementer's, effectively nullifying the decrement. By repeating this, you can maximize the final value.

B. Finding All Possible Distinct Values

A variation of this problem asks for the total number of distinct final values a shared variable can have. The strategy here is to be systematic:

1. Calculate the result of serial execution (e.g., P1 then P2).
2. Calculate the result of the other serial execution (P2 then P1).
3. Calculate the result(s) of interleaved executions (i.e., where a race condition occurs).

Let's analyze a simple example.

Strategy 2: Analyzing Synchronization Logic

In the previous lesson, we saw how a faulty implementation of the Bakery algorithm could lead to deadlock. GATE questions often present you with a piece of synchronization logic and ask you to evaluate its correctness based on the three pillars: Mutual Exclusion, Progress, and Bounded Waiting.

Let's revisit a classic software solution: the turn variable (strict alternation).

As you saw, the turn variable solution ensures Mutual Exclusion and Bounded Waiting (the wait is bounded to 1 turn). However, it fails the Progress requirement. If turn = 0 and process P1 is not interested in its critical section, process P0 is stuck waiting, even though the critical section is free. This is a key insight that is frequently tested.

Strategy 3: Deconstructing Complex GATE Problems

The most challenging questions combine multiple concepts: race conditions on shared data, flawed entry/exit protocols, and the potential for deadlock. Your strategy should be to break the problem down into smaller, manageable parts.

Let's analyze a problem from GATE 2021.

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

1. counter = 0;
2. S = 5;

function parop() {
3.    //...
4.    wait(S);
5.    wait(S);
6.    counter++; // Not atomic
7.    signal(S);
8.    signal(S);
9.    //...
}

If five threads execute parop concurrently, which of the following behaviors are possible?
(A) The final value of counter is 5.
(B) The final value of counter is 1.
(C) The final value of counter is 0.
(D) There is a deadlock involving all the threads.

Let's deconstruct this together:

• Entry Protocol: Each thread must perform wait(S) twice. Since S starts at 5, how many threads can be inside the critical section (line 6) at most? The first thread decrements S to 3. The second thread decrements S to 1. The third thread attempts wait(S) twice, but S would go to -1, so it blocks. Thus, at most 2 threads can be in the critical section concurrently.
• Vulnerability: counter++ is not atomic. This means it's composed of read-modify-write steps, and a thread can be preempted between these steps. This is a classic race condition setup.

Now let's evaluate the options:

• (A) Counter is 5: Is this possible? Yes, if all 5 threads execute sequentially (one after another), each will successfully increment the counter.
• (B) Counter is 1: Is this possible? This would be the result of a severe race condition. Imagine Thread 1 enters, reads counter (value 0) into its register, and is then preempted. Threads 2, 3, 4, and 5 then execute fully, setting counter to 4. Finally, Thread 1 resumes, increments its register value (which is still 0) to 1, and writes 1 back to counter, overwriting the value of 4. So, yes, this is possible.
• (C) Counter is 0: Is this possible? No. Each thread that successfully executes must increment the counter at least once. Even in the worst-case race condition above, the final value was 1. A final value of 0 is impossible.
• (D) Deadlock: Is this possible? Consider this interleaving: Each of the 5 threads executes the first wait(S) (line 4) and is then preempted. The sequence of S values would be: 4, 3, 2, 1, 0. Now, S is 0. All 5 threads are ready to execute their second wait(S) (line 5), but all of them will block because S is 0. No thread can proceed to the signal calls to increase S. This is a deadlock. So, yes, this is possible.

The following resources provide a detailed walkthrough of this exact problem.

Conclusion

Congratulations on completing the first module on synchronization fundamentals! We've moved from the basic definition of a critical section to analyzing complex, multi-threaded scenarios typical of the GATE exam.

Key Takeaways from this lesson:

• Master Race Condition Analysis: Be comfortable tracing non-atomic operations (read-modify-write) to find the minimum, maximum, and all possible outcomes of a shared variable.
• Evaluate Against the Pillars: Systematically check any given synchronization code for Mutual Exclusion, Progress, and Bounded Waiting. Know the classic failure modes, like the progress failure in strict alternation.
• Deconstruct Complex Problems: Break down problems by identifying the shared resources, the entry/exit protocols, and the key vulnerabilities (like non-atomic operations or flawed logic) to reason about possible behaviors, including deadlock.

The software-based solutions we've studied are foundational but often rely on inefficient busy-waiting. The GATE problems you solved also gave you a glimpse of semaphores. In our next module, we will formally dive into hardware and OS-level synchronization mechanisms. We'll start by exploring atomic hardware instructions like Test-and-Set and then use them to build more powerful and efficient tools like mutex locks and semaphores.