Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #1737

MCS queue Lock...

Cross-posted to 2 groups.

Show all headers | View raw

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.

Back to comp.programming.threads | Previous | Next | Find similar

Thread

MCS queue Lock... aminer <aminer@toto.net> - 2013-09-23 20:22 -0700

csiph-web