时间戳

首页 > 解决方案 > 这是真正具有最小阻塞的线程安全 LRU 缓存设计吗？

c++ - 这是真正具有最小阻塞的线程安全 LRU 缓存设计吗？

问题描述

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

缓存具有以下特点：

  1. 它有一个固定的大小MAX_CACHE_SIZE
  2. 是LRU

我希望以下条件为真：

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

下面是 psudocode 函数getData(name)，它根据数据的名称从缓存中返回数据。这种设计看起来安全吗？如果没有，如何改进？


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

    }

}

编辑：

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

标签： c++multithreadingcachingthread-safetylru

解决方案

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

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

（我想到的另一个问题是可以的，只要参与线程的最大数量小于 MAX_CACHE_SIZE。）

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

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

推荐阅读