アトミック操作 の

アトミック操作について

1つの命令は、一見すると不可分な1つの動作に見えますが、実際にはそうではありません。 メモリ上の値に5を足す場合を考えてみましょう。

add qword [rel counter], 5

内部では、プロセッサにはメモリに直接足し算をする方法がありません。 プロセッサはこの1つの命令を、マイクロオペレーションと呼ばれる3つの小さなステップに分解します。

1. メモリから現在の値を読み出します。
2. レジスタ上でこの値に5を足して変更します。
3. 結果を書き戻します。

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

これは**読み出し・変更・書き戻し（RMW）**と呼ばれる一般的なパターンです。

読み出し（ロード）と書き込み（ストア）は別々の出来事なので、その間には時間の隙間があります。 通常はこれに気づきません。シングルコアでは、各命令が次の命令の前にその効果を完全に及ぼすことが保証されているからです。 そのためこの隙間は見えず、addは1つのまとまりとして振る舞います。

しかし、現代のCPUがシングルコアであることはまれで、アプリケーションはしばしば複数のコア上で、互いの順序付けもなく同時に動作します。 複数のコアがまったく同じ瞬間に動作していると、別のコアがこのコアのロードとストアの間の隙間でcounterを読み書きできます。 2つのスレッドがそれぞれ同じ古い値をロードし、それぞれ5を足し、それぞれの結果をストアします。 2回の加算が起きたのに、値は5しか増えていません。 一方の更新は黙って失われました。

これがデータ競合で、マルチスレッドコードでよくある問題です。

すべての値がこのように晒されるわけではありません。 各スレッドは自分のレジスタと自分のスタックを持っているので、レジスタに保持された値やスレッドのスタック上のローカル変数はそのスレッド専用で、競合しません。 上のcounterのように、スレッドが共有するメモリだけが保護を必要とします。

x86-64はこの問題を解決するために、命令を不可分にする命令群を提供しています。 それは、それを処理するコアにとってだけでなく、ほかのすべてのコアにとっても1つのまとまりとして振る舞います。 ばらけず、ほかのどのコアにも分割できない操作は、アトミックと呼ばれます。

アトミックな交換

xchg命令は2つのオペランドを交換します。 宛先オペランドはソースオペランドの以前の値と等しくなり、ソースオペランドは宛先オペランドの以前の値と等しくなります。 概念的には、2つのmov命令が同時に起きていると考えることができます。

いつもどおり、2つのレジスタオペランドと一緒にも、1つのメモリオペランドと1つのレジスタオペランドと一緒にも使えます。

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

メモリオペランドと一緒に使う場合、xchgは_常に_アトミックです。 プロセッサはその間、その場所にロックをかけます。これは次に説明する、lockプレフィックスがほかの命令に使うのと同じ仕組みです。

lockプレフィックス

x86-64で命令をアトミックにする最も一般的な方法は、lockプレフィックスを付けることです。 これにより、読み出しと変更と書き戻しが1つの不可分なステップに融合されます。 つまり、コアはその処理全体を通じてメモリを排他的に保持するので、ほかのどのコアもその途中でその場所を読み書きできません。

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lockは宛先がメモリである場合にだけ、そしてそのメモリを読み出し・変更・書き戻しする命令にだけ機能します。

1. add、sub、inc、dec、negのような算術演算
2. and、or、xor、notのようなビット演算
3. bts、btr、btcといったビット操作
4. 以下で説明するxaddやcmpxchgのような、その他の専用命令

素のmovのようなその他の命令では、このプレフィックスは無効で、プロセッサは無効オペコード例外を発生させます。 単独のロードや単独のストアにはプレフィックスは不要です。自然にアラインされたアクセスはそれ自体ですでにアトミックだからです。

アトミックなビット操作

ロックできる命令の中でも、ビットテストはこの文書の最後で扱うスピンロックと自然に組み合わせられます。 bts、btr、btcはそれぞれ、選んだ1つのビットをキャリーフラグにコピーしてから、そのビットをセット、クリア、または反転します。 lockプレフィックスを付けると、これは1ビットの読み出し・変更・書き戻しになります。ビットはアトミックに変更され、CFは変更前の値を報告します。

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

セットしようとしてそのビットがすでにセットされている場合、別のスレッドが先にそれを確保したということです。 これは、xchgがワード全体に対して行うフラグの確保を、1ビットで行う版です。

交換と加算

素のlock addはメモリを更新しますが、古い値は捨ててしまいます。 古い値こそがまさに欲しいものであることもよくあります。たとえば、各スレッドに別々のチケット番号を渡す場合です。

xadd命令（xはexchangeの意味）は、加算しつつ以前の値を返します。 合計を宛先に書き込み、元の宛先の値をソースレジスタに残します。

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

lockプレフィックスを付けると、これはアトミックなfetch-and-addになります。 同じカウンターに対して多数のスレッドから実行すると、呼び出しごとに異なる古い値が返ります。

lock addと同様、カウンターは呼び出し回数ちょうどの値になります。 しかし、lock addと違い、途中の値もすべて、呼び出し元ごとに1つずつ返されます。

ソースは任意の汎用レジスタでよく、オペランド幅はバイトからクアッドワードまでです。 負の値を足せば、同じ命令がfetch-and-subtractになります。

比較と交換

xaddは加算し、xchgは上書きしますが、どちらも新しい値を現在の値に依存させ、その下で何も変わっていない場合にだけ適用する、ということはできません。 その条件付きの更新を提供するのがcmpxchg（compare-and-exchange）であり、これらのプリミティブの中で最も汎用的です。

cmpxchg dest, srcはraxを暗黙のアキュムレータとして使い、それをdestと比較します。

• dest == raxなら、dest = srcとなり、ZF = 1です。
• dest != raxなら、rax = destとなり、ZF = 0です。

アキュムレータはオペランドサイズに従います。バイトならal、より広い形ならax、eax、raxです。

destは、以前にraxにロードされた期待値と等しいときにだけ更新されることに注意しましょう。 この等しさによって、destが新しい値の計算元となった値をまだ保持していることが保証されるので、古い読み出しに基づく更新が適用されることはありません。 これにより、cmpxchgはアトミックな更新の構成要素となります。これはcompare-and-swap（CAS）としても知られています。

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

このリトライループはロックフリー更新の核心です。 読み出しとcompare-and-exchangeの間の隙間こそ、別のスレッドが割り込む可能性のある瞬間であり、cmpxchgは古い読み出しから計算された値のストアを拒否することでそれを捉えます。

知っておく価値のある微妙な点が1つあります。 cmpxchgが確認するのは、値が読み出したものと等しいかどうかであり、その場所に一度も触れられなかったかどうかではありません。 もし別のスレッドが隙間の中で値をAからBへ、そしてAへと戻したなら、その下で世界が変わったにもかかわらず、交換は_それでも成功します_。

素のカウンターではこれは無害です。等しいカウントは同じように良いカウントだからです。 ロックフリーリストの先頭にあるメモリアドレスではそうはいきません。同じアドレスが今では別の場所を指しているかもしれないからです。 これがABA問題です。

この問題に対する通常の解決策は、値に何らかの「スタンプ」を組み合わせることです。たとえば、増える一方のカウンターです。 スタンプは進む一方なので、一致するスタンプは、その場所が見た目に変わっていないというだけでなく、途中で触れられなかったことを証明します。

しかし、これがマルチスレッド環境で機能するには、メモリアドレスとそのスタンプの両方を一緒に更新しなければなりません。 x86-64ではメモリアドレスは完全なクアッドワードなので、cmpxchgだけではそれと同時に別の値も更新するには足りません。

cmpxchg16bという倍幅の命令があり、意味的にはcmpxchgと同じですが、一度に16バイトを扱い、そういう状況で使えます。 ソースオペランドを持たず、代わりにrcx:rbxを置き換え値として使います。 唯一のオペランドは16バイトにアラインされたメモリ位置です。 この命令はまた、raxだけでなくrdx:raxをアキュムレータとして使います。

メモリの順序付け

ここまでの操作はすべて、1つの場所だけに触れてきました。 スレッドが複数の場所を通じて協調するとき、新しい疑問が現れます。あるスレッドの書き込みは、別のスレッドにどのような順序で見えるようになるのか、という疑問です。 この疑問に答える規則が、プロセッサのメモリ順序付けです。

branchless-codeのコンセプトでは、現代のコアが命令を1つずつ黙々とこなすわけではないという考えを紹介しました。 コアは多くの命令を同時に飛ばしておき、進めるところでは先へ進みます。 つまり、ある書き込みが、プログラムの示すより遅くほかのコアに見えるようになる一方で、そのあとの命令はすでに先へ進んでいることがあります。

x86-64は通常のロードとストアの間で強いメモリ順序付けを保つので、各コアでは次のようになります。

1. ロードが、あとのロードの後ろに並べ替えられることはありません。
2. ストアが、あとのストアの後ろに並べ替えられることはありません。
3. ロードが、あとのストアの後ろに並べ替えられることはありません。

唯一あり得る並べ替えは、_異なる_アドレスのあとのロードのあとに、ストアが完了したように見える場合です。

lockプレフィックス付きの命令、またはメモリオペランドを持つxchgは、完全なバリアです。どちらの向きにも、何かがそのバリアを越えて移動したようには見えません。 これが、ほとんどの状況で完全な順序付けを保証するのにそれらで十分な理由です。

唯一生き残る並べ替えの背後にある仕組みは、ストアバッファです。 先へ進み続けるために、コアは各ストアをそのバッファに置き、ストアがほかのコアに見えるメモリに届く前に、あとの命令を進めます。 したがって、書き込みのあとに異なる場所の読み出しが続くと、順序が入れ替わって見えることがあります。あとの読み出しが先へ進む間、書き込みはまだバッファに残っているかもしれません。 このモデル、つまり書き込みのあとの読み出しの隙間以外はすべて順序付けられるモデルは、total store orderと呼ばれます。

そのたった1つの隙間が、ストアしてから確認するハンドシェイクを壊すのに十分です。 2つのスレッドがそれぞれ自分のフラグを書き込んでから相手のフラグを読むと、どちらのストアもまだストアバッファを出ていないため、どちらの読み出しも未設定のまま返ってくることがあります。 mfence命令はストアバッファを空にすることでこの隙間を埋めます。それより前のすべての書き込みは、それよりあとのどの読み出しよりも先に見えるようになります。

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

より範囲の狭いバリアも2つあります。

• sfenceは書き込み同士の順序を定め、主にストリーミングのノンタイムポーラルストアで重要です。
• lfenceは読み出しの順序を定めます。

上の通常のアトミックなパターンでは、lockプレフィックス付きの命令がすでに完全な順序付けを備えているので、明示的なバリアが必要なのは、上のような素のストアとロードで組み立てたハンドシェイクだけです。

これらの保証には、x86を超えて通用する名前があります。 ある操作がacquire順序付けを持つとは、あとのアクセスがその前に移動したように見えない場合です。release順序付けを持つとは、前のアクセスがそのあとに移動したように見えない場合です。 x86では、すべてのロードがacquireであり、すべてのストアがreleaseであり、lockプレフィックス付きの命令、またはメモリを伴うxchgは、両方を同時に備えています。

スピンとpause

フラグをセットしつつ、その以前の状態も返す命令は、test-and-setとして知られています。 これらはスピンロックの基礎として使え、あるコアがコードの一部を排他的にアクセスできるようにします。

2値のフラグとともにxchg命令を使う、全体のアルゴリズムは次のとおりです。

1. フラグは0から始まります。
2. ロックを獲得するために、コアはフラグの値を1と交換します。
3. 返された値が1なら、そのロックは別のコアに_保持されている_ということです。現在のコアは待ってから、もう一度ロックの獲得を試みます。
4. 返された値が0なら、そのロックは空いていたということです。xchgはそれを1にセットしたので、ほかのコアはこのコアが解放するまで待ちます。
5. 現在のコアが作業を終えたら、フラグを0に更新することでロックを解放します。

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

待機ループの中のpause命令は、コードの計算内容を変えません。 これはプロセッサに、これがスピンウェイトであることを伝えるヒントです。 CPUはそうすることで、待機中のスレッドの消費電力を減らし、同じコアを共有する兄弟スレッドに譲ることができます。 pauseのないスピンループも依然として正しく、ただ無駄が多いだけです。

test-and-setでは、xchgのような命令は、フラグがすでにセットされていても常にそれをセットすることに注意しましょう。 つまり、ロックがまだ保持されている可能性が高いときでも、スピンするたびにメモリへの排他的アクセスを得てしまいます。

このアルゴリズムにはtest-and-test-and-setとして知られる変種があり、まずフラグをテスト（読み出し）して、すでにセットされているか確認します。 そして、ロックが空いているように見えたときにだけ、test-and-set（この場合はxchg）を試みます。

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

スレッドが作業を終えたら、movを使って0を素のストアで書き込むことでロックを解放できます。 mov以上のものは必要ありません。x86-64ではロードとストアが、あとのストアの後ろに並べ替えられることはないからです。 前にあるアクセスを追い越さないストアは、release順序付けを持つと言われ、x86ではすべての素のストアがそれを持っています。