If Peterson's algorithm is used on a modern multi-core processor with weak memory ordering (e.g., relaxed memory consistency), what is a likely issue that can arise, and how can it be addressed?
hard🎤 Interviewer Follow-up Q15 of Q15
Operating Systems - Critical Section Problem - Requirements & Peterson's Solution
If Peterson's algorithm is used on a modern multi-core processor with weak memory ordering (e.g., relaxed memory consistency), what is a likely issue that can arise, and how can it be addressed?
AThe algorithm will cause starvation because weak memory ordering breaks bounded waiting
BThe algorithm will cause deadlock because weak memory ordering delays flag updates
CThe algorithm will work correctly without modification because it uses only atomic variables
DThe algorithm may fail mutual exclusion due to instruction reordering; inserting memory barriers can fix this
Step-by-Step Solution
Step 1: Understand weak memory ordering impact
Modern processors may reorder instructions, causing visibility issues for shared variables.
Step 2: Effect on Peterson's algorithm
Without memory barriers, the flags and turn variables may be seen out of order, breaking mutual exclusion.
Step 3: Solution
Inserting memory fences/barriers enforces ordering and visibility, preserving correctness.
Final Answer:
Option D -> Option D
Quick Check:
Memory barriers are essential on weakly ordered architectures for software synchronization.
Quick Trick:Weak memory ordering -> need memory barriers for Peterson's correctness
Common Mistakes:
MISTAKES
Assuming Peterson's works without modification on all hardware
Option B confuses deadlock with memory visibility issues. Option C ignores hardware memory models. Option D incorrectly links weak ordering to starvation.
Interviewer Note:
CONTEXT
Tests deep understanding of hardware memory models' impact on classical synchronization algorithms.
Master "Critical Section Problem - Requirements & Peterson's Solution" in Operating Systems
2 interactive learning modes - each teaches the same concept differently
