以下の内容はhttps://blog.neno.dev/entry/2021/12/23/124215より取得しました。

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

.NET .NET Core 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# の 32 bit 以下の 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 バリアより上にあるメモリ操作命令が、(最適化等で) バリアの下に順序が変更される事はないという保証をしてくれる。

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

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

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 だった場合、thread 1 でのタスクは完了しているが、thread 2 でのタスクは完了していない、ということになります。 したがって先に thread 2 が完了していて、thread 1 が完了していない、という事はありえないように思えます。しかし実はありえて、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 では 1 lock あたり 9 nsec 程度のコストです。確かにこれは後述する Volatile 等の操作に比べれば高コストですが、アプリケーションレイヤーであれば余計な BCL の API 呼び出し 1 つ削れば稼げる程度のコストだったりするので、そんなに嫌がらなくてもいいんじゃないでしょうか。 スピード狂でもない限り。

volatile (keyword)

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

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) では 32 bit より大きいプリミティブ型 (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:全順序関係は完全律、反対称律、推移律を満たす二項関係。ここでは全ての書き込みを元とした集合で、全ての元が (時系列順に) 比較可能な関係、くらいの認識で十分。



以上の内容はhttps://blog.neno.dev/entry/2021/12/23/124215より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14