重新排序操作和无锁数据结构

Question

假设我们Container维护了一组int值,并为每个值指示了该值是否有效.无效值被认为是INT_MAX.最初,所有值都无效.第一次访问值时,将其设置为INT_MAX并将其标志设置为有效.

struct Container {
  int& operator[](int i) {
    if (!isValid[i]) {
      values[i] = INT_MAX; // (*)
      isValid[i] = true;   // (**)
    }
    return values[i];
  }
  std::vector<int> values;
  std::vector<bool> isValid;
};

现在,另一个线程同时读取容器值:

// This member is allowed to overestimate value i, but it must not underestimate it.
int Container::get(int i) {
  return isValid[i] ? values[i] : INT_MAX;
}

这是完全合法的代码,但是它行是至关重要的(*),并(**)在给定的顺序执行.

1. 在这种情况下,标准是否保证线路按给定顺序执行？至少从单线程的角度来看,线路可以互换,不是吗？
2. 如果没有,确保订单的最有效方法是什么？这是高性能的代码,所以我不能没有-O3,也不想使用volatile.

Answer 1

这里没有同步.如果从一个线程访问这些值并从另一个线程更改它们,则会得到未定义的行为.你需要锁定所有访问,在这种情况下一切都很好.否则,您需要创建所有std::vector元素,atomic<T>并且可以使用适当的可见性参数控制值的可见性.

似乎存在对同步和特定原子操作的误解:它们的目的是使代码快速运行!这可能看起来反直觉所以这里是解释:非原子操作应该尽可能快,并且故意无法保证它们如何准确地访问内存.只要编译器和执行系统产生正确的结果,编译器和系统就可以自由地做他们需要或想做的事情.为了实现良好的性能,假设不存在不同线程之间的交互.

然而,在并发系统中,线程之间存在交互.这是原子操作进入阶段的地方:它们允许完全指定所需的必要同步.因此,它们允许告诉编译器必须遵守的最小约束,以使线程无法正确.编译器将使用这些指示符生成最佳代码以实现指定的内容.该代码可能与不使用任何同步的代码相同,但在实践中通常还需要防止CPU重新排序操作.因此,正确使用同步会产生最有效的代码,只有绝对必要的开销.

棘手的部分是在某种程度上找到需要哪些同步并最小化这些同步.简单地说,没有任何东西可以让编译器和CPU自由地重新排序操作,并且不起作用.

既然提到的问题volatile,请注意,volatile是完全无关的并发!主要目的volatile是通知系统地址指向访问可能有副作用的内存.它主要用于访问内存映射I/O或硬件控制.死于副作用的可能性它是C++定义程序语义的两个方面之一(另一个是使用标准库I/O工具的I/O).