How to implement prioritized lock with only compare_and_swap?

Given only compare and swap, I know how to implement a lock.

H开发者_运维百科owever, how do I implement a spin lock

1) multiple threads can block on it while trying to lock 2) and then the threads are un-blocked (and acquire the lock) in the order that they blocked on it?

Is it even possible? If not, what other primitives do I need?

If so, how do I do it?

Thanks!

You are going to need a list for the waiting threads. You need to add and remove items from the list in a thread safe manner. You will need to be able to sleep threads that fail to acquire the lock. You will need to be able to wake 1 thread when the lock becomes available. In linux you can accomplish the sleep and wait thing by having the thread wait on a signal.

Now there is a lazy way to do this, you might not need to care about waking threads. Here is pseudo code for our skiplist. This is what we do to add an item.

cFails = 0
while (1) {
  NewState = OldState = State;
  if (cFails > 3 || OldState.Lock) {
    sleep();  // not too sophisticated, because they cant be awoken
    cFails = 0;
    continue;
  }

  Look for item in skiplist
  return item if we found it

  // to add the item to the list we need to lock it

  // ABA lock uses a version number
  NewState.Lock=1;
  NewState.nVer++;
  if (!CAS(&State,OldState, NewState)) {
    ++cFails;
    continue; 
  }

  // if the thread gets preempted right here, the lock is left on, and other threads
  // spinning would waste their entire time slice.

  // unlock
  OldState = NewState;
  NewState.Lock = 0;
  NewState.nVer++;
  CAS(&State, OldState,NewState);  
}

We expect the skiplist to usually find the item and only rarely have to add it. We rarely have a race to add, even with a lot of threads. We tested this with a worst case scenario consisting of lots of threads adding and searching for millions of items to a single list. The result is we rarely saw threads fail to get the lock. So the simple approach that is high performance for the expected case works for us. There is one bad thing that can happen - a thread gets preempted holding the lock. Thats when cFails > 3 catches this and sleeps waiting threads so we don't waste their timeslices with a million useless spins. So cFails is set high enough that it detects that the owner of the lock is not active.