操作系统

2024-07-11 15:56| 来源: 网络整理| 查看: 265

一、算法介绍

1. 先进先出FIFO页面置换算法（来自百度百科-先进先出页面置换算法）

简介：优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。实现过程：假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：7, 0, 1, 2, 0, 3, 0,4,2,3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。釆用FIFO算法进行页面置换，进程访问页面2时，把最早进入内存的页面7换出。然后访问页面3时，再把2, 0, 1中最先进入内存的页换出。由下图可以看出，利用FIFO算法时进行了12次页面置换。访问页面70120304230321201701物理块1777222444000777物理块200033322211100物理块31110003332221缺页否√√√√√√√√√√√√√√√ 缺点：FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由Belady于1969年发现，故称为Belady异常，如下图所示。只有FIFO算法可能出现Belady异常，而LRU和OPT算法永远不会出现Belady异常。

2. 最近最久未使用LRU页面置换算法（来自博客园-操作系统之页面置换算法）

简介：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。实现过程：对上面的实例釆用LRU算法进行页面置换，如图所示。进程第一次对页面2访问时，将最近最久未被访问的页面7置换出去。然后访问页面3时，将最近最久未使用的页面1换出。补充说明：LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法。

访问页面70120304230321201701物理块1777224440111物理块200000033300物理块31133222227缺页否√√√√√√√√√√√√

二、代码实现

#include #include #include #include using namespace std; /* 2018.06.15 测试数据 ------------------------------------------- 3 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 # ------------------------------------------- 3 1 2 3 4 1 2 5 1 2 3 4 5 # ------------------------------------------- 5 0 1 2 3 4 5 0 2 1 8 5 2 7 6 0 1 2 # ------------------------------------------- */ int GetDistance(int currentPageID,int page);//按照页面编号获取在物理块内的页面最久未使用的时间（哪个距离当前pageID最远） class BLOCK{ public: int blockNum; //物理块总数 int pageNum; //物理块中的页面数量 int *pageID; //页面号（大小为blockNum） int *stayTime; //页面在物理块中的停留时间（与物理块ID对应） BLOCK(int num) { int i; pageNum=0; blockNum=num; pageID=new int[num]; stayTime=new int[num]; for(i=0;i

【本文地址】

操作系统

操作系统

今日新闻

推荐新闻