7

ここで説明するように、MagedM.MichaelとMichaelL.Scottによるアルゴリズムを使用して、並行アプリケーション用のノンブロッキングキューパッケージを作成しようとしています。

"sync/atomic"これには、パッケージによって提供されるアトミックなCompareAndSwapを使用する必要があります。
ただし、次の擬似コードに相当するGoが何であるかはわかりません。

E9:   if CAS(&tail.ptr->next, next, <node, next.count+1>)

ここでtail、nextは次のタイプです。

type pointer_t struct {
    ptr   *node_t
    count uint
}

nodeタイプは次のとおりです。

type node_t struct {
    value interface{}
    next  pointer_t
}

正しく理解できれば、構造体（ポインターとの両方uint）を使用してCASを実行する必要があるようです。atomicこれは-packageでも可能ですか？

手伝ってくれてありがとう！

4

2 に答える 2

13

私の理解が正しければ、構造体 (> ポインターと uint の両方) を使用して CAS を実行する必要があるようです。これはアトミックパッケージでも可能ですか?

いいえ、それはできません。ほとんどのアーキテクチャは、単一の単語に対するアトミック操作のみをサポートしています。しかし、多くの学術論文では、現在利用できないより強力な CAS ステートメント (compare and swap double など) を使用しています。幸いなことに、そのような状況で一般的に使用されるいくつかのトリックがあります。

  • たとえば、ポインターからいくつかのビットを盗み (特に 64 ビット システムで)、それらを使用してカウンターをエンコードすることができます。次に、Go の CompareAndSwapPointer を単純に使用できますが、ポインターを逆参照する前に、ポインターの関連ビットをマスクする必要があります。

  • もう 1 つの可能性は、(不変!) pointer_t 構造体へのポインターを操作することです。pointer_t 構造体の要素を変更する場合は常に、コピーを作成し、コピーを変更して、構造体へのポインターをアトミックに置き換える必要があります。このイディオムは COW (copy on write) と呼ばれ、任意の大きな構造で機能します。この手法を使用する場合は、 next 属性を に変更する必要がありますnext *pointer_t。

私は最近、教育上の理由から Go でロックフリー リストを作成しました。ここで（十分に文書化された）ソースを見つけることができます：https://github.com/tux21b/goco/blob/master/list.go

このかなり短い例では、atomic.CompareAndSwapPointerを過度に使用し、マーク付きポインター (MarkAndRef 構造体) のアトミック型も導入しています。この型は、pointer_t 構造体に非常に似ています (int+pointer の代わりに bool+pointer を格納することを除いて)。後で要素を直接挿入しようとしているときに、ノードが削除済みとしてマークされていないことを確認するために使用されます。独自のプロジェクトの開始点として、このソースを自由に使用してください。

于 2012-07-17T16:43:23.190 に答える
0

次のようなことができます。

 if atomic.CompareAndSwapPointer(
    (*unsafe.Pointer)(unsafe.Pointer(tail.ptr.next)), 
    unsafe.Pointer(&next), 
    unsafe.Pointer(&pointer_t{&node, next.count + 1})
 )
于 2012-07-17T15:47:06.990 に答える