Load-Link/Store-Conditional
弱いLL/SC[編集]
LL/SC命令の実装においては、そのメモリ位置への更新がないときでも失敗することがある。二つの操作の間に何らかの例外事象︵例えばコンテキストスイッチ、別の load-link 命令実行、多くの実装では他のロード命令やストア命令も︶が発生すると store-conditional 命令は失敗する。古い実装では、メモリバス上に何らかの更新ブロードキャストがあっただけで失敗していた。 このため、研究者はこれを﹁弱い﹂[2]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︵wcx命令)[3][4]、MIPS︵ld/scd命令)[5]、ARM (ldrex/strex命令) がある。
ほとんどのプラットフォームではデータサイズ毎の命令を備えている。例えば、PowerPC にはダブルワード用の ldarx/stdcx命令がある。
いくつかのCPUはライトスルーモードに設定して排他的にそのアドレスにアクセスする必要がある。
どのプラットフォームも弱いLL/SCを提供している。PowerPC の実装が最も強く、LL/SCの間で他のキャッシュラインへのロードやストアを許している。これを利用すると、ロックフリーなリファレンスカウントを実装できる︵他にDCASでも実装可能︶。
関連項目[編集]
- Lock-freeとWait-freeアルゴリズム
- コンペア・アンド・スワップ
- R4000#マルチプロセッサ対応 — R4000での
ll/sc命令
脚注[編集]
- ^ リード・モディファイ・ライトとは、あるメモリ位置の内容を読み取って、変更を加えて、書き戻す一連の操作を意味する。
- ^ weak
- ^ C.May 1993, p. 336-338,465.
- ^ C.Kacmarcik 1995, p. 71.
- ^ “APPLICATION NOTE MIPS R4000 Synchronization Primitives”. p. 5. 2024年3月11日閲覧。
参考文献[編集]
- 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
- Kacmarcik, Cary (1995). Optimizing PowerPC Code. Addison-Wesley Publishing Company. ISBN 0-201-40839-2
外部リンク[編集]
- Lock-free reference counting （英語） — D. Detlefs、P. Martin、M. Moir、Guy L. Steele, Jr. 共著
- Atomic Reference Counting Pointers （英語） — Kirk Reinholtz 著
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |
