3

構造体にアトミックな読み取り/書き込みを実装しようとする試みについて、フィードバック (明らかな欠陥/改善方法) を探しています。

1 つの書き込みスレッドと複数の読み取りスレッドがあります。目的は、書き手の妨げにならないようにしながら、読み手が構造について一貫性のない見方をするのを防ぐことです。

この場合、Qt フレームワークによって提供されるフェッチ アンド アド アトミック プリミティブを使用しています。

例えば：

/* global */
OneWriterAtomicState<Point> atomicState;

/* Writer */
while(true) {  
  MyStruct s = atomicState.getState()
  s.x += 2; s.y += 2;
  atomicState.setState(s);
}

/* Reader */
while(true) {  
  MyStruct s = atomicState.getState()
  drawBox(s.x,s.y);
}

OneWriterAtomicState の実装:

template <class T>
class OneWriterAtomicState
{
public:
    OneWriterAtomicState()
        : seqNumber(0)
    {
    }

    void setState(T& state) {
        this->seqNumber.fetchAndAddOrdered(1);
        this->state = state;
        this->seqNumber.fetchAndAddOrdered(1);
    }

    T getState(){
        T result;
        int seq;
        bool seq_changed = true;

        /* repeat while seq is ODD or if seq changes during read operation */
        while( (seq=this->seqNumber.fetchAndAddOrdered(0)) & 0x01 || seq_changed ) {
            result = this->state;
            seq_changed = (this->seqNumber.fetchAndAddOrdered(0)!=seq);
        }
        return result;
    }


private:
    QAtomicInt seqNumber;
    T state;
}

これがバージョン 2 です (memcpy、reader yield、できれば getState() を修正):

template <class T>
class OneWriterAtomicState
{

public:
    OneWriterAtomicState()
        : seqNumber(0)
    {
        /* Force a compile-time error if T is NOT a type we can copy with memcpy */
        Q_STATIC_ASSERT(!QTypeInfo<T>::isStatic);
    }

    void setState(T* state) {
        this->seqNumber.fetchAndAddOrdered(1);
        memcpy(&this->state,state,sizeof(T));
        this->seqNumber.fetchAndAddOrdered(1);
    }

    void getState(T* result){
        int seq_before;
        int seq_after  = this->seqNumber.fetchAndAddOrdered(0);
        bool seq_changed = true;
        bool firstIteration = true;

        /* repeat while seq_before is ODD or if seq changes during read operation */
        while( ((seq_before=seq_after) & 0x01) || seq_changed ) {

            /* Dont want to yield on first attempt */
            if(!firstIteration) {
                /* Give the writer a chance to finish */
                QThread::yieldCurrentThread();
            } else firstIteration = false;

            memcpy(result,&this->state,sizeof(T));
            seq_after = this->seqNumber.fetchAndAddOrdered(0);
            seq_changed = (seq_before!=seq_after);
        }
    }

    bool isInitialized() {  return (seqNumber>0); }

private:
    QAtomicInt seqNumber;
    T state;
} ;

#endif // ONEWRITERATOMICSTATE_H
4

3 に答える 3

2

アルゴリズムは完全には正しくありません。リーダーが一貫性のないデータを取得する場合に考えられるスレッドのインターリーブの 1 つを次に示します。

state initialized to {0,0} and seqNumber to 0

Writer:
seqNumber = 1;
state.x = 1;

Reader:
seq = seqNumber; //1
result = state; //{1,0}
seq_changed = (seqNumber != seq); //false

Writer:
state.y = 1;
seqNumber = 2;

Reader:
jumps back to the start of the loop
seq = seqNumber; //2
steps out of the loop because seq == 2 and seq_changed == false

したがって、問題はseqNumber2 つの場所で読み取られ、ライターが読み取りの間に値を更新する可能性があることです。

while( (seq=this->seqNumber.fetchAndAddOrdered(0)) & 0x01 || seq_changed ) {
    result = this->state;
    seq_changed = (this->seqNumber.fetchAndAddOrdered(0)!=seq);
    //If writer updates seqNumber here to even number bad things may happen
}

反復ごとに 1 回だけ読み取る必要があります。

T getState(){
    T result;
    int seq;
    int newseq = seqNumber.fetchAndAddOrdered(0);
    bool seq_changed = true;

    while( (seq = newseq) & 0x01 || seq_changed ) {
        result = state;
        newseq = seqNumber.fetchAndAddOrdered(0);
        seq_changed = (newseq != seq);
    }
    return result;
}

これは正しく動作するはずですが、何も保証しません。:) 少なくとも、例のようなテストプログラムを作成する必要がありますが、リーダーに矛盾する値のチェックを追加する必要があります。

考慮すべきことの 1 つは、アトミック インクリメント (fetchAndAdd) を使用することは、一種のやり過ぎだということです。スレッド書き込みは 1 つしかないseqNumberため、単純なアトミック ストア リリース操作とロード アクワイア操作で実行でき、多くのプロセッサではるかに高速に実装できます。QAtomicIntただし、これらの操作が;で可能かどうかはわかりません。ドキュメントはそれについて非常に不明確です。

編集:そして wilx が正しい、T は自明にコピー可能な型である必要があります

于 2012-04-18T18:56:52.577 に答える
1

優先度ベースのスレッド スケジューリングがあり、リーダーの優先度がライターよりも高い場合、ライブロックが発生する可能性があります。ライターが値の書き込みを開始し、リーダーがアクティブな待機を行っていると想像してください。リーダーの優先順位が高いため、ライターが書き込みを完了するチャンスはありません。

解決策は、待機ループにわずかな遅延を追加することです。

于 2012-04-18T19:32:24.660 に答える
1

Tこれは、のコピー代入演算子がプリミティブで、基本的にビットごとのコピーのみを行う場合にのみ機能すると思います。さらに複雑なT場合は、 の実行中に一貫性のない状態になる可能性がありresult = this->state;ます。

したがって、ライターの好みである種の rwlocks を使用することをお勧めします。

于 2012-04-18T14:27:35.523 に答える