cache 替换最近使用的cache line

### 替换最近使用的缓存行策略 在计算机体系结构中，缓存替换策略决定了当新数据需要存储到已满的缓存中时应该移除哪一行。常见的几种缓存替换策略包括： #### 1. 随机替换 (Random Replacement) 随机选择一条缓存行进行替换。这种方法简单易实现，但由于缺乏预测性和优化机制，在性能上通常不是最优的选择。 #### 2. 先进先出 (FIFO, First In First Out) 按照时间顺序记录每条进入缓存的数据项，并总是淘汰最早加入的那一项。尽管易于理解，但对于工作负载模式变化较大的情况表现不佳[^1]。 #### 3. 最近最少使用 (LRU, Least Recently Used) 跟踪各缓存行最后一次被访问的时间戳或位置，优先淘汰最久未使用的那一行。此方法能较好地适应多种应用场景下的局部性原理，因此应用广泛。为了高效管理 LRU 列表，可以采用位图或其他紧凑的数据结构来表示相对次序关系。 ```c++ struct CacheLine { int tag; bool valid; // 是否有效标志 unsigned long timestamp; // 时间戳用于模拟LRU行为 }; class LRUCache { private: std::unordered_map<int, CacheLine*> cacheMap; list<CacheLine> lruList; public: void access(int address) { auto it = cacheMap.find(address); if (it != cacheMap.end()) { // 命中 move_to_front(it->second); // 将其移到队列头部 } else { // 缺失 evict(); // 如果满了则驱逐最后面的一个元素 insert_new_line(address); // 插入新的缓存行至前端 } } void move_to_front(CacheLine* line){ lruList.splice(lruList.begin(), lruList, find(lruList.begin(),lruList.end(),line)); } void evict(){ if(cacheMap.size() >= MAX_SIZE){ CacheLine *last = &lruList.back(); cacheMap.erase(last->tag); lruList.pop_back(); } } void insert_new_line(int addr){ CacheLine newEntry{addr,true,time(NULL)}; lruList.push_front(newEntry); cacheMap[addr]=&lruList.front(); } }; ``` 对于使用了 Virtual Cache 的微架构而言，虽然 Bin-Index 算法仍然可能适用于某些场景，但主要是在更高级别的缓存（如 L2 或以上）而非追求极低命中延迟的一级缓存中找到更多应用实例。而针对具体某一层级内的 “最近使用过的” 行执行替换操作，则往往依赖上述提到的一种或组合形式的具体政策来进行决策。