マルチスレッドプログラミングにおいては、プログラム1行1行の実行順序がプログラマの直感に反することがある。以下の例を見てみよう。スレッド1と2はそれぞれ別のスレッド (コア) で同時に実行される。またここでは、すべての変数は初期値をゼロとする。 xとyはメモリ上のあるアドレスを指す変数で、r1、r2はスレッドローカルな、レジスタのような領域を示していることにする。
# スレッド1
x = 1
y = 1
# スレッド2
r1 = y
r2 = x
この時、このプログラムの各行の実行順序は次のように考えられるだろう。
x = 1
y = 1
r1 = y // r1は1
r2 = x // r2は1
r1 = y // r1は0
r2 = x // r2は0
x = 1
y = 1
# パターン3.1
x = 1
r1 = y // r1は0
y = 1
r2 = x // r2は1
# パターン3.2
x = 1
r1 = y // r1は0
r2 = x // r2は1
y = 1
# パターン3.3
r1 = y // r1は0
x = 1
r2 = x // r2は1
y = 1
# パターン3.4
r1 = y // r1は0
x = 1
y = 1
r2 = x // r2は1
r1とr2の組み合わせは、パターン1のケースで {1, 1} 、パターン2のケースで {0, 0} 、パターン3のケースは複数の可能性があるがいずれも {0, 1} となることがわかる。
では、r1とr2が {1, 0} となることはあり得ないのだろうか？実は場合によっては、 {1, 0} になることがある。
上のいずれもケースも、スレッド1・2は、それぞれが自スレッド内での命令実行順を変えない (プログラムで指定された通りの順序で命令が実行される) ことを前提としていた。実はこの前提は必ずしも正しくない。なぜならこの前提は、プロセッサとコンパイラによる最適化を考慮していないためである。プロセッサとコンパイラは、最適化のために命令の順序を変えることがある。しかし、これではプログラマが困ってしまうので、「メモリ上に保存されたデータの可視性と一貫性について定められたルール」が設けられる。このルールのことを「メモリ一貫性モデル」あるいは単に「メモリモデル」などと呼ぶ。
すなわちメモリモデルには、プロセッサを話題とする「ハードウェア・メモリモデル」と、コンパイラを話題とする「ソフトウェア・メモリモデル」の2種類が存在する。筆者は個人的に、メモリモデルという言葉がこれらをあまり区別せず使われていることが、メモリモデルのわかりにくさの理由の一つではないかと考えている。
この記事では、メモリモデルの理解を獲得するために必要な一貫性に関する知識をまず解説し、その後ハードウェア及びソフトウェア、そしてGoのメモリモデルについて書いていく。
なにか間違いがあればTwitterまたはGitHub issueにフィードバックしてもらいたい。
JavaやC++、Goといった高級言語でマルチスレッドプログラミングを書く時、メモリモデルの知識は必ずしも必要ない。Goではチャネルやsync/atomic、あるいはsync.Mutexなどの仕組みが既に用意されているため、これらを適切に使えればプログラムはプログラマが普通に考える通り動作する。したがって、プログラマに必要な知識はメモリモデルのような低レイヤな話題ではなく、ライブラリの適切な使用方法や並列処理設計といった高レイヤな部分である。
The Go Memory Modelの冒頭には、次のようにある。
If you must read the rest of this document to understand the behavior of your program, you are being too clever.
Don’t be clever.
メモリモデルを理解している必要があるのは、OSカーネルや並行・並列処理ライブラリ、コンパイラなどの開発者である。マルチスレッドプログラミングを書く開発者は必ずしもメモリモデルを学ぶ必要はない。筆者がメモリモデルについて勉強してこのブログまで書いている理由は、単に興味があったからでしかないので、そういう前提でこれより下は読んでいただきたい。
まずはハードウェア・ソフトウェア関係なく、メモリモデルを理解するために必須な知識である「逐次一貫性」について。 逐次一貫性 (Sequential Consistency) とは並行システムにおける一貫性モデルのひとつである。これ自体は単なる一貫性モデルのひとつなので、メモリモデルやマルチスレッドプログラミングとは独立して理解可能である。これから「プロセッサ」や「スレッド」という言葉を使って逐次一貫性を説明するが、これはわかりやすさのためであって、一貫性モデル自体はプロセッサやOSのスレッドとは独立した概念であることに注意して欲しい。
逐次一貫性は、1979年のLeslie Lamportの論文「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.
Wikipediaでは以下のように訳されている。
「どのような実行結果も、すべてのプロセッサがある順序で逐次的に実行した結果と等しく、かつ、個々のプロセッサの処理順序がプログラムで指定された通りであること」
逐次一貫性は、各プロセッサ自身が自分で実行する命令の順序がプログラム上の順序と一致することを保証する。その上で、複数のプロセッサによる全体の実行順序は、逐次的に実行された「ある順序」と一致する。これは、各プロセッサが実行する命令はプロセッサごとに任意の順序にインターリーブされうることを意味する。以下の例を考えると、
# スレッド1
op_1()
op_2()
# スレッド2
op_3()
op_4()
スレッド1はop_1をop_2よりも前に実行すること と スレッド2はop_3をop_4の前に実行すること を逐次一貫性は保証する。しかし、op_3の実行がop_1より前か、op_1とop_2の間にインターリーブされるか、あるいはop_2の後かは保証されない。複数のプロセッサによる命令がどのようにインターリーブされても、それは「the result of any execution is the same as if the operations of all the processors were executed in some sequential order」のルールに違反しない。
これら逐次一貫性に関する挙動は特に、プログラマの直感に違反するものではないだろう。書いた通りの順序で実行されるが、マルチスレッドとなるとスレッド間では命令の順序は (当然のごとく) ひとつに定まらないよ、というだけのことである。これらはプログラマにとって自然であり、かつ理想的なモデルであると考えられている (本当にこれが理想的か？というのはまた別の話である) 。
さて、メモリモデルについてのポストにも関わらず逐次一貫性について説明しているのには理由がある。逐次一貫性は、前述したコンパイラとプロセッサによる最適化を目的とした命令の順序の入れ替えに大きく関連している。というのは、逐次一貫性を諦めることで、プロセッサ・コンパイラはプログラムの実行を高速化できるのである。 次章からは、プロセッサ及びコンパイラがそれぞれどのように命令の順序を変更するのか、それに対してどうメモリモデルが関係するのかを見ていく。
こういった一貫性モデルには多くの種類があるが、逐次一貫性は比較的強いモデルである (Strong consistencyと呼ばれる一貫性モデルのひとつである) 。例えば、weak consistencyに分類される、最近はマイクロサービスなどの文脈でよく言及される結果整合性という一貫性モデルがある。結果整合性が保証するのは「ある操作はいずれ見えるようになる (いつかは不明)」ということだけなので、一度見えた値が巻き戻ったり、あるプロセッサが施した操作がそれとは異なる順番で見えるようになったりすることがあり得る。言い方を変えれば、あり得ないことを特に保証していない一貫性モデルである。
まずはハードウェア、すなわちプロセッサにおけるメモリモデルから。 マルチプロセッサのシステムでは、あるコアによるメモリへのロードやストアが、ほかのコアから可視になる順序が、プログラムの順序と異なることが発生する。なお、この章はハードウェアについて話しているので、ここでいうプログラムとは高級言語ではなくアセンブリ (または機械語) を指している。
Latency Numbers Every Programmer Should Knowによれば、プロセッサのメインメモリ参照のレイテンシは、L1キャッシュ参照の200倍の時間がかかるらしい。プロセッサから見るとメモリアクセスは極めて時間がかかるので、メモリへのアクセスをなるべく不要にすることはプロセッサの設計において重要な観点である。各CPUベンダはこれを実現するために、キャッシュがどのように振る舞うかや命令の順序の入れ替えルールなどを設計した。しかし、メモリへのアクセスを減らそうとするとどうしても、あるプロセッサが他のプロセッサによる書き込みを確実に観測することが保証できなくなる。こういった各プロセッサに設計の違いが結果的に各プロセッサ固有のメモリモデルとなった。
メモリモデルの種類は、Wikipediaを見た感じは以下のようになっているがこれの網羅性は不明。
次に、実際のハードウェアメモリモデルについて、TSOとRMO/WMOを挙げて見ていく。ただし、これら以外にもメモリモデルの種類はある。
まずは、有名な (？) メモリモデルであるTSOから。TSOは「Total Store Order」のアクロニムである。TSOは順序変更が発生しにくい、いわゆる「強いメモリモデル」に分類される。 TSOを実装しているプロセッサの典型はx86であるが、SPARCやRISC-VもTSOをサポートしている。
TSOでは、メモリへストアする命令がメモリからロードする命令の後に順序変更されることがあり得る。それ以外の、「ロード命令がストア命令の後に順序変更」「ロード命令がロード命令の後に順序変更」「ストア命令がストア命令の後に順序変更」などは発生しない。
なぜストアがロードの後に順序変更されるのか？というと、例えば以下はx86、SPARC TSOのアーキテクチャ図である (A Tutorial Introduction to the ARM and POWER Relaxed Memory Modelsより図を引用) 。
このアーキテクチャのポイントは以下の通りである。
これでなぜストアがロードの後に順序変更されるのか？というと、次のように発生する。
上記のようなシーケンスでは、プロセッサの利用者にとってプロセッサBは古い値を読み込んでいるように見える。これが「ストアがロードの後に順序変更」の内部的な仕組みである。 これ以外の順序変更は発生しないことは詳しくは説明しないが、アーキテクチャ図を見ながら考えれば理解できると思う。
TSOは「ストアがロードの後に順序変更」以外発生しないという点で強いメモリモデルではあるが、逐次一貫性が保証するものをTSOが全て保証するわけではない。これは後ほど説明する。
WMOは「Weak Memory Order」、RMOは「Relaxed Memory Order」を意味するがいずれも「弱いメモリモデル」である。 これらはARMv7やIBM POWER、またSPARC RMOやRISC-V WMOでサポートされている。 下はARM、POWERのアーキテクチャ図である (A Tutorial Introduction to the ARM and POWER Relaxed Memory Modelsより図を引用) 。
以下のようなポイントがある。
TSOと比較するとかなり緩い、「これは何を保証しているんだ？」と思ってしまうようなメモリモデルに見えるが、これは実際のところ、ロード・ストアの順序は全く保証されない。
次に、これらのメモリモデルの違いが現実のプログラムにどう影響するのかを見ていく。
まず、一番上で見た以下のプログラムを再度考える。繰り返すが、今私達はハードウェア・メモリモデルの話をしているので、これらのプログラムは実際にはアセンブリまたは機械語で書かれていると考えて欲しい。
# スレッド1
x = 1
y = 1
# スレッド2
r1 = y
r2 = x
このプログラムの実行結果を、「Sequential Consistencyを保証するハードウェア」「TSOなハードウェア」「RMOなハードウェア」でそれぞれ比較すると、次のようになる。
| ハードウェア | {r1, r2}が{1, 0}になることはあり得るか？ |
|---|---|
| Sequential Consistency | No |
| TSO | No |
| RMO | Yes |
Sequential Consistencyなハードウェアにおいては、一番上で説明したように、いかなるインターリーブが発生しても{1, 0}にはならない。
TSOではどうか？TSOでも{1, 0}にはならない。TSOではストアがロードの後に順序変更されることはありえるが、このプログラムではスレッド1はストア -> ストアで、スレッド2はロード -> ロードなので、順序変更の影響を受けないためである。
RMOでは、{1, 0}が発生してしまう。RMOではロード・ストアは一切順序が保証されないので、例えば次のように実行されると結果は{1, 0}になる。
y = 1
r1 = y // r1は1
r2 = x // r2は0
x = 1
上記では、スレッド1のストアの順序が入れ替わっているので、結果が{1, 0}になることがありえてしまう。
TSOとSequential Consistencyなハードウェアの違いを考えるためには、次のようなプログラムが必要だ。
# スレッド1
x = 1
r1 = y
# スレッド2
y = 1
r2 = x
上記のプログラムを実行後、{r1, r2}が{0, 0}になることはあり得るかどうかを考える。
| ハードウェア | {r1, r2}が{0, 0}になることはあり得るか？ |
|---|---|
| Sequential Consistency | No |
| TSO | Yes |
| RMO | Yes |
Sequential Consistentなハードウェアでは{0, 0}は発生しない。インターリーブの結果がどうなるかを考えてみれば理解できると思う。 TSOで{0, 0}になるのは、次のようなケースである。
r1 = y
r2 = x
x = 1
y = 1
両方のスレッドにおいて、ストアがロードの後に並び替えられている。TSOでは「ストアがロードの後に順序変更」は発生しうるので、これはTSO的に問題のない順序変更であるが、この場合結果は{0, 0}になってしまう。このプログラムは、TSOは逐次一貫性を満たさないことを示している。 RMOはTSOよりも弱いので、TSOで発生する順序変更はRMOでも起こりうる。すなわち、RMOも同様に{0, 0}になることがあり得る。
どういった順序変更が発生しうるのかはプロセッサによって、あるいはプロセッサがサポートするメモリモデルによって異なる。 こういった順序変更は、メモリバリア (あるいはメモリフェンス) と呼ばれる命令を使うで明示的に禁止できる。例えば、上記で考えた次のプログラムについて、
# スレッド1
x = 1
r1 = y
# スレッド2
y = 1
r2 = x
以下のようにメモリバリアを行うことで、順序変更は発生しなくなる。
# スレッド1
x = 1
Memory_barrier
r1 = y
# スレッド2
y = 1
Memory_barrier
r2 = x
メモリバリア命令は文字通りバリアとして、バリア前後の命令の順序変更が行われないことを保証する。
最後に、RMOやWMOでも発生しない問題であるDependent loads reordering (依存関係のあるロードの順序変更) について触れて、ハードウェア・メモリモデルについては終わりにする。
Wikipediaから引用した表によれば、AlphaプロセッサではDependent loads (依存関係のあるロード) の順序変更が許されている。これは、WMOやRMOなプロセッサでも発生しないため、Alphaプロセッサのメモリモデルはこの点でこれらよりも弱いと言える。 Alphaプロセッサ (Alpha21264ベースのプロセッサ) における依存関係のあるロードの順序変更とは、つまり以下のようなことである。
# 初期状態: p = &x, x = 1, y = 0
# スレッド1
y = 1
Memory_barrier
p = &y
# スレッド2
i = &p
Alpha21264ベースのプロセッサを備えたコンピュータ1では、このプログラムを実行した結果iが0になり得る。
上記のプログラムでは、 y=1 と p=&y はメモリバリアによって順序付けされている (=これらの命令には依存関係がある) 。スレッド2が i として 0 を読み取るためには、yが 0 である必要があるが、この依存関係によってそれはありえないように思われる。
これがどのように発生するかと言うと、次の通りである。
y=0 をキャッシュしているy=1 が実行されるp=&y に向かうi=&p を実行。pをデリファレンスするとyが出て来るが、スレッド2はまだy=0だと思っている (インバリデーションはまだキューの中にあるから) ので、 i=0 になるこれは、メモリバリアがあるにも関わらずスレッド2がスレッド1のyへの書き込みを読み取れないという点で興味深い事象である。この問題を解決するには、スレッド2のロードの前にProbe queueの中身をフラッシュする必要がある。Reordering on an Alpha processorによれば、Alpha21264ではメモリバリアのタイミングでキューのフラッシュが実行されるため、スレッド2にメモリバリアを追加するとよい、としている。
前章では、プロセッサに関するメモリモデル「ハードウェア・メモリモデル」について書いた。 筆者はGoプログラマなので、Goのメモリモデルはどのようなものかについて説明する。
ハードウェアメモリモデルが示すのは、あるプロセッサによるメモリへの書き込みや読み取りに関する命令順序に関するルールであった。 Goやその他の高水準言語が提供するメモリモデルは、ハードウェア・メモリモデルと対比して「ソフトウェア・メモリモデル」と呼ばれる。 ソフトウェア・メモリモデルが規定するのは、マルチスレッドプログラムが共有メモリに対してアクセスする際のルールである。マルチスレッドプログラムといっても、Goではgoroutineを話題にしているし、JavaScriptはシングルスレッドなプログラミング言語なためSharedArrayBufferに対するルールとなっているなど、言語ごとの差異は存在する。
昨今のプロセッサは逐次一貫性を保証していないが、代わりにDRF-SCと呼ばれる「同期モデル」をサポートしている。DRF-SCはソフトウェアと密接に関係しており、プログラマが高水準言語をどのように書けばハードウェアにおいても逐次一貫した振る舞いになるのかを示している。 DRF-SCとは「Data-race-free Sequential Consistency」の略で、「ソフトウェアがデータ競合 (Data Race) を回避するならば、ハードウェアは逐次一貫しているように振る舞う」という考え方である。内容の詳細はオリジナルの論文であるWeak Ordering - A New Definitionを参照してもらいたい。 DRF-SCにおいて、ソフトウェアはatomicなどの同期プリミティブを用いて複数のスレッドを同期する。同期は「Happens-before (先行発生)」と呼ばれる関係を規定する。例えば、次のようなプログラムを考える。
S(a) は、 a という (アトミックな) 変数への同期命令を指す。 こういった同期がある時、同期の前の命令は同期の後の命令よりも先行して発生することが保証される。
「先行して発生している」とはそのまま、「順序変更が発生しない」ことを意味する。
つまり、プログラマは適切に同期を行えば、コンパイラが適切にメモリバリア命令を発行して順序変更がないことを保証するようになる。このルールがDRF-SCである。
!! この内容はMay 31, 2014を基に書かれており、アップデートされていない箇所があります。Goのメモリモデルのアップデートも併せてご覧ください。
Goのメモリモデルにおいては、次のことが書かれている。
まず、先行発生は次のように定義されている。
If event e1 happens before event e2, then we say that e2 happens after e1. Also, if e1 does not happen before e2 and does not happen after e2, then we say that e1 and e2 happen concurrently.
筆者による日本語訳は以下の通り。
イベントe1がイベントe2よりも先行発生する場合、e2はe1よりも後に発生している。
また、もしe1がe2よりも先行発生しておらず、e2がe1よりも先行発生していなければ、e1とe2は並行で発生している。
例えば、ある変数 v への書き込み w を、読み取り r が観測するためには、 w が r よりも先行発生してかつ、w と r の間に別の書き込み w’ がない ( w よりも後に発生し、 r よりも先行発生する書き込み w’ がない) ことが必要である。
さらに、次のようにある。
When multiple goroutines access a shared variable v, they must use synchronization events to establish happens-before conditions that ensure reads observe the desired writes.
同期イベントを使うことで、先行発生を関係付けることができる。
先行発生を定義したい理由は、先行発生を示すことが機械語プログラムにおける順序変更の回避 (DRF-SCによる) にそのままつながるからである。 つまり私達Goプログラマは、同期イベントを使うことでプログラムの先行発生関係をコンパイラに伝えることができ、その結果コンパイラは適切にメモリバリア命令が発行できるので、意図しない順序変更を回避できる、というわけである。
ここまでくれば、後は同期イベントにどのようなものがあるかを見ていくだけである。同期というとatomicやミューテックスをイメージしてしまうが、実際にはほかにも色々書かれており、いくつか例を挙げる。
go 文は、goroutineの実行よりも先行発生するvar a string
func f() {
print(a)
}
func hello() {
a = "hello, world"
go f()
}
これら以外には、goroutineの破棄、チャネル、sync.Mutexとsync.RWMutex、sync.Onceについて書かれている。
これら以外にも、Goのメモリモデルはアップデートが予定されている。sync.MapやPoolがメモリモデルで言及されていないなどの問題があるが、proposal: Go Memory Model clarifications · Issue #50590 · golang/goがクローズされているなど、今後どうなるのかは不明である。
ハードウェアメモリモデル及びDRF-SC、そしてGoのメモリモデルについて見てきた。メモリモデルというものは元々ハードウェアがアセンブリプログラマに何を保証するのかを示すものでしかなかった。 しかし、フリーランチは終わり、人々はマルチスレッドなプログラムを書かなければならなくなった。ここで、コンパイラを対象としたソフトウェア・メモリモデルが生まれた。
現代では、DRF-SCのおかげで私達のような普通のプログラマは適切な同期を行いさえすれば不可解なハードウェアの挙動に悩まされることはない。これは過去の研究者やハードウェアエンジニア、プログラミング言語の開発者などによる高度な抽象化によるものである。 こういった普段は意識することのない領域も調べてみると面白いので、この記事を書いた。最後の方は力尽きて駆け足になってしまったが、まだ理解できていない部分も多いので、引き続き興味を持って調べていきたい。