0

わかりました、最近、私はスレッド セーフについてよく考えていて、なぜリンク リストや両端キューがスレッド セーフではないのか疑問に思っていました。

次のような単純なリンク リスト クラスがあるとします。

class myLinkedList {
private:
    myLinkedList* next;
    int m_value;

public:
    myLinkedList() { next = NULL; m_value = 0; }
    void setValue(int value) { m_value = value; }
    int getValue() { return m_value; }
    void addNext(int value) { next = new myLinkedList; next->setValue(value); }
    myLinkedList* getNext() { return next; }
};

ここで、最後に新しい要素を追加し、最初に要素を削除します (最初に要素を読み取ってから削除します)。基本的に、最初の のアドレスを取得し、最初の要素を削除して、 を新しい最初の要素としてnext記憶します。next新しい要素を追加する場合、最後の要素のみを覚えています。新しい要素を追加するときは、新しい要素を設定し、新しい要素を最後の要素としてnext覚えていnextます。

このシナリオでのスレッドの問題はどこにありますか? ライターとリーダーは、互いにやり取りすることはないため、これに関して問題はないはずです。配列やベクトルを使用するのとは異なります (問題が発生する理由がよくわかります)。

4

4 に答える 4

5

あなたの質問へのコメントは正しいです。実装は機能しません。ただし、実際の質問に答えるために、コード内の競合状態を次に示します。

void addNext(int value) { next = new myLinkedList; next->setValue(value) }

スレッド A が実行されると想像してください。

next = new myLinkedList;

ここで、スレッド A が横取りされ、スレッド B も同じ命令を実行します。これは、nextスレッド A がポイントしたい場所をポイントするのではなく、スレッド B が設定した場所をポイントするようになったことを意味します。スレッド B は次のように実行を続けます。

next->setValue(value)

その後すぐに (または同時に)、スレッド A も上記を実行します。

問題が見えますか？スレッド A がnext->setValue()Bnextを呼び出し、Anextが失われます。

于 2012-10-20T17:52:28.743 に答える
1

最も基本的なエクササイザー プログラムに変換された、質問で指定されたコードを次に示します。

class myLinkedList {
private:
    myLinkedList* next;
    int m_value;

public:
    myLinkedList() : next(0), m_value(0) { }
    int  getValue() const { return m_value; }
    void setValue(int value) { m_value = value; }
    void addNext(int value) { next = new myLinkedList; next->setValue(value); }
    const myLinkedList *getNext() const { return next; }
};

#include <iostream>

static void print_list(const myLinkedList *rover)
{
    std::cout << "List:";
    while (rover != 0)
    {
        std::cout << " " << rover->getValue();
        rover = rover->getNext();
    }
    std::cout << std::endl;
}

int main()
{
    myLinkedList mine;
    print_list(&mine);
    mine.addNext(13);
    print_list(&mine);
    mine.addNext(14);
    print_list(&mine);
    mine.setValue(3);
    print_list(&mine);
    mine.addNext(15);
    print_list(&mine);
}

このプログラムの出力は次のとおりです。

List: 0
List: 0 13
List: 0 14
List: 3 14
List: 3 15

ご覧のとおり、これは通常のリンク リストではありません。これは、最大 2 つの項目のリストです。の下でプログラム (llリンクされたリストに対して呼び出される) を実行すると、次のvalgrindようになります。

==31288== Memcheck, a memory error detector
==31288== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==31288== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==31288== Command: ll
==31288== 
List: 0
List: 0 13
List: 0 14
List: 3 14
List: 3 15
==31288== 
==31288== HEAP SUMMARY:
==31288==     in use at exit: 6,239 bytes in 36 blocks
==31288==   total heap usage: 36 allocs, 0 frees, 6,239 bytes allocated
==31288== 
==31288== LEAK SUMMARY:
==31288==    definitely lost: 48 bytes in 3 blocks
==31288==    indirectly lost: 0 bytes in 0 blocks
==31288==      possibly lost: 0 bytes in 0 blocks
==31288==    still reachable: 6,191 bytes in 33 blocks
==31288==         suppressed: 0 bytes in 0 blocks
==31288== Rerun with --leak-check=full to see details of leaked memory
==31288== 
==31288== For counts of detected and suppressed errors, rerun with: -v
==31288== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 1 from 1)

コードが機能するリンク リストの実装である場合、 でタイミングの問題が発生しaddNext()ます。

基本的に、でノードを作成し、newそれをリストにフックする必要があります。別のスレッドが同時にそれを行おうとすると、タイミング ウィンドウが発生し、構造の一貫性が失われる可能性があります。スレッド セーフのために、リストの変更中に相互排除を確保する必要があります。

于 2012-10-20T17:58:02.943 に答える
1

複数のスレッド内で共有されているコンテナー (またはその他のもの) のクラス インスタンスを使用している場合はstd::list、ミューテックスまたは同様のメカニズムを使用して同時アクセスを保護し、スレッドの保存動作を取得する必要があります。

アップデート

あなたが示すように構築します

 void setValue(int value) { m_value = value; }
 int getValue() { return m_value; }
 void addNext(int value) { next = new myLinkedList; next->setValue(value); }

アトミック操作ではありません。したがって、保護されたコンテキスト内で使用されない限り、これらはスレッドセーフではありません。のような STL コンテナについても同じことが言えますstd::list。

于 2012-10-20T17:46:44.457 に答える
0

一見単純に見えるものには、いくつかのスレッドセーフの問題があります。

next = new myLinkedList;

ハードウェアによっては、への割り当てがnextスレッド スイッチによって引き裂かれる場合があります。つまり、値の一部が書き込まれる可能性があり、残りの値が書き込まれる前にプロセッサが別のスレッドに変更されます。別のスレッドは、ガベージである値を参照します。

next複数のプロセッサでは、ストアを実行するプロセッサのローカル キャッシュに割り当てられた値が書き込まれるという追加の問題があります。他のプロセッサには独自のキャッシュがあるため、新しい値が表示されない場合があります。または、それは見えても、 への呼び出しによって書き込まれたnew myLinkedList値、またはによって書き込まれた値が表示されない可能性がありますnext->setValue(value);。

または、何か他の問題が発生する可能性があります。

別のスレッドが同じデータ位置の読み取りまたは書き込みを行っているときに、あるスレッドからデータ位置に書き込むことはデータ競合であり、データ競合のあるプログラムの動作は未定義です。実際には、最も重要な顧客のためにプログラムのデモを行うまでは問題なく動作し、プログラムが見事にクラッシュすることを意味します。

于 2012-10-20T18:12:44.067 に答える