Dekker's mutual exclusion algorithm made RW-safe

作者：Buhr Peter A^*; Dice David; Hesselink Wim H

来源：Concurrency and Computation: Practice and Experience (CCPE) , 2016, 28(1): 144-165.

DOI：10.1002/cpe.3659

• Dekker's algorithm
• software solution
• mutual exclusion
• performance experiment

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.

• 出版日期2016-1