CASを持たないアーキテクチャ
CAS(Compare-And-Swap)を持っていないアーキテクチャで、アトミック操作はどうやるのか調べてみました。そういう部分ではLoad-Link/Store-Conditionalという命令を使って実現するみたいです。
- PowerPCでは、lwarx/stwcx という命令。
- ARMでは、ldrex/strex という命令。
このLoad-Linkというのが何かしらのロック付きロードで、この命令が発行されるとそれに対するアクセスを見張るらしい。
そして、Store-Conditionalが名前のつき条件付きストア命令で、Load-Linkでとったロックが維持されているときに、ストアを正常に行うことができるようです。
もし、ほかのプロセッサが見張っていたアドレス(バス？)を操作した場合には、ロックが外れ、次段のStore-Conditional命令が失敗するという結果になります。
Load-Link(LL)はLoad and Reserve とも表現するらしい。そのデータに対する変更の予約、という意味合いなんだろう。
このCASじゃない方式は面倒なようだけど、実はCASより優れている点もあるらしい。
実はCASの方式では、ABA問題と呼ばれる不都合な点がある。
これは対象アドレスのデータが書き換わって元に戻されたという挙動を確認できないのです。LL/SCの方式では、対象データ領域からのデータ読み出しから書き込みの間で値が更新されていないことをチェックしてストアできる点で優れています。またバスをロックせずにすむ点も効率がよいとのことです。
このABA問題はロックフリーなデータ構造を作っているときに問題となるらしいです。
詳しくは調べてみてください。
