Critical Sections and Race Conditions

1. Cooperative vs. Independent Processes

In a modern multitasking operating system, multiple processes can run concurrently. From a synchronization perspective, these processes can be divided into two main categories:

• Independent Processes: The execution of one process does not affect and is not affected by the execution of other processes. They do not share any data.
• Cooperative Processes: The execution of one process can affect or be affected by another. This happens because they share something, such as memory, a variable, a file, or a hardware resource.

Our focus throughout this course will be on cooperative processes, as their interaction is what creates the need for synchronization mechanisms.

To get a clear introduction to these concepts, please watch the first part of the following video from Gate Smashers.

As the video explains, when processes share data, the order in which they execute can lead to unexpected and incorrect outcomes. This brings us to a fundamental problem in concurrent programming: the race condition.

2. The Race Condition

A race condition is an undesirable situation that occurs when a device or system attempts to perform two or more operations at the same time, but because of the nature of the device or system, the operations must be done in the proper sequence to be done correctly.

In the context of operating systems, a race condition occurs when multiple processes access and manipulate the same shared data concurrently, and the final outcome depends on the particular order in which the access takes place. The "race" is among the processes to see who can access and change the data last.

A Concrete Example

Let's analyze the classic example of a race condition. Imagine two processes, P1 and P2, that both access a shared integer variable count, which is initially 5.

• Process P1 executes count++.
• Process P2 executes count--.

If these operations were atomic (indivisible), the final value of count would always be 5, regardless of which process runs first. However, these high-level operations are not atomic. At the machine level, they are typically broken down into three instructions:

1. Load the value of count from memory into a register.
2. Increment/decrement the value in the register.
3. Store the new value from the register back into memory.

Now, consider what happens if the operating system switches context between these low-level instructions. The next video segment walks through this scenario in detail, showing how preemption can lead to an incorrect result.

This unpredictability is the core of the problem. Your program might work correctly 99 times, but that one time the scheduler interleaves instructions in a specific "unlucky" way, the result is wrong. For the GATE exam, understanding how different interleavings produce different results is crucial.

3. The Critical Section Problem

To prevent race conditions, we need a way to ensure that when one process is manipulating shared data, no other process can interfere. The part of a program where a process accesses shared resources is called the critical section.

The critical section problem is to design a protocol that cooperative processes can use to synchronize their actions. Each process must request permission to enter its critical section. The section of code implementing this request is the entry section. The critical section may be followed by an exit section. The remaining code is the remainder section.

The challenge is to write the entry and exit sections to guarantee that only one process is in its critical section at any given time.

The next video defines the critical section and its surrounding structure.

4. Requirements for a Valid Solution

Any valid solution to the critical section problem must satisfy three essential conditions. For GATE, these are very important to know by heart.

1. Mutual Exclusion: If a process is executing in its critical section, then no other processes can be executing in their critical sections. This is the fundamental requirement.
2. Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then the selection of the process that will enter the critical section next cannot be postponed indefinitely. This means there should be no deadlock among the processes trying to enter.
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 ensures that no process has to wait forever (starvation).

The video you just started watching also covers these three requirements in detail.

5. GATE-Style Problem Analysis

Let's apply these concepts to a typical problem you might encounter. The key is to trace the possible interleavings of execution.

Let's break down the problem from the article:

• Shared variable B starts at 2.
• Process P1: C = B - 1; B = 2 * C;
• Process P2: D = 2 * B; B = D - 1;

Let's trace a few scenarios:

• Scenario 1 (P1 then P2):

  1. C = B - 1 -> C = 2 - 1 = 1
  2. B = 2 * C -> B = 2 * 1 = 2
  3. D = 2 * B -> D = 2 * 2 = 4
  4. B = D - 1 -> B = 4 - 1 = 3

• Scenario 2 (P2 then P1):

  1. D = 2 * B -> D = 2 * 2 = 4
  2. B = D - 1 -> B = 4 - 1 = 3
  3. C = B - 1 -> C = 3 - 1 = 2
  4. B = 2 * C -> B = 2 * 2 = 4

• Scenario 3 (Interleaved):

  1. (P1) C = B - 1 -> C = 2 - 1 = 1 (P1 is preempted)
  2. (P2) D = 2 * B -> D = 2 * 2 = 4
  3. (P2) B = D - 1 -> B = 4 - 1 = 3 (P2 finishes)
  4. (P1) B = 2 * C -> B = 2 * 1 = 2 (P1 resumes and overwrites P2's work)

As the article's solution demonstrates, by exploring the different interleavings, we find the distinct possible values for B are 2, 3, and 4. The number of distinct values is 3.

Conclusion

In this lesson, we established the fundamental "why" of process synchronization. You learned that when concurrent, cooperative processes share resources, we can face unpredictable outcomes.

Key Takeaways:

• Cooperative processes share data, which creates the potential for conflict.
• A race condition occurs when the outcome of an operation depends on the non-deterministic scheduling order of concurrent processes.
• The code segment where shared resources are accessed is the critical section.
• The critical section problem is to design a protocol (entry/exit sections) that allows processes to cooperate safely.
• Any valid solution must satisfy three conditions: Mutual Exclusion, Progress, and Bounded Waiting.

In our next lesson, we will begin exploring solutions to the critical section problem. We'll start with software-based solutions, specifically looking at Peterson's solution, a classic and elegant algorithm for two processes.