Zenn
📚

Rust Atomics and Locksの紹介とAtomicを自分なりに整理する

2022/12/21に公開
Rust
tech

はじめに

Rust Atomics and Locksという本が素晴らしかったので、この記事ではその本の紹介と、Atomicに関する私なりの理解を記述していこうと思います。

Rust Atomics and Locksについて

この本はRustの並行処理関連の機能(Scoped Threads, Atomics, 内部可変性, 排他参照と共有参照, SendとSync, Lock, Thread Parking等)を紹介したあと、それらの機能を使ってSpin Lock, Channel, Arc, Mutex, Condition Variable, RWLockなどをstep by stepで作っていくという構成になっています。なのでこの本を読むとArcやMutexなどがRustでどうやって実装されているのかなんとなく分かるようになります。私はこの本を読むまではRustの並行処理よく分かっていないなあと感じていたのですが、この本を呼んでRustの並行処理についてチョット分かるようになりました。

並行処理は当然、OSやハードウェアも密接に関係しています。そのため、LinuxのfutexなどのOSレベルの話題や、x86-64やARMプロセッサーのMemory Orderingのようなハードウェアレベルの知識も簡単に紹介されていました。

Atomics

本の紹介だけだと味気ないので、この記事では加えて本の題名にもなっているAtomicについて私なりの理解を記述していきます。

Atomicは分割できないという意味で、Atomic変数に対する操作はそれが完了したか、行われていないかのどちらかです。途中の状態を観測することはできません。

Rustでスレッド間で値を共有する最もプリミティブな機能がAtomic変数です。Atomic変数はMutexや条件変数のようなすべての並行処理プリミティブの実装で使われています。ということで、RustのMutexや条件変数がどのように実装されているかをキチンと理解するためにはAtomic変数に関する理解が必要になります。

Memory Ordering

Atomic操作を理解するためには、Memory Orderingを理解する必要があります。Memory Orderingは操作の順序に対する保証の強さを表現します。

「操作の順序って言っても、a(); b();って書いてあったらa()が実行されてそのあとにb()が実行されるでしょ？保証の強さもなにもなくない？」と思われるかもしれません。はい、スレッド内の順序は確かにそうなのですが、スレッド間の操作の順序となると話は変わってきます。

本で紹介されていた例で私が驚いたものを紹介します。

use std::{
    sync::atomic::{AtomicI32, Ordering::Relaxed},
    thread,
};

static X: AtomicI32 = AtomicI32::new(0);
static Y: AtomicI32 = AtomicI32::new(0);

fn a() {
    X.store(10, Relaxed); // (1)
    Y.store(20, Relaxed); // (2)
}

fn b() {
    let y = Y.load(Relaxed); // (3)
    let x = X.load(Relaxed); // (4)
    println!("{x} {y}");
}

fn main() {
    thread::scope(|s| {
        //スレッドを生成してaを呼ぶ
        s.spawn(|| {
            a();
        });
        //スレッドを生成してbを呼ぶ
        s.spawn(|| {
            b();
        });
    })
}

Relaxedという謎の値を無視すれば何をしているかはなんとなく分かると思います。さてこのプログラムを走らせるとどんな値がプリントされうるでしょうか？片方が実行される前にもう片方が終了すれば0 0または10 20になります。並行に実行されていれば10 0もありえます。ここまでは納得してもらえると思います。

私が驚いたのは0 20も有効な結果ということです。直感的にはbがYをloadしてその値が20だったら、もう一方のスレッドでXには10がすでにstoreされているはずだから、bのその後のXのloadは10を取得すると思いますよね？

0 20が有効な結果とされるのはMemory OrderがRelaxedだからです。Relaxed順序はスレッド間の操作にどんな順序付も保証しません。なので以下のようになります。

  • (3)が実行されたとき(2)との順序関係(happen-before関係)は保証されないので0または20になる
  • (4)が実行されたとき(1)との順序関係は保証されないので0または10になる

よって0　20は有効な結果となります。

有効な結果と言われても実際そんな値になることはありえないやろ。。と思われるかもしれません。ただこれは実際ありえて、なぜありえるかというと、ときにコンパイラやハードウェアはプログラムを効率的に実行するためにプログラムを変更したり命令を並び替えるからです。そしてこのMemroy Orderingというのはプログラムとコンパイラ・ハードウェアとの間の契約のようなもので、コンパイラ・ハードウェアは指定されたMemory Orderingの保証を満たす限りはプログラムの意味を変えない範囲で、命令を並び替えて良いということになります。

Atomic変数はスレッド間で共有できるのでスレッド内にとどまる変数と同じように最適化することはできません。よりよい最適化を実現するためAtomic変数への操作に関してはプログラマが順序関係の保証の強さを明示的に指定します。順序関係に対する保証が弱ければより積極的な最適化を施せることになります。なのでRustのような性能を重視するプログラミング言語ではMemory Orderを指定できるようになっているのでしょう。

順序関係の保証の強さには種類があります。ここでは代表的な4つを紹介します。

Relaxed Ordering

Relaxedは一番弱い順序付でスレッド間の操作の順序付けの保証を一切もちません。ただし個々のアトム変数の総変更順序は保証されるようです。例えばあるアトミック変数A（初期値0)に対して、スレッドXが5を加算して、スレッドYが10を加算したとすると、Aの値の変遷は0->5->15または0->10->15となります。総変更順序が保証されるというのはもしあるスレッドがAの値10を観測したら、他のスレッドが5を観測することはありえないということです。

Release and Acquire Ordering

ReleaseとAcquireはペアで使われます。Releaseは書き込み、Acquireは読み込みに対して指定します。Acquire-load操作がRelease-store操作を観測すると、storeとその前のすべての操作とloadとそのあとすべての操作の間に順序関係が成立します。

RustのMutexはこのReleaseとAcquireが使われています。使われ方はおおざっぱに以下のような感じです。

lockという変数がlocked状態とunlocked状態を取るとします。スレッドAがlockを持っていたとして、unlocked状態にするためにRelease-storeで書き込みます。そしてスレッドBがロックをとるためにAcquire-loadを行い、もしunlocked状態であればアトミックにlocked状態にします。これはcompare_exchange命令で実現できます。そうすることでMutexをunlockedしたstore(スレッドA)と、それを読み取ったload(スレッドB)との間に順序関係(happen-before関係)を成立させることができます。つまり、unlockするまでにAでやっていたことは、lockの後で行うBのすべての操作の前に実行されることが保証されます。

Sequentially Consistent Ordering

SeqCstはもっとも強い順序です。これはRelease、Acquireの効果を持ち、さらにグローバルに一貫した操作の順序付を保証します。グローバルに一貫した操作の順序付を保証するとは、SeqCstを使った各々の操作はどのスレッドからもグローバルに一貫した順序で見えるということだと思います。

SeqCstはあるstoreが同じスレッドの後続のloadの前にグローバルに観察可能になって欲しい場合に使うことが多いらしいです。

fence

fenceという命令を用いることでatomic操作とMemory Orderingを分離させることができます。あるスレッドのfence(Release)の後のあるアトミック変数へのstoreを、別のスレッドのfence(Acquire)の前のloadが観測した場合、fence(Release)とfence(Acquire)の間で順序が成立します。

おわりに

AtomicのMemory Orderingに関して説明しましたが、「なんでこんなこと考えなくちゃいけないの？」と思われると思います。確かに私含む多くの人がMemory Orderingを理解する必要は薄いかもしれません。ただMutexやCondition VariableなどRustの並行処理プリミティブはMemory Orderingを意識して実装されています。さらに自分でRustの並行処理プリミティブを実装したい方にもMemory Orderingの知識は必要でしょう。なので、Rustの並行処理プリミティブがどう実装されているか興味のある方、自分で並行処理プリミティブを実装してみたい方はこの本を読むととても面白いのではないかと思います。

GitHubで編集を提案

Discussion