Critical section problem in Operating Systems - Step-by-Step Execution

Concept Flow - Critical section problem

Process wants to enter CS

↓

Check if CS is free

↓

Enter CS

↓

Execute CS code

↓

Exit CS

↓

Allow others to enter

The flow shows a process checking if the critical section (CS) is free, entering if yes, or waiting if no, then executing and exiting the CS to allow others.

Execution Sample

Operating Systems

Process 1:
while (true) {
  wait(); // wait for CS
  critical_section();
  signal(); // release CS
}

This code shows a process repeatedly trying to enter the critical section by waiting, executing, and then signaling release.

Analysis Table

Step	Process	CS Status	Action	Result
1	P1	Free	Check CS	CS is free, enter CS
2	P1	Occupied	Execute CS	Process P1 is in CS
3	P2	Occupied	Check CS	CS is occupied, wait
4	P1	Occupied	Exit CS	CS becomes free
5	P2	Free	Check CS	CS is free, enter CS
6	P2	Occupied	Execute CS	Process P2 is in CS
7	P2	Occupied	Exit CS	CS becomes free
8	P3	Free	Check CS	CS is free, enter CS
9	P3	Occupied	Execute CS	Process P3 is in CS
10	P3	Occupied	Exit CS	CS becomes free
11	-	Free	Check CS	No process waiting, system idle

💡 Processes take turns entering CS; when no process wants CS, it remains free.

State Tracker

Variable	Start	After Step 1	After Step 4	After Step 7	After Step 10	Final
CS Status	Free	Occupied by P1	Free	Free	Free	Free
Waiting Queue	Empty	Empty	P2 waiting	Empty	Empty	Empty

Key Insights - 3 Insights

Why does Process 2 have to wait at Step 3 even though Process 1 is almost done?

Because the critical section is still occupied by Process 1 at Step 3, Process 2 must wait until Process 1 exits (Step 4) before entering, as shown in the execution_table.

What happens if a process exits the critical section but no other process is waiting?

The critical section remains free and idle, as seen at Step 11 in the execution_table where no process is waiting and CS is free.

How does the system ensure only one process is in the critical section at a time?

By checking the CS status before entering and making processes wait if occupied, the system enforces mutual exclusion, demonstrated by the alternating CS Status in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3. What is the status of the critical section?

A Unknown

B Free

C Occupied

D Being released

💡 Hint

Refer to the 'CS Status' column at Step 3 in the execution_table.

At which step does Process 2 enter the critical section?

A Step 2

B Step 5

C Step 7

D Step 3

💡 Hint

Check the 'Action' and 'Result' columns for Process 2 in the execution_table.

If Process 3 arrives when the CS is free, what will be the CS Status after Step 8?

A Occupied by P3

B Occupied by P2

C Free

D Waiting

💡 Hint

Look at Step 8 and Step 9 in the execution_table for Process 3's actions.

Concept Snapshot

Critical Section Problem:
- Only one process can be in the critical section (CS) at a time.
- Processes check if CS is free before entering.
- If occupied, processes wait.
- After executing CS, process exits and signals others.
- Ensures mutual exclusion and prevents race conditions.

Full Transcript

The critical section problem involves multiple processes wanting to access a shared resource exclusively. Each process checks if the critical section is free before entering. If free, it enters and executes its code inside the critical section. If occupied, the process waits until the critical section becomes free. After finishing, the process exits and signals others to enter. This ensures only one process accesses the shared resource at a time, preventing conflicts. The execution table shows processes taking turns entering and exiting the critical section, with waiting processes queued until the resource is free.

Practice

1. What is the main goal of the critical section problem in operating systems?

easy

A. To ensure only one process accesses shared resources at a time

B. To allow multiple processes to access resources simultaneously

C. To speed up the execution of all processes

D. To prevent processes from running in parallel

Solution

1. Step 1: Understand the critical section concept

   The critical section is a part of the program where shared resources are accessed.

2. Step 2: Identify the problem goal

   The goal is to prevent multiple processes from entering the critical section simultaneously to avoid conflicts.

3. Final Answer:

   To ensure only one process accesses shared resources at a time -> Option A

4. Quick Check:

   Critical section = exclusive access [OK]

Hint: Only one process can be inside critical section at once [OK]

Common Mistakes:

• Thinking multiple processes can safely access shared data simultaneously
• Confusing critical section with process scheduling
• Believing critical section speeds up all processes

2. Which of the following is a correct way to indicate a process is in its critical section using a flag variable flag[i]?

easy

A. flag[i] = true

B. flag[i] = -1

C. flag[i] = 0

D. flag[i] = false

Solution

1. Step 1: Understand flag usage in critical section

   A flag variable is often used to indicate if a process wants to enter or is inside the critical section.

2. Step 2: Identify correct flag value for 'in critical section'

   Setting flag[i] = true means the process is active or wants to enter the critical section.

3. Final Answer:

   flag[i] = true -> Option A

4. Quick Check:

   Flag true means process active [OK]

Hint: True means process wants or is inside critical section [OK]

Common Mistakes:

• Using 0 or false to indicate active process
• Confusing flag values with process IDs
• Using negative values for flags

3. Consider this pseudocode for two processes P0 and P1 using flags to enter critical section:

flag[0] = true
while(flag[1]) { /* wait */ }
// critical section
flag[0] = false

What happens if both processes set their flags to true at the same time?

medium

A. Both enter critical section simultaneously

B. Both skip critical section

C. Both wait forever (deadlock)

D. One waits while the other enters critical section

Solution

1. Step 1: Analyze the waiting condition

   Each process waits while the other's flag is true, so if both flags are true simultaneously, both wait.

2. Step 2: Identify the outcome

   Since both wait for the other to clear their flag, neither proceeds, causing deadlock.

3. Final Answer:

   Both wait forever (deadlock) -> Option C

4. Quick Check:

   Both flags true = deadlock [OK]

Hint: Both flags true means both wait forever [OK]

Common Mistakes:

• Assuming both can enter critical section simultaneously
• Thinking one process always proceeds first
• Ignoring the waiting loop condition

4. In the following code snippet, what is the main error that can cause the critical section problem?

flag[i] = true
while(flag[j]) {
  // do nothing
}
// critical section
flag[i] = false

Assuming two processes P0 and P1 use this code with i=0, j=1 and vice versa.

medium

A. Infinite loop if flag[j] is false

B. No mutual exclusion, both can enter critical section

C. Flag reset happens before critical section

D. Deadlock if both set flag true simultaneously

Solution

1. Step 1: Understand the waiting condition

   Each process waits while the other process's flag is true.

2. Step 2: Identify the error scenario

   If both processes set their flags to true simultaneously, both wait forever, causing deadlock.

3. Final Answer:

   Deadlock if both set flag true simultaneously -> Option D

4. Quick Check:

   Simultaneous flags true = deadlock [OK]

Hint: Both flags true causes deadlock, not mutual exclusion [OK]

Common Mistakes:

• Thinking both can enter critical section simultaneously
• Believing flag reset is before critical section
• Assuming infinite loop if flag[j] is false

5. Which of the following solutions correctly solves the critical section problem by ensuring mutual exclusion, progress, and bounded waiting?

hard

A. Using a simple flag variable without turn variable

B. Peterson's algorithm using flags and turn variable

C. Both processes entering critical section simultaneously

D. Ignoring synchronization and relying on process speed

Solution

1. Step 1: Review solution requirements

   The solution must ensure mutual exclusion, progress, and bounded waiting to solve the critical section problem correctly.

2. Step 2: Evaluate each option

   Using a simple flag variable without turn variable lacks a turn variable, so it can cause deadlock or starvation. Peterson's algorithm using flags and turn variable uses flags and turn to guarantee all three conditions. The other options are incorrect approaches.

3. Final Answer:

   Peterson's algorithm using flags and turn variable -> Option B

4. Quick Check:

   Peterson's algorithm = correct solution [OK]

Hint: Peterson's algorithm uses flags + turn for safe access [OK]

Common Mistakes:

• Ignoring the need for a turn variable
• Assuming simple flags are enough
• Believing processes can safely ignore synchronization