Load-Link/Store-Conditional
出典: フリー百科事典『ウィキペディア（Wikipedia）』
Load-Link（LL、他に "Load-Linked" または "Load and Reserve"）とStore-Conditional（SC)は組み合わせて使用されるコンピュータの命令。これによりロックなしのアトミックなリード・モディファイ・ライト操作が可能となる。（リード・モディファイ・ライトとは、あるメモリ位置の内容を読み取って、変更を加えて、書き戻す一連の操作を意味する）
Load-Link命令は指定されたメモリ位置の現在の内容を返す。その後の Store-Conditional命令は同じメモリ位置へ新たな値を書き込むが、前回の Load-Linked命令以降にそのメモリ位置の内容が書き換えられていないときだけ書き込みが行われる。何らかの更新がなされていたら、たとえLoad-Link命令で読み取った値と同じ内容が書かれていたとしても Store-Conditional命令は失敗する。従って、LL/SC命令はコンペア・アンド・スワップ(CAS)命令のような False Negative 問題を発生しない。
目次 |
[編集] 弱い LL/SC
LL/SC命令の実装においては、そのメモリ位置への更新がないときでも失敗することがある。二つの操作の間に何らかの例外事象（例えばコンテキストスイッチ、別のLoad-Link命令実行、多くの実装では他のロード命令やストア命令も）が発生すると Store-Conditional命令は失敗する。古い実装では、メモリバス上に何らかの更新ブロードキャストがあっただけで失敗していた。
このため、研究者はこれを「弱い; weak」LL/SC と呼び、本来の理論上の LL/SC アルゴリズムと区別している。弱さは相対的で、弱い実装でもアルゴリズムで使うことが出来る。
弱い LL/SC と CAS を比較したとき、後者の方が公平さで優れていると言える。本来の LL/SC も公平さを持っている。（訳注：弱い LL/SC では、後から Load-Link命令を実行した方が勝ってしまうため、Load-Link命令を発行した順番に処理できるようにすべきという公平さに問題がある）
[編集] 実装
LL/SC命令を実装したプロセッサとして、Alpha（ldl_l/stl_c、ldq_l/stq_c）、PowerPC（lwarx/stwcx）、MIPS（ll/sc）、ARM（ldrex/strex）がある。
ほとんどのプラットフォームではデータサイズ毎の命令を備えている。例えば、PowerPC にはダブルワード用の ldarx/stdcx などがある。
いくつかのCPUはライトスルーモードに設定して排他的にそのアドレスにアクセスする必要がある。
どのプラットフォームも弱い LL/SC を提供している。PowerPCの実装が最も強く、LL/SCの間で他のキャッシュラインへのロードやストアを許している。これを利用すると、ロックフリーなリファレンスカウントを実装できる（他にDCASでも実装可能）。
[編集] 関連項目
[編集] 外部リンク
いずれも英文
- Lock-free reference counting by D. Detlefs, P. Martin, M. Moir and Guy L. Steele, Jr.
- Atomic Reference Counting Pointers by Kirk Reinholtz
 |
この「Load-Link/Store-Conditional」は、コンピュータに関連した書きかけです。この記事を加筆して下さる人を求めています。（Portal:コンピュータ） |
