5

ロックフリーのデータ構造を開発すると、次の問題が発生します。

ヒープ上にオブジェクトを作成し、それらを参照カウンター付きのスマート ポインターにラップするライター スレッドがあります。また、これらのオブジェクトを操作するリーダー スレッドも多数あります。コードは次のようになります。

SmartPtr ptr;

class Reader : public Thread {
    virtual void Run {
       for (;;) {
           SmartPtr local(ptr);
           // do smth   
       }
    }   
};

class Writer : public Thread {
    virtual void Run {
       for (;;) {
           SmartPtr newPtr(new Object);    
           ptr = newPtr;  
       }
    }
};

int main() {
    Pool* pool = SystemThreadPool();
    pool->Run(new Reader());
    pool->Run(new Writer());
    for (;;) // wait for crash :(
}

スレッドローカルコピーを作成ptrすると、少なくとも

  1. アドレスを読み取ります。
  2. 参照カウンターをインクリメントします。

これら 2 つの操作をアトミックに実行できないため、リーダーが削除されたオブジェクトを操作することがあります。

問題は、正しいメモリ管理を可能にして複数のスレッドから読み取り/書き込みアクセスを可能にするために、どのような種類のスマート ポインターを使用する必要があるかということです。Java プログラマーはそのような問題を気にすることさえなく、すべてのオブジェクトが参照であり、誰もそれらを使用しない場合にのみ削除されることに単純に依存しているため、解決策が存在するはずです。

PowerPC についてはhttp://drdobbs.com/184401888を見つけました。見栄えは良いのですが、x86 にはない Load-Linked 命令と Store-Conditional 命令を使用しています。

私が理解している限り、ブースト ポインターは、ロックを使用してのみそのような機能を提供します。ロックフリーのソリューションが必要です。

4

4 に答える 4

9

boost::shared_ptr には、考えられるケースの 99% に対して十分に高速な「ロックフリー」スピンロックを使用する atomic_store があります。

    boost::shared_ptr<Object> ptr;
class Reader : public Thread {
    virtual void Run {
       for (;;) {
           boost::shared_ptr<Object> local(boost::atomic_load(&ptr));
           // do smth   
       }
    }   
};

class Writer : public Thread {
    virtual void Run {
       for (;;) {
           boost::shared_ptr<Object> newPtr(new Object);    
           boost::atomic_store(&ptr, newPtr);
       }
    }
};

int main() {
    Pool* pool = SystemThreadPool();
    pool->Run(new Reader());
    pool->Run(new Writer());
    for (;;)
}

編集：

以下のコメントに応えて、実装は「boost/shared_ptr.hpp」にあります...

template<class T> void atomic_store( shared_ptr<T> * p, shared_ptr<T> r )
{
    boost::detail::spinlock_pool<2>::scoped_lock lock( p );
    p->swap( r );
}

template<class T> shared_ptr<T> atomic_exchange( shared_ptr<T> * p, shared_ptr<T> r )
{
    boost::detail::spinlock & sp = boost::detail::spinlock_pool<2>::spinlock_for( p );

    sp.lock();
    p->swap( r );
    sp.unlock();

    return r; // return std::move( r )
}
于 2011-11-04T09:42:52.413 に答える
4

InterlockedCompareExchange128 を使用してこれを達成できるはずです。参照カウントとポインターを 2 要素の __int64 配列に格納します。参照カウントが配列 [0] にあり、ポインターが配列 [1] にある場合、アトミック更新は次のようになります。

while(true)
{
    __int64 comparand[2];
    comparand[0] = refCount;
    comparand[1] = pointer;
    if(1 == InterlockedCompareExchange128(
        array,
        pointer,
        refCount + 1,
        comparand))
    {
        // Pointer is ready for use. Exit the while loop.
    }
}

お使いのコンパイラで InterlockedCompareExchange128 組み込み関数を使用できない場合は、アセンブリ言語をいじっても構わなければ、基になる CMPXCHG16B 命令を代わりに使用できます。

于 2011-11-04T10:04:00.670 に答える
2

RobH によって提案されたソリューションは機能しません。元の質問と同じ問題があります。参照カウント オブジェクトにアクセスすると、既に削除されている可能性があります。

グローバル ロック (boost::atomic_store など) または条件付きの読み取り/書き込み命令を使用せずに問題を解決する唯一の方法は、オブジェクト (または共有参照カウント オブジェクトが使用されている場合) の破棄を何らかの形で遅らせることです。つまり、zennehoy には良いアイデアがありますが、彼の方法は安全ではありません。

私がそれを行う方法は、ライターがオブジェクトの破棄を制御できるように、すべてのポインターのコピーをライター スレッドに保持することです。

class Writer : public Thread {
    virtual void Run() {
        list<SmartPtr> ptrs; //list that holds all the old ptr values        

        for (;;) {
            SmartPtr newPtr(new Object);
            if(ptr)
                ptrs.push_back(ptr); //push previous pointer into the list
            ptr = newPtr;

            //Periodically go through the list and destroy objects that are not
            //referenced by other threads
            for(auto it=ptrs.begin(); it!=ptrs.end(); )
                if(it->refCount()==1)
                    it = ptrs.erase(it);
                else
                    ++it;
       }
    }
};

ただし、スマート ポインター クラスにはまだ要件があります。読み取りと書き込みはアトミックではないため、これは shared_ptr では機能しません。boost::intrusive_ptr でほぼ動作します。intrusive_ptr の割り当ては、次のように実装されます (疑似コード):

//create temporary from rhs
tmp.ptr = rhs.ptr;
if(tmp.ptr)
    intrusive_ptr_add_ref(tmp.ptr);

//swap(tmp,lhs)
T* x = lhs.ptr;
lhs.ptr = tmp.ptr;
tmp.ptr = x;

//destroy temporary
if(tmp.ptr)
    intrusive_ptr_release(tmp.ptr);

私が理解している限りでは、ここに欠けているのは、コンパイラ レベルのメモリ フェンスの前だけlhs.ptr = tmp.ptr;です。それを追加すると、読み取りrhsと書き込みの両方lhsが厳密な条件下でスレッドセーフになります: 1) x86 または x64 アーキテクチャ 2) アトミック参照カウント 3)rhs割り当て中に refcount がゼロになってはならない (上記の Writer コードによって保証される) 4) のみ1 つのスレッドに書き込みlhsます (CAS を使用すると、複数のライターを持つことができます)。

とにかく、必要な変更を加えて intrusive_ptr に基づいて独自のスマート ポインター クラスを作成できます。shared_ptr を再実装するよりも確実に簡単です。さらに、パフォーマンスが必要な場合は、侵入型が最適です。

于 2011-11-04T21:11:53.823 に答える
-2

これが Java でより簡単に機能する理由は、ガベージ コレクションです。C++ では、値を削除するときに、値が別のスレッドによって使用され始めたばかりではないことを手動で確認する必要があります。

同様の状況で私が使用した解決策は、単に値の削除を遅らせることです。削除するもののリストを反復処理する別のスレッドを作成します。何かを削除したいときは、タイムスタンプを付けてこのリストに追加します。削除スレッドは、実際に値を削除する前に、このタイムスタンプから一定時間経過するまで待機します。値の一時的な使用が完了したことを保証するのに十分な遅延があることを確認する必要があります。

私の場合は 100 ミリ秒で十分だったので、安全のために数秒を選びました。

于 2011-11-04T09:52:02.027 に答える