2

只考虑比较和交换，我知道如何实现锁。

但是，如何实现自旋锁

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

甚至可能吗？如果没有，我还需要哪些其他原语？

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

谢谢！

4

1 回答 1

0

您将需要等待线程的列表。您需要以线程安全的方式从列表中添加和删除项目。您将需要能够使无法获取锁的线程休眠。当锁可用时，您将需要能够唤醒 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 设置得足够高，以至于它检测到锁的所有者没有激活。

于 2012-04-09T17:21:43.827 回答