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

Xiaodong Zhang, Yong Yan and Robert Castaneda 

IEEE Parallel & Distributed Technology, Spring Issue, 1996, pp. 25-42.

Abstract 

Performance evaluations and comparisons of mutual exclusion algorithms
have been mainly focused on algorithm analyses in terms of their
computational complexities.  However, effects from architectures and
implementation variations also play important roles in performance of
the algorithms.  In this paper, we propose a framework for mutual
exclusion algorithm performance evaluation on shared-memory
multiprocessors, which combines three important factors, namely, the
properties of the algorithms, execution complexities, and architecture
and system effects.  We implemented several representative mutual
exclusion algorithms on two different shared-memory multiprocessor
systems: the BBN TC2000 and the KSR-1.  Using measured network
latencies of algorithm executions, we evaluate and compare the
scalabilities of the algorithms.  Finally, we propose new and efficient
mutual exclusion algorithms that combine good features of existing
mutual exclusion algorithms.  Our results show that execution
performance of software-based algorithms are highly
architecture-dependent. In general, a hardware-based algorithm performs
more efficiently than a software-based algorithm in the presence of
contention, due to support from atomic instructions. However,
software-based algorithms have a unique advantage of flexibility, which
can be used to take advantage of the structure of architectures and
systems.  Execution performance of these new software-based algorithms
shows their potential to rival against hardware-based algorithms for
mutual exclusion on shared-memory architectures.