c++ - C++ - Threads without coordinating mechanism like mutex_Lock

Question

I attended one interview two days back. The interviewed guy was good in C++, but not in multithreading. When he asked me to write a code for multithreading of two threads, where one thread prints 1,3,5,.. and the other prints 2,4,6,.. . But, the output should be 1,2,3,4,5,.... So, I gave the below code(sudo code)

mutex_Lock LOCK;
int  last=2;
int last_Value = 0;

void function_Thread_1()
{
      while(1)
      {
          mutex_Lock(&LOCK);
          if(last == 2)
          {
              cout << ++last_Value << endl;
              last = 1;
          }
          mutex_Unlock(&LOCK);
      }
}

void function_Thread_2()
{
      while(1)
      {
          mutex_Lock(&LOCK);
          if(last == 1)
          {
              cout << ++last_Value << endl;
              last = 2;
          }
          mutex_Unlock(&LOCK);
      }
}

After this, he said "these threads will work correctly even without those locks. Those locks will reduce the efficiency". My point was without the lock there will be a situation where one thread will check for(last == 1 or 2) at the same time the other thread will try to change the value to 2 or 1. So, My conclusion is that it will work without that lock, but that is not a correct/standard way. Now, I want to know who is correct and in which basis?

score 3 · Accepted Answer

インタビュアーはアトミック変数の使用を考えていたのではないかと思います。

std::atomic テンプレートの各インスタンス化と完全な特殊化は、atomic 型を定義します。アトミック型のオブジェクトは、データ競合のない唯一の C++ オブジェクトです。つまり、あるスレッドがアトミックオブジェクトに書き込み、別のスレッドが読み取りを行っている場合、動作は明確に定義されています。さらに、アトミックオブジェクトへのアクセスは、スレッド間の同期を確立し、非アトミックメモリアクセスを std::memory_order で指定された順序に並べることができます。

【ソース】

lastつまり、変更する必要があるのは、ロックを削除し、変数を次のように変更することだけですstd::atomic<int> last = 2;。int last = 2;

lastこれにより、変数に同時にアクセスしても安全になります。

好奇心から、あなたのコードを少し編集して、Windows マシンで実行しました。

#include <iostream>
#include <atomic>
#include <thread>
#include <Windows.h>

std::atomic<int>    last=2;
std::atomic<int>    last_Value = 0;
std::atomic<bool>   running = true;

void function_Thread_1()
{
      while(running)
      {
          if(last == 2)
          {
              last_Value = last_Value + 1;
              std::cout << last_Value << std::endl;
              last = 1;
          }
      }
}

void function_Thread_2()
{
      while(running)
      {
          if(last == 1)
          {
              last_Value = last_Value + 1;
              std::cout << last_Value << std::endl;
              last = 2;
          }
      }
}

int main() 
{
    std::thread a(function_Thread_1);
    std::thread b(function_Thread_2);

    while(last_Value != 6){}//we want to print 1 to 6

    running = false;//inform threads we are about to stop

    a.join();
    b.join();//join

    while(!GetAsyncKeyState('Q')){}//wait for 'Q' press
    return 0;
}

出力は常に次のとおりです。

Ideoneはこのコードの実行を拒否します (コンパイルエラー)。

編集：しかし、これは動作するLinuxバージョンです:)（おかげですぐに）

score 3 · Accepted Answer

ロックがなければ、2 つの関数を同時に実行すると未定義の動作になります。これは、アクセス時にデータ競合が発生しlast、last_Valueさらに (UB は発生しませんが) 印刷が予測不能になるためです。

ロックを使用すると、プログラムは本質的にシングルスレッドになり、単純なシングルスレッドコードよりもおそらく遅くなります。しかし、それは問題の性質上 (つまり、一連のイベントをシリアル化すること) にすぎません。

score 2 · Accepted Answer

インタビュアーは彼が何について話しているのか分かりません。ロックがないと、との両方lastで競合が発生しますlast_value。たとえば、コンパイラはへの代入を並べ替えてからをlast印刷およびインクリメントしlast_value、古いデータに対して別のスレッドが実行される可能性があります。さらに、インターリーブされた出力を得ることができます。つまり、改行で区切られていない 2 つの数値などです。

もう 1 つの問題として、コンパイラーがリロードしないこと、lastおよび (それほど重要ではありませんが)last_value各反復を決定する可能性があります。これは、いずれにせよ、これらの反復間で (安全に) 変更できないためです (データ競合は C++11 標準では違法であるため)。以前の規格では認められていません)。これは、インタビュアーによって提案されたコードが、実際には絶対に何もしないという無限ループを作成する可能性が高いことを意味します。

そのコードをミュートせずに正しくすることは可能ですが、適切な順序制約 ( if ステートメント内の割り当てlastとacquireロードに関するリリースセマンティクス) を伴うアトミック操作が絶対に必要です。last

もちろん、実行全体を効果的にシリアル化するため、ソリューションの効率は低下します。ただし、ランタイムはほぼ完全にロックを使用して内部的に同期されるストリームアウト操作内で費やされるため、ソリューションは効率を低下させることはありません。利用可能なリソースによっては、コード内でロックを待機する方が、ロックを待機するよりも実際には高速である場合があります (アトミックを使用する非ロックバージョンは、シングルコアマシンで実行すると完全に機能しなくなります)。

c++ - C++ - Threads without coordinating mechanism like mutex_Lock

3 に答える 3

Related

Reference