Zenn
🧰

マルチスレッド・プログラミングの道具箱

2020/09/28に公開
並行処理
並列処理
マルチスレッド
tech

まえがき

クラウド上の仮想サーバから手元のスマートフォンまで、いまや複数のCPUコアを搭載するマルチコアはどこにでもある環境になりました。ハードウェア側が並列(Parallel)・並行(Concurrent)処理に向けて急速に進化する一方で、ソフトウェア側つまりプログラミング言語の進化はさほど追い付いていません。並行処理記述の手軽さを求めた Go言語 や、マルチスレッド処理の安全性を重視する Rust言語 などが登場してはいるものの、「普通にプログラムを記述するだけで複数CPUコア環境で高速に走るプログラミング言語」は遠い夢物語のままです。

モダンなプログラミング言語や並列・並行処理ライブラリは、複雑で難解なマルチスレッド処理を直接記述しなくてすむよう、安全性・利便性の高い抽象化レイヤを提供します（例：Go言語のgoroutineとchannel、Rust言語の Rayonライブラリ）。しかしそれらの水面下では複数スレッドが動いていることに変わりはなく、性能チューニングや障害解析といった込み入った場面ではマルチスレッド・プログラミングの基礎知識はきっと役立つことでしょう。

本記事では、マルチスレッド・プログラミングのネジやクギに相当する基本的な構成部品について、特定のプログラミング言語や並列・並行処理ライブラリによらない概念的な説明をおこないます。

🧰基本の道具箱

複数のスレッドが協調動作してタスクを完遂するには、スレッド間での同期(Synchronization)制御が必要となります。このとき用いるマルチスレッド・プログラミングの基礎部品は、同期プリミティブ(Synchronization Primitive)とも呼ばれます。

モダンなプログラミング言語や言語や並列・並行処理ライブラリでは、安全で便利なスレッド間同期とデータ共有機構を提供します。例えばスレッドセーフなデータコンテナ、複数スレッド間で進行を揃えるバリア同期といった高レイヤな機構は、いずれも内部的には低レイヤな同期プリミティブを用いて実装されます。

マルチスレッド・プログラミングの基礎部品となる同期プリミティブと、関連する用語群をあわせて整理します。

  • セマフォ(Semaphore)
  • ミューテックス(Mutex)
  • 条件変数(Condition Variable)
  • アトミック変数(Atomic Variable)

🚦セマフォ(Semaphore)

セマフォ(Semaphore) は エドガー・ダイクストラ(Edsger W. Dijkstra) により考案された 最も原始的な同期プリミティブ であり、異なるスレッド間で共有される変数などの共有資源に対する 同時アクセス数を制限する機構 です。

セマフォは下記2種類に区分できますが、基本的な考え方はいずれも同じです。

  • カウンティングセマフォ(Counting Semaphore)
  • バイナリセマフォ(Binary Semaphore)

カウンティングセマフォ(Counting Semaphore)

単にセマフォに言及する場合、カウンティングセマフォ(Counting Semaphore) を指すことが一般的です。セマフォは概念的には 単一の数値カウンタとみなす ことができ、シンプルな2つの操作を提供します[1]［角括弧内は操作名[2]］。

  • カウンタ値に1加算してから待機中スレッドを起こす［V操作, Up, Signal, Post］
  • カウンタ値が0より大きくなるまで待機してからカウンタ値を1減算する［P操作, Down, Wait, Pend］

たったこれだけの原始的な同期プリミティブですが、セマフォとデータ構造の組み合わせにより多種多様なスレッド間同期やデータ共有機構を実現できます。つまりセマフォ以外のすべての同期プリミティブは、セマフォさえ提供される環境であればプログラマ自身でも実装可能なのです。

バイナリセマフォ(Binary Semaphore)

バイナリセマフォ(Binary Semaphore) はその名前通り二値状態、つまりセマフォが概念上もつ 数値カウンタは0または1のいずれかしか取らないと制限 した同期プリミティブです。その振る舞いはカウンティングセマフォに完全に包含されるため、バイナリセマフォが独立して提供される必然性はありません。それでもなおバイナリセマフォを提供するメリットは、二値状態しか取りえないという制約に基づいて設計不良や実装誤りを検知 できる可能性があるためです。

バイナリセマフォの動作は、セマフォという名前の由来でもある鉄道線路の 腕木式信号機 のアナロジーで解釈できます。線路上を走る電車がスレッド、信号機より先の線路区間が共有資源に対応します。青信号ならば電車は線路区間へ侵入可能＝1つのスレッドだけが共有資源にアクセスしてよく、赤信号ならば前の電車がいなくなるまで待機＝他スレッドは共有資源へのアクセス許可が出るまで待機します。ここではバイナリセマフォによって、複数スレッドから共有資源アクセスの相互排他(Mutual Exclusion)制御が実現されています。

スレッド間での排他制御は ミューテックス(Mutex) を用いても実現できます。カウンティングセマフォとバイナリセマフォの議論と同様に、共有資源へのアクセス相互排他が目的であれば その用途に特化したミューテックス利用が好ましい といえます。ミューテックスはバイナリセマフォにはない追加の概念をもつため、設計不良や実装誤りの検知可能性につながります。

🔓ミューテックス(Mutex)

ミューテックス(Mutex) は、複数スレッドから共有資源へのアクセス相互排他(MUTual EXclusion)制御を実現する機構です。ミューテックスの利用によって、あるタイミングにおいて共有資源へアクセス可能なスレッドがただ1つしか存在しないことを保証します。

ミューテックスにより相互排他制御される対象は、共有資源としての変数やデータ構造です。各スレッド上にて実行されるプログラムのコード区間ではありません。この2つは同じに聞こえるかもしれませんが、両者を明確に区別することは非常に重要です。マルチスレッド・プログラミングにおいては このミューテックスはどの共有資源を保護するのか を考えて設計すべきです（例：Rust言語の std::sync::Mutex は必ず保護対象のデータ構造と関連付く）。

ロック(Lock)

ミューテックスは二値状態 ロック(Lock)が所有されている／されていない のいずれかをとり、2つの基本操作を提供します。［角括弧内は操作名］

  • 他スレッドがロック所有権を解放するまで待機し、自スレッドがロック所有権を獲得する［Lock, Acquire］
  • 自スレッドが所有中のロックを解放し、同ミューテックスに対して待機中の他スレッドへ通知する［Unlock, Release］

バイナリセマフォとミューテックスとの差異は、この ロック所有権(Lock Ownership) という概念にあります。ミューテックスに対するロック解放操作では、該当スレッドがあらかじめ同ミューテックスのロックを所有している必要があります。つまりロック所有権という制約をあえて設けることで、同一スレッド上でのロック獲得／解放操作が1:1対応しないといった設計不良や実装誤りを検知 できる可能性があるのです。

バイナリセマフォをカウンタ値1で初期化し、待機＆カウンタ減算操作をロック獲得、カウンタ加算＆通知操作をロック解放とみなすこともできます。バイナリセマフォにはロック所有権の概念はないため、両操作をそれぞれ異なるスレッドから実行しても良いのです。これを自由度が高いというメリットに解釈できもしますが、一般にマルチスレッド・プログラミングにおいては 目的に適した制約を提供する同期プリミティブの利用を強く推奨 します。

クリティカルセクション(Critical Section)

クリティカルセクション(Critical Section) は、あるスレッドがミューテックスのロックを所有した状態で実行するコード区間を指します。クリティカルセクションを直訳すると "危険区域" または "きわどい領域" となり、排他制御を行わないと複数スレッドからのアクセスにより共有資源が壊れてしまうことに由来します。

クリティカルセクションはソースコード上に表現されているコード区間（レキシカル・スコープ）だけでなく、そのスレッドの実行パス上にある全てのコード区間（ダイナミック・スコープ）を指すことに留意してください。あるミューテックスのロックを所有したまま呼び出した関数のコード区間は、関数呼出元で開始したクリティカルセクションに包含されます。

適切な並列・並行処理設計の下では、クリティカルセクションの範囲を可能な限り狭くすべきです。ロックを所有したまま何らかの条件が満たされるまでスレッドを待機するといった設計は、明らかな設計不良の兆候といえます。特定条件を待機するようなケースでは、後述する 条件変数(Condition Variable) とミューテックスとを組合せて利用ください。

再帰ミューテックス(Recursive Mutex)

ミューテックスがもつ特性の1つに、同一ミューテックスのロック獲得操作を同一スレッドから複数回行えるか否かがあります。このような自己再帰的なロック獲得操作は 再入可能ロック(Reenterant Lock) と呼ばれ、同操作をサポートするミューテックスは 再帰ミューテックス(Recursive Mutex) と呼ばれます。

再帰ミューテックスはロック所有権の有無(0/1)ではなく、ロック獲得を行った回数つまりロックカウントで表現されます。ロックカウント0がロック非所有状態に、1以上がロック所有状態に対応します。これ以外は通常ミューテックスと同じ動作です。

別の見方をすると、通常ミューテックスは再帰ミューテックスのロックカウント最大値を1に制約したバージョンともいえます。既に何度も言及しているとおり、より制約された通常ミューテックスで十分なケースにおいて、再帰ミューテックスをむやみに使うべきではありません。

スピンロック・ミューテックス(Spinlock Mutex)

ミューテックスのロック獲得操作にて他スレッドが既にロックを所有していた場合、自スレッドはロック所有権を獲得できるまで待機します。このスレッドの待機方法に着目すると、一般的なミューテックスではスレッド自身を休眠(Sleep)してOSに制御を委ねますが、スピンロック・ミューテックス(Spinlock Mutex) ではスレッド実行を継続して ロック状態をひたすらループ監視する待機(Busy-loop, Spin) を行います。

スピンロック・ミューテックスのメリットとして、十分なCPUコア数が存在するならOSや言語ランタイムに制御を返す必要がなく、ロック獲得までの遅延時間を短縮できる可能性があります。一方のデメリットとして、待機処理でCPUコアを1つ占有することで他スレッドの実行機会を奪い、またCPUコア消費電力の増加にもつながります。

現実のCPU上では他プロセスに属するスレッドも多数同時実行されており、普通のアプリケーションプログラマが期待するようにロック獲得が行われるとは期待できません。スピンロック・ミューテックスを有効活用できるのは、OS本体やデバイスドライバ開発、組み込みソフトウェア開発といった特殊なケースに限られるでしょう。

公平ミューテックス(Fair Mutex)

ミューテックスのロック所有権が解放されたタイミングで、同ミューテックスに対して複数スレッドがロック獲得操作の待機状態にある状況が考えられます。この状況は ロック競合(Lock Contention) と呼ばれ、いずれか1つのスレッドはロック所有権を獲得できますが、他のスレッド群は再び待機状態へと戻されます。

一般的なミューテックスでは、待機中スレッドのうちどれがロック獲得できるかについて保証を与えません。複数のスレッドがロック獲得を競っている状態から、ランダムなスレッドが選出されてロック獲得されます。つまり先行してロック獲得要求を出したスレッドであっても、なかなかロック獲得できないという不公平(Unfair)な状況が発生し得ます。

公平ミューテックス(Fair Mutex) はこの不公平さを改善すべく、概念的には待機スレッドの待ち行列を内包したミューテックスといえます。公平ミューテックスでは先行してロック獲得要求を出したスレッドが、後続スレッドよりも先にロック獲得できることを保証します。

公平ミューテックスは望ましい性質ではあるものの、ロック獲得順の 公平性(Fairnesss)を実現するオーバーヘッドはそれなりに大きい ため、不公平な通常ミューテックスを利用した方が高い処理スループットを得られるケースもあります。対象プログラムの実行解析や動作性能計測を行ったうえで、本当に公平ミューテックスが必要とされる状況でのみ利用すべきです。

共有／排他ミューテックス(Shared-Exclusive Mutex)

通常のミューテックスは、共有資源としてのデータ構造にアクセス可能なスレッドがただ1つと保証する 排他ミューテックス(Exclusive Mutex) です。共有データ構造を 書換える(Write) 場合はこの排他保証が重要となりますが、読取り(Read) のみであれば複数スレッドが同時に共有データ構造を読取っても問題となりません。通常の排他ミューテックスでは読取りであっても他スレッド進行を妨害するため、少数の書込スレッド(Writer thread)と多数の読取スレッド(Reader threads)が存在する状況では全体の処理スループットが低下してしまいます。

共有／排他ミューテックス(Shared-Exclusive Mutex) は通常のミューテックスが提供する 排他ロック(Exclusive Lock) の獲得／解放操作に加えて、共有資源からの同時読み取りを実現するために 共有ロック(Shared Lock) の獲得／解放操作 を追加で提供します。そのユースケースに合わせて排他ロックを 書込ロック(Writer Lock)、共有ロックを 読取ロック(Reader Lock) とも呼びます。

共有／排他ミューテックスはその動作仕様が複雑であり、適切な利用が難しいミューテックスです。排他ロックと共有ロックを管理するオーバーヘッドも無視できないため、実際のプログラムに組込んで動作性能を計測したうえで利用を判断ください。

📬条件変数(Condition Variable)

ミューテックス(Mutex) は単純な共有資源アクセスの排他制御しか行えません。一方で典型的な並行・並列理設計では「共有資源としてのデータ構造が、特定の状態に変化するまで待機」したい状況がよくあります。例えば複数スレッド間でデータを安全に送受信する有限長のFIFO待ち行列データ構造を考えると、取出側は有効なデータが存在するまで待機、挿入側は空きができるまで待機する必要があります。

このような条件待機はミューテックスのみでは実現できないため、ナイーブに実装すると 非効率なビジーループ構造をとる 必要があります。条件変数(Condition Variable) は ミューテックスで保護されるデータ構造が、特定条件を満たすまで効率的に待機する機構 の実装を助ける同期プリミティブです。条件変数をそれ単体で使うことはできず、常にデータ構造を保護するミューテックスと関連付けて利用されます。

同期プリミティブとしての条件変数は、3つの基本操作を提供します。［角括弧内は操作名］

  • 関連付けられたミューテックスのロックを解放し、条件変数に通知があるまで待機し、再びロック獲得する［Wait］
  • 同じ条件変数に対して待機中のスレッド群のうち、ランダムな1スレッドに対して通知する［Notify, Signal］
  • 同じ条件変数に対して待機中の全スレッドに対して通知する［NotifyAll, Broadcast］

その名前に変数と付いていますが、一般的な変数とは異なり値や状態を保持しません。条件変数という同期プリミティブが提供する機能は2つ、自スレッドの待機／再開処理と待機中スレッドへの通知処理だけです。条件変数への通知処理はステートレス、つまり通知が行われたタイミングで待機状態にあるスレッドにしか作用しません。

並列・並行処理設計では、スレッド間の同期制御の道具として「セマフォ」または「ミューテックス＋条件変数」のいずれかを利用します。両者は本質的に等価な表現能力をもつため、先にあげた スレッドセーフな有限FIFO待ち行列データ構造 はどちらの同期プリミティブを使っても実装可能です。どちらを選ぶかは好みや慣れの問題もありますが、一般的にはミューテックス＋条件変数を用いた方が 設計不良を引き起こしにくい とされています。個人的にもミューテックス＋条件変数ベース設計の方が、セマフォを用いた設計よりも拡張性・保守性の面で優れるという考えです。

モニター(Monitor)

本記事の対象よりは高レイヤに位置づけられる同期プリミティブとして、 モニター(Monitor) を紹介します。モニターは、共有資源としてのデータ構造とそれに対する操作、セマフォやミューテックス＋条件変数といったデータ保護と待機／通知機構をひとまとめにした、スレッドセーフなオブジェクトです。

例えばJava言語はモニターによる同期制御を言語サポートしており、synchronized構文と ルートクラスjava.lang.Object のメソッド群wait, notify, notifyAllを組み合わると、任意のクラスをモニターとして実装できます。言い換えると、あらゆるJavaオブジェクトはミューテックス＋条件変数に相当する機能を内包していると解釈できます。

他にはC#言語の System.Threading.Monitorクラス、Ruby言語の Monitorクラス などがモニター実装をサポートする同期プリミティブです。いずれもミューテックスと条件変数の両機能をパッケージ化した同期プリミティブとなっています。

⚛️アトミック変数(Atomic Variable)

スレッド間で共有される通常の変数を安全に読み／書きするには、必ずセマフォ(Semaphore)やミューテックス(Mutex)による排他制御が必要となります。この原則を守らないと データ競合(Data Race) が発生し、そのマルチスレッド・プログラムの実行結果は何の保証も無くなります。一方で、プログラミング言語で定義する整数型といった単純な型の変数に対して、つど排他制御を行うのはオーバーヘッドが大きいケースもあります。この問題を解決する アトミック変数(Atomic Variable) は、複数スレッドから同時に読み／書きしてもデータ競合を起こさないと保証する変数です。アトミック変数という名前は、同変数に対する操作が不可分(Atomicity)であることに由来します。

アトミック変数では、4種類の操作を提供します。［角括弧内は操作名］

  • 現在の値の読取る［Read］
  • 新しい値を書込む［Write］
  • 現在の値を読取って、更新してから値を書込む［RMW, Read-Modify-Write］
  • 現在の値を読取って期待値と比較し、等しいときだけ新しい値を書込む［CAS, Compare-and-Swap］

読取-更新-書込(RMW)

読取-更新-書込(RMW; Read-Modify-Write)操作 は、アトミック変数に固有の操作です。値0をもつ通常の変数iに対してi += 1という更新操作を考えたとき、シングルスレッド実行後の値が1となることを疑う人は居ないでしょう。同様の処理をアトミック変数に対して行う場合は他スレッドからの同時操作を考慮する必要があり、RMW操作の不可分性が保証されなければ変数の値が1以外になることがあります。これは読取(Read)／書込(Write)操作それぞれが不可分性を保証していようとも起こりうる問題です。

比較-交換(CAS)

比較-交換(CAS; Compare-and-Swap)操作 はアトミック変数ならではの複雑な操作です。動作仕様を疑似コードで記述したものが下記になります。アトミック変数の真価は、このCAS操作にあるといっても過言ではないでしょう。

# CAS操作の疑似コード（一連の操作は不可分に行われる）
def CAS(atomic_var, expected, new_value):
    # Atomic変数の現在の値を読取る
    old_value = atomic_var.load()
    # 現在値(old_value)と期待値(expexted)が等しいときのみ
    # Atomic変数へ新しい値(new_value)を書込む
    if old_value == expected:
        atomic_var.store(new_value)
    # 操作結果として古い値(old_value)を返す
    return old_value

セマフォやミューテックス＋条件変数を用いる並列・並行処理アルゴリズムは全てブロッキング型、つまり一部のスレッド進行を休止させながら目的のタスクを遂行します。いちどスレッドを休止させると実行再開タイミングはOSや言語ランタイムのスレッド・スケジューラ依存となり、時間要求が非常にシビアなアプリケーションでは問題になります。アトミック変数のCAS操作を活用すると、ロックフリー(Lock-free)アルゴリズム のようにスレッド進行を止めずにタスクを遂行できるようになります。

ロックフリーアルゴリズムは個別にコンピュータサイエンス論文となるほど難解で複雑ですから、信頼できるライブラリとして提供されたものを利用すべきです。スレッド進行を止めずにタスクを遂行するために、その内部では非常に複雑な処理を行います。ロックを伴うブロッキング型の並列・並行処理アルゴリズムを使った方が、高い処理スループットを得られるケースもあります。ロックフリーアルゴリズム以外では問題が解決できないケースでのみ利用検討してください。

📑[PR]

本記事の内容に関心がある方向けの、他サイトでの投稿記事リストです。

脚注

  1. セマフォに対する追加の操作として、タイムアウト指定付きの待機や待機を伴わないカウンタ減算試行が提供される環境もあります。本記事の範囲ではこれらは本質的でないため言及しません。 ↩︎

  2. 考案者がオランダ語話者のため、V／P操作はオランダ語由来となります。教科書的には重要な操作名ですが、実践的には英語由来のSignal／WaitまたはPost／Waitだけで十分でしょう。 ↩︎

Discussion