c++ - 在具有最小锁争用的映射中初始化 coSTLy 值 (C++)

Question

假设我们有一个在多个线程之间共享的映射。它表示存储在磁盘上的某种层次结构(例如，文件系统中的目录)中的一个节点。构造一个值在时间和内存上都是昂贵的。这是经典的“按需初始化”问题，有一个转折点:我们在有查找请求时初始化映射中的值，但我们不想在查找请求时锁定整个映射这样做是为了让其他线程访问已经构造的值。在此应用程序中，现有值的查找将远比不存在的值更常见。

尝试 1:在 map 上获取写锁，检查 Key 是否存在，如果存在则返回，否则构造 Value，放入 map。

评估:这可以防止其他线程在我们构建值时访问 map 。由于读取非常普遍且非常快，这将表现为延迟的丑陋跳跃:不好。

尝试 2:在 map 上获取读锁，检查 Key 是否存在，如果存在则返回，否则释放读锁，构造 Value，获取写锁，检查是否存在，如果不存在，则放入在 map 中，如果存在则删除新构造的值。

评估:现在我们不会导致读取延迟的跳跃，但我们最终可能会不必要地构造多个相同值的内存表示(当多个线程尝试查找相同的值时-同时未构造值)。问题是，我们不希望这样:创建这些值(value)真的很昂贵。此外，它们可能会开始触发事件或执行 I/O，这意味着现在我们必须处理允许短暂但重量级的 Value 实例存在的设计:最好避免额外的麻烦。

尝试 3:使用两级锁。获取map上的读锁，查找Key，如果存在则返回，否则，释放map上的读锁，获取map上的写锁，检查占位符，获取占位符的读锁，如果存在，则创建占位符，获取其写锁，插入进入 map ，释放 map 上的写锁，创建值，用值替换占位符，释放占位符的写锁。

评估:在构造Value时在map中插入占位符保证只有一个线程会尝试它，从而解决了尝试2的问题。然而，这种设计留下了一个悬而未决的问题:什么< em>form 这个占位符应该采用？答案并不简单。首先，如果它包含一个锁并且线程等待它，就很难删除它(你怎么知道没有人持有占位符的锁？你可以捕获它，当然，但是你持有它所以，同样，你不能删除它)。其次，可以查找磁盘上不存在值的键。如果我们为每个 查找尝试插入一个占位符(即使对于最终会失败的尝试)，那么谁来清理这些呢？最后，有了两级锁，代码变得相当难看:我们首先获取读锁，检查，然后获取写锁，重新检查，我们需要在映射级别和单个占位符级别执行此操作(容易造成死锁，我可以证明这一点)。

这个小宝贝不断弹出，我似乎找不到优雅的解决方案。尝试 3 是我最接近满足我的性能条件的尝试，但是一旦你深入了解肮脏的细节，它就会很丑陋并且容易出错。如果有任何见解或建议，我将不胜感激。

Answer 1

目标似乎是以创建新对象为代价实现对现有对象的快速周转。这是一个可以为您完成此操作的解决方案。

您需要在内存中维护两个 map ，两者最终将具有相同的内容。您还需要一个用于写入和读取的互斥锁: -curReadMap * - curWriteMap * - 写互斥体 - 读互斥体

这两个指针很重要，我们将交换它们。现在读取您拥有的值(粗略的伪代码):

  lock( readMutex )
  value = checkValueIn( curReadMap, key )
  unlock()
  if( value ) return value

如果没有找到值可以进入写作部分

  lock( writeMutex )
  value = checkValueIn( curWriteMap, key ) //double check now
  if( value ) return value

  value = createNewValue()
  putIn( curWriteMap, key, value )

  lock( readMutex )
  swap( curWriteMap, curReadMap )
  unlock( readMutex )

  putIn( curWriteMap, key, value ) //update old map now as well
  unlock( writeMutex )

在这个方案中，典型的读者只承担一个互斥锁和映射中查找的成本。如果找不到对象，他们只会承担创建成本。映射指针的交换还确保了 readMutex 上的锁定时间非常短。