LRU （移除最少使用内存）
模拟算法
语言：JAVA
数据结构：HASH+双向链表
原则：
1)最少使用的是链表头（removeLRUNode）
2)最近使用的放在链表尾（get）
3)最近添加或更新值放在链表尾（add）
4)节点有变化，节点的前后节点互联
package test.lrucache;
import java.util.HashMap;
public class LRUCache {
private HashMap<String, LinkedNode> nodeMap = new HashMap<>();
private LinkedNode rootNode;
private LinkedNode bottomNode;
/**
* 添加一个新节点，如果节点已存在，则覆盖值并移至链表最后
* @param key
* @param value
*/
public void add(String key, Object value) {
LinkedNode node = get(key);
if (node != null) {
nodeMap.get(key).setValue(value);
} else {
if (bottomNode == null) {
rootNode = bottomNode = new LinkedNode(key, value, null, null);
} else {
node = new LinkedNode(key, value, bottomNode, null);
bottomNode.setAftNode(node);
bottomNode = node;
}
nodeMap.put(key, bottomNode);
}
}
/**
* 获取一个节点，并移至链表最后
* @param key
* @return
*/
public LinkedNode get(String key) {
LinkedNode node = nodeMap.get(key);
if (node != null) {
if (rootNode != bottomNode && node != bottomNode) {
updatePreAndAftNode(node);
node.setPreNode(bottomNode);
node.setAftNode(null);
bottomNode.setAftNode(node);
bottomNode = node;
}
}
return node;
}
/**
* 删除指定节点
* @param key
* @return
*/
public LinkedNode remove(String key) {
LinkedNode node = nodeMap.remove(key);
if (node != null) {
updatePreAndAftNode(node);
if (node.isRootNode()) {
rootNode = node.getAftNode();
}
if (node.isBottomNode()) {
bottomNode = node.getPreNode();
}
}
return node;
}
/**
* 删除最少使用的节点
*/
public void removeLRUNode() {
remove(rootNode.getKey());
}
/**
* 打印链表
*/
public void printAllNode() {
if (rootNode == null)
return;
LinkedNode curNode = rootNode;
System.out.print(curNode.getValue() + "\t");
while ((curNode = curNode.getAftNode()) != null) {
System.out.print(curNode.getValue() + "\t");
}
System.out.println();
}
/**
* 反转打印链表
*/
public void revePrintAllNode() {
if (bottomNode == null)
return;
LinkedNode curNode = bottomNode;
System.out.print(curNode.getValue() + "\t");
while ((curNode = curNode.getPreNode()) != null) {
System.out.print(curNode.getValue() + "\t");
}
System.out.println();
}
/**
* 对节点的前后节点创建连线
* @param node
*/
private void updatePreAndAftNode(LinkedNode node) {
//整个链表只有一个节点
if (node.isSingleNode()){
return;
}
//是根节点
if (node.isRootNode()) {
node.getAftNode().setPreNode(null);
rootNode = node.getAftNode();
}
//是尾节点
else if(node.isBottomNode()) {
node.getPreNode().setAftNode(null);
bottomNode = node.getPreNode();
}
//是中间节点
else{
node.getPreNode().setAftNode(node.getAftNode());
node.getAftNode().setPreNode(node.getPreNode());
}
}
public static void main(String[] args) {
LRUCache cache = new LRUCache();
for (int i = 0; i < 10; i++) {
cache.add("key" + i, i);
}
System.out.println("初始化节点key0-9");
cache.printAllNode();
System.out.println("删除尾节点key9");
cache.remove("key9");
cache.printAllNode();
System.out.println("删除不存在的节点key10,链表不变");
cache.remove("key10");
cache.printAllNode();
System.out.println("删除根节点key0");
cache.removeLRUNode();
cache.printAllNode();
System.out.println("添加key10=10");
cache.add("key10", 10);
cache.printAllNode();
System.out.println("使用key5，key5移到最后");
cache.get("key5");
cache.printAllNode();
System.out.println("添加存的节点key10=-10,覆盖原值，并且移到最后");
cache.add("key10", -10);
cache.printAllNode();
System.out.println("使用根节点key1，key1移到最后");
cache.get("key1");
cache.printAllNode();
System.out.println("删除中间节点key7");
cache.remove("key7");
cache.printAllNode();
System.out.println("反转打印链表");
cache.revePrintAllNode();
System.out.println("只保留8节点");
cache.remove("key2");
cache.remove("key3");
cache.remove("key4");
cache.remove("key6");
cache.remove("key5");
cache.remove("key10");
cache.remove("key1");
cache.printAllNode();
cache.revePrintAllNode();
System.out.println("8节点也删除");
cache.remove("key8");
cache.printAllNode();
cache.revePrintAllNode();
}
}
package test.lrucache;
public class LinkedNode {
private String key;
private Object value;
private LinkedNode preNode;
private LinkedNode aftNode;
public LinkedNode(String key, Object value, LinkedNode preNode, LinkedNode aftNode) {
this.key = key;
this.value = value;
this.preNode = preNode;
this.aftNode = aftNode;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
public LinkedNode getPreNode() {
return preNode;
}
public void setPreNode(LinkedNode preNode) {
this.preNode = preNode;
}
public LinkedNode getAftNode() {
return aftNode;
}
public void setAftNode(LinkedNode aftNode) {
this.aftNode = aftNode;
}
public boolean isRootNode() {
return this.preNode == null;
}
public boolean isBottomNode(){
return this.aftNode == null;
}
public boolean isSingleNode() {
return isRootNode() && isBottomNode();
}
public void clear() {
setAftNode(null);
setPreNode(null);
setValue(null);
}
}
控制台： ------------------------------------------------------------- 初始化节点key0-9 0 1 2 3 4 5 6 7 8 9 删除尾节点key9 0 1 2 3 4 5 6 7 8 删除不存在的节点key10,链表不变 0 1 2 3 4 5 6 7 8 删除根节点key0 1 2 3 4 5 6 7 8 添加key10=10 1 2 3 4 5 6 7 8 10 使用key5，key5移到最后 1 2 3 4 6 7 8 10 5 添加存的节点key10=-10,覆盖原值，并且移到最后 1 2 3 4 6 7 8 5 -10 使用根节点key1，key1移到最后 2 3 4 6 7 8 5 -10 1 删除中间节点key7 2 3 4 6 8 5 -10 1 反转打印链表 1 -10 5 8 6 4 3 2 只保留8节点 8 8 8节点也删除 Process finished with exit code 0
相关推荐
在这个项目中，我们关注的是虚拟存储中的页面调度算法，具体包括FIFO（先进先出）、LRU（最近最少使用）以及OPT（最佳页面替换）这三种算法的模拟实现。 1. FIFO（先进先出）算法是最简单的页面替换策略。当内存满...
实验目的是通过编程模拟LRU算法的工作过程，帮助学生理解页面调度和页面置换算法，特别是LRU算法的实现细节。实验前需要学习虚拟存储管理、页面调度等相关概念，以及LRU、FIFO、LFU等常见页面调度算法的基本思想。 ...
在Java中实现LRU算法，通常会使用数据结构如HashMap或LinkedHashMap来存储页面及其访问信息。HashMap提供快速的查找操作，而LinkedHashMap则同时保持了插入顺序，这对于实现LRU至关重要，因为我们需要快速找到最近...
在C语言中实现LRU算法，需要理解数据结构和算法的基础知识，以及如何在C语言中有效地管理内存。 首先，LRU算法的核心是数据结构的选择。通常使用双向链表来存储数据，因为双向链表允许我们快速地插入和删除元素，...
实验内容包括实现LRU算法的两种不同变体：计数器实现和栈实现。在计数器实现中，每个页面都有一个访问计数器，每当页面被访问时，计数器增加，淘汰时选择计数最小的页面。而在栈实现中，页面按访问顺序存储在栈中，...
### LRU算法C语言实现详解 #### 一、引言 LRU（Least Recently Used，最近最少使用）算法是一种常用的数据缓存淘汰策略，在计算机科学领域应用广泛，尤其是在操作系统、数据库管理和Web服务器缓存管理等方面。本文...
实验报告中，学生被要求用 C 或 C++ 编写程序来模拟 LRU 页面置换算法。实验的主要目标包括理解和实现 LRU 算法的调度过程，并计算出访问页面时的命中率。 实验内容分为以下部分： 1. 设计一个虚拟存储系统，其中...
LRU算法和FIFO算法合体
然而，这个简单的C语言实现提供了一个直观的理解基础，展示了LRU算法的基本操作和逻辑。通过这样的实验，学生可以深入理解页面替换策略的工作原理，并为进一步学习操作系统和内存管理打下坚实的基础。
模拟页式虚拟存储管理中硬件地址变换和缺页中断，并用LRU算法处理缺页中断
在这个实验设计课程中，我们将探讨LRU算法的原理和实现。 首先，我们需要理解LRU算法的核心思想。假设有一个固定大小的缓存（或内存），当新的数据请求进来而缓存已满时，LRU算法会选择最近最少使用的数据进行替换...
操作系统之LRU算法（Java） LRU（Least Recently Used，最近最少使用）算法是一种常用的页面置换算法，用于操作系统中管理内存页面。该算法的基本思想是：当进程在 CPU 上运行时，如指令中涉及逻辑地址时，操作系统...
进程调度、银行家算法、页式地址重定位...本文对操作系统中进程调度、银行家算法、页式地址重定位模拟、LRU 算法模拟和先来先服务算法代码进行了详细的分析和实现。这些知识点对于操作系统的学习和开发具有重要的意义。
`queue`类表示一个队列，用于模拟LRU算法中的页面队列。队列包含两个指针`front`和`rear`分别指向队列的前端和后端，并且有一个静态成员变量`count`记录队列中的元素数量。 ```cpp class queue { friend class LRU...
2. **数据结构实现**：通常，LRU算法会用到一种数据结构——双向链表和哈希表。双向链表可以方便地按照访问顺序移动页面，而哈希表则用于快速查找页面。 - **双向链表**：新访问的页面被添加到链表头部，表示其是...
在C语言实现LRU算法时，通常需要维护一个数据结构来记录每个页面的访问信息，如访问时间戳或者访问计数。一个常见的方法是使用链表，每个节点代表一个页面，链表的顺序表示页面的访问顺序。每当有新的页面被访问，...
### LRU算法（Least Recently Used）在C语言中的实现 #### 概述 LRU算法是一种常用的缓存淘汰策略，在计算机科学中广泛应用于操作系统、数据库系统以及Web浏览器等场景。其核心思想是当缓存满时，优先淘汰最近最少...
在电子科技大学的这个实验报告中，学生需要设计并改进LRU算法的实现。实验的目标是让用户自定义页块数量和页面访问序列，然后模拟页面访问过程，计算缺页次数和缺页率。实验的具体内容是根据一个给定的20位长页面...
LRU页面淘汰算法模拟程序(源码)C++ 产生一个进程的大小，构建页表并对页表进行初始化，随后生成访问的指令地址流（是一系列需要访问的指令的地址）。不失一般性，可以适当地（人工指定或随机数产生器）生成这个序列...
页面置换算法LRU（模拟页面管理） 用高级语言编写一个页面置换算法LRU的模拟程序。 设置恰当的数据结构，有效存储数据。 动态输入存储区块数、作业调度序列。 输出分配结果、置换过程以及其它相关的...