3

私は、C++ 11 の Anthony Williams Concurrency book に取り組んでいます。

ロックフリースタックの pop 実装に少し混乱しています。

template<typename T>
class lock_free_stack
{
private:
struct node
{
    std::shared_ptr<T> data;
    node* next;
    node(T const& data_): data( std::make_shared<T>(data_)){}
};

std::atomic<node*> head;

public:

void push(T const& data)
{
    node* const new_node = new node(data);
    new_node->next = head.load();
    while(!head.compare_exchange_weak(new_node->next, new_node));
}

std::shared_ptr<T> pop()
{
    node* old_head = head.load();
    while( old_head && !head.compare_exchange_weak(old_head, old_head->next));

            // Does This not return the data of the next node before the head if 
            // compare_exchange_weak returns true
    return old_head ? old_head->data : std::shared_ptr<T>();
}
};

私を混乱させているのは pop 関数の最後の 2 行です。

    while( old_head && !head.compare_exchange_weak(old_head, old_head->next));
    return old_head ? old_head->data : std::shared_ptr<T>();

true を返した場合、compare_exchange_weak 関数は old_head をスタック内の次のノードに変更しませんか? これにより、old_head が nullptr でない場合、return ステートメントはスタックの一番上にある古いヘッドではなく、次のノードからデータを返します。

これを間違って解釈しましたか?

4

2 に答える 2

3

私のコメントとは別に、compare_exchange_weak が成功しheadた場合、値から値old_headへの更新に成功したold_head->nextため、old_head はリストの一部ではなくなり、正しく返すことができます。

falseの値を変更することを返す場合のみold_head

編集:上記のコードの問題を示しています。

まず、2 つのスレッドが入り、両方とも( 経由で)pop読み取り、同じ値を取得する場合headhead.load()old_head

スレッド 1 がスワップ アウトされます (たとえば)

スレッド 2 は実行を続け、ヘッドをポップして呼び出し元に戻り、呼び出し元はノードを保持している値を削除します。

その後、スレッド 1 が再開され、compare_exchange_weakを呼び出すold_head->nextために読み取りを試みます。

ただし、old_head は削除されたメモリを指します。未定義の動作です。segfault できればラッキーです。

第二に、これには古典的な ABA 問題があります。十分に文書化され、理解されているので、わざわざ説明するつもりはありません。それを検索します。

于 2013-06-24T18:48:36.237 に答える
1

head.compare_exchange_weak戻るときfalseに変更しold_headます。

戻るときは修正しtrue、修正headしませんold_head。

http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchangeおよび/またはhttp://cpp0x.centaur.ath.cx/atomics.types.operations.req.html#p21を参照してください。

于 2013-06-24T18:47:57.520 に答える