MCS queue Lock...

[aminer]

Hello,

Please take a look at the follwing MCS queue lock algorithm:

==

mcs_node{
mcs_node next;
int is_locked;
}

mcs_lock{
mcs_node queue;
}

function Lock(mcs_lock lock, mcs_node my_node){
my_node.next = NULL;
mcs_node predecessor = fetch_and_store(lock.queue, my_node);
//if its null, we now own the lock and can leave, else....
if (predecessor != NULL){
my_node.is_locked = true;
//when the predecessor unlocks, it will give us the lock
predecessor.next = my_node;
while(my_node.is_locked){}
}

function UnLock(mcs_lock lock, mcs_node my_node){
//is there anyone to give the lock to?
if (my_node.next == NULL){
//need to make sure there wasn't a race here
if (compare_and_swap(lock.queue, my_node, NULL)){
return;
}
else{
//someone has executed fetch_and_store but not set our
next field
while(my_node.next==NULL){}
}
}
//if we made it here, there is someone waiting, so lets wake them up
my_node.next.is_locked=false;
}

===


Firt you will notice that it's using an atomic fetch_and_store,
plus it is using a spin wait, so it's more expensive than
the Spinlock with an exponential backoff, so i prefer the
SpinLock with an exponential backoff cause the exponential backoff
will reduce the cache coherency traffic and reduce the CPU utilisation
when there is more contention, this is why the Spinlock with an
exponential backoff is giving a good performance , and almost the same
performance as the MCS queue Lock,
proof of that ? look at the the following graph of the "Lock
comparison" up to 80 core bellow in the following PDF file and
you will notice that the test&set with an exponential backoff
have almost the same performance as the MCS queue Lock:

http://www.cs.rice.edu/~vs3/comp422/lecture-notes/comp422-lec19-s08-v1.pdf


So i think i will stay with the Spinlock with an exponential backoff
cause it has a good performance.



Thank you,
Amine Moulay Ramdane.