8

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

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

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

我的点子：

使用全局 bool 变量作为标志，如果线程 5 未将其设置为 true，则所有其他线程在某一时刻等待并将其标志变量设置为 true。线程 5 发现所有线程的 flag 变量为 true 后，将其设置 flag var true。

这是一个忙碌的等待。

有更好的主意吗？

谢谢

 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); 
  }
4

4 回答 4

5

从等待线程的空链表开始。头部应设置为 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; 
}
于 2012-05-26T22:24:09.533 回答
1
  1. 选择要使用的信号，例如 SIGUSR1。
  2. 使用 pthread_sigmask 阻止 SIGUSR1。
  3. 创建线程（它们继承信号掩码，因此必须先完成 1！）
  4. 线程 1-4 调用 sigwait，阻塞直到收到 SIGUSR1。
  5. 线程 5 使用 SIGUSR1 调用 kill() 或 pthread_kill 4 次。由于 POSIX 指定信号将被传递给未阻塞信号的线程，因此它将被传递给在 sigwait() 中等待的线程之一。因此，不需要跟踪哪些线程已经接收到信号，哪些没有，以及相关的同步。
于 2012-05-27T08:18:35.600 回答
1

您可以使用 SSE3MONITOR和MWAIT指令来执行此操作，这些指令可通过_mm_mwait和内在函数获得，英特尔在此处_mm_monitor有一篇关于它的文章。（这里还有一个使用 memory-monitor-wait for lock contention 的专利，这可能很有趣）。

于 2012-05-27T08:59:52.077 回答
1

我认为您正在寻找Peterson 算法或Dekker 算法

他们仅基于共享内存同步线程

于 2012-05-28T03:05:51.913 回答