Dekker's mutual exclusion algorithm made RW-safe

Peter A. Buhr, Dave Dice, Willem H. Hesselink

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)144-165
Number of pages22
JournalConcurrency and Computation
Volume28
Issue number1
DOIs
Publication statusPublished - Jan-2016

Keywords

  • INTERPROCESS COMMUNICATION
  • PROGRAMS
  • mutual exclusion
  • performance experiment
  • Dekker's algorithm
  • software solution

Cite this