CODEWITHSUNDEEP
c++synchronizationlinux-kernelmutexspinlock
KodeWarrior
KodeWarrior

Reputation: 3598

Queued Spinlock

I happened to stumble upon Queued Spinlock and would like to implement in C++. I googled a bit for info on this but wasn't able to get proper documentation.

Any documentation / implementation tips would be much appreciated.

Thanks in advance

I have the following doubt in the code pointed by Michael Brown

// 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 -- Is this what is line is doing ?
    // ebx contains address of lck & [ ebx ] refers to address pointed by lck & 
    // it is over written to ent. eax now contains the memory the lck was pointing to.
    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 -- really ? are we nt overwritting
        // the next pointer here ?
        mov [eax],edx

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

    enter_section:
 }
}

Is this implementation even correct ? I doubt so !

Upvotes: 1

Views: 2558

Answers (1)

Mladen Janković
Mladen Janković

Reputation: 8045

Author of the code in question here. First let me state the code is correct. I just wrote more detailed explanation of the code here: http://kataklinger.com/index.php/queued-spinlocks/

Also I have another implementation, which is somewhat simpler, but not as good as this one (correct nevertheless). I will see if I can find it somewhere. I found it. Here's the link to discussion that includes both implementations: http://forum.osdev.org/viewtopic.php?f=15&t=15389

The last post also has link that discuss queued spinlocks in more depths: http://www.cs.rice.edu/~johnmc/papers/tocs91.pdf

Yeah, I'm bit late for the party, but I was this post just few days ago and it inspired me to write better explanation of the code.

Upvotes: 3

Related Questions