C++11中的无锁缓存实现

Question

在C++11中有没有任何方法可以实现对象的无锁缓存，这样可以安全地从多个线程访问？我想要缓存的计算并不是非常便宜，但也不是非常昂贵，所以在我的情况下，需要锁将无法实现缓存的目的。IIUC，std::atomic不能保证是无锁的。

编辑：由于计算并不太贵，我其实并不介意它运行一到两次太多。但我确实需要确保所有消费者都能得到正确的价值。在下面的简单示例中，这并不能保证，因为由于内存重新排序，线程可能会获得未初始化的m_val值，因为另一个线程将m_alreadyCalculated设置为true，但尚未设置m_val的值。

Edit2：下面的注释指出，对于基本类型，std::atomic可能是无锁的。如果是这样的话，在下面的例子中，使用C++11的内存排序来确保在设置m_val的值之前m_alreadyCalculated不可能设置为true的正确方法是什么？

非线程安全缓存示例：

class C {
public:
   C(int param) : m_param(param) {}
   getValue() {
      if (!m_alreadyCalculated) {
          m_val = calculate(m_param);
          m_alreadyCalculated = true;
      }
      return m_val;
   }
   double calculate(int param) {
       // Some calculation
   }
private:
   int m_param;
   double m_val;
   bool m_alreadyCalculated = false;
}

Answer 1

考虑以下内容：

class C {
public:
   double getValue() {
      if (alreadyCalculated == true)
         return m_val;
      bool expected = false;
      if (calculationInProgress.compare_exchange_strong(expected, true)) {
         m_val = calculate(m_param);
         alreadyCalculated = true;
      // calculationInProgress = false;
      }
      else {
     //  while (calculationInProgress == true)
         while (alreadyCalculated == false)
            ; // spin
      }
      return m_val;
   }
private:
   double m_val;
   std::atomic<bool> alreadyCalculated {false};
   std::atomic<bool> calculationInProgress {false};
};

事实上，它不是无锁的，里面有一个旋转锁。但我认为，如果您不想通过多个线程运行calculate()，就无法避免这样的锁定。

getValue()在这里变得更加复杂，但重要的是，一旦计算出m_val，它总是会在第一个if语句中立即返回。

更新

出于性能原因，最好将整个类填充到缓存行大小。

更新2

最初的答案中有一个错误，感谢JVApen指出这一点（用注释标记）。变量calculationInProgress最好重命名为calculationHasStarted。

此外，请注意，此解决方案假定calculate()不会引发异常。

Answer 2

std:：atomic不能保证是无锁的，尽管您可以检查std::atomic<T>::is_lock_free()或std::atomic::is_always_lock_free()，看看您的实现是否可以做到无锁。

另一种方法可能是使用std::call_once，但据我所知，这更糟糕，因为它旨在阻止其他线程。

所以，在这种情况下，我会使用std:：atomic来表示m_val和alreadyCalculated。其中包含2个（或多个）线程正在计算相同结果的风险。

Answer 3

这里只回答一个技术问题：为了确保值在标志之前更新，您使用发布语义更新标志。发布语义的含义是，此更新必须（被视为）发生在之前的所有更新之后。在x86上，它只意味着在更新之前有一个编译器屏障，并对内存进行更新，而不是注册，就像这样：

asm volatile("":::"memory");
*(volatile bool*)&m_alreadyCalculated = true;

这正是原子集在发布语义