7-1 页面置换算法--FIFO (50 分)（思路详解）_fif0替换算法

物理块号 页号

0 0

1 1

2 2

页号：3 页内偏移：103

已无空闲物理块,置换!

物理块号 页号

0 3

1 1

2 2

结尾无空行

二：思路

===================================================================

算法思路：

1.为什么分页？ 我们之前学的连续分配方式中，对内存的空间利用并不合理，所以我们采用

分页这种离散的方式分配内存（离散体现在页表的地址映射当中）

2.分页:分页储存管理将进程的逻辑地址空间分为若干的页，并为每页加以编号，从0开始

如，第0页，第1页

物理块:把内存的物理地址空间分为若干个块，也为他们加以编号，在为进程分配内存的时候

以块为单位，将进程中的若干页分别加入到多个可以不相链接的的物理块中

3.页号:逻辑地址对页面大小 取整

页内地址也就是业内偏移:逻辑地址对页面大小取余

4.进程的运行当中，若其发现所要访问的页面不在内存中，则产生缺页中断。

当发生缺页中断时，

<1>:如果内存中还有剩余的物理块，那就将该页调入内存

<2>:如果内存中没有剩余的物理块, 那就采用页面置换算法

即操作系统必须在内存选择一个页面将其移出内存，将其移到外存对换区上,

以便为即将调入的页面让出空间，而用来选择淘汰哪一页的规则叫做页面置换算法

5.如果刚移出的页面,内存马上又要用了，这时又需要页面置换，那么这是我们最不想要的

结果，所以我们在移除页面的时候，就需要一种算法来选择移除的页面

写码构思：

1.那么我们该如何写码呢? ,通过分析数据我们可以得出，除了第一行的初始化，下面的每一行

输入，我们都要进行相应的判断和输出，那么就说明我们得创建一个函数专门处理这些，同时

很明显，函数的参数就是我们每次输入的逻辑地址

2.这里该如何初始化我们的数据结构呢？我选择的是结构体数组，可以存多组数组！

三:上码

===================================================================

/**

算法思路：

1.为什么分页？ 我们之前学的连续分配方式中，对内存的空间利用并不合理，所以我们采用

分页这种离散的方式分配内存（离散体现在页表的地址映射当中）

2.分页:分页储存管理将进程的逻辑地址空间分为若干的页，并为每页加以编号，从0开始

如，第0页，第1页

物理块:把内存的物理地址空间分为若干个块，也为他们加以编号，在为进程分配内存的时候

以块为单位，将进程中的若干页分别加入到多个可以不相链接的的物理块中

3.页号:逻辑地址对页面大小 取整

页内地址也就是业内偏移:逻辑地址对页面大小取余

4.进程的运行当中，若其发现所要访问的页面不在内存中，则产生缺页中断。

当发生缺页中断时，

<1>:如果内存中还有剩余的物理块，那就将该页调入内存

<2>:如果内存中没有剩余的物理块, 那就采用页面置换算法

即操作系统必须在内存选择一个页面将其移出内存，将其移到外存对换区上,

以便为即将调入的页面让出空间，而用来选择淘汰哪一页的规则叫做页面置换算法

5.如果刚移出的页面,内存马上又要用了，这时又需要页面置换，那么这是我们最不想要的

结果，所以我们在移除页面的时候，就需要一种算法来选择移除的页面

写码构思：

1.那么我们该如何写码呢? ,通过分析数据我们可以得出，除了第一行的初始化，下面的每一行

输入，我们都要进行相应的判断和输出，那么就说明我们得创建一个函数专门处理这些，同时

很明显，函数的参数就是我们每次输入的逻辑地址

2.这里该如何初始化我们的数据结构呢？我选择的是结构体数组，可以存多组数组！

*/

#include<bits/stdc++.h>

using namespace std;

struct Node{

int block; //块

string page; //页

}node[100];

int N,M;//N代表页面大小 M代表物理块数

queueq1;

queueq2;

void printSate(){

cout << “物理块号 页号” << endl;

for(int i = 0; i < M; i++){

cout << node[i].block << ’ ';

cout << node[i].page << endl;

}

}

void outResult(int address){

int pageNumber = address/N; //页号

int pageMigration = address%N; //页内偏移

stringstream st; //这是为了将int类型转换成 string 类型

st << pageNumber;

string str = st.str();

int temp1 = 0,temp2 = 0;

cout << “页号：”<< pageNumber <<" 页内偏移：" << pageMigration << endl;

//遍历内存的物理块中是否有该页号

for(int i = 0; i < M; i++){

if(node[i].page == str){

temp1 = 1;

}

if(node[i].page == “void”){ //统计有空闲的位置

temp2++;

}

}

//在内存的时候

if(temp1 == 1){

printSate();

}

//不在内存的时候 ,且内存中还有空间

if(temp1 == 0 && temp2 > 0){

cout << “该页不在内存中,调入!” << endl;

//更新物理块中的页号状态

for(int i = 0; i < M; i++){

if(node[i].page == “void”){

node[i].page = str;

q1.push(node[i].block);

q2.push(node[i].page);

break;

}

}

printSate();

}

//当不在内存的时候,内存中没有空间

if(temp1 == 0 && temp2 == 0){

cout << “已无空闲物理块,置换!” << endl;

int bk = q1.front(); q1.pop();

string page = q2.front(); q2.pop(); //将队列当中的首个元素移除

q2.push(str);//将新的页号入队

q1.push(bk);//其物理块号是固定不变的

for(int i = 0; i < M; i++){

if(node[i].block == bk) {//这里就是我们根据物理块号更新 页号状态

node[i].page = str;

}

}

printSate();

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！

如果你觉得这些内容对你有帮助，可以扫码获取！！（资料价值较高，非无偿）

总结

对于面试，一定要有良好的心态，这位小伙伴面试美团的时候没有被前面阿里的面试影响到，发挥也很正常，也就能顺利拿下美团的offer。
小编还整理了大厂java程序员面试涉及到的绝大部分面试题及答案，希望能帮助到大家，

最后感谢大家的支持，希望小编整理的资料能够帮助到大家！也祝愿大家都能够升职加薪！
《一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码》，点击传送门即可获取！

对于面试，一定要有良好的心态，这位小伙伴面试美团的时候没有被前面阿里的面试影响到，发挥也很正常，也就能顺利拿下美团的offer。
小编还整理了大厂java程序员面试涉及到的绝大部分面试题及答案，希望能帮助到大家，

[外链图片转存中…(img-3SrTWEZ9-1711570671069)]

[外链图片转存中…(img-REimJpWf-1711570671069)]

最后感谢大家的支持，希望小编整理的资料能够帮助到大家！也祝愿大家都能够升职加薪！
《一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码》，点击传送门即可获取！