他のオブジェクトの要素へのポインタがあります。持っていても大丈夫ですか？より多くのスペースが必要な場合、vectorはすべてのオブジェクトを移動するため、ポインターは無効になります。
mylist.push_back（MyObj（1））;
if（someCond）
{
_myLastObj =＆mylist.back（）;
}
_myLastObjタイプですMyObj*
ベクトルを使用した場合、オブジェクトは別の場所に移動され、ポインターはゴミを指します。リストで安全ですか？
std::list、同じ要素がリストから削除された場合にのみ無効になります。コードがリストから何も削除しないため、ポインターは安全です。ロックが必要な具体的な理由から、たとえばlist::push_back、次の順序で実行が許可されていることを考慮してください。
リーダースレッドが2から3の間にある場合、それは前のテールから新しいノードに移動し、初期化されていないポインターをたどろうとします。ブーム。
ただし、一般的には、同期が必要です。これは、ライタースレッドで行われた変更が、あらゆる種類の適切な順序で（またはまったく）リーダースレッドに公開されることを保証する唯一の方法だからです。
異なるスレッドが異なる惑星で実行され、それぞれがプログラムのメモリの独自のコピーを持ち、同期オブジェクト（またはC ++ 11のアトミック変数）を使用するときに相互に変更を送信することを想像する場合、コードは正しいはずです。 ）、さらに（b）同期オブジェクトを使用しないが、特定の部分的な変更を送信すると、コードが破損します（2ワードオブジェクトの半分、この場合は、発生する必要のある2つのポインター書き込みの1つなど）。特定の順序で）。このモデルは、厳密に必要なものよりも保守的であり、コードが遅くなる場合があります。ただし、それほど保守的ではないモデルは、スレッドシステムとメモリモデルの実装固有の詳細に依存しています。
リストが一般的にスレッドセーフであるかどうかを知りたかったので、このスレッドを尋ねて見つけました。私が得た結論は、gcclibstdc++のstd::listの現在の実装では、1つのスレッドでリストを安全に変更し、リストを同時に任意に反復することができますが、2つのスレッドを変更する必要はありません。同じリスト（同期なし）。 さらに、この動作に依存するべきではありません。問題をもう少し詳しく指摘するために、ライブラリコードをリッピングしました。お役に立てば幸いです。
まず、リストのスレッドセーフに関する一般的な質問から始めましょう。例としてリストが安全でないことを「証明」するといいと思ったので、次のコードを一緒に投げました。
#include <iostream>
#include <list>
#include <mutex>
#include <thread>
using namespace std;
list<int> unsafe_list;
class : public list<int> {
mutex m;
public:
void push_back(int i) {
lock_guard<mutex> lock{m};
list<int>::push_back(i);
}
} safe_list;
template <typename List> void push(List &l) {
for (auto i = 0; i < 10000; ++i)
l.push_back(0);
}
void report_size(const list<int> &li, char const *name) {
size_t count{};
for (auto && i : li) ++count;
cout << name << endl;
cout << "size() == " << li.size() << endl;
cout << "count == " << count << endl;
}
int main() {
auto unsafe = []() { push(unsafe_list); };
auto safe = []() { push(safe_list); };
thread pool[]{
thread{unsafe}, thread{unsafe}, thread{unsafe},
thread{safe}, thread{safe}, thread{safe},
};
for (auto &&t : pool)
t.join();
report_size(unsafe_list, "unsafe_list");
report_size(safe_list, "safe_list");
}
私が得た出力は次のとおりです。
unsafe_list
size() == 19559
count == 390
safe_list
size() == 30000
count == 30000
うわぁ。つまり、私がプッシュした要素がリストに含まれることはほとんどありませんでした。しかし、それよりも悪いです！要素の数が適切でないだけでなく、実際とは異なる数であると考えられ、その数も私が望むものではありません。これはほぼ確実にメモリリークがあることを意味しますが、valgrindを使用して実行すると、すべての操作が正常に完了しました。valgrindやその他のツールは、並行性を処理しようとするときに役に立たないと聞いていますが、これはその証拠だと思います。
最初は一度に10個程度押してみましたが、怪しいことは何もありませんでした。タイムスライス内ですべてをプッシュすることができたと思ったので、10000に上げて、希望する結果を得ました。実験を複製しようとしている人へのメモですが、システム構成やスケジューリングアルゴリズムなどによっては、機能する場合と機能しない場合があります。
リンクリストの性質を考えると、私はそのような実験がセグメンテーション違反またはその他の方法で破損したリストになることを期待していました。これがあなたが探していたバグの原因である場合、セグメンテーション違反は慈悲になります。
ここでは、何が起こったのか、そしてその理由を正確に説明します（または少なくとも非常に説得力のある説明をします）。並行性の問題に初期化されていない場合は、これをイントロと見なしてください。あなたが専門家なら、私が間違っているか不完全なところを教えてください。
興味があったので、gcclibstdc++の実装を見ました。観察された動作を説明するために、リストがどのように機能するかを簡単に説明します。
基礎となる構造やアルゴリズムについては、興味深いことや奇妙なことは何もありませんが、言及する必要のあるさまざまなC++実装の詳細があります。まず、リストのノードはすべて、2つのポインターのみを格納する共通の基本クラスから派生します。このようにして、リストのすべての動作がカプセル化されます。ベースから派生する以外の実際のノードは、非静的データメンバーを持つ構造体__gnu_cxx::__aligned_membuf<_Tp> _M_storageです。これらのノードはリストのを認識しており、リバウンドからvalue_type派生します。allocator_type_List_node<_Tp>。これらのノードの目的は、リストのストレージを取得および解放し、それらのベースを使用してデータの構造を維持することです。（タイプがイテレータからどのように除外されるかを説明するために、このペーパーをお勧めします。特定のものがhttp://www.stroustrup.com/SCARY.pdfのように実装される理由に光を当てる可能性があります。このウィザードがc++アロケータである美しい悪夢を説明するのを見てくださいhttps://www.youtube.com/watch?v=YkiYOP3d64E）。次に、リストは構築と破棄を処理し、ライブラリユーザーにインターフェイスを提供します。
ノードに共通の（タイプを無視する）基本クラスを使用する主な利点は、任意のノードをリンクできることです。これは、無謀な放棄で行われた場合はあまり役に立ちませんが、制御された方法で使用します。「テールノード」はタイプvalue_typeではなく、タイプsize_tです。テールノードはリストのサイズを保持します！（何が起こっているのかを理解するのに数分かかりましたが、面白かったので大したことはありませんでした。これの主な利点は、存在するすべてのリストが同じタイプのテールノードを持つことができるため、コードの重複が少なくなることです。テールノードを処理するためのものであり、リストは、必要なことを実行するために1つの非静的データメンバーのみを必要とします）。
したがって、ノードをリストの最後にプッシュすると、end()イテレーターは次の関数に渡されます。
template<typename... _Args>
void
_M_insert(iterator __position, _Args&&... __args)
{
_Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
__tmp->_M_hook(__position._M_node);
this->_M_inc_size(1);
}
_M_create_node()最終的には、適切なアロケータを使用してノードのストレージを取得し、提供された引数を使用してそこに要素を構築しようとします。関数の「ポイント」は、ポインターが指す必要の_M_hook()あるポインターへのポインターを指すことであり、ここにリストされています。
void
_List_node_base::
_M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT
{
this->_M_next = __position;
this->_M_prev = __position->_M_prev;
__position->_M_prev->_M_next = this;
__position->_M_prev = this;
}
ポインタを操作する順序は重要です。 これが、リストを同時に操作しながら反復できると私が主張する理由です。これについては後で詳しく説明します。次に、サイズが調整されます。
void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += __n; }
前に述べたように、リストにはタイプのテールノードがあるsize_tため、ご想像のとおり_M_impl._M_node._M_valptr()、この番号へのポインタを取得し+=て、適切な量にします。
それで、何が起こっているのですか？スレッドは、および関数でデータ競合（https://en.cppreference.com/w/cpp/language/memory_model）に参加しています。オンラインで素敵な写真を見つけることができないので、それが尻尾であり、「後ろ」であり、後ろに押したいとしましょう。つまり、リスト（フラグメント）があり、が必要です。最終的に、を呼び出すと、次のようになります。_M_hook()_M_inc_size()TB1B <-> TB <-> 1 <-> T1_M_hookT
1に転送するT1後ろ向きBBに転送する1T後ろ向き1このようにして、場所が「忘れられる」ことはありません。今、それを言って1、2同じリストの異なるスレッドにプッシュバックされています。手順（1）と（2）が完了し1、2完全に押し戻されてから、（1）が終了する必要があることは完全に妥当です。この場合はどうなりますか？リストはありますB <-> 2 <-> Tが、と1を指しているので、ポインターを調整すると、リストはのようになります。これはメモリリークの息子です。BTB <-> 1 <-> T
反復する限り、前後に移動するかどうかは関係ありません。常にリストを適切にインクリメントします。この動作は標準では保証されていないようですが、コードがこの動作に依存している場合は脆弱です。
さて、それは並行性101のようなもので、古い話はおそらく何度もよく語られています。少なくともライブラリコードを見る価値があることを願っています。サイズの問題はもう少し面白いと思います、そして私は確かにそれを理解することから何かを学びました。
基本的に、インクリメントされる値は「ローカル」変数ではないため、その値をレジスタに読み込んで、その値に1を加算してから、その値を変数に格納し直す必要があります。いくつかのアセンブリを見てみましょう（私のアセンブリゲームは弱いです、修正があればいいことはしないでください）。次のプログラムを検討してください。
int i{};
int main() {
++i;
}
オブジェクトに対してobjdump-Dを実行すると、次のようになります。
Disassembly of section .text:
0000000000000000 <main>:
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 8b 05 00 00 00 00 mov 0x0(%rip),%eax # a <main+0xa>
a: 83 c0 01 add $0x1,%eax
d: 89 05 00 00 00 00 mov %eax,0x0(%rip) # 13 <main+0x13>
13: b8 00 00 00 00 mov $0x0,%eax
18: 5d pop %rbp
19: c3 retq
4:の値iをレジスタに移動しますeax。 0x1に追加されてからeax、eaxに戻されiます。では、これはデータの競合と何の関係があるのでしょうか？リストのサイズを更新する関数をもう一度見てください。
void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += __n; }
リストの現在のサイズがレジスタにロードされ、このリストを操作している別のスレッドが操作を実行することは完全に妥当です。したがって、リストの古い値がレジスタに格納されていますが、その状態を保存して、制御を他の誰かに移す必要があります。たぶん、彼らはリストにアイテムを正常に追加し、サイズを更新してから、私たちに制御を戻します。状態を復元しますが、状態は無効になります。リストの古いサイズがあり、それをインクリメントして、その値をメモリに戻し、他のスレッドが実行した操作を忘れます。
i前述したように、上記のプログラムではの「局所性」が作用しました。これの重要性は次のように見ることができます：
int main() {
int i{};
++i;
}
Disassembly of section .text:
0000000000000000 <main>:
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: c7 45 fc 00 00 00 00 movl $0x0,-0x4(%rbp)
b: 83 45 fc 01 addl $0x1,-0x4(%rbp)
f: b8 00 00 00 00 mov $0x0,%eax
14: 5d pop %rbp
15: c3 retq
ここでは、値がレジスタに格納されておらず、レジスタが変数にプッシュされていないことがわかります。残念ながら、私が知る限り、これは同時実行性の問題を回避するための良いトリックではありません。同じ変数を操作する複数のスレッドは、レジスターだけでなく、メモリアクセスを介して操作する必要があるためです。私はここですぐにリーグから抜け出しますが、それは事実だと確信しています。次善の策は使用することですatomic<int>が、このいまいましいことはすでに長すぎます。