1

非常に優れた Bounded MPMC キュー ソースを

http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue

テストは非常に簡単です。

mpmc_bounded_queue<string> mq(8) ;

for(int idx=0;idx<10;idx++)
{
    string s = to_string(idx);
    if(mq.enqueue(s))
        cout << s << " ok" << endl ;
    else
        cout << s << " not ok" << endl ;
}

string strx;    
if(mq.dequeue(strx))
{
    cout << "The dequeue value=" << strx << endl ;
}else{
    assert(1 == 2) ;
}

string s = "THE END" ;
if(mq.enqueue(s))
    cout << s << " ok" << endl ;
else
    cout << s << " not ok" << endl ;

このコードを調べた後、このソースを正しく使用できるかどうかを確認したいと思います。セマフォを待機しているスレッド C が 1 つあるとします。起動後 (セマフォ >0)、スレッド C は dequeue 関数を呼び出してキューからデータを取得します。 !! スレッド A とスレッド B は、1 つのデータ、セマフォ + 1 を挿入した後、エンキュー関数を呼び出します。したがって、スレッド A とスレッド B がキューに 10 回エンキューすると、セマフォは 10 になり、スレッド C は 10 回デキューできるはずです。これまでのところ完璧に動作します!!!

しかし、私が思うことが1つ起こるかもしれません! ... スレッド A とスレッド B がまったく同時にエンキューするとします。Compare-And-Swap の後、スレッド A は buffer[0] を埋め、スレッド B は buffer[1] を埋め、スレッド A はエンキューを終了せず、スイッチアウトします。オペレーティング システムによって、したがって Buffer[0] の sequence_ は変更されず、スレッド B はエンキューを終了し、セマフォを増やします。この時点で、スレッド A はバッファ [0] を終了せず、スレッド B はバッファ [1] を終了し、スレッド c は目覚めましたセマフォ = 1 であるため、スレッド C はデキューし、準備ができていない buffer[0] にアクセスしようとするため、デキューは false を返します。つまり、スレッド C は次のように実装する必要があります。

Right !!

while(1){
    sem_wait(sem1) ;
    while(1){
        if(mq.dequeue(strx))
            break ;
    }
    //doing something about strx
}

=====================================

Wrong !!

while(1){
    sem_wait(sem1) ;
    mq.dequeue(strx) ;
    //doing something about strx
}
=====================================

私のポイントは、スレッド C が目覚めたことは、キューに入れられた新しいデータがあることを意味しますが、 buffer[dequeue_pos_] の位置にない可能性があるため、デキュー関数を無限ループに入れると役立ちます!!!!

私はこの実装で正しいですか? つまり、 buffer[0] の前に buffer[1] がいっぱいになる可能性があり、スレッド C が buffer[0] をデキューしようとして失敗しました。スレッド A はオペレーティング システムによって切り替えられ、バッファ [0] がいっぱいになりました。スレッド C はループを破ります!!

どんな提案、コメントも大歓迎です!!!

4

0 に答える 0