代码之家 › 专栏 › 技术社区 › Koosha

危险指针的内存排序

atomic multithreading c++

Koosha · 技术社区 · 5 年前

this 纸张)。由于简化的总量,它不能代替算法(和 回答这个问题不需要知道任何关于算法的知识

ptr->a = 1; 执行时,结果将不会是未定义的(值为 order1 ... order5

struct T { int a = 0; };
static_assert(std::is_trivially_destructible_v<T>);
std::atomic<T*> a{new T()};
std::atomic<T*> h{nullptr};

// Thread 1
auto ptr = a.load(order1);
h.store(ptr,order2);
if(ptr == nullptr || ptr != a.load(order3))
  return;
ptr->a = 1;

// Thread 2
auto ptr = a.exchange(nullptr,order4);
if(ptr != h.load(order5))
  delete ptr;

我们知道 ptr->a=1; 为了被处决, a.exchange 必须在2号之后发生 a.load (即使是宽松的内存顺序也能保证这一点)。然而,问题是如何确保 h.load 将看到 h.store . 即使我们在任何地方都只使用顺序内存排序,我也无法理解为什么代码可以工作。

0 回复 | 直到 5 年前

mpoeter 5 年前

为了简单起见,这些论文通常假设一个顺序一致的内存模型——这也是您引用的论文的情况。您的示例高度简化,但仍然包含危险指针算法的要点。您必须确保线程2“看到”线程1存储的危险指针(即线程1已获取安全引用),或者线程1看到a的更新值。

在我的论证中,我将使用以下符号 - a -sb-> b 表示“a在b之前排序” - a -sco-> b - a -rf-> b

让我们假设所有原子操作都是顺序一致的。这将导致以下情况:

线程1: a.load() -sb-> h.store() -sb-> a.load() -sb-> ptr->a=1
线程2: a.exchange() -sb-> h.load() -> delete ptr

h.store() -sco-> h.load()
这意味着 h.store() -rf-> h.load() ptr->a
h.load() -sco-> h.store()
因为我们也有 a.exchange() -sb-> h.load() (线程2)和 h.store() -sb-> a.load() (线程1),这意味着 a.exchange() -sco-> a.load() a.exchange() -rf-> a.load() ,即线程1保证“看到”的更新值 a (因此不会尝试更新 ptr->A.

因此,如果所有操作顺序一致,则算法将按预期工作。但是,如果我们不能(或不想)假设所有操作都是顺序一致的呢?我们能放松一些手术吗?问题是我们必须确保两个不同变量之间的可见性( A. h )在两个不同的线程中,这需要acquire/release提供更强的保证。但是,如果引入顺序一致的围栏,则可以放松操作:

// Thread 1
auto ptr = a.load(std::memory_order_acquire);
h.store(ptr, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
if(ptr == nullptr || ptr != a.load(std::memory_order_relaxed))
  return;
ptr->a = 1;

// Thread 2
auto ptr = a.exchange(nullptr, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
if(ptr != h.load(std::memory_order_relaxed))
  delete ptr;

线程1: a.load() -sb-> h.store() -sb-> fence() -sb-> a.load() -sb-> ptr->a=1
线程2: a.exchange() -sb-> fence() -sb-> h.load() -> delete ptr

该标准规定:

A. 和 M 哪里和 B X 和 Y 之前是按顺序排列的 , Y B X 先于 Y 在里面那么观察 A. 或者后来对在其修改顺序中。

围栏也是单一总订单的一部分

Thread1 fence -sco-> Thread 2 fence
自从 h.store() -sb-> fence() (线程1)和 fence() -sb-> h.load() (线程2)保证线程2“看到”由线程1写入的危险指针。
Thread 2 fence -sco-> Thread 1 fence
自从 a.exchange() -sb-> fence() (线程2)和 fence() -sb-> a.load() (线程1)保证线程1“看到”的更新值 A. .

xenium 图书馆。