Evaluating and designing software mutual exclusion algorithms on shared-memory multiprocessors

Abstract

Performance evaluations of software-based mutual exclusion algorithms must take into account the effects of architectures and systems. We demonstrate a framework for such evaluation, and use the framework as a basis for designing more efficient algorithms. We propose a comprehensive performance evaluation framework that examines the overhead patterns inherent in the mutual exclusion algorithms and in the architectures on which the algorithms run. We used this framework to evaluate several representative mutual exclusion algorithms on the BBN TC2000 and KSR-1. Our research with this framework has helped us determine the characteristics of efficient software mutual exclusion algorithms. Based on these characteristics, we've developed three mutual exclusion algorithms, two of which combine good features of two of the representative algorithms. Tests show that these new algorithms are fast and can be highly scalable.