Last time I presented a solution to the Thundering Herd problem: the Random Backoff, but noted a problem with solution.  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 tries to obtain the now-free lock.  This solution is thus not optimal.

As a follow-up I’d like to present a SMP refinement that I believe solves this problem: isolating and separating all locks so that there is a single lock per cache line.  Why do we do this?

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

My last three blog posts have presented the SMP (Symmetric Multi Processor scaling problem, Performance Solution as presented by Pyramid Technology, and the user space SMP problem. Now, I’d like to delve into the locks themselves.  What actually is a lock?

There are essentually two types of SMP locks: mutexes and semaphores.

SMP Mutex Lock

A mutex (short for mutual exclusion), is a lock that waits for a field to be released before proceeding.  In its simplist incantation, a mutex constantly checks the field in question.  This type of lock thus uses the following alorithm: