FIFO（先进先出）算法的基本原理为：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
数据结构
先定义一个主存表memeoryList用来存放主存中的地址空间用来进行页面变换
再定义一个pageList作为页表
替换
注意这里首先判断当前位置是否被占用，再判断页面是否在当前位置。如果需要中断替换，则进行判断由于是FIFO算法，需要替换放得最久的
替换的位置按照公式更新
position = (position+1)%memoryList.size();
流程图
缺点
FIFO算法的缺页率占到60%因此并不适合在现代操作系统中使用。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<iostream> #include<deque> #include<cstdio> #define NONE 999 using namespace std; struct Lnode{ int id; }; deque<Lnode> memoryList; deque<int> pageList; void initMemory(int memorySize){ for(int i=0;i<memorySize;i++){ struct Lnode temp; temp.id = NONE; memoryList.push_back(temp); } } float FIFO(){ int replace_count=0; int position=0; cout<<"\n页表 替换? 内容\n"; for(int i=0;i<pageList.size();i++){ cout<<pageList[i]<<" "; int j=0; for(j=0;j<memoryList.size();j++){ if(memoryList[j].id==NONE||memoryList[j].id==pageList[i]){ memoryList[j].id=pageList[i]; break; } } if(j==memoryList.size()){ replace_count++; printf("%d被%d替换掉！ ", memoryList[position],pageList[i]); memoryList[position].id = pageList[i]; position = (position+1)%memoryList.size(); }else{ printf(" "); } for(j=0;j<memoryList.size();j++){ if(memoryList[j].id!=NONE) cout<<memoryList[j].id<<" "; else cout<<" "; } cout<<endl; } return replace_count; } int main(){ int num = 20; cout<<"输入流："<<endl; int arrayList[20] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}; initMemory(3); for(int i=0;i<num;i++){ pageList.push_back(arrayList[i]); cout<<pageList[i]<<" "; } cout<<endl; float replace_count = FIFO(); cout<<"\n置换率为："<<replace_count<<"/"<<num<<"="<<replace_count/num<<endl; } |
结果
