如何仅用compare_and_swap实现优先级锁？

Question

仅给出比较和交换，我就知道如何实现锁。

但是，如何实现自旋锁

1）多个线程在尝试锁定时可以阻塞它 2）然后线程按照它们阻塞的顺序解除阻塞（并获取锁）？

有可能吗？如果没有，我还需要什么其他原语？

如果是这样，我该怎么做？

谢谢！

Answer 1

您将需要一个等待线程的列表。您需要以线程安全的方式在列表中添加和删除项目。您需要能够休眠未能获取锁的线程。当锁可用时，您需要能够唤醒 1 个线程。在 Linux 中，您可以通过让线程等待信号来完成睡眠和等待。

现在有一种懒惰的方法可以做到这一点，您可能不需要关心唤醒线程。这是我们的跳跃列表的伪代码。这就是我们添加项目所做的事情。

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);  
}

我们期望跳跃列表通常能够找到该项目，并且很少需要添加它。即使有很多线程，我们也很少需要添加竞争。我们使用最坏的情况对此进行了测试，其中包括大量线程向单个列表添加和搜索数百万个项目。结果是我们很少看到线程无法获得锁。因此，对于预期情况而言高性能的简单方法对我们来说很有效。可能会发生一件坏事 - 持有锁的线程被抢占。那就是 cFails > 的时候3 捕捉到这个并让等待线程休眠，这样我们就不会浪费它们的时间片进行一百万次无用的旋转。因此，cFails 设置得足够高，以使其检测到锁的所有者不处于活动状态。