multithreading - ロードおよびストアのxの値は何ですか

Question

これはいくつかの課題です

ロードとストアがアトミックであると想定されるシングルプロセッサシステムで、xがOに初期化されていると仮定して、次の実行で両方のスレッドが完了した後のxのすべての可能な値は何ですか？ヒント：このコードを機械語にコンパイルする方法を検討する必要があります。

for（int i = 0; i <5; i ++）：x = x + 1;

for（int j = 0; j <5; j ++）：x = x + 1;

Answer 1

質問の 2 行はそれぞれ、個別のスレッドを表すことを意図しています。共有変数xは保護されていないため、ほとんど何でも起こりえます。あなたが思いついた可能性は何ですか？（そうでなければ、あなたの問題に答えているだけのように感じるでしょう）

2 番目のヒント: C コンパイラに例を示してもらいましょう...

int x;

void f(void)
{
  int i;
  for (i = 0; i < 5; i++)  x = x + 1;
}

(これは C に翻訳されたプログラムです)

gcc -S -fno-PIC t.c 

（これは、読み取り可能なアセンブリを取得するためにマシンで入力する必要があるものです）

_f:
pushl   %ebp
movl    %esp, %ebp
subl    $24, %esp
movl    $0, -12(%ebp)
jmp L2
L3:
movl    _x, %eax
incl    %eax
movl    %eax, _x
leal    -12(%ebp), %eax
incl    (%eax)
L2:
cmpl    $4, -12(%ebp)
jle L3
leave
ret

最適化 (オプション -O2 をコンパイルに追加):

_f:
movl    _x, %eax
xorl    %edx, %edx
pushl   %ebp
movl    %esp, %ebp
.align 4,0x90
L2:
incl    %edx
incl    %eax
cmpl    $5, %edx
jne L2
movl    %eax, _x
leave
ret

Answer 2

ヒント: 考えられるすべてのシーケンスを考慮する必要はありません。最も極端なケースを考慮する必要があるだけです。x が取りうる最小値は? また、x の最大値はいくつですか?

最小のケースは、1 つのスレッドのロードがロードの後、他のスレッドのストアの前に常に発生する場合です。

最大のケースは、重複するロード - モディファイ - ストア シーケンスがない場合に発生します。

それはあなたが今それを解決するための十分なヒントになるはずです.

Answer 3

各スレッドには、5 セットの命令があります。

LOAD X
INCREMENT X
STORE X

各命令の後、CPU は実行を 2 つの別のスレッドに譲ることを選択できます。

• X の最高値は 10 です。これは、各スレッドが他のスレッドに譲らずに実行を終了したときに発生します。
• 私が見た最低値は 5 です。これは、最初のロード命令が両方のスレッドで発生し、次に一方が実行を終了し、次にもう一方が終了したときです。

Answer 4

まあ、ほとんどのまともなコンパイラはそれを最適化してx=10;

Answer 5

うーん、10.そうでなければ教えてください。