从等待线程的空链表开始。头部应设置为 0。
使用 CAS,比较和交换,在等待者列表的头部插入一个线程。如果head =-1,则不要插入或等待。如果操作正确,您可以安全地使用 CAS 在链表的头部插入项目。
插入后,等待线程应该在 SIGUSR1 上等待。使用 sigwait() 来执行此操作。
准备就绪后,信令线程使用 CAS 将等待列表的头部设置为 -1。这可以防止更多线程将自己添加到等待列表中。然后信号线程迭代等待列表中的线程并调用 pthread_kill(&thread, SIGUSR1) 唤醒每个等待线程。
如果 SIGUSR1 在调用 sigwait 之前发送,sigwait 将立即返回。因此,在将线程添加到等待列表和调用 sigwait 之间不会存在竞争。
编辑:
为什么 CAS 比互斥锁快?外行的回答(我是外行)。在某些情况下,它对某些事情的速度更快,因为在没有比赛时它的开销较低。因此,如果您可以将并发问题减少到需要更改 8-16-32-64-128 位的连续内存,并且不会经常发生争用,那么 CAS 获胜。CAS 基本上是一个稍微花哨/昂贵的 mov 指令,无论如何你都要做一个常规的“mov”。它是一个“锁交换”或类似的东西。
另一方面,互斥锁是一大堆额外的东西,它会使其他缓存线变脏并使用更多的内存屏障等。尽管 CAS 在 x86、x64 等上充当内存屏障。当然你必须解锁互斥量可能是大约相同数量的额外东西。
以下是使用 CAS 将项目添加到链表的方法:
while (1)
{
pOldHead = pHead; <-- snapshot of the world. Start of the race.
pItem->pNext = pHead;
if (CAS(&pHead, pOldHead, pItem)) <-- end of the race if phead still is pOldHead
break; // success
}
那么,您认为您的代码多久会在该 CAS 行同时具有多个线程?实际上……不是很常见。我们做了测试,只是循环添加了数百万个项目,同时具有多个线程,而且发生的时间不到 1%。在真正的程序中,它可能永远不会发生。
显然,如果有一场比赛,你必须回去再做一次那个循环,但在链表的情况下,你要花多少钱?
不利的一面是,如果要使用该方法将项目添加到头部,则无法对该链接列表执行非常复杂的操作。尝试实现一个双链表。多么痛苦。
编辑:
在上面的代码中,我使用了一个宏 CAS。如果您使用的是 linux,CAS = 使用 __sync_bool_compare_and_swap 的宏。请参阅gcc atomic builtins。如果您使用的是 Windows,则 CAS = 使用 InterlockedCompareExchange 之类的宏。下面是 Windows 中的内联函数的样子:
inline bool CAS(volatile WORD* p, const WORD nOld, const WORD nNew) {
return InterlockedCompareExchange16((short*)p, nNew, nOld) == nOld;
}
inline bool CAS(volatile DWORD* p, const DWORD nOld, const DWORD nNew) {
return InterlockedCompareExchange((long*)p, nNew, nOld) == nOld;
}
inline bool CAS(volatile QWORD* p, const QWORD nOld, const QWORD nNew) {
return InterlockedCompareExchange64((LONGLONG*)p, nNew, nOld) == nOld;
}
inline bool CAS(void*volatile* p, const void* pOld, const void* pNew) {
return InterlockedCompareExchangePointer(p, (PVOID)pNew, (PVOID)pOld) == pOld;
}