パラレルプログラミングのマルチスレッドは非volatile変数を共有し、スレッドwhileのデッドサイクルを引き起こす可能性がありますか?

8725 ワード
C++ 並行
背景
スレッド間で変数を共有するにはvolatileキーワードが必要であることはよく知られています.しかし、volatileで識別しないと、スレッドがデッドサイクルになるのではないでしょうか.たとえば、次の疑似コードがあります.
static int flag = -1;
void thread1(){
  while(flag > 0){
    //wait or do something
  }
}
void thread2(){
  //do something
  flag = -1;
}

スレッド1、スレッド2は同時に実行され、スレッド2が終了した後、スレッド1はキャッシュなどの原因で、ずっとデッドサイクルになる可能性がありますか?
真実の世界
最初のピット:頼りないコーディネータ
直接コード:
#include 
#include 
#include 

static int vvv = 1;
void* thread1(void *){
	sleep(2);
	printf("sss
");
	vvv = -1;
	return NULL;
}
int main() {
	pthread_t t;
	int re = pthread_create(&t, NULL, &thread1, NULL);
	if(re < 0){
		perror("thread");
	}
	while(vvv > 0){
//		sleep(1);
	}
	return 0;
}

main関数でスレッドthread 1が起動し、thread 1はしばらく待ってからvvv=-1を変更し、vvv>0の場合、メインスレッドはwhileループで待機します.
理想的には、
メインスレッドデッドサイクル待機、2秒後にthread 1が「sss」を出力し、thread 1が終了し、メインスレッドが終了します.
thread-studyとして保存する.cファイル、直接gcc-O 3で最適化:
gcc thread-study.c -O3  -pthread -gstabs
再実行./a.outは、コンソールが「sss」を出力していることを発見した後、ずっと待っていて、CPUの使用率を確認して、1つのコアがいっぱいになって、メインスレッドがデッドサイクルしていることを示します.
上記のように、メインスレッドはキャッシュのため、読み込まれたvvv変数が古いため、デッドサイクルになっているようです.
でも本当にそうじゃないの?
試験により、O 0レベル(すなわち、完全に最適化されていない)の不死サイクルを除いて、O 1、O 2、O 3レベルは、いずれも死サイクルとなる.
O 3レベルのアセンブリコード(gcc-S thread-study.cで生成)を確認します.main関数セクションは次のとおりです.
表示を容易にするために、手動でコメントを付けました.
main:
.LFB56:
	.cfi_startproc
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	xorl	%ecx, %ecx
	xorl	%esi, %esi
	movl	$_Z7thread1Pv, %edx
	movq	%rsp, %rdi
	call	pthread_create                              //int re = pthread_create(&t, NULL, &thread1, NULL);
	testl	%eax, %eax
	js	.L9
.L4:
	movl	_ZL3vvv(%rip), %eax         //while(vvv > 0){
	testl	%eax, %eax
	jle	.L5
.L6:
	jmp	.L6
	.p2align 4,,10
	.p2align 3
.L5:
	xorl	%eax, %eax
	addq	$24, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 8
	ret
.L9:
	.cfi_restore_state
	movl	$.LC1, %edi
	call	perror                               //perror("thread");
	jmp	.L4
	.cfi_endproc

L 6の番号では、おかしいです.
.L6:jmp .L6
ここでは明らかにデッドサイクルであり、xxxの値を読み取る試みは全く行われていない.では、L 4の記号はどうなっていますか.L 4のコードは、vvv変数を読み出して判断する.しかし、なぜ循環していないのですか?
さらにgdbを使用してアセンブリからデバッグすると、プライマリスレッドは確かにデッドサイクルを実行していることがわかります.
   0x0000000000400609 :    mov    0x200a51(%rip),%eax        # 0x601060 <_zl3vvv>
   0x000000000040060f :    test   %eax,%eax
   0x0000000000400611 :    jle    0x400618 

=> 0x0000000000400613 :    jmp    0x400613 

   0x0000000000400615 :    nopl   (%rax)

一个jmp指令原地跳转，自然是一个死循环，正对应上面汇编代码的L6部分。

相当于生成了这样的代码：

	if(vvv > 0){
		goto return
	}
	for(;;){
	}

gccが生成したコードに問題があり、正しいアセンブリコードを生成していないことがわかります.この最適化は規範に合っているが、個人的には直感に深刻な最適化に反感を持っている.
では、私たちの問題はまだ解決されていません.次に、アセンブリコードを修正して、このように予想通りに動作させます.簡単にL 6のjmpをL 4にジャンプすれば:
.L4:
	movl	_ZL3vvv(%rip), %eax
	testl	%eax, %eax
	jle	.L5
.L6:
	jmp	.L4
	.p2align 4,,10
	.p2align 3
これは私たちが本当に予想していたコードです.
この修正後のコードをテストします.
gcc thread-study.s -o test -pthread -gstabs -O3
./test
実行2秒後、終了しました.
説明:プライマリ・スレッドは、古い共有変数の値まで読み込まれず、予想に合致しています.
volatileを加える
「vvv」変数にvolatileを追加します.
volatile static int vvv = 1;

再編成後、さらに走ってみると正常になり、2秒後にプロセスが終了した.
アセンブリコードを確認します.
.L5:
	movl	_ZL3vvv(%rip), %eax
	testl	%eax, %eax
	setg	%al
	testb	%al, %al
	jne	.L5
このアセンブリコードは、予想に合致します.
しかし、ここはまだ少し間違っています.volatileの特殊性はどこですか.生成されたアセンブリには特別な命令はありません.スレッドが共有変数をキャッシュしないことをどのように「防止」しますか?
ネット上ではvolatileキーワードを使った後、読み出しデータは必ずメモリから読み出すという説が流れています.
この言い方は正しいし、間違っている.volatileキーワードはプロセッサ最適化を防止するので,変数はレジスタに入れたり最適化されたりしない.しかしvolatileでは,CPUがCacheからデータを読み出すことを防止することはできない.
キャッシュとは何か
CPU内部にはレジスタがあり,各クラスCache,L 1,L 2,L 3がある.スレッド共有変数がCPUのレジスタまたは各クラスCacheに格納される場合について考えてみよう.
volatileは,プロセッサが変数をレジスタに格納することを阻止し,スレッド共有変数の読み出し,すなわち直接メモリアクセスを行う.
CPU Cache
CPU Cacheはまさにメモリのデータを入れて、像
movl _ZL3vvv(%rip), %eax
このような命令は,まずCPU Cacheから検索し,なければバスを介してメモリに読み出す.
一方,現代CPUにはマルチコアがあり,通常,各コアのL 1,L 2 Cacheは共有されず,L 3 Cacheは共有されている.
では問題は、スレッドAがCacheの内容を修正し、スレッドBがずっと古いデータを読み取っているかどうかということです.
MESIプロトコル
Cacheデータが一致しない以上、自然に一致を取り戻すメカニズムが必要です.古典的なCacheコンシステンシプロトコルはMESIプロトコルである.
MESIプロトコルは、Write Backポリシーを使用します.すなわち、1つのコア内のCacheが更新されると、自分のコア内部のみが変更され、他のコアに同期して変更されるわけではありません.
MESIプロトコルでは、Cache Lineの行ごとに4つのステータスがあります.
  • ModifiedこのCache Lineデータは修正され、メモリの中の不一致となり、データは本Cache Lineにのみ格納される.
  • ExclusiveこのCache Lineデータはメモリと一致し、データは本Cache Lineにのみ存在する.
  • SharedこのCache Lineデータはメモリと一致し、データは複数のCache Lineに存在し、いつでもInvalid状態になる.
  • InvalidこのCache Lineデータが無効(すなわち再使用しない)
    • MESIプロトコルでは,状態の転換は複雑であるが,いずれも人間の直感と一致している.私たちが研究している問題については、次のことを知る必要があります.
    Shared状態の場合、Cache Lineの内容を修正する前に、Request For Ownership(RFO)方式で他のコアにブロードキャストして通知し、Cache LineをInvalidにします.
    Modified状態の場合、Cacheコントローラは、Cache Lineに対応するメモリアドレスに対する他のアクセスをブロックし、現在のCache Lineを挿入したデータに応答します.本Cache Lineの内容をメモリに戻し、ステータスをSharedに変更します.
    したがって,一つの核内のCacheデータが修正され,もう一つの核が感知されない場合はない.
    つまり,スレッドAがCacheの内容を修正し,スレッドBが古いデータを読み込んでしまうことはない.CPU内部の通迅が速いことを考慮して、私はスレッドAが共有変数を修正したと推定して、スレッドBが新しい値を読み取る時間はナノ秒級以内であるべきです.
    もう一つのピット:CPU乱順実行
    現代では多くのCPUに乱順実行能力があり、volatileを加えて生成されたアセンブリコードから見ると、特別なところはありません.CPUの乱順実行にはどうしようもありません.例:
    volatile static int flag = -1;
void thread1(){
  ...
  jobA();
  flag = 1;
}
void thread2(){
  ...
  while(1){
    if(flag > 0)
      jobB();
  }
}

    この2つのスレッドに対してjobB()はjobA()よりも先に実行される可能性があります!
    thread 1では、CPUが乱順で実行される可能性があるので、flag=1を先に実行し、jobA()を実行します.
    では、どうやってこのような状況を防ぐのでしょうか.このトラブルはCPUが作り出したもので、当然CPUが提供する解決策でもある.
    GCCには、次のような原子間メモリアクセス機能が組み込まれています.
    http://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/Atomic-Builtins.html
    type __sync_fetch_and_add (type *ptr, type value, ...) type __sync_fetch_and_sub (type *ptr, type value, ...) type __sync_fetch_and_or (type *ptr, type value, ...) type __sync_fetch_and_and (type *ptr, type value, ...) type __sync_fetch_and_xor (type *ptr, type value, ...) type __sync_fetch_and_nand (type *ptr, type value, ...)
    これらの関数は実際にはmemory barrierを隠しています.
    たとえば、前に議論したコードにmemory barrierを追加します.
    	while(true){
		__sync_fetch_and_add(&vvv,0);
		if(vvv < 0 )
			break;
	}
    で生成されたアセンブリコードを確認します.
    .L4:
	lock addl	$0, _ZL3vvv(%rip)
	movl	_ZL3vvv(%rip), %eax
	shrl	$31, %eax
	testb	%al, %al
	je	.L5
	jmp	.L8
.L5:
	jmp	.L4
    には、lock addlの命令が1つ追加されていることがわかります.
    このlockは,実際には命令接頭辞であり,現在動作しているCache LineがExclusive状態であることを保証し,命令の順序性を保証している.この命令は、バスをロックすることによって実現される可能性があるが、バスがロックされている場合、接尾辞命令の時間しか消費されない.実際にJavaのvolatileは前にlock addコマンドを追加して実現しています.これは暇があればまた書きます.
    他のいくつかは
    volatileを使わないシーンもあります
    上記の議論を抜きにして、volatileを使用しないシーンもあります.例えば、このようなランダムにリソースを取得するコードは次のようになります.
    ramdonArray[10];
int pos = 0;
Resource getResource(){
  return ramdonArray[pos++%10];
}

    このようなコードposは非volatileであるが,マルチスレッド呼び出しgetResource()関数は全く問題ない.
    C 11とC++11
    なぜC 11とC++11はvolatileをjava/C#のような意味にアップグレードしないのですか?いわゆる「互換性」の問題かもしれないと思います.の卵が痛い
    C++11はAtomic関連の操作を提供し,意味はJavaのvolatileとあまり差がない.しかしC 11はまだ良い方法がなく、GCC内蔵関数を使ったり、似たようなアセンブリマクロを書いたりするしかないようです.
    http://en.cppreference.com/w/cpp/atomic
    GCC最適化のいくつかの東
    実際に議論されているコードの中で、whileサイクルにいくつかのコードがあれば、GCCは最適化できるかどうか分からないかもしれません.
    最適化されたもの:
    たとえば、ほとんどの言語(特にダイナミック言語)では、最初のコードは2番目のコードよりもずっと効率的です.
    //1
int len = array.length;
for(int i = 0; i < len; ++i){
}
//2
for(int i = 0; i < array.length; ++i){
}

    まとめ:
    最初の問題に戻ります:マルチスレッドは非volatile変数を共有し、スレッドwhileのデッドサイクルを引き起こす可能性がありますか?
    実はこのことは他のものの顔色を見なければならない.のコーディネータの、CPUの、言語規範の.
    プロセッサによって最適化されていないコードについては、CPUのCacheコンシステンシプロトコル(典型的なMESI)は、デッドサイクルが発生しないことを保証している.これはvolatileの功績ではなく、CPU内部の正常なメカニズムにすぎない.
    マルチスレッド同期プログラムでは、メモリバリア(memory barrier)を適切な場所に注意して追加します.
    参照先:
    http://en.wikipedia.org/wiki/Volatile_variable  
    http://en.wikipedia.org/wiki/MESI
    http://en.wikipedia.org/wiki/Write-back#WRITE-BACK
    http://en.wikipedia.org/wiki/Bus_snooping
    http://en.wikipedia.org/wiki/CPU_cache#Multi-level_caches
    http://blog.jobbole.com/36263/プログラマが知るべきCPUキャッシュ
    http://stackoverflow.com/questions/4232660/which-is-a-better-write-barrier-on-x86-lockaddl-or-xchgl
    http://stackoverflow.com/questions/8891067/what-does-the-lock-instruction-mean-in-x86-assembly
    http://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/Atomic-Builtins.html
    http://en.cppreference.com/w/cpp/atomic
    はじめてのC#アプリケーション
    c++いくつかの重要な問題