std::forward_list::insert_after 线程安全

std::forward_list::insert_after thread safety

在共享的 std::forward_list 中,如果多个线程保证永远不会使用相同的位置迭代器调用它,那么多个线程同时调用 insert_after 是否安全?这似乎是安全的,因为插入保证不会使其他迭代器无效,并且容器没有 size() 方法,但也许我遗漏了什么?

编辑:

我写了一个小的折磨测试程序,似乎 运行 在没有任何锁定的情况下在 Clang 中运行良好:

#include <forward_list>
#include <iostream>
#include <thread>
#include <vector>

using List = std::forward_list< int >;
using It = List::const_iterator;

void insertAndBranch (List& list, It it, int depth)
{
    if (depth-- > 0) {
        It newIt = list.insert_after (it, depth);
        std::thread thread0 ([&]{ insertAndBranch (list, it, depth); });
        std::thread thread1 ([&]{ insertAndBranch (list, newIt, depth); });
        thread0.join();
        thread1.join();
    }
}

int main()
{
    List list;
    insertAndBranch (list, list.before_begin(), 8);

    std::vector< It > its;
    for (It it = list.begin(); it != list.end(); ++it) {
        its.push_back (it);
    }
    std::vector< std::thread > threads;
    for (It it : its) {
        threads.emplace_back ([&]{ list.insert_after (it, -1); });
    }
    for (std::thread& thread : threads) {
        thread.join();
    }

    for (int i : list) {
        std::cout << i << ' ';
    }
    std::cout << '\n';
}

我知道这不能证明任何事情,但它让我相信这是安全的。不过,我不确定是否可以在没有标准确认的情况下使用它。

In a shared std::list is it safe for multiple threads to call insert concurrently if they are guaranteed to never call it with the same position iterator?

没有。这不安全...(无论如何)。

插入 std::list 将需要访问迭代器位置的 previous nodenext node,以及列表的 size

即使位置相距很远,std::list::size() 的简单事实也需要 常数时间 (C++11)。这意味着每次插入都会更新 std::list::size().


编辑:

In a shared std::forward_list is it safe for multiple threads to call insert_after concurrently if they are guaranteed to never call it with the same position iterator?

不安全。并且不推荐。没有一个 STL 容器被设计成线程安全的。


无论如何,让我们假设一些基本保证,让我们假设一个非常简单的 std::forward_list 版本: insert_after 修改迭代器指向的节点,以便该节点现在指向新插入的节点, 而新插入的节点指向下一个节点。因此,如果迭代器彼此相距至少两个节点并且您的分配器是 thread-safe.

,它只会是 "safe"

插图:

Initial Forward_list
A -> B -> C -> D -> E

Insert K after C
A -> B -> C x D -> E
           \ /
            K

如你所见,C被读取和修改。 D 可能被读取,而 K 被插入。


为什么说"at least two nodes away",我们拿一个节点的情况来说:假设两个线程想在C之后插入K,在M之后D分别为:

Initial Forward_list
A -> B -> C -> D -> E

Insert K after C
A -> B -> C x D x E
           \ / \ /
            K   M

来自 cppreference

When an evaluation of an expression writes to a memory location and another evaluation reads or modifies the same memory location, the expressions are said to conflict.

当另一个线程 写入 到列表时,甚至 read 操作都是 thread-safe(参见 here进一步解释);所以:多次写入不是 thread-safe:

虽然在没有锁的情况下从列表中读取不会损坏列表,但如果在另一个线程正在读取列表时修改列表,则任一线程都可能损坏(即崩溃,或产生不正确的结果) ).

您需要某种锁定。期间.