Blog

I’m wrapping up a nine-part series on Symmetric Multi Processors (SMP). Following up on #8 the Random Back-off Problem which focused on a solution to isolating locks so that a cache line can only hold a single lock, I’ll conclude with another solution that completely solves the Thundering Herd problem in an optimal manner: Queued Locks.

I’ve shown you how a 32 bit cpu commonly uses an 8-word cache line.  And we only want a single lock (or word) on a cache line.  We can use the rest of the cache line to implement a Queued Lock.

Queued Locks

The Queued Lock algorithm essentually consists of having a cpu add itself to the end of a queue when it is waiting for a lock (this gives us fairness).  The cpu then does a tight spin on a private cache line, waiting for the lock to be released (this gives us optimality).  When the lock is released, the holding cpu picks the first cpu off of the queue (this is fair) and pokes the private cache line of that cpu to wake it up (optimal).

Single Cache

Here is the Queued Lock data structure that resides on a single cache line:

struct queued_lock
{
    int  mutex; // locks this data structure.

    int  value; // 0 = free, 1 = locked

    char  queue[24];
};

This data structure can thus handle a 25 cpu system.  The queue field contains cpu numbers.  A zero value indicates that the entry is free.

Private Wait Array

Here is the Private Wait Array:

struct private_wait
{
    int  value;

    int  fill[7];
};

struct private_wait private_wait_array[25];

This array is indexed by the cpu number.

Queued Lock Algorithms

Here is the Queued Lock lock algorithm:

queued_lock_lock (struct queued_lock *lock)
{

Now that I've laid out various scenarios and solutions, have I missed anything? What solutions would you add?
    while (test_and_set(lock->mutex) == 1)    // lock the data structure
        ;

    if (lock->value == 0)    // lock is not set, take it
    {
        lock->value = 1;
        lock->mutex = 0;    // unlock the data structure
    }
    else    // lock is set, add myself to the queue, and wait
    {
        for (index = 0; ; index++)
        {
            assert(index < 24)

            if (lock->queue[index] == 0)
                break;
        }

        lock->queue[index] = my_cpu_number + 1;
        private_wait_array[my_cpu_number]->value = 0;
        lock->mutex = 0;    // unlock the data structure

        while (private_wait_array[my_cpu_number]->value == 0)
            ;
    }
}

And finally here is the Queued Lock unlock algorithm:

queued_lock_unlock (struct queued_lock *lock)
{
    while (test_and_set(lock->mutex) == 1)    // lock the data structure
        ;

    if (lock->queue[0] == 0)  // no one is waiting
    {
        lock->value = 0;
    }
    else  // somebody is waiting, poke them
    {
        cpu = lock->queue[0] - 1;
        memmove(&lock->queue[0], &lock->queue[1], 23);
        private_wait_array[cpu]->value = 1;
    }

    lock->mutex = 0;    // unlock the data structure
}

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?

Isolated & Separated Locks

Consider two SMP locks: L1 and L2, both on a single cache line.  Note: on a 32 bit cpu, a word is 32 bits and a cache line is commonly 8 words, and a single cache line could thus hold 8 locks.  If a cpu locks L1, then its cached copy of L1 is updated and the cache copy of L1 for the other cpus is invalidated.  A waiting cpu will thus have to get the up to date copy of L1 from main memory.  This is an expensive operation in time and bus traffic.  If L2 is also on the same cache line, then L1 traffic will invalidate L2 cache copies.  The L2 cache invalidates are not necessary for L2 cache coheriency and thus adversly effect system performance.

If we seperate L1 and L2 and place them on different cache lines, then L1 activity does not effect L2 activity and visa versa.

Memory Wasted

The downside of this solution is that memory is wasted.  Optimally (as far as memory is concerned) we could pack 8 locks into a single cache line.  So for every lock we are wasting 7 words.  If we consider Moore’s Law and how the price of memory chips is constantly dropping, I think this solution is worth the price.

So how much does this solution help?  Turns out that cache line isolation does not completely solve this problem.  It improves the situation, but does not completely elliminate it.  So in my next post, I will present another solution to the SMP Random Backoff problem.

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)
{
    int  index;
    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.

My last five blogs posts have presented:

1. The Symmetric Multi Processor (SMP) scaling problem.
2. The solution as presented by Pyramid Technology.
3. The user space SMP problem.
4. The various lock primitives.
5. Debugging locks.

Now, let’s explore something called the Thundering Herd Problem. If you recall, a previous blog presented the mutex algorithm as:

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

Now consider the scenerio where Process 1 (P1) is holding a lock and two other processes (P2 and P3) are trying to obtain the same lock.  If P2 has waiting for a long time and P3 has been waiting for a small amount of time, then there is nothing in the mutext algorithm that enforces fairness.  That is, once P1 releases the lock, P3 can immediately obtain it, even though P2 has been waiting for a much longer time.

Now extend this problem to a 12 CPU SMP system.  One cpu could hold a lock and 11 cpu’s could be waiting on the same lock.  And extend this problem to a 24 CPU SMP system.  One cpu could hold a lock and 23 cpu’s could be waiting on the same lock.

In this case, when a cpu releases a lock, possibly 23 other cpus could all try to get the same lock.  This mass attempt to obtain a single lock results in a non linear increase in bus and cache traffic.  The Thundering Herd is the 23 other cpus.  And the problem is, only one cpu is going to obtain the lock.  The other 23 cpus go back into a wait state and the process continues.  Since fairness is not built into this algorithm, there is no gaurantee that a particular cpu will obtain the lock in a reletively fair fashon.

Are there locks that suffer from this kind of contention?  Does the Thundering Herd problem occur in a real engineering envirnoment?  Or, is all of this just an interesting theory?

At Pyramid we actually ran into this problem.  In the Unix kernel, there a number of locks that experience this kind of contention.  And we experienced the Thundering Herd problem when we expanded our cachsis from 12 cpus to 24 cpus.  We actually ran into Lock Timeouts (30 seconds) where no single cpu was holding the lock for an excessive amount of time.  The problem was that the mutex algorithm was not fair, a waiting cpu was starved for attention.

In my next post I will present solutions to this problem.

My last four blogs posts have presented:

1. Symmetric Multi Processor (SMP) scaling problem.
2. Solution as presented by Pyramid Technology.
3. User space SMP problem.
4. Various lock primitives.

It’s logical to now explore how to debug an SMP system. But first I need to present the classic locking problem as defined by Dijkstra.

Classic Locking Problem

Consider two processes: P1 and P2; and two locks: L1 and L2.  Now consider the following locking scenerio: P1 locks L1 (P1.L1) and then L2 (P2.L1); P2 locks L2 (P2.L2) and then L1 (P2.L1).

If the locks are aquired in the order: (1: P1.L1, 2: P2.L2, 3: P1.L2, 4: P2,L1), then steps 3 and 4 will never complete.  This scenerio is called a deadlock in that both processes are stuck waiting for locks that are held by each other.

So how do we deal with a SMP deadlock?  There are essentually two ways to deal with deadlocks.  Method 1: try to detect when a deadlock has occured.  Method 2: prevent deadlocks from occuring.

The first method is somewhat problomatic in that you have to keep track of all of the locks in the system and periodically monitor them for a deadlock.

The second method is much easier to implement.  Pyramid dealt with this problem by adding code to detect when a deadlock was immenant.  To wit, a positive, non-zero level was assigned to each lock and the lock protocol was modified to ensure that a lock could only be aquired if the lock level was increased.

Now let us apply lock levels to the Dijkstra lock problem.  L1 will now be defined as L1.5 (lock 1 with level 5) and L2 will now be defined as L2.10 (lock 1 with level 10).  If the locks are aquired in the order: (1: P1.L1, 2: P2.L2, 3: P1.L2, 4: P2,L1), then step 4 will generate a Lock Level Violation since P2 is holding L2 (which has a level of 10) and P2 is trying to lock L1 (which has a level of 5) – you can only increase the lock levels.

Handling SMP Interrupts

There is another problem that we have to deal with: interrupts.  If a process is holding a lock and interrupts occur, then it will look like the process is holding the lock for a long time.

This problem is dealt with by adding an interrupt level to the definition of a lock.  In addition, the lock protocol is expanded by requiring that the cpu interrupt level be set to the lock interrupt level.  Setting the cpu interrupt level blocks interrupts at a lower level.  System interrupts are defined by levels, for example: 0 = none, 1 = tty, 2 = network, 3 = disk, etc.  The higher the interrupt level, the higher the priority.  Higher level interrupts block out lower level interrupts.  Thus, setting the interrupt level of a cpu to priority X, blocks all interrupts lower than and including level X.

Defining the Locking Protocol

So a lock is now defined as: (Name, Level, Interrupt).  And the locking protocol is now defined as:

1)  If the new lock level is less than the current lock level, then generate a Lock Level Protocol Violation.

2)  If the new lock interrupt priority is less than the current cpu interrupt priority, then generate a Lock Interrupt Protocol Violation.

Next up? SMP’s Thundering Herd Problem.