任意大小的原子和无锁写入 data/vector/array

Question

我正在尝试实现以下功能：

任意大小的数据类型的原子和无锁写入或读取-修改-写入（在我的例子中通常是一个 float/int 向量，最多包含 6 个元素）。
从不阻塞写入线程的上述数据类型进行原子读取。读操作可能被写操作阻塞。

用例：我正在尝试为 CNC 机器编写软件。电机的步进脉冲在实时线程中的软件中生成。这个实时线程不断更新一个保存轴当前位置的变量。多个其他非实时线程可能会读取该变量，例如显示当前位置。

问题 1：是否有针对此类问题的 standard/accepted 解决方案或模式？

我想到了以下想法：使用 std::atomic<uint64_t> 来保护数据并跟踪线程当前正在写入（通过检查最后一位）或自读取开始以来已写入的天气（通过递增写入值）。

template <class DATA, class FN>
void read_modify_write(DATA& data, std::atomic<uint64_t>& protector, FN fn)
{
  auto old_protector_value = protector.load();
  do
  {
    // wait until no other thread is writing
    while(old_protector_value % 2 != 0)
      old_protector_value = protector.load();

    // try to acquire write privileges
  } while(!protector.compare_exchange_weak(old_protector_value, old_protector_value + 1));

  // write data
  data = fn(data);

  // unlock
  protector = old_protector_value + 2;
};

template <class DATA>
DATA read(const DATA& data, std::atomic<uint64_t>& protector)
{
  while(true)
  {
    uint64_t old_protector_value = protector.load();

    // wait until no thread is writing
    while(old_protector_value % 2 != 0)
      old_protector_value = protector.load();

    // read data
    auto ret = data;

    // check if data has changed in the meantime
    if(old_protector_value == protector)
      return ret;
  }
}

问题二：上述代码是否线程安全，是否满足上述要求？

问题三：能否改进？

（我能找到的唯一理论问题是计数器是否回绕，即在 1 次读取操作期间执行了 2^63 次写入操作。如果没有更好的解决方案，我认为这个弱点是可以接受的。）

谢谢

Answer 1

严格来说你的代码不是lock-free，因为你有效地使用了protector的LSB来实现自旋锁。

您的解决方案看起来很像 sequence lock。然而，实际的读操作 auto ret = data; 严格来说是数据竞争。公平地说，在 C++17 中编写完全符合标准的 seqlock 是根本不可能的，因为我们必须等待 C++20。

可以扩展 seqlock 以进行读取操作 lock-free，但会占用更多内存。这个想法是拥有多个数据实例（让我们称它们为插槽），并且写操作总是以循环方式写入下一个插槽。这允许读取操作从最后一个完全写入的槽中读取。 Dmitry Vyukov 在 Improved Lockfree SeqLock. You can take a look at my seqlock implementation that is part of my xenium library 中描述了他的方法。它还可以选择允许 lock-free 具有可配置数量的插槽的读取操作（尽管它与 Vyukov 在 reader 如何找到最后一个完全写入的插槽方面略有不同）。

任意大小的原子和无锁写入 data/vector/array

Atomic and lock-free write of arbitrary sized data/vector/array

c++

multithreading

atomic