Empirical Studies of Competitive Spinning for Shared-Memory Multiprocessors

Abstract:

A common operation in multiprocessor programs is acquiring a lock to
protect access to shared data. Typically, the requesting thread is
blocked if the lock it needs is held by another thread. The cost of
blocking one thread and activating another can be a substantial part of
program execution time. Alternatively, the thread could spin until the
lock is free, or spin for a while and then block. This may avoid
context-switch overhead, but processor cycles may be wasted in
unproductive spinning. This paper studies seven strategies for
determining whether and how long to spin before blocking. Of
particular interest are competitive strategies, for which the
performance can be shown to be no worse than some constant factor times
an optimal off-line strategy. The performance of five competitive
strategies is compared with that of always blocking, always spinning,
or using the optimal off-line algorithm. Measurements of lock-waiting
time distributions for five parallel programs were used to compare the
cost of synchronization under all the strategies. Additional
measurements of elapsed time for some of the programs and strategies
allowed assessment of the impact of synchronization strategy on overall
program performance. Both types of measurements indicate that the
standard blocking strategy performs poorly compared to mixed
strategies. Among the mixed strategies studied, adaptive algorithms
perform better than non-adaptive ones.

This technical report has been published as

Empirical Studies of Competitive Spinning on a Shared-Memory
Multiprocessor.
Anna R. Karlin, Kai Li, Mark S. Manasse and susan Dwicki, Proc. of
the 12th ACM Symposium on Operating Systems
Principles, October 1991.