A FAST, SCALABLE MUTUAL EXCLUSION ALGORITHM

Cited 50 time in webofscience Cited 0 time in scopus
  • Hit : 166
  • Download : 0
This paper is concerned with synchornization under read/write atomicity in shared memory multi-processors. We present a new algorithm for N-process mutual exclusion that requires only read and write operations and that has O(logN) time complexity, where ''time'' is measured by counting remote memory references. The time complexity of this algorithm is better than that of all prior solutions to the mutual exclusion problem that are based upon atomic read and write instructions; in fact, the time complexity of most prior solutions is unbounded. Performance studies are presented that show that our mutual exclusion algorithm exhibits scalable performance under heavy contention. In fact, its performance rivals that of the fastest queue-based spin locks based on strong primitives such as compare-and-swap and fetch-and-add. We also present a modified version of our algorithm that generates only O(1) memory references in the absence of contention.
Publisher
SPRINGER VERLAG
Issue Date
1995-08
Language
English
Article Type
Article
Citation

DISTRIBUTED COMPUTING, v.9, no.1, pp.51 - 60

ISSN
0178-2770
DOI
10.1007/s004460050009
URI
http://hdl.handle.net/10203/74715
Appears in Collection
RIMS Journal Papers
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 50 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0