如何在不使用互斥、半裸、spinLock和futex的情况下进行线程同步？

Question

这是一个面试问题，面试已经做完了。

如何在不使用互斥、半裸、spinLock和futex的情况下进行线程同步？

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

我的想法是：

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

这是一个忙碌的等待。

有更好的主意吗？

谢谢

 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

从一个空的等待线程链表开始。head应设置为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行上同时具有多个线程的频率是多少呢？在reality....not中很常见。我们做了一些测试，在同一时间循环添加数百万个具有多个线程的项目，这种情况发生的概率不到1%。在真正的程序中，这可能永远不会发生。

显然，如果有一场比赛，你必须返回并再次循环，但在链表的情况下，这会花费你什么？

缺点是，如果您打算使用该方法向头部添加项，则不能对该链表执行非常复杂的操作。尝试实现一个双向链表。太痛苦了。

编辑：

在上面的代码中，我使用了一个宏CAS。如果您使用的是linux，则使用__sync_bool_compare_and_swap设置CAS =宏。参见gcc atomic builtins。如果您使用的是windows，则使用类似于InterlockedCompareExchange的CAS =宏。下面是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; 
}

Answer 2

1. 选择要使用的信号，比如SIGUSR1。
2. 使用pthread_sigmask来阻塞线程(它们继承了信号掩码，因此1必须完成1-4调用received.
3. Thread )，阻塞直到pthread_kill为SIGUSR1 5次调用pthread_sigmask()或pthread_kill 4次。由于POSIX指定信号将被传递到没有阻塞信号的线程，因此它将被传递到sigwait()中等待的线程之一。因此，不需要使用关联的synchronization.

来跟踪哪些线程已经接收到信号，哪些线程还没有接收到信号

Answer 3

您可以使用SSE3的MONITOR和MWAIT指令来实现这一点，这些指令可以通过_mm_mwait和_mm_monitor内部提供，英特尔有一篇关于它的文章here。(还有一项使用内存-监视器-等待锁争用here的专利可能会引起人们的兴趣)。