Critical Section Problem - Requirements & Peterson's Solution

▶

Steps

setup

Initialize shared variables

Both processes start with their flags set to False, indicating neither wants to enter the critical section. The turn variable is initialized to 0 arbitrarily.

💡 Initialization ensures no process is in or requesting the critical section at the start, setting a clean state for synchronization.

Line:

flag = [False, False]
turn = 0

💡 The flags and turn variables are the core shared state controlling access to the critical section.

insert

Process 0 sets its flag to True

Process 0 indicates its desire to enter the critical section by setting flag[0] to True.

💡 Setting the flag signals intent to enter the critical section, a prerequisite for Peterson's algorithm to coordinate access.

Line:

flag[process_id] = True  # process_id = 0

💡 A process must first declare its interest before any coordination can happen.

insert

Process 0 sets turn to Process 1

Process 0 sets the turn variable to 1, giving priority to Process 1 if it also wants to enter the critical section.

💡 Setting turn to the other process ensures fairness and prevents deadlock by allowing the other process to proceed if it wants to enter.

Line:

turn = other  # other = 1

💡 The turn variable is a key mechanism to avoid deadlock and ensure mutual exclusion.

compare

Process 0 checks if Process 1 wants to enter and turn is 1

Process 0 evaluates the condition: while flag[1] and turn == 1. Since flag[1] is False, the condition is false and Process 0 proceeds.

💡 This check ensures Process 0 waits only if Process 1 wants to enter and has priority.

Line:

while flag[other] and turn == other:
    pass  # busy wait

💡 The busy wait loop only blocks if the other process is interested and has priority.

traverse

Process 0 enters critical section

Process 0 is now inside the critical section, executing its critical code safely without interference.

💡 Entering the critical section means mutual exclusion is enforced; no other process can enter simultaneously.

Line:

# critical section code here

💡 Mutual exclusion is achieved by the combination of flags and turn variables.

insert

Process 1 sets its flag to True

Process 1 now wants to enter the critical section and sets flag[1] to True.

💡 Process 1 signals its intent to enter, starting the synchronization process.

Line:

flag[process_id] = True  # process_id = 1

💡 Both processes can indicate interest independently, but only one can enter at a time.

insert

Process 1 sets turn to Process 0

Process 1 sets turn to 0, giving priority to Process 0 if it also wants to enter the critical section.

💡 This step ensures fairness and prevents deadlock by allowing the other process priority.

Line:

turn = other  # other = 0

💡 Turn variable alternates priority between processes to avoid starvation.

compare

Process 1 checks busy wait condition

Process 1 evaluates while flag[0] and turn == 0. Since flag[0] is True and turn is 0, Process 1 must wait.

💡 Process 1 must wait because Process 0 is inside the critical section and has priority.

Line:

while flag[other] and turn == other:
    pass  # busy wait

💡 Busy waiting enforces mutual exclusion by blocking the second process until the first leaves.

delete

Process 0 leaves critical section and resets flag

Process 0 finishes its critical section and sets flag[0] to False, signaling it no longer needs access.

💡 Resetting the flag allows the waiting process to proceed.

Line:

flag[process_id] = False  # process_id = 0

💡 Releasing the critical section is essential to allow other processes to enter.

compare

Process 1 detects flag[0] is False and exits busy wait

Process 1 reevaluates the busy wait condition. Now flag[0] is False, so the condition is false and Process 1 proceeds into the critical section.

💡 The waiting process can now enter safely, ensuring mutual exclusion.

Line:

while flag[other] and turn == other:
    pass  # busy wait

💡 The busy wait loop effectively blocks and resumes processes based on shared variables.

traverse

Process 1 enters critical section

Process 1 is now inside the critical section, executing its critical code exclusively.

💡 Mutual exclusion is maintained as only one process is inside the critical section at a time.

Line:

# critical section code here

💡 Peterson's algorithm guarantees safe access even when both processes want to enter.

delete

Process 1 leaves critical section and resets flag

Process 1 finishes its critical section and sets flag[1] to False, releasing access.

💡 Resetting the flag allows the system to return to an idle state or accept new requests.

Line:

flag[process_id] = False  # process_id = 1

💡 Releasing the critical section is necessary for continued system progress.

prune

Final state: Both processes idle, no flags set

Both processes have completed their critical sections and reset their flags. The turn variable remains set but is irrelevant when no process is requesting access.

💡 The system is now in a safe state, ready for future critical section requests.

Line:

N/A - final state

💡 Peterson's algorithm ensures mutual exclusion, progress, and bounded waiting.

flag = [False, False]  # STEP 1
turn = 0  # STEP 1

def enter_critical_section(process_id):  # STEP 2 start
    other = 1 - process_id  # STEP 2
    flag[process_id] = True  # STEP 2
    global turn
    turn = other  # STEP 3
    while flag[other] and turn == other:  # STEP 4, 8, 10
        pass  # busy wait

def leave_critical_section(process_id):  # STEP 9, 12
    flag[process_id] = False

# Example usage:
# Process 0 and Process 1 call enter_critical_section before critical section
# and leave_critical_section after finishing.

📊

Critical Section Problem - Requirements & Peterson's Solution - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how mutual exclusion is enforced by simple shared variables and busy waiting, which is hard to grasp from code alone.

0

ready

1

ready

Ready Queue

01

Waiting Queue

empty

🖥CPUidlet=0

Transition ready → running pid:0 - Process 0 starts entering critical section

0

running

1

ready

Ready Queue

1

Waiting Queue

empty

🖥CPU0t=1

Transition running → running pid:0 - Process 0 sets turn to 1

0

running

1

ready

Ready Queue

1

Waiting Queue

empty

🖥CPU0t=2

Transition running → running pid:0 - Process 0 passes busy wait condition

0

running

1

ready

Ready Queue

1

Waiting Queue

empty

🖥CPU0t=3

Transition running → running pid:0 - Process 0 executes critical section

0

running

1

ready

Ready Queue

1

Waiting Queue

empty

🖥CPU0t=4

Transition ready → running pid:1 - Process 1 starts entering critical section

0

running

1

running

Ready Queue

0

Waiting Queue

empty

🖥CPU1t=5

0

Transition running → running pid:1 - Process 1 sets turn to 0

0

running

1

running

Ready Queue

0

Waiting Queue

empty

🖥CPU1t=6

0

Transition running → waiting pid:1 - Process 1 busy waits

0

running

1

waiting

Ready Queue

empty

Waiting Queue

1 (flag[0] == False or turn != 0)

🖥CPU0t=7

0

Transition running → ready pid:0 - Process 0 leaves critical section

0

ready

1

waiting

Ready Queue

0

Waiting Queue

1 (flag[0] == False or turn != 0)

🖥CPU0t=8

0

Transition waiting → running pid:1 - Process 1 exits busy wait

0

ready

1

running

Ready Queue

0

Waiting Queue

empty

🖥CPU1t=9

0

Transition running → running pid:1 - Process 1 executes critical section

0

ready

1

running

Ready Queue

0

Waiting Queue

empty

🖥CPU1t=10

0

Transition running → ready pid:1 - Process 1 leaves critical section

0

ready

1

ready

Ready Queue

01

Waiting Queue

empty

🖥CPU1t=11

0

1

0

ready

1

ready

Ready Queue

01

Waiting Queue

empty

🖥CPUidlet=12

0

1

Key Takeaways

✓ Peterson's algorithm uses two shared variables (flags and turn) to enforce mutual exclusion without hardware support.

This insight is hard to see from code alone because the interplay of flags and turn is subtle and timing-dependent.

✓ The busy wait loop blocks a process only if the other process wants to enter and has priority, ensuring fairness and preventing deadlock.

Seeing the busy wait condition evaluated step-by-step clarifies how the algorithm avoids simultaneous critical section entry.

✓ Resetting the flag after leaving the critical section signals other processes to proceed, enabling progress and bounded waiting.

The importance of resetting flags is often overlooked in code but is critical for correct synchronization.

Practice

1. In which scenario is contiguous file allocation most suitable compared to linked or indexed allocation?

easy

A. When files are frequently extended or shrunk dynamically during runtime

B. When the file system must handle very large files with unpredictable sizes

C. When fast sequential and direct access to file blocks is required with minimal overhead

D. When minimizing external fragmentation is the highest priority

Solution

1. Step 1: Understand contiguous allocation characteristics

   Contiguous allocation stores all file blocks sequentially on disk, enabling fast sequential and direct access without extra pointers.

2. Step 2: Analyze when fast sequential and direct access to file blocks is required with minimal overhead

   Fast sequential and direct access is exactly what contiguous allocation optimizes for.

3. Step 3: Analyze when files are frequently extended or shrunk dynamically during runtime

   Contiguous allocation struggles with dynamic file size changes due to fragmentation and need for contiguous free space.

4. Step 4: Analyze when the file system must handle very large files with unpredictable sizes

   Large unpredictable files are better handled by linked or indexed allocation to avoid fragmentation and allocation overhead.

5. Step 5: Analyze when minimizing external fragmentation is the highest priority

   Contiguous allocation tends to cause external fragmentation, so it does not minimize it.

6. Final Answer:

   Option C -> Option C

7. Quick Check:

   Contiguous allocation -> fast access but poor flexibility and fragmentation handling.

Hint: Contiguous = fastest direct access but poor flexibility [OK]

Common Mistakes:

• Assuming contiguous allocation handles dynamic file sizes well
• Confusing fragmentation minimization with contiguous allocation benefits

2. Trace the sequence of state transitions for a process that requests I/O while running and then completes the I/O operation. What is the correct order of states the process goes through?

easy

A. Running -> Waiting -> Ready -> Running

B. Running -> Ready -> Waiting -> Running

C. Running -> Waiting -> Running -> Ready

D. Running -> Ready -> Running -> Waiting

Solution

1. Step 1: Identify the event

   The process requests I/O while Running, so it must wait for I/O completion.

2. Step 2: State transition on I/O request

   Process moves from Running to Waiting state to wait for I/O.

3. Step 3: After I/O completes

   Process moves from Waiting to Ready state, waiting for CPU scheduling.

4. Step 4: CPU scheduling

   Process moves from Ready to Running when CPU is allocated.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Running -> Waiting (I/O request), Waiting -> Ready (I/O done), Ready -> Running (CPU assigned) [OK]

Hint: I/O request moves process Running -> Waiting, then Waiting -> Ready after I/O completes [OK]

Common Mistakes:

• Confusing Ready and Waiting states order
• Assuming process goes directly from Waiting to Running
• Skipping the Ready state after I/O completion

3. Which of the following statements about non-preemptive SJF scheduling is INCORRECT?

medium

A. Once a process starts executing, it cannot be preempted until completion

B. It selects the process with the shortest burst time from the ready queue when CPU is free

C. It can lead to longer average waiting time compared to preemptive SJF

D. It guarantees no starvation of any process

Solution

1. Step 1: Understand starvation in non-preemptive SJF

   Non-preemptive SJF can cause starvation if short jobs keep arriving, delaying longer jobs indefinitely.

2. Step 2: Analyze other options

   A: Correct, non-preemptive means no interruption once started.
   B: Incorrect, non-preemptive SJF does not guarantee no starvation.
   C: Correct, it can lead to longer average waiting time compared to preemptive SJF.
   D: Correct, selection is based on shortest burst time when CPU is free.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Non-preemptive SJF does not guarantee no starvation; starvation can occur.

Hint: Non-preemptive SJF can starve long processes if short ones keep arriving [OK]

Common Mistakes:

• Assuming non-preemptive SJF prevents starvation
• Confusing preemptive and non-preemptive behavior

4. If the Dining Philosophers problem is extended to allow philosophers to pick up forks in any order but with a timeout mechanism to release held forks after waiting too long, what is a potential downside of this approach?

hard

A. It completely eliminates deadlock and starvation without any performance penalty

B. It may cause livelock where philosophers repeatedly pick up and release forks without eating

C. It guarantees fairness by enforcing strict turn-taking among philosophers

D. It simplifies synchronization by removing the need for semaphores or locks

Solution

1. Step 1: Understand timeout-based fork release

   Philosophers release forks if waiting too long, preventing indefinite blocking.

2. Step 2: Analyze consequences

   This can cause livelock, where philosophers continuously pick up and release forks without making progress.

3. Step 3: Evaluate other options

   It completely eliminates deadlock and starvation without any performance penalty is false because performance penalties and livelock can occur; It simplifies synchronization by removing the need for semaphores or locks is false as synchronization primitives are still needed; It guarantees fairness by enforcing strict turn-taking among philosophers is false as fairness is not guaranteed.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Timeouts prevent deadlock but risk livelock due to repeated retries.

Hint: Timeouts prevent deadlock but can cause livelock [OK]

Common Mistakes:

• Assuming timeouts solve all synchronization issues
• Confusing livelock with deadlock
• Believing fairness is guaranteed by timeouts

5. If a system using FCFS scheduling introduces a mix of I/O-bound and CPU-bound processes arriving at different times, how does this affect the convoy effect and waiting times, and what strategy could reduce the negative impact?

hard

A. The convoy effect disappears because I/O-bound processes run first, so waiting times decrease automatically

B. The convoy effect worsens as CPU-bound processes block I/O-bound ones, increasing waiting times; introducing preemption can help

C. Waiting times remain unchanged because FCFS ignores process type and arrival time

D. The convoy effect is irrelevant in mixed workloads since I/O-bound processes do not use the CPU

Solution

1. Step 1: Understand process types in FCFS

   FCFS schedules strictly by arrival order, regardless of process type.

2. Step 2: Analyze impact of mixed workloads

   CPU-bound processes arriving first can delay I/O-bound processes, worsening the convoy effect and increasing waiting times.

3. Step 3: Mitigation strategy

   Introducing preemption or priority scheduling can reduce waiting times for I/O-bound processes by allowing them to run sooner.

4. Step 4: Evaluate options

   A is incorrect; convoy effect does not disappear automatically.
   B is correct; convoy effect worsens and preemption helps.
   C is incorrect; waiting times do change due to process mix.
   D is incorrect; convoy effect is relevant because all processes compete for CPU.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Mixed workloads worsen convoy effect; preemption mitigates it.

Hint: Mixed CPU/I-O bound + FCFS -> worse convoy; preemption helps

Common Mistakes:

• Assuming I/O-bound processes run first automatically
• Believing waiting times don't change with process mix
• Ignoring convoy effect in mixed workloads