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. Trace the sequence of checks the Banker's Algorithm performs when a process requests additional resources. Which step occurs immediately after verifying the request does not exceed the process's declared maximum need?

easy

A. The algorithm preempts resources from other processes to fulfill the request.

B. The algorithm immediately grants the request without further checks.

C. The algorithm simulates allocation and checks if the system remains in a safe state.

D. The algorithm checks if the requested resources are currently available in the system.

Solution

1. Step 1: Recall the Banker's Algorithm request sequence

   First, it checks if the request is within the process's maximum declared need.

2. Step 2: Next step after need check

   The algorithm then verifies if the requested resources are available in the system's current available pool.

3. Step 3: Subsequent steps

   If available, it simulates allocation and checks for safe state, but this occurs after availability check.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Availability check precedes simulation to avoid unnecessary computation.

Hint: Request ≤ Need -> check availability -> simulate safe state [OK]

Common Mistakes:

• Assuming simulation happens before availability check
• Believing requests are granted immediately after need check
• Thinking preemption is part of Banker's Algorithm

2. In a Unix-like file system, which component is primarily responsible for mapping a file name to its data blocks on disk?

easy

A. The inode, which stores metadata and pointers to data blocks

B. The data block itself, which contains the file's content and its name

C. The superblock, which manages overall file system metadata

D. The directory entry, which contains the file name and a pointer to the inode

Solution

1. Step 1: Understand the role of directory entries in file name resolution

   Directory entries map file names to inode numbers, acting as the bridge between human-readable names and inode metadata.

2. Step 2: Clarify inode responsibilities

   Inodes store metadata and pointers to data blocks but do not contain file names.

3. Step 3: Differentiate superblock and data blocks

   The superblock manages file system-wide metadata, not individual file mappings; data blocks store file content, not names.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Directory entries handle name-to-inode mapping [OK]

Hint: Directory entries map names -> inodes; inodes map data blocks

Common Mistakes:

• Confusing inode as containing file names
• Assuming data blocks store file names
• Believing superblock handles file name mappings

3. Which component is responsible for switching the CPU from user mode to kernel mode when a system call is invoked?

easy

A. The user-level application itself triggers the mode switch directly

B. The CPU hardware via a software interrupt or trap mechanism

C. The operating system scheduler decides when to switch modes

D. The device driver initiates the mode switch

Solution

1. Step 1: Understand system call invocation

   System calls are invoked by user programs to request kernel services. This requires a mode switch from user to kernel mode.

2. Step 2: Role of CPU hardware

   The CPU provides a mechanism (trap or software interrupt) that safely switches the mode and transfers control to the OS kernel.

3. Step 3: Why other options are incorrect

   The user-level application itself triggers the mode switch directly is wrong because user applications cannot directly change CPU mode for protection reasons. The operating system scheduler decides when to switch modes is incorrect because the scheduler manages process execution but does not trigger mode switches on system calls. The device driver initiates the mode switch is wrong because device drivers run in kernel mode and do not initiate mode switches from user mode.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   System call -> trap -> CPU switches mode -> kernel handles request [OK]

Hint: CPU hardware trap triggers mode switch on system call

Common Mistakes:

• Thinking user code can directly switch CPU mode
• Confusing scheduler role with mode switching
• Believing device drivers initiate user-to-kernel transitions

4. Why is it generally inefficient to implement all OS services as system calls requiring mode switches?

medium

A. Because mode switches cause significant CPU overhead and latency

B. Because system calls cannot access hardware devices

C. Because user mode has unrestricted access to kernel data structures

D. Because system calls bypass the CPU privilege checks

Solution

1. Step 1: Understand mode switch cost

   Switching from user to kernel mode involves saving/restoring CPU state and flushing pipelines, which is expensive.

2. Step 2: Why not all services as system calls

   Excessive mode switches degrade performance, so only critical OS services use system calls.

3. Step 3: Why other options are incorrect

   Because system calls cannot access hardware devices is false; system calls are the mechanism to access hardware safely. Because user mode has unrestricted access to kernel data structures is false; user mode is restricted from kernel data. Because system calls bypass the CPU privilege checks is false; system calls enforce privilege checks via mode switch.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Mode switch overhead limits system call usage [OK]

Hint: Mode switches are costly, so minimize system calls

Common Mistakes:

• Believing system calls cannot access hardware
• Thinking user mode has full kernel access
• Assuming system calls skip privilege checks

5. Suppose a disk scheduler uses C-SCAN but the disk head speed varies dynamically, sometimes moving faster or slower between tracks. How does this affect the fairness and average wait time guarantees of C-SCAN, and what modification could mitigate this issue?

hard

A. Variable head speed causes starvation in C-SCAN; switching to SSTF is the best mitigation.

B. Variable head speed does not affect C-SCAN fairness since it always services requests in one direction; no modification is needed.

C. Variable head speed improves average wait time by allowing faster servicing of distant requests; no modification is necessary.

D. Variable head speed breaks C-SCAN's uniform wait time guarantee; adding a dynamic priority queue based on estimated seek time can mitigate this.

Solution

1. Step 1: Understand C-SCAN fairness assumptions

   C-SCAN assumes uniform head movement speed to provide uniform wait times.

2. Step 2: Impact of variable head speed

   Variable speed causes some requests to wait longer, breaking fairness and uniform wait time guarantees.

3. Step 3: Mitigation strategies

   Introducing a dynamic priority queue that accounts for estimated seek time can help balance servicing order and restore fairness.

4. Step 4: Evaluate other options

   Variable head speed does not affect C-SCAN fairness since it always services requests in one direction; no modification is needed. ignores the impact of speed variation; Variable head speed causes starvation in C-SCAN; switching to SSTF is the best mitigation. incorrectly claims starvation occurs and suggests SSTF, which can worsen starvation; Variable head speed improves average wait time by allowing faster servicing of distant requests; no modification is necessary. incorrectly claims variable speed improves wait times.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Variable head speed breaks C-SCAN's uniform wait time guarantee; adding a dynamic priority queue based on estimated seek time can mitigate this. correctly identifies the problem and a plausible mitigation.

Hint: C-SCAN fairness depends on constant head speed; variable speed needs dynamic adjustments

Common Mistakes:

• Assuming C-SCAN fairness is speed-independent
• Confusing starvation with fairness degradation
• Believing variable speed always improves performance