C ++ 11中的无锁缓存实现 [英] Lock-free cache implementation in C++11

问题描述

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;
}

解决方案

考虑以下内容:

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()不会引发异常.

Is there any way in C++11 to implement a lock-free cache for an object, which would be safe to access from multiple threads? The calculation I'm looking to cache isn't super cheap but also isn't super expensive, so requiring a lock would defeat the purpose of caching in my case. IIUC, std::atomic isn't guaranteed to be lock-free.

Edit: Since calculate isn't -too- expensive, I actually don't mind if it runs once or twice too many. But I -do- need to make sure all consumers get the correct value. In the naive example below, this isn't guaranteed because due to memory re-ordering it's possible for a thread to get an uninitialized value of m_val since another thread set m_alreadyCalculated to true, but didn't set m_val's value yet.

Edit2: The comments below point out that for basic types, std::atomic would probably be lock free. In case it is, what's the correct way in the example below of using C++11's memory ordering to make sure it isn't possible for m_alreadyCalculated to be set to true before m_val's value is set?

Non-thread-safe cache example:

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;
}

解决方案

Consider something as:

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};
};

It's not in fact lock-free, there is a spin lock inside. But I think you cannot avoid such a lock if you don't want to run calculate() by multiple threads.

getValue() gets more complicated here, but the important part is that once m_val is calculated, it will always return immediately in the first if statement.

UPDATE

For performance reasons, it might also be a good idea do pad the whole class to a cache line size.

UPDATE 2

There was a bug in the original answer, thanks JVApen to pointing this out (it's marked by comments). The variable calculationInProgress would be better renamed to something as calculationHasStarted.

Also, please note that this solution assumes that calculate() does not throw an exception.

这篇关于C ++ 11中的无锁缓存实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！