Load-Link/Store-Conditional

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

Load-LinkLL、他に "Load-Linked" または "Load and Reserve")とStore-Conditional (SC) は組み合わせて使用されるコンピュータの命令。これによりロックなしアトミックなリード・モディファイ・ライト操作が可能となる。(リード・モディファイ・ライトとは、あるメモリ位置の内容を読み取って、変更を加えて、書き戻す一連の操作を意味する)

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

弱い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でも実装可能)。

関連項目[編集]

外部リンク[編集]

いずれも英文