Queued spinlocks

About queued spinlocks

Queued spinlocks are designed as replacement for standard spinlock as main synchronization mechanism in kernel mode of an OS. They provide better performance on multiprocessor systems by reducing contention of interconnection bus during busy waiting, providing fairness and locality of reference. Standard spinlocks suffers from contention of interconnection between processors caused by usage of a single memory location shared by all processors for spinning. This significant increase traffic between processors is caused by cache coherency protocol. On the other hand, when queued spinlocks are used, each processor uses it's own memory location to spin which avoids memory sharing and ease traffic between processor, in addition to that, memory used for spinning is located on the stack currently used by the processor which further improves performance. Queued spinlocks also guarantee that processors will enter guarded critical section in the same order in which they arrive, which is not the case with standard spinlocks.

Implementation

// represents processor in wait queue of the spinlock
struct qsl_entry
{

    // next processor in the queue that is waiting to enter section
    qsl_entry* next;

    // indicates whether the access to section has been granted to processor
    int state;

};

// queued spinlock
struct qsl
{

    // the first processor in the queue that is waiting to enter section
    qsl_entry* head;

};

// requests access to critical section guarded by the spinlock,
// if the section is already taken it puts processor to wait
// and insert it into queue
// lck - queued lock that used to guard section
// ent - entry that represent processor in queue of the spinlock
void lock_qsl(qsl* lck, qsl_entry* ent)
{
    __asm
    {
        mov eax, ent;
        mov ebx, lck;

        // prepare queue entry
        mov [eax], 0;
        mov edx, eax;
        mov [eax]qsl_entry.state, 1;

        // store it as the last entry of the queue
        lock xchg [ebx],eax;

        // if the section available grant access to processor?
        test eax, eax;
        jz enter_section;
            // link new entry with the rest of queue
            mov [eax],edx

            // wait for processor's turn
            wait1:
                pause;
                cmp [edx]qsl_entry.state, 1;
                je wait1;

        enter_section:
    }
}

// release access to critical section guarded by the spinlock
// it also grants access to next processor in the queue if there is one
// lck - queued lock that used to guard section
// ent - entry that represent processor in queue of the spinlock
void unlock_qsl(qsl* lck, qsl_entry* ent)
{
    __asm
    {
        mov eax, ent;
        mov ebx, lck;
        xor ecx, ecx;
        mov edx, eax;

        // release section and get next processor in the queue
        // which is waiting for the section
        lock cmpxchg [ebx], ecx;

        // is this the last processor waiting for the queue?
        je exit_section;

            // wait for processor that just has started entering into section
            wait2:
                pause;
                cmp [edx], ecx;
                je wait2;

            // grant access to next processor in the queue
            mov eax, [edx];
            mov [eax]qsl_entry.state, ecx;

        exit_section:
    }
}

Using the Code

qsl lock;
int thread_1(void* p)
{
    qsl_entry entry;
    while( 1 )
    {
        lock_qsl( &lock, &entry );
        printf( "thread " );
        printf( "%d", (int)p );
        printf( "\n" );
        unlock_qsl( &lock, &entry );
     }
     return 0;
}

int main()
{
    CreateThread( NULL, 0, (LPTHREAD_START_ROUTINE)thread_1,
        (void*)1, 0, NULL ); 
    CreateThread( NULL, 0, (LPTHREAD_START_ROUTINE)thread_1,
        (void*)2, 0, NULL ); 
    getchar();
    return 0;
}