c++ - 我不明白在C++11中如何实现乐观并发

Question

我试图在 C++11 中实现一个不使用锁的 protected 变量。我读过一些关于乐观并发的内容，但我不明白它怎么能既不是用 C++ 也不是用任何语言来实现。

我尝试实现乐观并发的方法是使用“最后修改 ID”。我正在做的过程是:

• 复制上次修改的 ID。
• 修改 protected 值。
• 将修改id的本地拷贝与当前拷贝进行比较。
• 如果以上比较为真，则提交更改。

我看到的问题是，比较“最后修改 ID”(本地拷贝和当前拷贝)并在提交更改之前，有无法确保没有其他线程修改 protected 变量的值。

下面是一个代码示例。假设有许多线程执行该代码并共享变量 var。

/**
 * This struct is pretended to implement a protected variable,
 * but using optimistic concurrency instead of locks.
 */
struct ProtectedVariable final {

   ProtectedVariable() : var(0), lastModificationId(0){ }

   int getValue() const {
      return var.load();
   }

   void setValue(int val) {
      // This method is not atomic, other thread could change the value
      // of val before being able to increment the 'last modification id'.
      var.store(val);
      lastModificationId.store(lastModificationId.load() + 1);
   }

   size_t getLastModificationId() const {
      return lastModificationId.load();
   }

private:
   std::atomic<int> var;
   std::atomic<size_t> lastModificationId;
};



ProtectedVariable var;


/**
 * Suppose this method writes a value in some sort of database.
 */
int commitChanges(int val){
   // Now, if nobody has changed the value of 'var', commit its value,
   // retry the transaction otherwise.
   if(var.getLastModificationId() == currModifId) {

      // Here is one of the problems. After comparing the value of both Ids, other
      // thread could modify the value of 'var', hence I would be
      // performing the commit with a corrupted value.
      var.setValue(val);

      // Again, the same problem as above.
      writeToDatabase(val);

      // Return 'ok' in case of everything has gone ok.
      return 0;
   } else {
      // If someone has changed the value of var while trying to 
      // calculating and commiting it, return error;
      return -1;
   }
}

/**
 * This method is pretended to be atomic, but without using locks.
 */
void modifyVar(){
   // Get the modification id for checking whether or not some
   // thread has modified the value of 'var' after commiting it.
   size_t currModifId = lastModificationId.load();

   // Get a local copy of 'var'.
   int currVal = var.getValue();

   // Perform some operations basing on the current value of
   // 'var'.
   int newVal = currVal + 1 * 2 / 3;

   if(commitChanges(newVal) != 0){
      // If someone has changed the value of var while trying to 
      // calculating and commiting it, retry the transaction.
      modifyVar();
   }
}

我知道上面的代码有错误，但我不明白如何以正确的方式实现上面的代码，没有错误。

Answer 1

乐观并发并不意味着您不使用锁，它只是意味着您在大多数操作期间不保留锁。

这个想法是将修改分成三个部分:

1. 初始化，比如获取 lastModificationId。这部分可能需要锁，但不一定。
2. 实际计算。所有昂贵或阻塞的代码都放在这里(包括任何磁盘写入或网络代码)。结果的编写方式不会掩盖以前的版本。它的可能工作方式是将新值存储在旧值旁边，并按尚未提交的版本进行索引。
3. 原子提交。这部分是有锁的，一定要短、简单、不阻塞。它可能的工作方式是它只是增加版本号——在确认之后，没有其他版本同时提交。在此阶段没有数据库写入。

这里的主要假设是计算部分比提交部分要昂贵得多。如果你的修改是微不足道的并且计算成本低，那么你可以只使用锁，这要简单得多。

一些示例代码分为这 3 个部分，如下所示:

struct Data {
  ...
}

...

std::mutex lock;
volatile const Data* value;  // The protected data
volatile int current_value_version = 0;

...

bool modifyProtectedValue() {
  // Initialize.
  int version_on_entry = current_value_version;

  // Compute the new value, using the current value.
  // We don't have any lock here, so it's fine to make heavy
  // computations or block on I/O.
  Data* new_value = new Data;
  compute_new_value(value, new_value);

  // Commit or fail.
  bool success;
  lock.lock();
  if (current_value_version == version_on_entry) {
    value = new_value;
    current_value_version++;
    success = true;
  } else {
    success = false;
  }
  lock.unlock();
  
  // Roll back in case of failure.
  if (!success) {
    delete new_value;
  }

  // Inform caller about success or failure.
  return success;
}

// It's cleaner to keep retry logic separately.
bool retryModification(int retries = 5) {
  for (int i = 0; i < retries; ++i) {
    if (modifyProtectedValue()) {
      return true;
    }
  }
  return false;
}

这是一个非常基本的方法，尤其是回滚是微不足道的。在现实世界的例子中，重新创建整个数据对象(或其对应对象)可能是不可行的，因此版本控制必须在内部某处完成，并且回滚可能要复杂得多。但我希望它能说明总体思路。