TY - GEN
T1 - Empirical studies of competitve spinning for a shared-memory multiprocessor
AU - Karlin, Anna R.
AU - Li, Kai
AU - Manasse, Mark S.
AU - Owicki, Susan
PY - 1991
Y1 - 1991
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=70450049370&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70450049370&partnerID=8YFLogxK
U2 - 10.1145/121132.286599
DO - 10.1145/121132.286599
M3 - Conference contribution
AN - SCOPUS:70450049370
SN - 0897914473
SN - 9780897914475
T3 - Proceedings of the 13th ACM Symposium on Operating Systems Principles, SOSP 1991
SP - 41
EP - 55
BT - Proceedings of the 13th ACM Symposium on Operating Systems Principles, SOSP 1991
T2 - 13th ACM Symposium on Operating Systems Principles, SOSP 1991
Y2 - 13 October 1991 through 16 October 1991
ER -