There is no way around the fundamental problem, as ldstub must be atomic. It must occupy the
bus for the duration. What we can do is simply not call it too often. In particular, this means
modifying our definition of spin locks. Whereas our first definition of spin locks resulted in our
calling ldstub on every iteration of the loop (thus flooding the bus), our better definition (Code
Example 16-1) will avoid calling ldstub unless we're fairly sure that it will succeed. What we'll
do is spin in a loop, looking at the value of the ownership byte. As long as it's owned, we'll just
keep spinning, looking at the value in cache, not generating any bus traffic at all.
Example 16-1 Spin Locks Done Better
/* Implementation dependent. This is valid only for Solaris 2.5 */
void spin_lock(mutex_t *m) {
int i;
for (i = 0; i < SPIN_COUNT; i++) {
if (m->lock.owner64 == 0)
/* Check w/o ldstub */
if (pthread_mutex_trylock(m) != EBUSY)
return;
/* Got it! */
/* Didn't get it, continue the loop */
}
pthread_mutex_lock(m);
/* Give up and block */
}
When the lock is released, the owner CPU will write out zero, which our bus snooper will see,
invalidating our copy of the byte. On our next iteration we'll get a cache miss, reload from main
memory, and see the new value. We'll call trylock (hence ldstub), and if we're lucky, it will
succeed and we'll get lock ownership. On the off chance that some other CPU sneaks in there at
exactly the right nanosecond, our ldstub will fail, and we'll go back to spinning. Generally, you
should expect spin locks to be provided by your vendor.
The Thundering Herds
This is as far as we're going to go with spin locks. This covers 99.9% of all programs that need
spin locks. For that final 0.1%, where there is enormous contention for a single spin lock, even
this scheme will suffer. If there are 10 CPUs all spinning on this lock, the moment it's released, all
ten of them will take cache misses, flooding the bus first with cache load requests, then ldstub
requests. This is known as the thundering herds problem and is discussed in more detail by
Hennessy and Patterson (see Appendix B). Suffice it to say, if you're suffering from this problem,
Search WWH :
