std :: list thread_safety

Question

1. 我有一个列表,其中一个线程只是push_back和其他线程偶尔循环遍历列表并打印所有元素.在这种情况下我需要锁吗？

2. 我有指向其他对象中的元素的指针.有安全感吗？我知道当需要更多空间时,向量将移动所有对象,因此指针将无效.

   mylist.push_back(MyObj中(1));
   if(someCond)
   {_
   myLastObj =&mylist.back();
   }

_myLastObj 是类型的 MyObj*

如果我使用了一个向量,该对象将被移动到另一个位置,指针将指向垃圾.列表是否安全？

Answer 1

1. 是的,你需要一个锁(某种形式的同步).
2. std::list仅当从列表中删除相同的元素时,指向a元素的指针才会失效.由于您的代码永远不会从列表中删除任何内容,因此您的指针是安全的.

有关您需要锁定的具体原因,请考虑list::push_back以下顺序执行以下操作:

1. 分配一个新节点,
2. 将列表尾部的"next"指针设置为新节点,
3. 将新节点的"next"指针设置为null(或其他一些end-of-list-marker),
4. 将新节点的"previous"指针设置为前一个尾部,
5. 将列表自己的指针设置为新节点.

如果您的阅读器线程介于2和3之间,那么它将从前一个尾部转到新节点,然后尝试跟随未初始化的指针.繁荣.

通常,您需要同步,因为这是保证在编写器线程中所做的更改以任何合理顺序(或根本)发布到读取器线程的唯一方法.

如果你想象不同的线程在不同的行星上运行,你的代码应该是正确的,每个行星都有自己的程序内存副本,并且在你使用同步对象(或C++ 11中的原子变量)时相互传递变化(a) ),加上(b)当你不使用同步对象但传输某些特定的部分更改会破坏你的代码(例如双字对象的一半,或者在这种情况下,你需要发生两个指针写入之一)按特定顺序).有时这个模型比严格必要的更保守,导致代码更慢.但是较不保守的模型依赖于线程系统和内存模型的特定于实现的细节.

Answer 2

我想知道列表是否是线程安全的，所以我问并找到了这个线程。我得出的结论是，在目前gcc libstdc++中std::list的实现中，你可以安全地在一个线程中修改一个列表，并任意并发地遍历列表，但不敢有两个线程修改相同的列表（没有同步）。 此外，不应依赖此行为。我已经撕掉了库代码以更详细地指出问题。我希望它有帮助。

首先让我们从列表的线程安全的一般问题开始。我认为通过示例“证明”列表是不安全的会很好，所以我将以下代码放在一起。

#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 并获得了我想要的结果。对于任何试图复制实验的人来说，这只是一个注意事项，它可能工作或不工作取决于系统配置和调度算法等。

鉴于链表的性质，我预计这样的实验会导致段错误或以其他方式损坏的列表。如果这是您正在寻找的某些错误的原因，那么段错误将是一种怜悯。

到底他妈发生了什么

在这里，我将准确地解释发生了什么以及为什么（或者至少给出一个非常合理的解释）。如果您未初始化并发问题，请考虑这是一个介绍。如果您是专家，请告诉我我哪里错了或不完整。

我很好奇，所以我只看了 gcc libstdc++ 实现。为了解释观察到的行为，对列表如何工作的快速解释是有序的。

实施细则

底层结构或算法没有什么有趣或奇怪的地方，但有各种 C++ 实现细节需要提及。首先，链表的节点都派生自一个只存储两个指针的公共基类。这样，列表的所有行为都被封装了。除了从基派生之外，实际节点是具有非静态数据成员的结构__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）。然后列表处理构造和销毁，并为库用户提供接口，等等。

为节点使用公共（类型无知）基类的一个主要优点是您可以将任意节点链接在一起。如果鲁莽地放弃，这不是很有帮助，但他们以受控的方式使用它。“尾节点”不是 type value_type，而是 type size_t。尾节点保存列表的大小！（我花了几分钟才弄清楚发生了什么，但它很有趣所以没什么大不了的。这样做的主要优点是存在的每个列表都可以具有相同类型的尾节点，因此代码重复较少用于处理尾节点，并且列表只需要一个非静态数据成员来完成它需要做的事情）。

因此，当我将节点推送到列表的后面时，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）。我在网上找不到好看的图片，所以可以说是尾巴，是“背部”，我们想推到后面。也就是说，我们有 list (fragment) ，我们想要. 最后，呼吁上，然后会发生以下情况：_M_hook()_M_inc_size()TB1B <-> TB <-> 1 <-> T1_M_hookT

1. 1 指向 T
2. 1 向后指向 B
3. B 指向 1
4. T 向后指向 1

这样，就不会“忘记”任何位置。现在说，1并2在同一列表的不同线程中被推回。完全有可能的是，步骤 (1) 和 (2) 完成1，然后2被完全推回，那么 (1) 必须完成。在这种情况下会发生什么？我们有 list B <-> 2 <-> T，但1指向Band T，所以当它们的指针被调整时， list 看起来像B <-> 1 <-> T，这是一个内存泄漏的儿子。

就迭代而言，向后或向前并不重要，您将始终正确地通过列表递增。然而，这种行为似乎不受标准的保证，所以如果代码依赖于这种行为，它就很脆弱。

尺码呢？？？

好的，这就像是并发 101，一个老故事可能讲得更好很多次，我希望它至少值得看一下库代码。我认为尺寸问题更有趣一点，我当然从解决这个问题中学到了一些东西。

基本上，因为递增的值不是“局部”变量，所以必须将其值读入寄存器，将一个值加到该值上，然后将该值存储回变量中。来看看一些组装（我的组装游戏很弱，有更正的请不要客气）。考虑以下程序：

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>，但是这个该死的东西已经太长了。