Peterson's solution in Operating Systems - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of Peterson's solution

What is the main goal of Peterson's solution in operating systems?

A To ensure mutual exclusion between two processes accessing a shared resource

B To increase the speed of process execution by parallelizing tasks

C To allocate memory dynamically to processes

D To schedule processes based on priority levels

💡 Hint

Think about what problem arises when two processes try to use the same resource at the same time.

Peterson's solution is a classic algorithm designed to ensure that two processes do not enter their critical sections simultaneously, thus achieving mutual exclusion.

📋 Factual

intermediate

Key variables in Peterson's solution

Which two shared variables are used in Peterson's solution to coordinate access between two processes?

A "semaphore" and "mutex"

B "priority" variable and "state" array

C "lock" variable and "counter" variable

D "flag[]" array and "turn" variable

💡 Hint

One variable indicates if a process wants to enter the critical section, and the other decides whose turn it is.

Peterson's solution uses a boolean array "flag[]" where each process sets its intent to enter the critical section, and a "turn" variable to decide which process gets priority.

🔍 Analysis

advanced

Analyzing Peterson's solution for deadlock

Does Peterson's solution allow deadlock to occur? Why or why not?

A No, because it uses semaphores to prevent deadlock

B Yes, because both processes can wait indefinitely if they set their flags simultaneously

C No, because the "turn" variable ensures that one process will always proceed if both want to enter the critical section

D Yes, because it does not handle process priorities

💡 Hint

Consider how the "turn" variable helps break ties when both processes want to enter.

Peterson's solution prevents deadlock by using the "turn" variable to give priority to one process, ensuring that if both want to enter, one will proceed while the other waits.

❓ Comparison

advanced

Peterson's solution vs. hardware-based locking

Compared to hardware-based locking mechanisms like test-and-set, what is a limitation of Peterson's solution?

A It requires special CPU instructions to function

B It only works correctly for two processes and relies on strict memory ordering

C It can handle multiple processes without any modification

D It guarantees fairness without any waiting

💡 Hint

Think about the number of processes and hardware requirements.

Peterson's solution is designed for exactly two processes and assumes sequential consistency in memory operations, which may not hold on modern hardware without additional memory barriers.

❓ Reasoning

expert

Why Peterson's solution is not widely used in modern systems

Despite its correctness, why is Peterson's solution rarely used in real-world operating systems today?

A Because modern CPUs have relaxed memory models that can break its assumptions without explicit memory barriers

B Because it causes deadlocks in multi-threaded environments

C Because it requires too much memory to store flags for each process

D Because it only works on single-core processors

💡 Hint

Consider how modern CPU architectures handle memory operations.

Modern CPUs often reorder memory operations for performance, which can break the assumptions Peterson's solution relies on unless special memory barriers are used, making it impractical for real systems.

Practice

1. What is the main purpose of Peterson's solution in operating systems?

easy

A. To prevent two processes from accessing a shared resource simultaneously

B. To increase the speed of process execution

C. To allocate memory to processes

D. To schedule processes based on priority

Solution

1. Step 1: Understand the problem Peterson's solution addresses

   Peterson's solution is designed to handle the critical section problem where two processes must not access a shared resource at the same time.

2. Step 2: Identify the main goal of the solution

   The main goal is to ensure mutual exclusion, preventing simultaneous access to shared resources.

3. Final Answer:

   To prevent two processes from accessing a shared resource simultaneously -> Option A

4. Quick Check:

   Mutual exclusion = Prevent simultaneous access [OK]

Hint: Peterson's solution controls access to shared resources [OK]

Common Mistakes:

• Confusing it with process scheduling
• Thinking it manages memory allocation
• Assuming it increases execution speed

2. Which of the following variables is NOT used in Peterson's solution?

easy

A. flag

B. turn

C. counter

D. process_id

Solution

1. Step 1: Recall the variables used in Peterson's solution

   Peterson's solution uses two flags (one per process) and a turn variable to control access.

2. Step 2: Identify the variable not part of the solution

   The variable 'counter' is not used in Peterson's solution; it is unrelated to mutual exclusion control.

3. Final Answer:

   counter -> Option C

4. Quick Check:

   Variables used = flag, turn; counter not used [OK]

Hint: Remember only flag and turn variables are used [OK]

Common Mistakes:

• Assuming process_id is a variable in Peterson's solution
• Confusing counter with flag
• Thinking turn is a counter

3. Consider two processes P0 and P1 using Peterson's solution. If both set their flags to true and turn to 1, which process will enter the critical section first?

medium

A. P0

B. P1

C. Both enter simultaneously

D. Neither enters

Solution

1. Step 1: Analyze the turn variable's role

   The turn variable indicates which process's turn it is to enter the critical section when both want access.

2. Step 2: Apply the given values

   Both flags are true, meaning both want to enter. Since turn is set to 1, process P1 has priority to enter first.

3. Final Answer:

   P1 -> Option B

4. Quick Check:

   Turn = 1 means P1 enters first [OK]

Hint: Turn variable decides which process enters first [OK]

Common Mistakes:

• Assuming both enter simultaneously
• Ignoring the turn variable
• Thinking the first flag set enters first

4. Identify the error in this Peterson's solution snippet for process P0:

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

medium

A. No error; this is correct Peterson's solution code

B. turn should be set to 0 instead of 1

C. flag[0] should be set to false before the while loop

D. The while condition should use OR instead of AND

Solution

1. Step 1: Review the Peterson's solution steps for process P0

   Process P0 sets its flag true, sets turn to the other process (1), then waits while the other process wants to enter and it's their turn.

2. Step 2: Check the correctness of the code snippet

   The code correctly implements the waiting condition and resets the flag after the critical section.

3. Final Answer:

   No error; this is correct Peterson's solution code -> Option A

4. Quick Check:

   Code matches Peterson's solution pattern [OK]

Hint: Check waiting condition and flag reset carefully [OK]

Common Mistakes:

• Changing turn to own process instead of other
• Misplacing flag reset before critical section
• Using OR instead of AND in while condition

5. How does Peterson's solution ensure fairness between two processes competing for a critical section?

hard

A. By allowing the process with higher priority to enter first

B. By locking the resource permanently for the first process

C. By using a random number generator to decide access

D. By using a turn variable to alternate access between processes

Solution

1. Step 1: Understand fairness in Peterson's solution

   Fairness means no process waits forever; both get a chance to enter the critical section.

2. Step 2: Identify how fairness is implemented

   The turn variable ensures that if both processes want access, the one whose turn it is gets priority, then the turn switches, alternating access.

3. Final Answer:

   By using a turn variable to alternate access between processes -> Option D

4. Quick Check:

   Turn variable alternates access = fairness [OK]

Hint: Turn variable alternates access to ensure fairness [OK]

Common Mistakes:

• Thinking priority decides access
• Assuming random choice controls fairness
• Believing resource is locked permanently