スピンロック

出典: フリー百科事典『ウィキペディア（Wikipedia）』

あなた宛の新しいメッセージが届いています（差分）。

スピンロック（Spinlock）とは、ソフトウェア工学におけるロックの一種で、スレッドがロックを獲得できるまで単純にループ（スピン）して定期的にロックをチェックしながら待つ方式。スレッドはその間有益な仕事を何もせずに動作し続けるため、これは一種のビジーウェイト状態を発生させる。獲得されたスピンロックは明示的に解放するまでそのまま確保されるが、実装によってはスレッドがブロック（スリープ）したときに自動的に解放される場合もある。

スレッドが短時間だけブロックされるなら、スピンロックは効率的であり、オペレーティングシステムのプロセススケジューリングのオーバヘッドを防ぐことにもなる。このため、スピンロックはカーネル内でよく使われる。しかし、確保期間が長くなるとスピンロックは無駄が多くなり、他のスレッドの処理を妨害するだけでなく、再スケジューリングが必要になることもある。スピンロックはシングルプロセッサシステム上では非効率である。というのも、他のスレッドが並行して動いていないので、いったんスピンし始めるとタイムスライスを使い切るまでスピンし続けることになるのである。

スピンロックの実装は難しく、競合状態を避けるためにロックの同時アクセスの可能性を考慮しなければならない。一般に、これは特別なアセンブリ言語の命令（アトミックなテスト・アンド・セット操作など）を使う必要があり、C言語のような高級言語では実装できない。^[1]

[編集] 実装例

以下の例は 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命令自体は完全なメモリバリアではない。しかし、いくつかのプロセッサ（一部のCyrixプロセッサ、バグを持っている一部バージョンのPentium Pro、初期のPentiumやi486によるSMPシステム）では、この方法は使えず、ロックが壊れてしまう。x86 アーキテクチャ以外では明示的なメモリバリア命令やアトミック命令が使われるか、特別な unlock 命令（IA-64など）があって必要なメモリの順序性を提供している。

この場合のメモリの順序性(memory ordering)とは、ロックとロック対象のデータの更新タイミングの問題を意味する。プログラム上ロック対象データを先に更新してからロックをアンロック操作でクリアするが、他のプロセッサからこれがその通りの順番に観測されることは一般に保証されない。つまり、次のスレッドがロックを確保してからロック対象データを参照したときに前のスレッドによる更新内容を得られない可能性がある。このため、メモリバリア命令などで、あるプロセッサのメモリ書き込みが全て他のプロセッサから観測可能になることを保証する。

CPU間のバストラフィックを低減するため、ロックを獲得できなかったときのループではロックの値が変化するまでメモリへの書き込みをすべきでない。MESIプロトコルなどのキャッシュプロトコルでは、これによってロックを含むキャッシュラインが "Shared" 状態になるため、CPUはロックを待っている間全くバストラフィックを発生しない。この最適化はCPU毎のキャッシュを持つあらゆるアーキテクチャで有効である。

つまり、上記の例で毎回XCHG命令を実行しながらループするのは得策ではない。一度XCHG命令を実行してだめだった場合、単にロック変数を読むだけのループに移行し、値が変化したときに再度 XCHG 命令を実行すべきということになる。

電力消費量を減らすため、上記の例のループで rep nop 命令を使用すると、一部の x86 系CPUでは消費電力を抑えることができる（サポートしていないCPUでは無視される）。これは「公平さ; fairness」を向上させることにもつながるが、公平さは他のCPUアーキテクチャでも大きな問題である。

[編集] 代替方式

スピンロックの第一の問題点はロックを獲得しようと待っている時間を浪費することである。これを避ける代替方式が2つ存在する。

ロックを獲得しない。多くの場合、データ構造をうまく設計することでロックを使わずに済むようにできる。すなわち、スレッド毎にデータを用意したり、CPU毎にデータを用意して割り込み不可にして使用するなどの手法がある。
待っている間は他のスレッドに切り換える（スリープロックなどど呼ばれる）。一般にスレッドをそのロックを待っているスレッドのキューに登録し、他のスレッドにコンテキストスイッチする。全てのスレッドが確保済みのロックを解放してスリープするならデッドロック（あるいはリソーススタベーション）が発生しにくくなるという利点があり、スケジューリングによって次にどのスレッドにそのロックを獲得させるかを決めることが（ある程度）可能である。

いくつかのオペレーティングシステムは、まずスピンロックを使って、時間がかかるときはスレッドをサスペンドさせるという混合型の手法を用いる。Solarisは現在走行中のスレッドのリソースへのアクセスはスピンロックを使用し、走行中でないスレッドのリソースについてはスリープロックを使用する（シングルプロセッサシステムでは常に後者となる）。^[2]

[編集] 参考文献

↑ Silberschatz, Abraham; Galvin, Peter B. (1994).Operating System Concepts, Fourth Edition, pp176-179, Addison-Wesley. ISBN 0-201-59292-4.
↑ Silberschatz, Abraham; Galvin, Peter B. (1994).Operating System Concepts, Fourth Edition, p198, Addison-Wesley. ISBN 0-201-59292-4.