RISC-Vの仕様書を読んでいて、アトミックアクセスの所に色々書いていったので自分でも勉強してみることにした。
まず、大前提としてRISC-Vではアトミックアクセスのための命令としてLR/SC(Load-Reserved / Store-Conditional)の命令を採用している。 この命令自体は非常にありふれた命令で、基本的な動作はここではあまり説明しない。
アトミックアクセスの例題として良く用いられるものに「ABA問題」というものがある。これは何かの略称ではなく、「共有メモリの値をAからBに書き換える」問題だと思えば良い。 あるスレッドがとあるメモリ位置からデータをロードし(これを値Aとする)、それをもとに新しい値を計算し(これを値Bとする)、同じメモリ位置にストアする。 しかしこのAのロードとBの書き換え、ストアはある一定の時間をかけて行われるので、その間に別のスレッドによって同じ場所のメモリを書き換えられてしまった場合、データの矛盾が発生することになる。これがABA問題である。
これを解決するためのいくつかの方法があるが、ここではLR/SCとCASの2つの方法を挙げる。
- Load Reserved(LR)はとあるメモリ領域からデータをロードし、それと同時にそのメモリアドレスを「予約セット(Reservation Set)」に登録する。
- Store Conditional(SC)は同じ場所にデータをストアするが、予約セット内にそのメモリアドレスがまだ存在していれば成功し、そうでなければ失敗する。
- 予約セットは、別のスレッドやCPUデバイスが同じアドレスにアクセスすると外されてしまう。つまり、LRとSCの間に別のCPUデバイスやスレッドがそのアドレスにアクセスを行わない場合、SCは成功する。
もう一つ別の方法として"Compare and Swap"(CAS)という方法がある。CASの使い方は、まずとあるメモリアドレスからデータをロードし、それを古い値としてどこかに格納しておく。古い値をもとに計算を行い新しい値を算出し、最後にCAS命令によってその値をストアする。その際、ストア時に事前に取ってきた古い値と新しい値が一致していない場合(つまり別のCPUデバイスやスレッドによってその値が更新された場合)に、CASは失敗し、最初からやり直すことになる。
という訳で、CAS命令自体には「元の値」「更新した値」「ストアアドレス」の3つのオペランドを用意する必要があり、これがRISC-Vの標準的なオペランドフォーマットのどれにも当てはまらない。これにより、CASの定義をやめたというのが理由の一つに挙げられている。
LR/SCのCASに対する欠点として、ライブロックが回避できないということが挙げられている。ライブロックの詳細は別の文献に譲るが、有名なイメージとしては「正面から向かってきた2人が同じ方向に避けようとしていつまでたっても交差することができない」というやつだ。 イメージだが、LR/SCの場合は、2つのスレッドがLRとSCを交互に進めるとどちらとも成功せずにライブロック状態になるが、CASの場合は最新の値を持っているどちらかが常に勝つのでライブロックは発生しない、という理解であっているかな？
もう一つ、CASにはDW-CAS(double-word CAS)という仕組みがあり、2つのメモリアドレスに対してCAS操作を実行することによりリンクリストの操作を容易にするというものがある。
このLR/SCの実装についてはかなりいろんなコメントが残されているので、さらに続く。
