c++ - 如何在不使用mutex、semorphore、spinLock、futex的情况下实现线程同步？

Question

这是一道面试题，面试过了。

如何在不使用mutex、semorphore、spinLock、futex的情况下实现线程同步？

给定 5 个线程，如何让其中的 4 个线程在同一点等待来自左侧线程的信号？这意味着当所有线程 (1,2,3,4) 在其线程函数中的某个点执行时，它们会停止并等待来自线程 5 的信号发送信号，否则它们将不会继续。

我的想法:

使用全局 bool 变量作为标志，如果线程 5 没有将其设置为真，则所有其他线程在某一点等待并设置它们的标志变量为真。线程 5 发现所有线程的标志变量都为真后，它会设置它的标志变量为真。

这是一个忙等待。

有什么更好的主意吗？

谢谢

 the pseudo code:
 bool globalflag = false; 
 bool a[10] = {false} ;  
 int main()
 {
  for (int i = 0 ; i < 10; i++)
  pthread_create( threadfunc, i ) ; 

      while(1)
      {
         bool b = true; 
         for (int i = 0 ; i < 10 ; i++)
         {  
              b = a[i] & b ; 
         }
         if (b) break; 
    }
  }
  void threadfunc(i)
  {
   a[i] = true; 
   while(!globalflag); 
  }

Answer 1

从等待线程的空链表开始。头部应设置为 0。

使用 CAS、比较和交换，在等待者列表的头部插入一个线程。如果 head = -1，则不插入或等待。如果操作正确，您可以安全地使用 CAS 在链表的头部插入项。

插入后，等待线程应该在 SIGUSR1 上等待。使用 sigwait() 来执行此操作。

准备就绪后，信号线程使用 CAS 将等待列表的头部设置为 -1。这可以防止更多线程将自己添加到等待列表中。然后发信号线程迭代等待列表中的线程，调用pthread_kill(&thread, SIGUSR1)唤醒每个等待线程。

如果在调用 sigwait 之前发送 SIGUSR1，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 = macro 使用类似 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; 
}