For faster navigation, this Iframe is preloading the Wikiwand page for Load-Link/Store-Conditional.

Load-Link/Store-Conditional

load-linkロード・リンクLL、他に load-linkedロードリンクトまたは load and reserveロード・アンド・リザーヴ)と store-conditionalストア・コンディショナルSC)は組み合わせて使用されるコンピュータの命令。これによりロックなしアトミックなリード・モディファイ・ライト操作[1]が可能となる。

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

弱い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パワーピーシー (lwarx/stwcx命令)[3][4]MIPSミップス (ll/sc命令、lld/scd命令)[5]ARM (ldrex/strex命令) がある。

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

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

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

関連項目

[編集]

脚注

[編集]
  1. ^ リード・モディファイ・ライトとは、あるメモリ位置の内容を読み取って、変更を加えて、書き戻す一連の操作を意味する。
  2. ^ weakウィーク
  3. ^ C.May 1993, p. 336-338,465.
  4. ^ C.Kacmarcik 1995, p. 71.
  5. ^ 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 

外部リンク

[編集]
{{bottomLinkPreText}} {{bottomLinkText}}
Load-Link/Store-Conditional
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?