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.
Transitionrunning → running pid:1 - Process 1 sets turn to 0
0
running
1
running
Ready Queue
0
Waiting Queue
empty
🖥CPU1t=6
0
Transitionrunning → 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
Transitionrunning → 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
Transitionwaiting → running pid:1 - Process 1 exits busy wait
0
ready
1
running
Ready Queue
0
Waiting Queue
empty
🖥CPU1t=9
0
Transitionrunning → running pid:1 - Process 1 executes critical section
0
ready
1
running
Ready Queue
0
Waiting Queue
empty
🖥CPU1t=10
0
Transitionrunning → 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/5)
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
Step 1: Recall the Banker's Algorithm request sequence
First, it checks if the request is within the process's maximum declared need.
Step 2: Next step after need check
The algorithm then verifies if the requested resources are available in the system's current available pool.
Step 3: Subsequent steps
If available, it simulates allocation and checks for safe state, but this occurs after availability check.
Final Answer:
Option D -> Option D
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 which scenario is the SSTF (Shortest Seek Time First) disk scheduling algorithm most appropriate compared to SCAN or C-SCAN?
easy
A. When minimizing average seek time is the highest priority and starvation is acceptable
B. When fairness and avoiding starvation are more important than minimizing seek time
C. When the disk requests are uniformly distributed and the workload is heavy
D. When the disk head movement must always proceed in one direction only
Solution
Step 1: Understand SSTF's goal
SSTF selects the closest request to the current head position to minimize seek time.
Step 2: Consider starvation risk
SSTF can cause starvation for requests far from the current head position because it always picks the nearest request.
Step 3: Compare with SCAN and C-SCAN
SCAN and C-SCAN move the head in a fixed direction to provide fairness and avoid starvation, sacrificing some seek time efficiency.
Final Answer:
Option A -> Option A
Quick Check:
When minimizing average seek time is the highest priority and starvation is acceptable correctly identifies SSTF's strength and its tradeoff with starvation risk.
Hint: SSTF = fastest seek but can starve distant requests
Common Mistakes:
Assuming SSTF always avoids starvation
Believing SCAN/C-SCAN minimize seek time better than SSTF
Confusing uniform distribution with SSTF suitability
3. Which of the following statements about the five-state process model is INCORRECT?
medium
A. The New state represents a process that is being created but not yet ready to run
B. The Waiting state is used when a process is blocked for I/O completion
C. A process in the Terminated state can be moved back to Ready state if needed
D. The Running state means the process is currently executing on the CPU
Solution
Step 1: Review each statement
A, B, and D correctly describe standard process states. C incorrectly states that a Terminated process can return to Ready, which violates the model.
Step 2: Understand Terminated state
Terminated means process execution is complete; it cannot be restarted or moved back.
Final Answer:
Option C -> Option C
Quick Check:
Terminated processes cannot be revived in the five-state model [OK]
Hint: Terminated means final; no return to Ready [OK]
Common Mistakes:
Thinking Terminated processes can be restarted
Confusing Waiting with Ready state
Misunderstanding New state as Ready
4. Why is it generally not advisable to use a counting semaphore as a mutex replacement for protecting a critical section?
medium
A. Because counting semaphores do not enforce ownership, leading to potential release by non-owner threads
B. Because counting semaphores have higher overhead due to maintaining a count variable
C. Because counting semaphores cannot block threads when the count is zero
D. Because counting semaphores allow only one thread at a time, making them equivalent to mutexes
Solution
Step 1: Understand mutex ownership
Mutex enforces strict ownership; only the locking thread can unlock.
Step 2: Counting semaphore behavior
Counting semaphores track resource count but do not enforce ownership.
Step 3: Consequences of no ownership
Any thread can signal (release) the semaphore, risking synchronization errors.
Step 4: Why other options are incorrect
B is true but not the main reason; C is false--semaphores do block; D is false--counting semaphores allow multiple threads.
Final Answer:
Option A -> Option A
Quick Check:
Ownership enforcement is key difference; counting semaphores lack it.
Hint: Mutex ownership vs semaphore count: ownership prevents misuse.
Common Mistakes:
Confusing blocking behavior of semaphores
Assuming counting semaphore overhead is prohibitive
Believing counting semaphore is equivalent to mutex
5. Suppose a file system uses indexed allocation with a single-level index block. What happens when a file grows beyond the capacity of the index block, and how can this limitation be addressed?
hard
A. The file cannot grow further; to support larger files, multi-level or combined index schemes must be used
B. The file system automatically converts the file to contiguous allocation to accommodate growth
C. The index block dynamically expands by linking to additional index blocks without performance penalty
D. The file system switches to linked allocation for that file to handle the extra blocks
Solution
Step 1: Understand single-level index block capacity
A single-level index block can only hold pointers to a fixed number of blocks.
Step 2: What if file grows beyond index block capacity?
The single index block cannot hold more pointers, so the file cannot grow further under this scheme.
Step 3: Analyze the file cannot grow further; to support larger files, multi-level or combined index schemes must be used
Correct: multi-level or combined index schemes (e.g., multi-level indexing, inode structures) are used to support larger files.
Step 4: Analyze the file system automatically converts the file to contiguous allocation to accommodate growth
File systems do not convert allocation methods automatically; contiguous allocation is inflexible for growth.
Step 5: Analyze the index block dynamically expands by linking to additional index blocks without performance penalty
Index blocks do not dynamically expand by linking; multi-level indexing is a designed solution.
Step 6: Analyze the file system switches to linked allocation for that file to handle the extra blocks
File systems do not switch allocation methods on the fly; allocation method is fixed per file.
Final Answer:
Option A -> Option A
Quick Check:
Single-level index block limits file size; multi-level indexing needed for large files.
Hint: Single-level index block -> fixed max file size; multi-level indexing needed [OK]
Common Mistakes:
Believing index blocks can dynamically expand
Thinking allocation methods switch automatically
Assuming contiguous allocation can handle dynamic growth easily
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.