【プログラミング】マルチコア環境における排他制御の課題

【※ 当記事は2020年7月2日時点の情報です】

ペイヴメント（@pavement1234）です。

マルチスレッドプログラミングにおいて排他制御は永遠の課題。
特にマルチコアになり難易度が増しました。
ちょっとマニアックな話題ですし、課題の根本的な解決までは至っていない
単なるメモ書きです。
※字ばっかりですいません。

排他制御とは？

排他制御（Wikipedia）を調べてみると
コンピュータ・プログラムの実行において複数のプロセスが利用出来る共有資源に対し、
複数のプロセスからの同時アクセスにより競合が発生する場合に、
あるプロセスに資源を独占的に利用させている間は、
他のプロセスが利用できないようにする事で整合性を保つ処理の事をいうとあります。

これまでの経験上、
排他制御のソフトウェア実装とは
（シングルコアにおける）割込禁止、
排他オブジェクト（セマフォ、ミューテックス）、
ビジーループを使うスピンロック。
あたりと思ってますが、
マルチコア時代の排他は何を使えばいいのか深堀してみます。

マルチコア時代の排他について調べた

①何はともあれスピンロック

Linuxのスピンロックでは
1つの資源に対して1つのロック変数をメモリー上に用意します。
そしてロック変数を取得できたCPUだけが資源にアクセスできます。
ロック変数を取得できなかったCPUはロック変数が取得できるまで
ループして待ち続けます。
この状態を「ビジーウエイト」と呼びます。

スピンロックは
マルチプロセッサシステムで手軽に排他制御を実現する方法としてよく利用されています。
ただしビジーウエイト中のCPUは処理が実行できずに待たされた状態になりますから
ビジーウエイトが頻繁に発生すると処理効率が悪くなります。
処理効率を考えるなら
スピンロックで排他制御する資源を
なるべく細かく分けるなどの工夫が必要です。

ロック取れなかったCPUはビジーループして待つ。
当たり前だけどビジーループ中のCPUは他の処理ができないため効率は悪いです。

とあるプロジェクトでマルチコアCPUで動くアプリを見てますが、
多分ミューテックスとセマフォしか使ってない気がしてます。
とはいえ明示的にアフィニティ設定してないので
恐らくCPU0しか使われずシングルコアな動作になってる気もします。

スピンロック。
デバドラを解析してると
管理構造体の変数の排他で使われてるのを見かけることが多々あります。

Ethernetのマルチポートのデバドラを例に挙げますが
IRQ毎にアフィニティ設定を分けることで並列動作できると思いますが
スピンロックしてないと危ないです。

②そして、割り込み禁止

シングルコアのときは割り込み禁止すれば、
コンテキスト割込が発生しなくなりコンテキストスイッチできないので、
スレッドが遷移しません。
従って自然と排他されます。
しかしマルチコアのときは他のCPUが割込を発生させるため、
排他が保証されません。

③セマフォのこと

セマフォの取得を読むと、こんなことが書いてあります。
セマフォの中ではスピンロック使ってるみたい。
だとすればマルチコアでも安全なんですかね。

セマフォは排他制御として使いますが、
他にスピンロックというのがあります。
スピンロックはロックを獲得（変数のチェック）するまで、
ビジーウエイトと言うCPUを全消費するループで待ちます。
一方、セマフォーは他のタスクに実行を譲ることができます。
「それならセマフォーの方がいいじゃん」と言われそうですが
「排他区間が短い場合、タスクスイッチングするより、
ビジーウエイトでループし続けた方がパフォーマンスいい」という事のようです。
実は、このセマフォ、実装する上でスピンロックを使っているんですね。

スピンロックというのは、
マルチCPUシステムでの排他制御を実現する手法として誕生したもののようで、
単一CPUシステムでは割り込みを禁止すれば、
それ以降の排他性は保障されます。
しかしマルチCPUでは他のCPUからの割り込みが発生するわけです。
割り込み禁止のCLIはそのCPUに対してだけです。
このような背景でスピンロックが登場したようです。

④ミューテックスのこと

スピンロックの使用を読むと、
ミューテックスよりスピンロックの方が効率が良いことがある、
なんてことが書いてあります。
大抵のプログラムはミューテックスを使いまくってます。
スピンロックとmutexの速度比較を読むと速度差は２倍。
スピンロックの方が効率が良いなら、そうすべきな気がしますが、実際どうでしょう。
結局マルチコアでミューテックスを使うのが安全なのか、
よくわかりません。

スピンロックは、
主に共有メモリー型のマルチプロセッサ上での使用に適した低レベルの同期機構です。
呼び出しスレッドが、
すでに別のスレッドによって保持されているスピンロックを要求する場合、
2 番目のスレッドは、
そのロックが使用可能になったかどうかをテストするためのループに入ります。
スピンはプロセッササイクルを浪費するため、
ロックを獲得したら、短時間だけ保持するようにすべきです。
呼び出し元は、ほかのスレッドがロックを獲得できるようにするための
スリープ操作を呼び出す前に、スピンロックを解除するようにしてください。

スピンロックは mutex と条件変数を使用して実装することもできますが、
スピンロックを実行するための標準化された方法は
pthread_spin_* 関数です。
短期間のロックであれば、pthread_spin_* 関数に
必要なオーバーヘッドははるかに少なくなります。

どういうロックを実行する場合も、
スレッドのブロックを設定している間に消費されるプロセッサリソースと、
ブロックされている間にスレッドによって消費されるプロセッサリソースとの間に
トレードオフが発生します。
スピンロックでは、スレッドのブロックを設定したあと、単純なループを実行して、
ロックが使用可能になるまで
不可分なロック処理を繰り返すためのリソースがほとんど必要ありません。
スレッドは、待機している間もプロセッサリソースを消費し続けます。

スピンロックに比べると、
mutex はスレッドのブロックにより大量のプロセッサリソースを消費します。
相互排他ロックが使用できない場合、
スレッドはスケジューリングの状態を変更して、
自身を待機スレッドの待ち行列に追加します。
ロックが使用可能になると、スレッドがロックを獲得する前に、
これらの手順を逆にたどる必要があります。
スレッドは、ブロックされている間、プロセッサリソースを消費しません。

したがって、
スピンロックと mutex は別の目的に使用すると有効な場合があります。
非常に短期間のブロックでは、
スピンロックの方が全体的なオーバーヘッドは少なくなることがあります。
スレッドがより長期間ブロックされる場合は、
mutex の方が全体的なオーバーヘッドは少なくなることがあります。

④キャッシュのこと

マルチコア環境において共有メモリ変数に排他をかける場合、
キャッシュ全体の一貫性（キャッシュコヒーレンシ）を
考慮しなければならないという話があります。
CPU とキャッシュのはなしを読んだところ
やはりマルチコア環境で共有変数を更新したら必ずキャッシュをFlashせよとあります。
あとは命令実行の並列化（アウト・オブ・オーダ実行）がされることを考慮し
メモリバリアも行う、ってあたりが重要な気がします。

すべてのスレッドが1つのシングルCPUから実行されるシングルコアプロセッサでは、
メモリ内のミューテックス（またはセマフォなど）に
アトミックなテストセット操作を使用して
クリティカルセクションを実装するという考えは十分に簡単に思えます。
あなたのプロセッサは
あなたのプログラムのある場所からテストとセットを実行しているので、
それは他のスレッドのように偽装されたあなたのプログラムの中の別の場所から
必ずしもそれをすることはできません。

しかし、実際に複数の物理プロセッサを使用しているとどうなりますか？
単純な命令レベルのアトミック性では十分ではないようです。
2つのプロセッサが同時にテストと設定操作を実行するb / cでは、
アトミック性を維持するために本当に必要なのは、共有メモリの場所へのアクセスです。
ミューテックス（そして、共有メモリの場所がキャッシュにロードされている場合は、
キャッシュ全体の一貫性についても対処する必要があります）。

まとめ

マルチコア環境の排他制御は奥が深いです。
結局、セマフォとミューテックスをマルチコアで使うことの是非について
完全に安心できる情報は得られませんでした。
ただ、直感的に心配してたことは現状起きてないので
杞憂なのかもしれない、とも思います。
でも確信をもってOKとなんとなくOKは雲泥の差と思ので、
私は納得いくまで追及し続けようと思います。

あと組込みシステムにおける割り込み制御に関する研究を見つけました。
体系的に書いてそうなので、近々読んでみます。
新しい発見があったら追記します。