スピンロック
スピンロック（英: spin lock, spinlock）[1]とは、計算機科学におけるロックの一種で、スレッドがロックを獲得できるまで単純にループ（スピン）して定期的にロックをチェックしながら待つ方式。スレッドはその間有益な仕事を何もせずに動作し続けるため、これは一種のビジーウェイト状態を発生させる。獲得されたスピンロックは明示的に解放するまでそのまま確保されるが、実装によってはスレッドがブロック（スリープ）したときに自動的に解放される場合もある。
スレッドが短時間だけブロックされるならば、スピンロックは効率的であり[2]、オペレーティングシステムのプロセススケジューリングのオーバーヘッドを防ぐことにもなる。このため、スピンロックはカーネル内でよく使われる。特に、スケジューラ自身のロックにあってはスリープ可能なロックを使用するとそれが再帰的にスケジューラに依存してしまうことにより実装や動作を混乱させる恐れがあることから、何らかの形でスピンロックを使用することが必須となる。
スピンロックは、コンボイの問題を自然に避ける。定義により、スピンロックの獲得に成功したスレッドは現にCPU上にて実行していることによる。そのようなスレッドは獲得したスピンロックが保護している処理を遅延なく実行でき、別途スケジューリングを待つ必要がない。
スピンロックの重要な制限として、スピンロックを所有しているスレッドは、自発的なスリープ、プリエンプションの如何を問わず、CPUを手放してはならない。これに反した挙動が発生すると、最悪の場合デッドロックに陥る。ロックを保持しているスレッドがCPUを手放した後、何らかの原因により再度実行できなくなった場合、他のスレッドは（ロックを繰り返し獲得しようとして）スピンし続けてしまう。その結果、ロックを保持するスレッドがロックを解放するまで、他のスレッドは先に進むことができない。これは indefinite postponement 状態と呼ばれる。シングルプロセッサシステムではこの状態が発生すると直ちにシステムが無限ループに陥る。というのも、他のスレッドが並行して動くことは決してないので、いったんスピンし始めると永久にスピンし続けることになるのである。マルチプロセッサシステムではすぐには致命的な問題にはならないものの、システム全体の並列度が徐々に低下する。すべてのCPUが決して解放されないスピンロック待ちのスレッドで埋まった時点で、システムはシングルプロセッサと同様動作しなくなる。このような問題を防ぐため、スピンロックを所有しているスレッドに対しては一般に以下の制限を課す。
- スレッドが実行しているCPUでの割り込みおよび例外処理を禁止する。やむを得ず許可する場合は、割り込まれたスレッドがCPUを奪われないことを保証する。
- スレッドが自発的にスリープする場合は、スピンロックを解放する。
- スレッドのスリープは、別のスレッドにスリープを終了させる挙動を期待することを意味する。そのような挙動を実行するためには同じスピンロックの獲得が不可欠なので、この制限は自然なものである。
上記の制限により理論的にはデッドロックを避けることができる。一方、スピンロックを所有しているスレッドに対してプリエンプトが不可能になるため、主にRTOSにて応答遅延など別の問題が生じる場合がある。
スピンロックを正しく実装することは難しい。なぜなら、競合状態を避けるためにロックの同時アクセスの可能性を考慮しなければならないからである。一般に、これは特別なアセンブリ言語の命令（アトミックなテスト・アンド・セット操作など）を使う必要があり、高級言語やアトミック命令をサポートしていない言語では簡単には実装できない[3]。アトミック命令をサポートしないアーキテクチャや、高級言語で実装しなければならない場合、ピーターソンのアルゴリズムといったアトミックでないロックアルゴリズムを用いることができるかもしれない。ただし、スピンロックより多くのメモリが必要になるかもしれないし、アウト・オブ・オーダー実行が許される場合は高級言語では実装できないかもしれない。
スピンロック所有中にプリエンプト防止のため割り込みを禁止する場合、スピン中の割り込み制御に注意する必要がある。スピン処理中、スピンロックの獲得を試みる際はこれが成功した場合に備えて割り込みを禁止する必要がある。一方、スピンロックの獲得に失敗した場合、そのままスピンするとロックを所有していないにもかかわらず割り込みを禁止しているので割り込みに対する応答遅延が発生する。これを軽減するため、スピンロックの獲得に失敗した場合は一時的に割り込みを許可し、保留していた割り込み処理をすべて済ませた上で再度割り込みを禁止してスピンすることが望ましい。また、複数のスピンロックを同時に獲得可能とする場合、割り込みの禁止をネストする必要がある。これは一般にはハードウェアによるサポートがなく、ソフトウェアによる参照カウント等の実装が必要となる。
実装例
[編集]以下の例は x86 アセンブリ言語によるスピンロックの実装である。Intel 80386互換プロセッサで動作する。
lock: # ロック変数。1 = ロック済み, 0 = ロックされていない
dd 0
spin_lock:
mov eax, 1 # EAX レジスタに 1 をセット
loop:
xchg eax, [lock] # アトミックにEAXレジスタとロック変数の値を交換
# ロックには常に 1 が格納され、以前の値が EAX レジスタに格納される。
test eax, eax # EAX 自身をチェック。EAX がゼロならば プロセッサのゼロフラグがセットされる。
# EAX が 0 なら、ロックは解放状態から新たに確保されたとみなせる。
# そうでなければ、EAX は 1 であり、ロックを獲得できていない。
jnz loop # ゼロフラグがセットされていないときは XCHG 命令に戻る。
# これはロックが既に他に獲得されていた場合で、スピンする必要がある。
ret # ロックを獲得できたので、呼び出した関数へ戻る。
spin_unlock:
mov eax, 0 # EAX レジスタに 0 をセット
xchg eax, [lock] # アトミックに EAX レジスタとロック変数を交換
ret # ロックを解放
最適化
[編集]上記は（x86アセンブラを知っているならば）理解しやすい単純な実装で、全ての x86 アーキテクチャのCPUで動作する。しかし、非常に効果的な性能最適化手法がいくつか存在する。
x86 アーキテクチャでも比較的新しく実装されたものでは、ロックされた XCHG 命令の代わりにより高速なロックされていない MOV 命令で spin_unlock を実現できる。これは微妙なメモリの順序性によるもので、MOV命令自体は完全なメモリバリアではない。しかし、いくつかのプロセッサ（一部のサイリックスプロセッサ、バグを持っている一部バージョンのPentium Pro、初期のPentiumやi486によるSMPシステム）では、この方法は使えず、ロックが壊れてしまう。x86 アーキテクチャ以外では明示的なメモリバリア命令やアトミック命令が使われるか、特別な unlock 命令（IA-64など）があって必要なメモリの順序性を提供している。
- この場合のメモリの順序性 (memory ordering) とは、ロックとロック対象のデータの更新タイミングの問題を意味する。プログラム上ロック対象データを先に更新してからロックをアンロック操作でクリアするが、他のプロセッサからこれがその通りの順番に観測されることは一般に保証されない。つまり、次のスレッドがロックを確保してからロック対象データを参照したときに前のスレッドによる更新内容を得られない可能性がある。このため、メモリバリア命令などで、あるプロセッサのメモリ書き込みが全て他のプロセッサから観測可能になることを保証する。
CPU間のバストラフィックを低減するため、ロックを獲得できなかったときのループではロックの値が変化するまでメモリへの書き込みをすべきでない。MESIプロトコルなどのキャッシュプロトコルでは、これによってロックを含むキャッシュラインが "shared" 状態になるため、CPUはロックを待っている間全くバストラフィックを発生しない。この最適化はCPU毎のキャッシュを持つあらゆるアーキテクチャで有効である。
- つまり、上記の例で毎回XCHG命令を実行しながらループするのは得策ではない。一度XCHG命令を実行してだめだった場合、単にロック変数を読むだけのループに移行し、値が変化したときに再度XCHG命令を実行すべきということになる。
SSE2をサポートするx86系CPUでは、電力消費量を減らすために pause 命令を使用できる。上記の例のループの中に pause 命令を挿入すると、消費電力を抑えることができる（サポートしていないCPUでは rep nop と同等であり無視される）[4][5][6][7]。これは「公平さ; fairness」を向上させることにもつながるが、公平さは他のCPUアーキテクチャでも大きな問題である。
シングルプロセッサシステムにあっては、ロックの再帰的な獲得がない限りスピンロックの獲得は1回で必ず成功し、スピンすることは決してない。このため、スピンロックを利用したソフトウェアをシングルプロセッサ向けにビルドする場合、スピンロックの獲得および解放そのものを省略する最適化が可能である。ただし、スピンロックが保護している処理がプリエンプトされない前提で実装されていることが多いため、割り込みの禁止は依然必要となる。
代替方式
[編集]スピンロックの第一の問題点はロックを獲得しようと待っている時間を浪費することである。これを避ける代替方式が2つ存在する。
- ロックを獲得しない。多くの場合、データ構造をうまく設計することでロックを使わずに済むようにできる。すなわち、スレッド毎にデータを用意したり、CPU毎にデータを用意して割り込み不可にして使用するなどの手法がある。
- 待っている間は他のスレッドに切り換える（スリープロックなどと呼ばれる）。一般にスレッドをそのロックを待っているスレッドのキューに登録し、他のスレッドにコンテキストスイッチする。全てのスレッドが確保済みのロックを解放してスリープするならデッドロック（あるいはリソーススタベーション）が発生しにくくなるという利点があり、スケジューリングによって次にどのスレッドにそのロックを獲得させるかを決めることが（ある程度）可能である。
いくつかのオペレーティングシステムは、まずスピンロックを使って、時間がかかるときはスレッドをサスペンドさせるという混合型の手法を用いる。Solarisは現在いずれかのCPUにて実行中のスレッドが所有しているロックを待つ場合はスピンロックを使用する一方、実行中でない（スケジューラ上は実行可能だがCPUに割り当てられていない場合を含む）スレッドが所有するロックを待つ場合はスリープロックを使用する（シングルプロセッサシステムでは常に後者となる）[8]。特に、ロックを所有しているスレッドがプリエンプトされてCPUを失った場合は、そのロックをスピンしながら待っているスレッドをスリープさせることによりデッドロックを防いでいる。一方で、スピン中にロックの状態だけでなくそれを所有しているスレッドの状態も確認しなければならないため、実行コストは純粋なスピンロックよりも高くつく。
参考文献
[編集]- ^ Introduction to Spin Locks - Windows drivers | Microsoft Learn
- ^ マルチスレッドのプログラミング > 第 4 章 同期オブジェクトを使ったプログラミング > スピンロックの使用 | Oracle
- ^ Silberschatz, Abraham; Galvin, Peter B. (1994). Operating System Concepts (Fourth Edition ed.). Addison-Wesley. pp. pp176-179. ISBN 0-201-59292-4
- ^ Joe Olivas; Mike Chynoweth, Tom Propst (2015年8月7日). “Benefitting Power and Performance Sleep Loops”. Intel. 2019年5月5日時点のオリジナルよりアーカイブ。2022年12月3日閲覧。
- ^ “スリープループによる消費電力とパフォーマンスの改善”. iSUS (2012年4月6日). 2019年5月5日閲覧。
- ^ Pause Intrinsic | Intel® C++ Compiler Classic Developer Guide and Reference
- ^ ストリーミング SIMD 拡張命令 2 の PAUSE 組み込み関数
- ^ Silberschatz, Abraham; Galvin, Peter B. (1994). Operating System Concepts (Fourth Edition ed.). Addison-Wesley. pp. p198. ISBN 0-201-59292-4
関連項目
[編集]外部リンク
[編集]いずれも英文
- POSIX thread のスピンロック The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004年版より
- "User-Level Spin Locks - Threads, Processes & IPC" Gert Boddaert
- Austria C++ SpinLock Class Reference