Scalable Queue-Based Spin Locks with Timeout
Scalable Queue-Based Spin Locks with Timeout Pseudocode from article of the above name in PPoPP'01 . Michael L. Scott and William N. Scherer III . Copyright (c) Michael L. Scott, 2001. The CLH try-lock is derived from a version without timeout due to Craig, Landin, and Hagersten. It performs well on cache-coherent machines. Requires three words of space per lock. Requires SWAP and either CAS or LL/SC . The MCS try-lock is derived from our earlier version without timeout , due to Mellor-Crummey and Scott.
It can be expected to perform well on both cache-coherent and non-cache-coherent machines. Requires only one word of space per lock. Significantly more complicated than the CLH try-lock. Like that lock, requires SWAP and either CAS or LL/SC . CLH queue-based spin lock with timeout typedef enum {waiting, // lock is held available, // lock is free leaving, // node owner is giving up transient, // successor is giving up recycled} // no pointers to node remain clh_status; typedef struct clh_qnode { volatile clh_status status; volatile struct clh_qnode *volatile prev; } clh_qnode; typedef volatile clh_qnode *clh_qnode_ptr; typedef clh_qnode_ptr clh_try_lock; bool clh_try_acquire(clh_try_lock *L, clh_qnode_ptr I, hrtime_t T) { hrtime_t start; clh_status stat; I->status = waiting; clh_qnode_ptr pred = swap(L, I); // check lock once before querying timer -- optimization if (pred->status == available) { I->prev = pred; return true; } start = gethrtime(); // high resolution clock while (gethrtime() - start < T) { stat = pred->status; if (stat == available) { I->prev = pred; return true; } if (stat == leaving) { clh_qnode_ptr temp = pred->prev; pred->status = recycled; pred = temp; } // stat might also be transient, // if somebody left the queue just before I entered } // timed out while (1) { while (pred->status == transient); // spin stat = swap(&pred->status, transient); if (stat == available) { I->prev = pred; return true; } if (stat == leaving) { clh_qnode_ptr temp = pred->prev; pred->status = recycled; pred = temp; continue; } break; // stat == waiting } I->prev = pred; // so successor can find it // indicate leaving, so successor can't leave while (1) { stat = compare_and_swap(&I->status, waiting, leaving); if (stat == waiting) break; while (I->status != waiting); // spin } // if last process in line, link self out if (compare_and_store(L, I, pred)) { pred->status = waiting; return false; } // not last in line while (1) { stat = I->status; if (stat == recycled) { pred->status = waiting; return false; } } } void clh_release(clh_qnode_ptr *I) { clh_qnode_ptr pred = (*I)->prev; while (!compare_and_store(&(*I)->status, waiting, available)) { // can't set my node to available if it's currently transient while ((*I)->status == transient); // spin } *I = pred; } MCS queue-based spin lock with timeout typedef struct mcs_qnode { volatile struct mcs_qnode *volatile prev; volatile struct mcs_qnode *volatile next; } mcs_qnode; typedef volatile mcs_qnode *mcs_qnode_ptr; typedef mcs_qnode_ptr mcs_try_lock; /* We assume that all valid qnode pointers are word-aligned addresses (so the two low-order bits are zero) and are larger than 0x10.
We use low-order bits 01 to indicate restoration of a prev pointer that had temporarily been changed. We also use it to indicate that a next pointer has been restored to nil, but the process that restored it has not yet fixed the global tail pointer. We use low-order bits of 10 to indicate that a lock has been granted (If it is granted to a process that had been planning to leave, the process needs to know who its [final] predecessor was, so it can synch up and allow that predecessor to return from release).
Those two bits are mutually exclusive, though we don't take advantage of the fact. We use bogus pointer values with low-order 0 bits to indicate that a process or its neighbor intends to leave, or has recently done so. */ #define nil ((qnode_ptr) 0x0) #define leaving_self ((qnode_ptr) 0x4) #define leaving_other ((qnode_ptr) 0x8) #define gone ((qnode_ptr) 0xc) #define restored_tag ((unsigned long) 0x1) #define transient_tag restored_tag #define granted_tag ((unsigned long) 0x2) #define is_restored(p) ((unsigned long) (p) & restored_tag) #define is_transient(p) is_restored(p) #define is_granted(p) ((unsigned long) (p) & granted_tag) #define restored(p) ((qnode_ptr)((unsigned long) (p) | restored_tag)) #define transient(p) restored(p) #define granted(p) ((qnode_ptr)((unsigned long) (p) | granted_tag)) #define cleaned(p) ((qnode_ptr)(((unsigned long) (p)) & ~0x3)) #define is_real(p) (!is_granted(p) && ((unsigned long) (p) > 0x10)) /* prev pointer has changed from pred to temp, and we know temp is a real (though possibly restored) pointer.
If temp represents a new predecessor, update pred to point to it, clear restored flag, if any on prev pointer, and set next field of new predecessor (if not restored) to point to me. In effect, RELINK is step 6. */ #define RELINK \ do { \ if (is_restored(temp)) { \ (void) compare_and_swap(&I->prev, \ temp, cleaned(temp)); \ /* remove tag bit from pointer, if it hasn't \ been changed to something else */ \ temp = cleaned(temp); \ } else { \ pred = temp; \ temp = swap(&pred->next, I); \ if (temp == leaving_self) { \ /* Wait for precedessor to notice I've set its \ next pointer and move on to step 2 \ (or, if I'm slow, step 5). */ \ do { \ temp = I->prev; \ } while (temp == pred); \ continue; \ } \ } \ break; \ } while (is_real(temp)); bool mcs_try_acquire(mcs_try_lock *L, qnode_ptr I, hrtime_t T) { qnode_ptr pred; qnode_ptr succ; qnode_ptr temp; hrtime_t start = gethrtime(); // high resolution clock I->next = nil; pred = swap(L, I); if (pred == nil) { // lock was free return true; } // else queue was non-empty I->prev = transient(nil); // word on which to spin // Make predecessor point to me, but preserve transient tag if set. do { temp = pred->next; } while (!compare_and_store(&pred->next, temp, (is_transient(temp) ? transient(I) : I))); /* Old value (temp) can't be granted, because predecessor sets that only via CAS from a legitimate pointer value.
Might be nil (possibly transient) or leaving_self, though. */ if (is_transient(temp)) { while (I->prev == transient(nil)); // spin /* Wait for process that used to occupy my slot in the queue to clear the transient tag on our (common) predecessor's next pointer. The predecessor needs this cleared so it knows when it's safe to return and deallocate its qnode. I need to know in case I ever time out and try to leave: the previous setting has to clear before I can safely set it again. */ /* Store pred for future reference, if predecessor has not modified my prev pointer already. */ (void) compare_and_swap(&I->prev, nil, pred); } else if (temp == leaving_self) { /* I've probably got the wrong predecessor.
Must wait to learn id of real one, *without timing out*. */ do { temp = I->prev; } while (temp == transient(nil)); if (is_real(temp)) { RELINK } } else { /* Store pred for future reference, if predecessor has not modified my prev pointer already. */ (void) compare_and_swap(&I->prev, transient(nil), pred); } while (1) { do { if (gethrtime() - start > T) { goto timeout; // 2-level break } temp = I->prev; } while (temp == pred); // spin if (is_granted(temp)) { // this test is an optimization break; } if (temp == leaving_other) { // Predecessor is leaving; // wait for identity of new predecessor. do { temp = I->prev; } while (temp == leaving_other); } if (is_granted(temp)) { break; } RELINK } // Handshake with predecessor. pred = cleaned(temp); pred->next = nil; return true; timeout: // Timeout has expired; try to leave. /* Step 1: Atomically identify successor (if any) and indicate intent to leave. */ while (1) { do { do { succ = I->next; } while (is_transient(succ)); } while (!compare_and_store(&I->next, succ, leaving_self)); // don't replace a transient value if (succ == gone) { succ = nil; } if (succ == nil) { /* No visible successor; we'll end up skipping st
The rest of this page is on the live site.