Accession Number:

ADA272947

Title:

Fast Mutual Exclusion, Even with Contention

Descriptive Note:

Technical rept.

Corporate Author:

ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1993-06-01

Pagination or Media Count:

16.0

Abstract:

The authors present a mutual exclusion algorithm that performs well both with and without contention, on machines with no atomic instructions other than read and write. The algorithm capitalizes on the ability of memory systems to read and write at both full-and half-word granularities. It depends on predictable processor execution rates, but requires no bound on the length of critical sections, performs only On total references to shared memory when arbitrating among conflicting requests rather than On squared in the general version of Lamports fast mutual exclusion algorithm, and performs only 2 reads and 4 writes a new lower bound in the absence of contention. We provide a correctness proof. We also investigate the utility of exponential backoff in fast mutual exclusion, with experimental results on the Silicon Graphics Iris multiprocessor and on a larger, simulated machine. With backoff in place, we find that Lamports algorithm, our new algorithm, and a recent algorithm due to Alur and Taubenfeld all work extremely well, outperforming the native hardware locks of the Silicon Graphics machine, even with heavy contention.

Subject Categories:

  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE