下面是我一直在研究的具有最小阻塞的LRU缓存设计的伪代码。
缓存具有以下特征:
- 它有固定的大小
MAX_CACHE_SIZE - 是LRU
我希望下列条件为真:
- 如果发生缓存丢失，在数据可用(在这种情况下是下载)时不会发生阻塞
- 数据不会在两次并发缓存丢失后被检索两次
下面是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
}
}
编辑:
不确定这是否值得关注，但只是为了澄清-这个设计有一个全局互斥锁和一个全局条件变量。
伪代码没有描述线程安全算法。
考虑多个线程可能正在等待一个特定的项目被完全下载。它们中的每一个都持有(在堆栈内存中)相同的item_iterator。下载完成。当第一个等待线程唤醒时，为了维护LRU，它将使仍然由其他线程持有的迭代器失效。
(我想到的另一个问题是，只要参与线程的最大数量小于MAX_CACHE_SIZE。)
是否足以修复在醒来后查找新鲜item_iterator ?也许吧，但值得关注的是，共享的主要数据结构，即存储本身，在线程处于各种状态时经常发生变化。这不是一个稳健的设计。
我会考虑保持存储稳定，并以不同的方式评估LRU。