Dekker's mutual exclusion algorithm made RW-safe

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 algorith...

Full description

Saved in:
Bibliographic Details
Published in:Concurrency and computation 2016-01, Vol.28 (1), p.144-165
Main Authors: Buhr, Peter A., Dice, David, Hesselink, Wim H.
Format: Article
Language:English
Subjects:
Algorithms
Computer programs
Concurrency
Dekker's algorithm
Flicker
Hardware
Invariants
mutual exclusion
performance experiment
software solution
Threaded
Unity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. Copyright © 2015 John Wiley & Sons, Ltd.
ISSN:1532-0626
1532-0634
DOI:10.1002/cpe.3659