LRU with shared_ptr 在多线程环境中

Question

我运行在使用基于 shared_ptr 且兼作 LRU 的 "database" 时陷入极端情况。

从 C++17 开始，shared_ptr::use_count 是不精确的，所以我很难决定哪些元素可以安全地从 LRU 中删除。

我无法删除仍在使用的元素，因为这会破坏其余代码的约定。

据我所知，锁定互斥量是不够的，因为只有互斥量解锁才会强制内存屏障。即使持有锁，我仍然可以读取过时的值。

我当然可以在 LRU 中锁定互斥量后打一个内存屏障，但我有点担心性能影响。

这里概述了 lru 的工作原理：

template <k,v>
class DB{
  shared_ptr<V> emplace(k, args...) {
    lock guard();
    remove_elements_if_needed();
    insert_if_new(k, args...);
    refresh_lru(k);
    return ptr;
  }
};

Answer 1

我建议的一般解决方案是在处于锁定状态时，确定要删除的候选元素。然后尝试通过执行以下操作将其删除：

为您认为可能不错的元素创建一个 weak_ptr 实例要删除的候选人
像往常一样从列表中删除项目
尝试将项目从 weak_ptr
恢复为 shared_ptr
如果您将 weak_ptr 提升回 shared_ptr 并且它仍然为空，那么你就完成了。
如果新的shared_ptr不为空，那么你知道有人还有对项目的引用。将项目放回您的数据结构中与您找到的一模一样。

像这样。因为我还没有你的代码，所以我正在考虑你的实现。但我猜你有一组“节点”。每个节点都有一个成员，即您返回给调用者的 shared_ptr 实例。

 bool remove_unused_element() {

      bool removed = false;

      for (node& n : lru) {
          weak_ptr<X> wp = n.item;
          n.item.reset();
          shared_ptr<X> sp = wp.lock();
          if (sp != nullptr){
              n.item = sp ; // restore this node, someone is still using it
          }
          else {
              lru.erase(n);
              removed = true;
              break;
          }
     }
     return removed;
}             
          
          
void remove_elements_if_needed() {
    bool result = true;
    while ((lru.size() > max_lru_size) && result) {
         result = remove_unused_element();
    }
}

以上所有代码都假定您已经获得了伪代码中显示的互斥量。

LRU with shared_ptr 在多线程环境中

LRU with shared_ptr in multi-threaded environment

c++

shared-ptr

c++17