MCS Spin Lock

MCS spin lock is named after the inventors John Mellor Crummey and Michael Scotty.  see “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors”.  ACM Trans. Comput. Syst. 9(1): 21-65 (1991). The quotation from Edsger W. Dijkstra Prize in Distributed Computing  2006:

“The key lesson this work has taught us is that one cannot underestimate the importance of reducing memory traffic in scalable synchronization algorithms.  The “local spinning” technique used by the MCS algorithm has heavily influenced virtually all practical scalable synchronization algorithms since. ”

struct lock {
  bool locked;
  struct lock* next;
};
lock *current  = 0;

acquire_lock(lock *l) {
  node * n = atomic_swap(current, l);
  if (n) {
    l->lock=true;
    n->next=l;
    while(l->lock);
  }
}

procedure release_lock (lock *l) {
  if (!l->next) {
    if (atomic_cas(current, l, 0) == l)
      return;
    while (!l->next);
    l->next->locked=false;
  }
}

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s