In Part 6 I presented Symmetric Multi-Processor’s (smp) Thundering Herd problem; it’s the result of a lack of fairness in the mutex algorithm. This problem can occur when multiple cpus are using a lock under high contention. Next I’d like to share one of the smp solutions we used at Pyramid to solve this problem.

SMP Solution 1: Random Backoff

You may recall the mutex algorithm as:

mutex (void *addr)
{
while (test_and_set(addr) == 1)
;
}

The problem is that when multiple cpus are waiting for a single lock, the while loop is too predictable. It lacks variation. What we need is a random period before the next call to call test_and_set(). We thus create a Random Backoff array. The size of this array should be large relative to the number of cpus. In the case of 24 cpus, we use an array size of 1024. We then initialize the array entries to random numbers (in micro-seconds) with an appropriate upper bound of 1 second.

So the mutex algorithm now becomes:

mutex (void *addr)
{
intindex;
extern int random_backoff[];

while (test_and_set(addr) == 1)
{
index = random() % 1000000;
usec = random_backoff[index];
usleep(usec);
}
}

The particular use of random() is not required, any type of random number generater will do. What is important is how the random number generater is seeded. Each cpu must use a different seed. I recommend using the cpu number multiplied by the current date.

Notice how we index the array with a random number. If we did not did this, then indexing the array could become predictable.

Contentious Locks

There is a problem with this smp solution though. It is quite possible that when a cpu releases a contentious lock, waiting cpus will not wake up immediately. That is, it could take up to a second before a waiting lock trys to obtain the now free lock. Thus the Random Backoff solution is not optimal.

In my next blog, I will present solutions and refinements to this situation.