Load-Link/Store-Conditional

load-link（ロード・リンク、LL、他に load-linked（ロードリンクト） または load and reserve（ロード・アンド・リザーヴ））と store-conditional（ストア・コンディショナル） (SC) は組み合わせて使用されるコンピュータの命令。これによりロックなしのアトミックなリード・モディファイ・ライト操作が可能となる。（リード・モディファイ・ライトとは、あるメモリ位置の内容を読み取って、変更を加えて、書き戻す一連の操作を意味する）

load-link 命令は指定されたメモリ位置の現在の内容を返す。その後の store-conditional 命令は同じメモリ位置へ新たな値を書き込むが、前回の load-link 命令以降にそのメモリ位置の内容が書き換えられていないときだけ書き込みが行われる。何らかの更新がなされていたら、たとえ load-link 命令で読み取った値と同じ内容が書かれていたとしても store-conditional 命令は失敗する。従って、LL/SC命令はコンペア・アンド・スワップ (CAS) 命令のような false positive（フォールス・ポジティヴ）（偽陽性）問題を発生しない。

弱いLL/SC

LL/SC命令の実装においては、そのメモリ位置への更新がないときでも失敗することがある。二つの操作の間に何らかの例外事象（例えばコンテキストスイッチ、別の load-link 命令実行、多くの実装では他のロード命令やストア命令も）が発生すると store-conditional 命令は失敗する。古い実装では、メモリバス上に何らかの更新ブロードキャストがあっただけで失敗していた。

このため、研究者はこれを「弱い」^[1]LL/SCと呼び、本来の理論上のLL/SCアルゴリズムと区別している。弱さは相対的で、弱い実装でもアルゴリズムで使うことが出来る。

弱いLL/SCとコンペア・アンド・スワップ（CAS）を比較したとき、後者の方が公平さで優れていると言える。本来のLL/SCも公平さを持っている。（訳注：弱いLL/SCでは、後から load-link 命令を実行した方が勝ってしまうため、load-link 命令を発行した順番に処理できるようにすべきという公平さに問題がある）

実装

LL/SC命令を実装したプロセッサとして、DEC Alpha（デック・アルファ） (ldl_l/stl_c命令とldq_l/stq_c命令)、PowerPC（パワーピーシー） (lwarx/stwcx命令)^[2]、MIPS（ミップス） (ll/sc命令)、ARM (ldrex/strex命令) がある。

ほとんどのプラットフォームではデータサイズ毎の命令を備えている。例えば、PowerPC にはダブルワード用の ldarx/stdcx命令がある。

いくつかのCPUはライトスルーモードに設定して排他的にそのアドレスにアクセスする必要がある。

どのプラットフォームも弱いLL/SCを提供している。PowerPC の実装が最も強く、LL/SCの間で他のキャッシュラインへのロードやストアを許している。これを利用すると、ロックフリーなリファレンスカウントを実装できる（他にDCASでも実装可能）。

関連項目

• Lock-freeとWait-freeアルゴリズム
• コンペア・アンド・スワップ
• (R4000#マルチプロセッサ対応) — R4000でのll/sc 命令

脚注

1. ^ weak（ウィーク）
2. ^ C.May 1993, p. 465.

参考文献

• May, Cathy; Silha, Ed; Simpson, Eick; Warren, Hank (1993). The PowerPC architecture: A SPECIFICATION FOR A NEW FAMILY OF RISC PROCESSORS. Morgan Kaufmann PUblishers, Inc. p. 350. ISBN (1-55860-316-6) 

外部リンク

• Lock-free reference counting （英語） — D. Detlefs、P. Martin、M. Moir、Guy L. Steele, Jr. 共著
• Atomic Reference Counting Pointers （英語） — Kirk Reinholtz 著