私は論文「シンプルで高速、かつ実用的なノンブロッキングおよびブロッキング同時キューアルゴリズム」を読んでいて、コンピューターが次の疑似コードをアトミックに実装していると想定していることに気付きました。
CAS(Q->Tail,tail,<next.ptr,next.count+1>)
Q->Tail と tail はポインターであり、ポインターとカウンターを含む構造体のインスタンスです。
私は、gcc が c で単一ワードの比較と交換を行うための組み込み機能をいくつか提供していることを知っています。ただし、(Linux を使用して) c で単一の比較とスワップからノンブロッキングのアトミックな二重比較とスワップを実装することは可能ですか? これは、参照されている論文の疑似コードを実装するための正しいアプローチですか?
2 つの異なるメモリ位置で動作する CAS 操作については知りません。ただし、論文ではポインターとカウンターの構造体を回避策として使用して、両方のフィールドをより大きな型として扱い、両方をアトミックに変更している可能性があります。
ポインタとカウンタの 2 つのフィールドの構造体があると仮定します。ポインタのサイズは 4 バイト、カウンタのサイズは 4 バイトです。パディングなしで 8 バイトの構造体サイズに適切に配置されます。8 バイトの値 (64 ビット整数へのポインターなど) を処理する CAS 操作もあると仮定します。構造体の値を個別に準備し、構造体全体に対して CAS 操作を使用して、2 つの値を一度に変更できます。
Gcc はダブルワード CAS 用のビルトインも提供します。sizeof(*Q->Tail) == sizeof(tail) == sizeof(third_arg) == 8 の場合、__sync_bool_compare_and_swap を使用できます。 CAS を実行する前に「next.count」。