这是真正的线程安全的 LRU 缓存设计，具有最少的阻塞吗？

Question

下面是我一直在研究的具有最小阻塞的 LRU 缓存设计的伪代码。

缓存具有以下特点：

它有固定大小MAX_CACHE_SIZE
是LRU

我希望满足以下条件：

如果发生缓存未命中，当数据可用（在这种情况下下载）时不会发生阻塞
在两次并发缓存未命中后数据未被检索两次

下面是 psudocode 函数 getData(name) returns 给定数据名称的缓存中的数据。这种设计看起来安全吗？如果不行，如何改进？


storage : dequeue<data> // container for the cache data
lookupmap : map<string, dequeue::iterator> // lookup map with name of data and position in storage dequeue

data getData(name) {
    lock()
    item_iterator : dequeue::iterator
    item_iterator = lookupmap[name]

    // if item name is present in the lookup map 
    if(item_iterator != null) {
       
       // unlocks and waits while item is being downloaded. Still a cache miss, 
       // but not this threads responsibility to get the data therefore wait for it to be downloaded
       cond_var.wait({return item_iterator.item.isDownloaded}) 
       
       // this removes the item from the queue and adds it to the front, essentially "bumping" it
       item : data
       item = item_iterator.item
       storage.remove(item_iterator)
       storage.push_front(item)
       lookupmap[name] = storage.begin()
       unlock()
       
       return item
    } else {
       // registers that item name but initialises it as null to indicate not downloaded yet
       lookupmap[name] = null
       unlock() // unlocks so that other threads can proceed while peforming download
       item : data
       item = downloadItem(name)
       lock() // locks again once downloaded
    
       // removes last item in cache if storage is full (LRU)
       if(storage.size() == MAX_CACHE_SIZE) {
           tempitem : data
           tempitem = storage.back()
           storage.pop_back()
           lookupmap.remove(tempItem.name)
       }

       // registers new item in cache
       storage.push_front(item)
       lookupMap[dataname] = storage.begin()
       
       unlock()
       cv.notify_all() // notifies any waiting threads that a item has now been downloaded
       return item

    }

}

编辑：

不确定这是否是一个问题，只是想澄清一下 - 此设计有一个全局互斥锁和一个全局条件变量。

Answer 1

伪代码没有描述线程安全算法。

考虑到多个线程可能正在等待特定项目完全下载。他们每个人都将持有（在堆栈内存中）相同的 item_iterator。下载完成。当第一个等待线程醒来时，为了维护 LRU，它将使其他线程持有的迭代器失效。

（我想到的另一个问题只要最大参与线程数小于MAX_CACHE_SIZE就OK了。）

唤醒后查找新鲜 item_iterator 是否足够修复？也许吧，但令人担忧的是，当线程在各种状态下处于活动状态时，共享的主要数据结构（存储本身）经常发生变化。这不是一个稳健的设计。

我会考虑保持存储稳定并以不同的方式评估 LRU。

这是真正的线程安全的 LRU 缓存设计，具有最少的阻塞吗？

Is this a truly Thread-Safe LRU Cache Design with Minimal Blocking?

c++

multithreading

caching

thread-safety

lru