操作系统页面置换算法Java实现(LFU,OPT,LRU,LFU,CLOCK)

FIFO先进先出算法

```java import java.util.LinkedList; import java.util.Queue;

public class Main {
//先进先出的思想 是 用一个队列去模拟数据 如果当前不存在就是发生缺页中断了 就需要添加 如果已经满了 将队头的元素出队 即可
//先进先出 就是一个数组 frameCount
public static int FIFO(int[] pages, int frameCount) {
Queue queue = new LinkedList<>();
int pagesFaults = 0; //页面终端的次数
for (int page : pages) {
if (!queue.contains(page)) {
//不存在就缺页了
pagesFaults++;
// 如果页面框架已满，则移除最早进入的页面
if (queue.size() == frameCount) {
queue.poll(); // 移除最早的页面）
}
queue.add(page);
}
System.out.println("页面: " + page + " -> 内存框架: " + queue);
}
return pagesFaults;
}

public static void main(String[] args) {int arr1[] = {3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4};System.out.println(FIFO(arr1, 3));System.out.println("验证bleady现象");int arr2[] = {3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4};System.out.println(FIFO(arr2, 4));
}

}

![](https://cdn.nlark.com/yuque/0/2024/png/38629240/1730959589251-0e3d864e-e03e-4738-83b1-cabc767cdf86.png)<h3 id="OikGZ">OPT最佳置换算法</h3>
选择淘汰以后永远不使用的页面或者在最长时间内不再被使用的页面。双层for 循环当前的页面内元素，找到一个不存在或者位置最后的```java
import java.util.LinkedList;
import java.util.Queue;public class Main {public static int OPT(int[] pages, int frameCount) {Queue<Integer> queue = new LinkedList<>();int pageFaults = 0;int n = pages.length;for (int i = 0; i < n; i++) {if (!queue.contains(pages[i])) {pageFaults++;  //发生页面中断了if (queue.size() == frameCount) {//考虑淘汰谁出去int page = findPage(queue, pages, i);  //往后看queue.remove(page); // 删除需要置换的页面}queue.add(pages[i]);}System.out.println("页面: " + pages[i] + " -> 内存框架: " + queue);}return pageFaults;}private static int findPage(Queue<Integer> pageFrames, int[] pages, int currentIndex) {int farthestIndex = -1;int pageToReplace = -1;// 遍历当权的queuefor (int page : pageFrames) {int nextUseIndex = Integer.MAX_VALUE;  //假设最远的位置// 找出页面下次访问的索引位置for (int j = currentIndex + 1; j < pages.length; j++) {if (pages[j] == page) {nextUseIndex = j;break;}}// 找到下次使用最远的页面if (nextUseIndex > farthestIndex) {farthestIndex = nextUseIndex;pageToReplace = page;}}return  pageToReplace;}public static void main(String[] args) {int[] a = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};System.out.println(OPT(a, 3));}
}

LRU缓存算法

```java import java.util.LinkedList; import java.util.Queue;

public class Main {

public static int LRU(int[] pages, int frameCount) {Queue<Integer> queue = new LinkedList<>();int frageCount = 0;int n = pages.length;for (int i = 0; i < n; i++) {int page = pages[i];boolean flag=false;if (!queue.contains(page)) {flag=true;frageCount++;//移除头部 添加到末尾去if (queue.size() == frameCount) {queue.poll(); //弹出最久没有使用的}queue.add(page);} else {//先移除queue.remove(page);//再加到末尾queue.add(page);}System.out.print("页面: " + page + " -> 内存框架: " + queue);if (flag==true){System.out.println("  发生缺页中断");}else{System.out.println();}}return  frageCount;
}public static void main(String[] args) {int[] a = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};System.out.println("一共发生"+LRU(a, 3)+"缺页中断");
}

}

![](https://cdn.nlark.com/yuque/0/2024/png/38629240/1730961672007-f3a00b4e-312a-4840-942c-d2b8deec4ae9.png)<h3 id="AZw5J">Clock时钟算法</h3>
<h3 id="e0704aae">**Clock算法的步骤**</h3>
1. **初始化**：- 为每个页面框架分配一个**使用位**，初始为0。- 设置一个指针（通常称为“手”）指向第一个页面框架。
2. **页面访问**：- 当一个页面被访问时：* **如果页面已经在内存中，设置其使用位为1。*** **如果页面不在内存中，发生页面缺失：**+ **如果有空闲的页面框架，直接将页面加载到空闲框架中，并设置使用位为1。**+ **如果没有空闲框架，启动页面置换过程。**
3. **页面置换**：- 检查指针指向的页面的使用位：* **使用位为0**：将该页面置换出去，加载新页面到该位置，并将使用位设置为1。然后将指针移动到下一个页面框架。* **使用位为1**：将使用位重置为0，指针移动到下一个页面框架，继续检查。- 重复上述过程，直到找到一个使用位为0的页面进行置换。```java
package 操作系统代码.页面置换算法.clock时钟算法;import java.util.Arrays;public class Main {//要构建成一个循环的 指针    通过取模来实现public static int CLOCK(int[] pages, int fragmeCount) {int[] pageFrames = new int[fragmeCount]; //创建一共循环块Arrays.fill(pageFrames, -1); //刚开始的框架boolean[] useBits = new boolean[fragmeCount]; //访问位int current = 0;  //当前所在int pageFaults = 0;//页面确实for (int page : pages) {boolean flag=false;boolean isExist = false;int frameIndex = -1;//如果存在 访问为变为truefor (int i = 0; i < fragmeCount; i++) {if (pageFrames[i] == page) {frameIndex = i;isExist = true;break;}}if (isExist) {useBits[frameIndex] = true;} else {pageFaults++;flag=true;while (true) {if (!useBits[current]) {  //当前访问位为0 也就是false1了 将当前的移除pageFrames[current] = page;useBits[current] = true;current = (current + 1) % fragmeCount;break;} else {useBits[current] = false;current = (current + 1) % fragmeCount;}}}System.out.print("页面: " + page + " -> 内存框架: " + Arrays.toString(pageFrames));if (flag==true){System.out.println("  发生缺页中断");}else{System.out.println();}}return pageFaults;}public static void main(String[] args) {int[] a = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};int frameCount = 4; // 页面框架数量int totalPageFaults = CLOCK(a, frameCount);System.out.println("总页面缺失数: " + totalPageFaults);}
}

LFU算法

LFU（**Least Frequently Used**，**最不经常使用**）算法是一种页面置换策略，旨在通过替换使用频率最低的页面来优化内存管理。这种算法基于一个假设：那些在过去较少被访问的页面，在未来也可能不常被访问，因此更适合被置换出去。### **LFU算法的基本思想**LFU算法选择那些在当前内存中被访问次数最少的页面进行置换。与其他算法（如FIFO、LRU）主要关注页面的时间特性不同，LFU关注的是页面的频率特性。具体来说，当需要置换页面时，LFU会：1. **统计每个页面的访问频率**：记录每个页面在内存中被访问的次数。
2. **选择访问频率最低的页面**：当内存已满且需要置换页面时，选择访问频率最少的页面进行置换。
3. **处理频率相同的页面**：如果有多个页面具有相同的最低访问频率，可以采用其他策略（如FIFO）来决定具体置换哪个页面。### **LFU算法的工作步骤**1. **初始化**：- 创建一个数据结构（通常是哈希表）来存储当前内存中的页面及其对应的访问频率。- 设置页面框架的数量（即内存中可以同时容纳的页面数量）。2. **页面访问**：- **页面命中**（Page Hit）：如果访问的页面已经在内存中，增加该页面的访问频率。- **页面缺失**（Page Fault）：如果访问的页面不在内存中，发生页面缺失。- 如果内存中还有空闲页面框架，直接将新页面加载到空闲框架中，并将其访问频率设置为1。- 如果内存已满，选择访问频率最低的页面进行置换，将新页面加载到该位置，并将新页面的访问频率设置为1。3. **频率更新**：- 每次页面被访问时，更新其访问频率。- 在某些实现中，可能需要周期性地调整频率计数器以防止频率数值无限增大。### **LFU算法的优缺点**#### **优点**1. **高效的频率管理**：LFU算法能够有效地管理页面的访问频率，减少那些经常被访问的页面被置换的可能性。
2. **适用于频繁访问模式**：在某些应用场景中，如缓存系统，LFU算法能够保持热点数据在内存中，提高系统性能。#### **缺点**1. **实现复杂**：相比FIFO和LRU，LFU需要维护额外的频率计数器，增加了实现的复杂性。
2. **不适应动态访问模式**：如果某些页面的访问频率在一段时间后突然下降，LFU可能仍然保留这些页面，导致新热点页面被频繁置换。
3. **频率数值膨胀**：频率计数器可能随着时间的推移而变得非常大，需要定期重置或使用其他技术来管理频率数值。### **LFU算法的示例**假设有3个页面框架，页面访问序列为：`[1, 2, 3, 2, 4, 1, 5, 2, 1, 2, 3, 4, 5]`#### **步骤解析**| 步骤 | 访问页面 | 页面框架状态          | 访问频率（页面:频率） | 页面缺失 |
|------|----------|-----------------------|-----------------------|----------|
| 1    | 1        | [1, -, -]             | {1:1}                 | 是       |
| 2    | 2        | [1, 2, -]             | {1:1, 2:1}            | 是       |
| 3    | 3        | [1, 2, 3]             | {1:1, 2:1, 3:1}       | 是       |
| 4    | 2        | [1, 2, 3]             | {1:1, 2:2, 3:1}       | 否       |
| 5    | 4        | [1, 2, 4]             | {1:1, 2:2, 4:1}       | 是（置换页面3）|
| 6    | 1        | [1, 2, 4]             | {1:2, 2:2, 4:1}       | 否       |
| 7    | 5        | [5, 2, 4]             | {5:1, 2:2, 4:1}       | 是（置换页面1）|
| 8    | 2        | [5, 2, 4]             | {5:1, 2:3, 4:1}       | 否       |
| 9    | 1        | [5, 2, 1]             | {5:1, 2:3, 1:1}       | 是（置换页面4）|
| 10   | 2        | [5, 2, 1]             | {5:1, 2:4, 1:1}       | 否       |
| 11   | 3        | [5, 2, 3]             | {5:1, 2:4, 3:1}       | 是（置换页面1）|
| 12   | 4        | [5, 2, 4]             | {5:1, 2:4, 4:2}       | 是（置换页面3）|
| 13   | 5        | [5, 2, 4]             | {5:2, 2:4, 4:2}       | 否       |**总页面缺失数：8**#### **解释**1. **步骤1-3**：加载页面1、2、3到内存，均发生页面缺失。
2. **步骤4**：页面2已在内存中，更新其频率。
3. **步骤5**：页面4缺失，选择频率最低的页面3进行置换（页面1和3的频率均为1，但假设选择了页面3）。
4. **步骤6**：页面1已在内存中，更新其频率。
5. **步骤7**：页面5缺失，选择频率最低的页面1进行置换。
6. **步骤8**：页面2已在内存中，更新其频率。
7. **步骤9**：页面1缺失，选择频率最低的页面4进行置换。
8. **步骤10**：页面2已在内存中，更新其频率。
9. **步骤11**：页面3缺失，选择频率最低的页面1进行置换。
10. **步骤12**：页面4缺失，选择频率最低的页面3进行置换。
11. **步骤13**：页面5已在内存中，更新其频率。### **LFU算法的实现示例（Java）**以下是一个简单的Java实现示例，展示如何使用LFU算法进行页面置换：```java
import java.util.*;public class LFUPageReplacement {public static int LFU(int[] pages, int frameCount) {// 用于存储当前内存中的页面及其频率Map<Integer, Integer> pageFrequency = new HashMap<>();// 用于存储页面的插入顺序（用于处理频率相同的页面，FIFO）Map<Integer, Integer> pageTime = new HashMap<>();int pageFaults = 0;int currentTime = 0;for (int page : pages) {currentTime++;if (!pageFrequency.containsKey(page)) {// 页面缺失pageFaults++;if (pageFrequency.size() == frameCount) {// 找到最不常使用的页面int lfuPage = -1;int minFreq = Integer.MAX_VALUE;int oldestTime = Integer.MAX_VALUE;for (Map.Entry<Integer, Integer> entry : pageFrequency.entrySet()) {int p = entry.getKey();int freq = entry.getValue();if (freq < minFreq) {minFreq = freq;lfuPage = p;oldestTime = pageTime.get(p);} else if (freq == minFreq) {// 频率相同，选择最早插入的页面if (pageTime.get(p) < oldestTime) {lfuPage = p;oldestTime = pageTime.get(p);}}}// 移除LFU页面pageFrequency.remove(lfuPage);pageTime.remove(lfuPage);}// 添加新页面pageFrequency.put(page, 1);pageTime.put(page, currentTime);} else {// 页面命中，增加频率pageFrequency.put(page, pageFrequency.get(page) + 1);}System.out.println("页面: " + page + " -> 当前内存: " + pageFrequency);}return pageFaults;}public static void main(String[] args) {int[] pages = {1, 2, 3, 2, 4, 1, 5, 2, 1, 2, 3, 4, 5};int frameCount = 3;int faults = LFU(pages, frameCount);System.out.println("总页面缺失数: " + faults);}
}

代码解释

1. 数据结构：

   • pageFrequency：存储每个页面的访问频率。
   • pageTime：记录每个页面第一次被加载到内存中的时间，用于处理频率相同的页面置换（FIFO）。

2. 页面访问处理：

   • 页面缺失：
     • 增加页面缺失计数。
     • 如果内存已满，找到频率最低且最早加载的页面进行置换。
     • 将新页面添加到内存中，初始化其频率为1，并记录加载时间。
   • 页面命中：
     • 增加该页面的访问频率。

3. 输出：

   • 每次页面访问后，打印当前内存中所有页面及其访问频率。
   • 最终输出总的页面缺失次数。

LFU算法的优缺点总结

优点：

1. 有效的频率管理：能够保留那些被频繁访问的页面，减少页面缺失次数。
2. 适用于特定场景：在一些访问模式中（如热点数据频繁访问），LFU表现优异。

缺点：

1. 实现复杂：需要维护额外的数据结构（频率计数器和时间戳），增加了实现的复杂性。
2. 频率衰减问题：某些实现中，频率计数器可能会无限增大，需定期重置或采用其他衰减策略。
3. 不适应动态访问模式：如果某些页面的访问频率突然下降，LFU可能仍然保留这些页面，导致新热点页面被频繁置换。
4. 缓存污染：对于一次性访问的页面，频率会被计入，可能导致其他需要长期缓存的页面被置换。

总结

LFU（最不经常使用）算法通过跟踪每个页面的访问频率，选择访问次数最少的页面进行置换，从而优化内存管理。尽管LFU在某些场景下表现出色，但其实现复杂性和对动态访问模式的不适应性使其在实际操作系统中的应用受到一定限制。为了解决这些问题，研究人员提出了多种改进版的LFU算法，如LFU-K、LFU with Dynamic Aging等，以提升算法的性能和适应性。

LFU（Least Frequently Used，最不经常使用）是一种缓存替换算法。该算法根据数据的使用频率决定其被替换的优先级，优先淘汰使用频率最低的数据，保留那些被频繁访问的数据。LFU 算法适用于频繁访问的缓存项有较大概率被再次访问的场景。<h3 id="216c1668">LFU算法原理</h3>
LFU算法会为每个缓存项维护一个计数器，记录其被访问的次数。当缓存空间满了需要替换数据时，算法会选择访问频率最少的项进行淘汰。+ **频率计数**：每次缓存项被访问时，计数器会增加。
+ **淘汰策略**：当缓存满了，需要替换数据时，优先选择那些计数器值最小的项。如果有多个频率相同的项，通常会使用FIFO（先进先出）策略来选择最早进入缓存的项进行替换。<h3 id="eb40924e">实现要点</h3>
1. **哈希表+最小堆**：可以使用一个哈希表存储每个缓存项的访问频率，以及一个最小堆来管理频率最小的项。
2. **哈希表+双向链表**：用一个哈希表存储缓存项，另一个哈希表存储不同频率的双向链表，以实现按频率访问的组织结构，便于在相同频率时使用先进先出原则。
3. **计数器更新**：每次访问缓存项时，更新计数器，并将该项移动到相应频率的链表中。<h3 id="1a63ac23">示例</h3>
假设缓存容量为3：1. 缓存初始为空。
2. 访问数据`A`，缓存变为`[A:1]`。
3. 访问数据`B`，缓存变为`[A:1, B:1]`。
4. 访问数据`C`，缓存变为`[A:1, B:1, C:1]`。
5. 再次访问数据`A`，缓存变为`[A:2, B:1, C:1]`。
6. 访问数据`D`，缓存已满，需要淘汰一个数据。`B`和`C`频率相同，按照FIFO策略淘汰`B`，缓存变为`[A:2, C:1, D:1]`。<h3 id="78102351">优缺点</h3>
+ **优点**：适合访问频率较高的数据项。
+ **缺点**：对于某些在一段时间内频繁访问但后续不再访问的数据，可能会造成缓存命中率下降（“缓存污染”现象）。