ねののお庭。

かりかりもふもふ。

【C#】マルチスレッド関連操作の詳説。

この記事は Qiita C# Advent Calendar 2021 23日目の記事です。

この記事のお話の流れは、①マルチスレッドプログラミングで発生する問題、②それらの問題に対処するためのメモリバイアについて、③それらを踏まえてC#でのマルチスレッド関連操作について見ていく、という感じです。 メモリバリアを解説する際にC++がちょっと登場しますが、これはC#での動作を理解するのに非常に役立つからです。 コード自体は何も難しい事はないので安心してください。 マルチスレッドプログラミングそのものに起因する難しさはだいぶ分かりやすく解説したつもりです...!

注意 この記事は非常にレイヤーが低いお話をしています。 マルチスレッドであれこれやりたくなったら、基本的にlock statementやBCL(Task, Channel, SemaphoreSlim, ConcurrentDictionaryなどなど)を活用するか、System.Reactiveなどのライブラリの活用を考える事を強くお勧めします。

と、マルチスレッドプログラミング初心者がvolatileとか使って:;(∩´﹏`∩);:ってならないよう、予防線を張ってから本編に入ります。

マルチスレッドプログラミングにおける問題。

シングルスレッド前提では問題にならず、マルチスレッドを考慮すると発生する問題に最たるものがコンパイラによる最適化と原子性です。

原子性

原子性とは、それ以上分割不可能という事です。 原子性が保証されている場合とされていない場合で、どのような違いがあるかを簡単に以下のコードでみてみましょう。

uint a;

// thread 1
a = 0xffffffff;

// thread 2
var b = a;

C#では、uintの読み書きに関する原子性は保証されています。そのため a をthread1で書き換え、b を別のスレッドから読んでもデフォルトの 0 か、0xffffffff であることが保証されます。

もし書き込みが原子性を保証できなかった場合、aが途中まで書き込まれている最中にbがaを読んでしまい、0x0000ffffとか0xffff0000とかになってもおかしくありません。しかしC#の32bit以下のprimitive type(int, uint, float, byteなど)と参照型は原子性が保証されているため、このような事にはなりません。 一方Guid(128 bit)などのような大きめな構造体は原子性が保証されていないため、どこかのスレッドで書き換え途中の中途半端なデータを別のスレッドが読み取ってしまう、みたいなこともありえます。

コンパイラによる命令の並び替え

マルチスレッドプログラミングにおいて、困るタイプの最適化は幾つかありますが、最たるものが命令の並び替えです。

class C
{
    private bool _initialized;
    private int _value;

    // thread 1
    public void M1()
    {
        _value = 99;
        _initialized = true;
    }

    // thread 2
    public void M2()
    {
        if(_initialized)
        {
            Console.WriteLine(_value);
        }
        else
        {
            Console.WriteLine("not initialized");
        }
    }
}

上記のようなコードがあった場合、期待される出力は99もしくはnot initializedです。 しかし、M1()とM2()が別々のスレッドで動いている場合、0を出力してしまう可能性もあります。 これはコンパイラがM1を以下のように命令の順序を変えてしまうかもしれないからです。

// before compiling
public void M1()
{
    _value = 99;
    _initialized = true;
}

// After compiling
public void M1()
{
    _initialized = true;
    _value = 99;
}

命令の並び替え以外にも、以下のような問題も発生します。

var c = new C();

Task.Run(async () =>
{
    await Task.Delay(TimeSpan.FromSeconds(5));
    c.Finished = true;
});

while (!c.Finished)
{
    // do something
}

class C
{
    // volatile キーワードをつければ意図通り動く。
    public bool Finished;
}

これはReleaseでビルドすると簡単に再現できますが、終了しなくなります。 while(!c.Finished)は別のスレッドでFinishedが変更されたという事が見えないからです。

似たようなのでwhile(flag)while(true)に最適化されて終了しない、とかもあります。

このように、コンパイラのシングルスレッドを前提にした最適化は、マルチスレッドを前提としたコードでは様々な問題を引き起こします。 そのため、最適化するな、命令の順序を変更するな、といった事をプログラマは明示して正しく動作するようにしなければいけません。

メモリバリアについて

上記の問題に対して、C#上でどのような操作を行い、どのように解決するかを理解するためには、まずメモリバリアについて理解しなければなりません。 メモリバリアについて分かりやすく理解するため、C++にちょっぴり登場していただます。

C++にはどのようなメモリバリアを張るか指定するためのメモリ順序に関するの定義があります。 (ちなみにC#でも似たようなメモリ順序に関するAPI作ろうゼみたいのは一時期ありましたが、没となったようです)

typedef enum memory_order {
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst
} memory_order;

この記事においては、acquire, release, sequential consistency(seq_cst)さえ分かってれば十分なのでこれらについて説明します。

acquire / release

acquireとreleaseは実質ペアで、読み込みをするときにはacquire、書き込みをする時にはreleaseを使います。 簡単な使い方は以下の通り。

// C++ではプリミティブ型も原子性が保証されません。
// 原子性を保証するためにはstd::atomic<T>を使う必要があります。
std::atomic atomic_value(0);

atomic_value.store(99, std::memory_order_release);

int result = atomic_value.load(std::memory_order_acquire);

まずacquire/releaseバリアがそれぞれ何を保証してくれるのかですが、

  • acquireバリアは、バリアより下にあるメモリ操作命令が、(最適化等で)バリアの上に順序が変更される事はないという保証をしてくれる。
  • releaseバリアは、releaseバリアより上にあるメモリ操作命令が、(最適化等で)バリアの下に順序が変更される事はないという保証をしてくれる。

図にすると分かりやすいです。

f:id:nenoNaninu:20211223000039p:plainf:id:nenoNaninu:20211223000036p:plain

一見この保証は何が嬉しいねん、という感じですが、もちろん嬉しい事はあります。 例えば次のコードを見てみましょう。

std::atomic atomic_value(0);
int value;

// thread 1
value = 7;
atomic_value.store(99, std::memory_order_release);

// thread2
int load_value = atomic_value.load(std::memory_order_acquire);
if(load_value == 99)
{
    // load_valueが99なら、load_valueより先に書き込みが済まされているvalueは7だよね、という事をプログラマは期待する。
    std::cout << value << std::endl;
}
else
{
    std::cout << "load_value is not 99." << std::endl;
}

このコードの出力は常に7もしくはload_value is not 99.のどちらかである事が保証されます

もし、acquire/releaseバリアが本来保証してくれる事を保証してくれなかった場合の事をちょっと考えてみましょう。

まず、もしreleaseバリアが順序の変更を許してしまった場合を考えてみましょう。 つまりコード的には以下のようになってしまった場合です。

// releaseバリアは本来このような順序の変更は起こらない事に注意してください。

// コンパイル前
value = 7;
atomic_value.store(99, std::memory_order_release);

// コンパイル後
// なんども言いますが、releaseバリアではこのような事は本来起きません。ifですよ!
atomic_value.store(99, std::memory_order_release);
value = 7;

このような変更が起きてしまった場合、thread 2上ではload_valueが99でも、valueが7とは限らないため、予期していない出力が得られる可能性があります。

次に、もしacquireバリアが順序の変更を許してしまった場合の事を考えてみましょう。

// acquireバリアは本来このような順序の変更は起こらない事に注意してください。

// コンパイル前
int load_value = atomic_value.load(std::memory_order_acquire);
if(load_value == 99)
{
    std::cout << value << std::endl;
}
else
{
    std::cout << "load_value is not 99." << std::endl;
}

// コンパイル後に順序が変更されてしまったとする。
// 口酸っぱく言いますが、acquireバリアではこのような事は本来起きません。ifですよ!
int cache = value; // valueをatomic_valueより先に読み取ってしまう風に順序が変更されてしまった、とする。
int load_value = atomic_value.load(std::memory_order_acquire);
if(load_value == 99)
{
    std::cout << cache << std::endl;
}
else
{
    std::cout << "load_value is not 99." << std::endl;
}

thread 1でatomic_valueが99になっていても、valueに7が書き込まれたかは分かりませんし、もしatomic_valueが99になっていなかったとしてもvalueに0ではない何かが書き込まれている可能性もあります。

acquire/releaseバリアが保証してくれる内容が何故嬉しいか、お分かりいただけたでしょうか。 要するにacquire/releaseバリアを用いることで、別々のスレッドで動いているものであっても、前後関係(これをhappens before relationshipとか呼ぶ)を考慮してコードが書けるようになります。今回の例では、atomic_valueが99になっているなら、必ずvalueは7であるという事が保証されるため、その前提にたってコードを書くことが出来ます。

acquire / releaseの取り扱いづらさ

そんな有益そうに見えるacquire/releaseバリアですが、atomic変数に対する全ての書き込みに対して単一の全順序関係*1を提供してはくれません。 この単一の全順序関係を提供してはくれない事に起因する問題は、2スレッド以下であれば発生しませんが、それより多くのスレッドで動作している場合に悩ましい問題として現われます。 具体的にどういう事かというと、

std::atomic atomic0(0), atomic1(0);

// Thread 1
atomic0.store(99, std::memory_order_release);

// Thread 2
atomic1.store(99, std::memory_order_release);

// Thread 3
int t3_a0 = atomic0.load(std::memory_order_acquire);
int t3_a1 = atomic1.load(std::memory_order_acquire);

// Thread 4
int t4_a1 = atomic1.load(std::memory_order_acquire);
int t4_a0 = atomic0.load(std::memory_order_acquire);

上記のコードの出力がt3_a0 == 99, t3_a1 == 0だった場合、thread1でのタスクは完了しているが、thread2でのタスクは完了していない、ということになります。 したがって先にthread2が完了していて、thread1が完了していない、という事はありえないように思えます。しかし実はありえて、t4_a0 == 0, t4_a1 == 99という出力が得られる場合があります。

この厄介な挙動から我々を解放してくれる、分かりやすいバリアの種類があります。 それがsequential consistencyです。

sequential consistency

このsequential consistencyはHow to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programsという論文で以下のように記述されたのが始まりのようです。

... the result of any execution is the same as if the operations of all the processors were executed in some sequential order, 
and the operations of each individual processor appear in this sequence in the order specified by its program. 
A multiprocessor satisfying this condition will be called sequentially consistent. 

噛み砕くと、普通のマルチスレッドプログラミングは並列で動いているわけですが、それがまるで直列で動いているかのように見える場合、これをsequential consistencyと呼称する、と書いてあります。日本語には逐次一貫性とか訳します。

上のacquire / releaseの取り扱いづらさの例では、 thread 3からはthread 1 -> thread 2のように動作しているように見えましたが、 thread 4からはthread 2 -> thread 1のように動作しているように見えてしまっていました。

一方で逐次一貫性が保証されるということは、thread 3からみた時thread 1 -> thread 2という順番で動いているなら、他のあらゆるthreadからみてもthread 1 -> thread 2と動作しているように見える、という保証がなされているという事です。 単一の全順序関係が提供されていると言えます。 素敵ですね。

非常に素敵ではありますが、acquire/releaseバリアに比べたら多少のコストはかかります(具体的には、x86であればreleaseがmovに対応するのに対して、seq_cstはxchgに対応)。 とはいえ、C++でさえもデフォルトではacquire/releaseバリアではなく、sequential consistencyを用いるようになっています。 それだけacquire/releaseバリアは扱いづらいという事です。

C#でのマルチスレッド関連操作

さて、知識の下準備も終わったので、本題のC#のお話に戻ります。 それぞれの操作が、なにを保証し、なにを保証しないのか、そして何に注意するべきか等を気にしながら見ていきます。

lock (statement)

書きやすさと安全面では最強です。 上記で説明したメモリモデルの複雑さなどから我々を完全に取り払ってくれます。

保証してくれる事

  • 命令の並び替えを防いでくれる事。
  • lock statement内で実行された書き込み等が、次のlock statement内で読み取る時に確実に最新になっている事。
  • ロックはかけたブロックは、ロックをかけた順序通りに実行される事。
    • thread 1 -> thread 2 -> thread 3の順番でロックがかけられたら、必ずthread 1 -> thread 2 -> thread 3の順番でロックが解放される。thread 1 -> thread 3 -> thread 2とかにはならない。

注意事項

ロック内で操作したオブジェクトを、ロックのかかってない場所で操作した場合、命令の並び替えが行われ、最新の値が取得できる保証もなくなるなどのメモリモデルの複雑さが噴き出します。

たとえば以下の例はM2()で_cの読み込み時にlockをしていませんが、これは危険です。

class C
{
    public void M()
    {
    }
}

class D
{
    private readonly object _lock = new();
    private C _c;

    // thread 1
    public void M1()
    {
        lock(_lock)
        {
            _c = new C();
        }
    }

    // thread 2
    public void M2()
    {
        // 必ずしも最新の_cが取得できるとは限らない。
        // 命令の並び替えも起きてしまうかもしれない。
        var c = _c;
        c.M();
    }
}

正しくはこうしましょう。

class D
{
    // 略

    // thread 2
    public void M2()
    {
        C c;
        lock(_lock)
        {
            // 必ず最新の_cが取得できる。
            // 命令の並び替えなども防がれる。
            c = _c;
        }
        c.M();
    }
}

パフォーマンスが~という声が聞こえてこなくもないですが、現代のCPUでは1lockあたり9nsec程度のコストです。確かにこれは後述するVolatile等の操作に比べれば高コストですが、アプリケーションレイヤーであれば余計なBCLのAPI呼び出し1つ削れば稼げる程度のコストだったりするので、そんなに嫌がらなくてもいいんじゃないでしょうか。 スピード狂でもない限り。

volatile (keyword)

volatile (keyword)が付与されたメンバの読み書きは、acquire/releaseバリアに対応します。 基本的に32bit以下の値型、もしくは参照型のメンバにしかこのキーワードは使えません。

class C
{
    public volatile bool Finished;
    // public volatile Guid Guid; とかは出来ない。
}

保証してくれる事

  • acquire/releaseバリアと同じ方法で、命令の順序変更を防ぐ事。
    • volatile read 命令は、volatile read 命令の後に記述されているメモリ操作命令の前に実行される事。
    • volatile write 命令は、volatile write 命令の前に記述されているメモリ操作命令の後に実行される事。
  • すべてのスレッドが、他のスレッドで実行されたvolatile writeを順序通りに観測する事。
    • ここでの"順序通り"とは、ある一つのスレッドの中で実行された複数のvolatile writeを実行順序通りに、という意味。別々のスレッドでの複数のvolatile writeの順序は単一ではない。

保証されない事

  • volatile writeについて、単一の全順序関係を提供する事は保証されていない。
  • マルチプロセッサシステムでは、最新の値が取得できる事を保証しない。また書き込みも即座に他のプロセッサから見える事は保証しない。

C#のECMAの仕様書に記述されている事を以下に載せておきます。(一応載せてるだけなので読み飛ばしてOKです)

15.5.4 Volatile fields

When a field-declaration includes a volatile modifier, the fields introduced by that declaration are volatile fields. 
For non-volatile fields, optimization techniques that reorder instructions can lead to unexpected and unpredictable results in multi-threaded programs that access fields without synchronization such as that provided by the lock-statement (§13.13).
These optimizations can be performed by the compiler, by the run-time system, or by hardware.
For volatile fields, such reordering optimizations are restricted:

• A read of a volatile field is called a volatile read.
  A volatile read has “acquire semantics”; that is, it is guaranteed to occur prior to any references to memory that occur after it in the instruction sequence.

• A write of a volatile field is called a volatile write.
  A volatile write has “release semantics”; that is, it is guaranteed to happen after any memory references prior to the write instruction in the instruction sequence.

These restrictions ensure that all threads will observe volatile writes performed by any other thread in the order in which they were performed.
A conforming implementation is not required to provide a single total ordering of volatile writes as seen from all threads of execution.
The type of a volatile field shall be one of the following:

• A reference-type.
• A type-parameter that is known to be a reference type (§15.2.5).
• The type byte, sbyte, short, ushort, int, uint, char, float, bool, System.IntPtr, or System.UIntPtr.
• An enum-type having an enum base type of byte, sbyte, short, ushort, int, or uint.

Volatile (class)

Volatile (class)を通した読み書きも、acquire/releaseバリアに対応します。 volatile (keyword)では32bitより大きいプリミティブ型(long等)や、配列などには使えませんでしたが、Volatile (class) ではそれらを扱えます。 volatile (keyword)よりVolatile (class)の方がだいぶ後発かつkeywordの範囲を全てカバーしているのと、後述する理由からvolatile (keyword)よりVolatile (class)を利用した方が良いかと思います。

class C
{
    // volatile int[] _array; とかは出来ない。
    private int[] _array = Array.Empty<int>();

    public int[] M1()
    {
        return Volatile.Read(ref _array);
    }

    public void M2(int[] array)
    {
        Volatile.Write(ref _array, array);
    }
}

保証してくれる事

  • acquire/releaseバリアと同じ方法で、命令の順序変更を防ぐ事。
    • Volatile.Read()より下に記述されてるメモリ操作命令が、Volatile.Read()より先に実行されない事。
    • Volatile.Write()より上に記述されてるメモリ操作命令が、Volatile.Write()より後に行われない事。
  • ユニプロセッサシステムでは、Volatileを経由したread/writeはメモリを通して行われ、CPUのレジスタなどにキャッシュされない事。
    • つまり、Volatile.Read/Writeを通して同期がとれる。

保証してくれない事

  • マルチプロセッサシステムでは、最新の値が取得できる事を保証しない。また書き込みも即座に他のプロセッサから見える事は保証しない。

注意事項 Volatile.Read/Write経由でメモリアクセスした場合、当然ながら影響を受けるのはメソッドを呼び出した箇所だけ。フィールド全体で同期を撮りたい場合は、全てのメモリアクセスでVolatile.Read/Writeを経由しなければいけません。

個人的にはVolatile.Read()を使う場合でも、書き込みにはVolatile.Write()ではなく、後述のInterlocked.CompareExchange()等を使う事をお勧めします。 なのでvolatile (keyword)よりVolatile (class)を、となります。

class C
{
    private int[] _array = Array.Empty<int>();

    void M(int value)
    {
        while (true)
        {
            int[] current = Volatile.Read(ref _array);

            int[] next= new int[current.Length + 1];
            Array.Copy(current, 0, next, 0, current.Length);
            next[current.Length] = value;

            if (Interlocked.CompareExchange(ref _array, next, current) == current)
            {
                // 他のスレッドで_arrayが書き換えられてなかったら、break;
                // 他のスレッドで_arrayが書き換えられていたら、Volatile.Read()からやり直し。
                // Volatile.Write()だとVolatile.Read()した後に他のスレッドで_arrayが書き換えられた場合を考慮できない。
                break;
            }
        }
    }
}

Interlocked (class)

Interlockedでの操作はsequential consistencyに対応します。 このクラスはread/writeだけではなく、incrementとかcompare exchange(比較して等しかったら交換)をアトミックに行う事等も出来ます。

var c = new C[] { new() };

// Interlockedに単純なreadはないけれど、以下みたいな感じで同等の事が出来る。
var old2 = Interlocked.CompareExchange(ref c, null, null);

// WriteはExchangeで
var ol3 = Interlocked.Exchange(ref c, Array.Empty<C>());

// Interlockedは64bitのデータも取り扱う。
long value = 99;

// アトミックにインクリメントとかも出来る。
var hundred = Interlocked.Increment(ref value);

class C
{
}

保証してくれる事

  • 逐次一貫性
  • 原子性

Interlockedはvolatileと比べたらだいぶ扱いやすい子です。

Common Language Infrastructure (CLI)における volatile read/write の仕様

おまけ程度にですが、ECMAのCLIの仕様書のVolatileに関する項目を見てみましょう。

I.12.6.7 Volatile reads and writes

The volatile. prefix on certain instructions shall guarantee cross-thread memory ordering rules. 
They do not provide atomicity, other than that guaranteed by the specification of §I.12.6.6.

A volatile read has “acquire semantics” meaning that the read is guaranteed to occur prior to any references to memory that occur after the read instruction in the CIL instruction sequence. 
A volatile write has “release semantics” meaning that the write is guaranteed to happen after any memory references prior to the write instruction in the CIL instruction sequence.

A conforming implementation of the CLI shall guarantee this semantics of volatile operations.
This ensures that all threads will observe volatile writes performed by any other thread in the order they were performed.  
(すべてのスレッドが他のスレッドが実行したvolatile writeを、実行された順に観察することを保証します。)
But a conforming implementation is not required to provide a single total ordering of volatile writes as seen from all threads of execution. 
(しかし、仕様に準拠した実装では全ての実行スレッドに対して、volatile writeの単一の全順序を提供する事は求められていません。)

An optimizing compiler that converts CIL to native code shall not remove any volatile operation, nor shall it coalesce multiple volatile operations into a single operation. 

C#のvolatile keyword とほぼ同じことが書かれていました。

まとめ

マルチスレッド関連の比較的プリミティブに近いところについて詳しく解説しました。 上記で記述した操作以外(たとえばTask.Run()等)でも、並び替えを暗黙的に防いでくれるようですが、正確なドキュメントや仕様が見つからなかったので言及は避けておきます。

恐らくacquire/releaseバリアを意識してVolatileを使った何かを書くことは滅多にないと思いますが、がっつり最適化されているOSS等を読む際には役に立つのではないでしょうか。

References

*1:全順序関係は完全律、反対称律、推移律を満たす二項関係。ここでは全ての書き込みを元とした集合で、全ての元が(時系列順に)比較可能な関係、くらいの認識で十分。