静态化网站和app的区别,ppt一键生成免费版,傻瓜式网站界面,wordpress 下载工具FIFO先进先出算法 java import java.util.LinkedList; import java.util.Queue;
public class Main { //先进先出的思想 是 用一个队列去模拟数据 如果当前不存在就是发生缺页中断了 就需要添加 如果已经满了 将队头的元素出队 即可 //先进先出 就是一个数组 frameCount publi…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));
}} h3 idOikGZOPT最佳置换算法/h3
选择淘汰以后永远不使用的页面或者在最长时间内不再被使用的页面。双层for 循环当前的页面内元素找到一个不存在或者位置最后的java
import java.util.LinkedList;
import java.util.Queue;public class Main {public static int OPT(int[] pages, int frameCount) {QueueInteger 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(QueueInteger 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) {QueueInteger queue new LinkedList();int frageCount 0;int n pages.length;for (int i 0; i n; i) {int page pages[i];boolean flagfalse;if (!queue.contains(page)) {flagtrue;frageCount;//移除头部 添加到末尾去if (queue.size() frameCount) {queue.poll(); //弹出最久没有使用的}queue.add(page);} else {//先移除queue.remove(page);//再加到末尾queue.add(page);}System.out.print(页面: page - 内存框架: queue);if (flagtrue){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)缺页中断);
}} h3 idAZw5JClock时钟算法/h3
h3 ide0704aae**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 flagfalse;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;flagtrue;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 (flagtrue){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和LRULFU需要维护额外的频率计数器增加了实现的复杂性。
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) {// 用于存储当前内存中的页面及其频率MapInteger, Integer pageFrequency new HashMap();// 用于存储页面的插入顺序用于处理频率相同的页面FIFOMapInteger, 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.EntryInteger, 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);}
}代码解释 数据结构 pageFrequency存储每个页面的访问频率。pageTime记录每个页面第一次被加载到内存中的时间用于处理频率相同的页面置换FIFO。 页面访问处理 页面缺失 增加页面缺失计数。如果内存已满找到频率最低且最早加载的页面进行置换。将新页面添加到内存中初始化其频率为1并记录加载时间。 页面命中 增加该页面的访问频率。 输出 每次页面访问后打印当前内存中所有页面及其访问频率。最终输出总的页面缺失次数。
LFU算法的优缺点总结
优点
有效的频率管理能够保留那些被频繁访问的页面减少页面缺失次数。适用于特定场景在一些访问模式中如热点数据频繁访问LFU表现优异。
缺点
实现复杂需要维护额外的数据结构频率计数器和时间戳增加了实现的复杂性。频率衰减问题某些实现中频率计数器可能会无限增大需定期重置或采用其他衰减策略。不适应动态访问模式如果某些页面的访问频率突然下降LFU可能仍然保留这些页面导致新热点页面被频繁置换。缓存污染对于一次性访问的页面频率会被计入可能导致其他需要长期缓存的页面被置换。
总结
LFU最不经常使用算法通过跟踪每个页面的访问频率选择访问次数最少的页面进行置换从而优化内存管理。尽管LFU在某些场景下表现出色但其实现复杂性和对动态访问模式的不适应性使其在实际操作系统中的应用受到一定限制。为了解决这些问题研究人员提出了多种改进版的LFU算法如LFU-K、LFU with Dynamic Aging等以提升算法的性能和适应性。 LFULeast Frequently Used最不经常使用是一种缓存替换算法。该算法根据数据的使用频率决定其被替换的优先级优先淘汰使用频率最低的数据保留那些被频繁访问的数据。LFU 算法适用于频繁访问的缓存项有较大概率被再次访问的场景。h3 id216c1668LFU算法原理/h3
LFU算法会为每个缓存项维护一个计数器记录其被访问的次数。当缓存空间满了需要替换数据时算法会选择访问频率最少的项进行淘汰。 **频率计数**每次缓存项被访问时计数器会增加。**淘汰策略**当缓存满了需要替换数据时优先选择那些计数器值最小的项。如果有多个频率相同的项通常会使用FIFO先进先出策略来选择最早进入缓存的项进行替换。h3 ideb40924e实现要点/h3
1. **哈希表最小堆**可以使用一个哈希表存储每个缓存项的访问频率以及一个最小堆来管理频率最小的项。
2. **哈希表双向链表**用一个哈希表存储缓存项另一个哈希表存储不同频率的双向链表以实现按频率访问的组织结构便于在相同频率时使用先进先出原则。
3. **计数器更新**每次访问缓存项时更新计数器并将该项移动到相应频率的链表中。h3 id1a63ac23示例/h3
假设缓存容量为31. 缓存初始为空。
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 id78102351优缺点/h3**优点**适合访问频率较高的数据项。**缺点**对于某些在一段时间内频繁访问但后续不再访问的数据可能会造成缓存命中率下降“缓存污染”现象。
