Algorithmic analysis demonstrates robust mutual exclusion in low-cost hardware systems, indicating that read-write-safe modifications remain competitive without hardware atomic operations.
Summary Dekker's algorithm was thought to be safe in an environment without atomic reads or writes where bits flicker or scramble during simultaneous operations. A counter‐example is presented showing Dekker's algorithm is unsafe without atomic read. A modification to the original algorithm is presented making it RW‐safe, allowing threaded systems to be built on low cost/power hardware without atomic read/write. Correctness is verified by means of invariants and UNITY logic. A performance comparison is made for several two‐thread software mutual‐exclusion algorithms to see if the RW‐safe Dekker is competitive. A subset of the two‐thread solutions are then compared in two N‐thread tournament algorithms. The performance results show that the additional checks in the RW‐safe Dekker do not disadvantage the algorithm in comparison with other two‐thread algorithms. The RW‐safe N‐thread tournament algorithms are competitive with the hardware‐assisted Mellor‐Crummey and Scott algorithm.
No takes yet. Share an insight, caveat, or question.
Buhr et al. (2015) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: