只考虑比较和交换,我知道如何实现锁。
但是,如何实现自旋锁
1)多个线程可以在尝试锁定时阻塞它 2)然后线程按照它们阻塞的顺序被解除阻塞(并获取锁)?
甚至可能吗?如果没有,我还需要哪些其他原语?
如果是这样,我该怎么做?
谢谢!
只考虑比较和交换,我知道如何实现锁。
但是,如何实现自旋锁
1)多个线程可以在尝试锁定时阻塞它 2)然后线程按照它们阻塞的顺序被解除阻塞(并获取锁)?
甚至可能吗?如果没有,我还需要哪些其他原语?
如果是这样,我该怎么做?
谢谢!
您将需要等待线程的列表。您需要以线程安全的方式从列表中添加和删除项目。您将需要能够使无法获取锁的线程休眠。当锁可用时,您将需要能够唤醒 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 设置得足够高,以至于它检测到锁的所有者没有激活。