How to make thread synchronization without using mutex, semorphore, spinLock and futex?

Question

This is an interview question, the interview has been done.

How to make thread synchronization without using mutex, semorphore, spinLock and futex ?

Given 5 threads, how to make 4 of them wait for a signal from the left thread at the same point ? it means that when all threads (1,2,3,4) execute at a point in their thread function, they stop and wait for signal from thread 5 send a signal otherwise they will not proceed.

My idea:

Use global bool variable as a flag, if thread 5 does not set it true, all other threads wait at one point and also set their flag variable true. After the thread 5 find all threads' flag variables are true, it will set it flag var true.

It is a busy-wait.

Any better ideas ?

Thanks

 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

Start with an empty linked list of waiting threads. The head should be set to 0.

Use CAS, compare and swap, to insert a thread at the head of the list of waiters. If the head =-1, then do not insert or wait. You can safely use CAS to insert items at the head of a linked list if you do it right.

After being inserted, the waiting thread should wait on SIGUSR1. Use sigwait() to do this.

When ready, the signaling thread uses CAS to set the head of wait list to -1. This prevents any more threads from adding themselves to the wait list. Then the signaling thread iterates the threads in the wait list and calls pthread_kill(&thread, SIGUSR1) to wake up each waiting thread.

If SIGUSR1 is sent before a call to sigwait, sigwait will return immediately. Thus, there will not be a race between adding a thread to the wait list and calling sigwait.

EDIT:

Why is CAS faster than a mutex? Laymen's answer (I'm a layman). Its faster for some things in some situations, because it has lower overhead when there is NO race. So if you can reduce your concurrent problem down to needing to change 8-16-32-64-128 bits of contiguous memory, and a race is not going to happen very often, CAS wins. CAS is basically a slightly more fancy/expensive mov instruction right where you were going to do a regular "mov" anyway. Its a "lock exchng" or something like that.

A mutex on the other hand is a whole bunch of extra stuff, that gets other cache lines dirty and uses more memory barriers, etc. Although CAS acts as a memory barrier on the x86, x64, etc. Then of course you have to unlock the mutex which is probably about the same amount of extra stuff.

Here is how you add an item to a linked list using 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
}

So how often do you think your code is going to have multiple threads at that CAS line at the exact same time? In reality....not very often. We did tests that just looped adding millions of items with multiple threads at the same time and it happens way less than 1% of the time. In a real program, it might never happen.

Obviously if there is a race you have to go back and do that loop again, but in the case of a linked list, what does that cost you?

The downside is that you can't do very complex things to that linked list if you are going to use that method to add items to the head. Try implementing a double linked list. What a pain.

EDIT:

In the code above I use a macro CAS. If you are using linux, CAS = macro using __sync_bool_compare_and_swap. See gcc atomic builtins. If you are using windows, CAS = macro using something like InterlockedCompareExchange. Here is what an inline function in windows might look like:

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