初日

アトミック操作

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プリフィックス

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など、後述するその他の専用命令

交換と加算

通常の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プリフィックスを付けると、これはアトミックなフェッチ・アンド・アッドになります。 同じカウンターに対して多くのスレッドから実行すると、呼び出しごとに異なる古い値が返ります。

lock addと同様、カウンターは最終的に呼び出し回数と正確に一致します。 ただし、lock addと違って、途中の値もすべて、呼び出した相手それぞれに1つずつ返されます。

比較と交換

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

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

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

destが更新されるのは、事前にraxにロードされた期待値と等しい場合だけであることに注意してください。 この等しさが保証するのは、destが新しい値の計算に使った値をまだ保持しているということであり、古い読み取りに基づく更新が適用されることはありません。 そのためcmpxchgは、**コンペア・アンド・スワップ（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

このリトライループが、ロックフリーな更新の核心です。 読み取りと比較・交換の間の隙間こそ、別のスレッドが割り込んでくるかもしれない瞬間であり、cmpxchgは古い読み取りから計算された値をストアすることを拒むことで、それに対処します。

メモリの順序付け

ここまでの操作はどれも、1つの場所だけを扱ってきました。 スレッドが複数の場所を介して協調するようになると、新しい疑問が生まれます。あるスレッドの書き込みは、ほかのスレッドからどのような順序で見えるようになるのでしょうか。 この疑問に答えるのが、プロセッサのメモリの順序付けです。

ブランチレスコードの演習では、現代のコアが命令を1つずつ黙々と処理するわけではないという考え方を学びました。 コアは多くの命令を同時に進行させ、可能なところでは先へ進んで実行します。 つまり、ある書き込みが、プログラムが示すタイミングより遅れてほかのコアから見えるようになる一方、その後の命令はすでに先へ進んでいることがあります。

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

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

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

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

スピンとpause

フラグを設定すると同時にその以前の状態も返す命令は、テスト・アンド・セットと呼ばれます。 これらはスピンロックの基礎として使うことができ、コアがコードのある部分を排他的にアクセスできるようにします。

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のないスピンループも正しく動作しますが、無駄が多いだけです。

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