8

これは面接の質問です、面接は行われました。

mutex、semorphore、spinLock、futexを使用せずにスレッドを同期させる方法は？

5つのスレッドがある場合、そのうちの4つを同じポイントで左側のスレッドからのシグナルを待機させるにはどうすればよいですか？これは、すべてのスレッド（1、2、3、4）がスレッド機能のあるポイントで実行されると、スレッド5からのシグナルが送信されるのを停止して待機することを意味します。そうでない場合、スレッドは続行しません。

私の考え：

グローバルbool変数をフラグとして使用します。スレッド5がそれをtrueに設定しない場合、他のすべてのスレッドは1つのポイントで待機し、フラグ変数もtrueに設定します。スレッド5は、すべてのスレッドのフラグ変数がtrueであることを検出すると、フラグvartrueを設定します。

ビジーウェイトです。

より良いアイデアはありますか？

ありがとう

 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、コンペアアンドスワップを使用して、ウェイターのリストの先頭にスレッドを挿入します。ヘッド=-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アトミックビルトインを参照してください。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

これは、SSE3MONITORと、および組み込み関数MWAITを介して利用できる命令を使用して行うことができます。Intelには、ここに記事があります。（memory-monitor-wait for lock競合を使用するための特許もありますが、これは興味深いかもしれません）。_mm_mwait_mm_monitor

于 2012-05-27T08:59:52.077 に答える
1
  1. 使用する信号、たとえばSIGUSR1を選択します。
  2. pthread_sigmaskを使用してSIGUSR1をブロックします。
  3. スレッドを作成します（シグナルマスクを継承するため、最初に1を実行する必要があります！）
  4. スレッド1〜4はsigwaitを呼び出し、SIGUSR1が受信されるまでブロックします。
  5. スレッド5は、SIGUSR1を使用してkill（）またはpthread_killを4回呼び出します。POSIXは、シグナルがシグナルをブロックしていないスレッドに配信されることを指定しているため、sigwait（）で待機しているスレッドの1つに配信されます。したがって、関連する同期を使用して、どのスレッドがすでにシグナルを受信し、どのスレッドが受信していないかを追跡する必要はありません。
于 2012-05-27T08:18:35.600 に答える
1

ピーターソンのアルゴリズムまたはデッカーのアルゴリズムを探していると思います

共有メモリのみに基づいてスレッドを同期しました

于 2012-05-28T03:05:51.913 に答える