（奥鹏答卷）大连理工大学2023春秋季《操作系统》大作业题目（题目：页面置换算法FIFO算法）

大连理工大学远程与继续教育学院《操作系统》课程设计远程与继续教育学院《操作系统》大作业完整答案附后题目：学习中心：层次：专业：年级：年春/秋季学号：学生：辅导教师：完成日期：年月日

1.谈谈你对本课程学习过程中的心得体会与建议？2.《操作系统》课程设计,从以下5个题目中任选其一作答。《操作系统》课程设计注意：从以下5个题目中任选其一作答。总则：不限制编程语言，可以选用C/C++等（具体工具平台及语言可以自己根据自己的习惯选用，不必完全按照上述技术要求）作业具体要求：1.正文格式作业正文内容统一采用宋体，字号为小四。2.作业上交大作业上交时文件名写法为：[姓名奥鹏卡号学习中心]（如：戴卫东101410013979浙江台州奥鹏学习中心[1]VIP）；以附件形式上交离线作业（附件的大小限制在10M以内），选择已完成的作业（注意命名），点提交即可。注意：作业应该独立完成，不准抄袭其他同学作业、网站或者请人代做，如有雷同作业，成绩以零分计。题目一：页面置换算法FIFO算法要求：（1）撰写一份word文档，里面包括（算法思路、算法数据结构、主要函数代码、测试案例）章节。（2）算法思路：FIFO为先进先出算法，简单介绍该算法的基本思想，100字左右即可。（3）算法数据结构：列出主要用的数据结构，比如存储页面号序列page[]，存储装入物理块中的页面memery[]等，只需要列出数据结构名称即可。（4）主要函数代码：列出先进先出页面置换算法的代码。不需要列出主函数。（5）给出一个测试案例即可，比如设置物理块个数为3，页面序号701230423，代码应列出算法置换的具体细节。题目二：页面置换算法LRU算法要求：（1）撰写一份word文档，里面包括（算法思路、算法数据结构、主要函数代码、测试案例）章节。（2）算法思路：LRU为最近最久未使用算法，简单介绍该算法的基本思想，100字左右即可。（3）算法数据结构：列出主要用的数据结构，比如存储页面号序列page[]，存储装入物理块中的页面memery[]等，只需要列出数据结构名称即可。（4）主要函数代码：列出LRU页面置换算法的代码。不需要列出主函数。（5）给出一个测试案例即可，比如设置物理块个数为3，页面序号701230423，代码应列出算法置换的具体细节。题目三：进程同步与互斥生产者-消费者问题要求：（1）撰写一份word文档，里面包括（设计思路、流程（原理）图、基本内容、源代码）章节。（2）设计思路：简单介绍生产者进程的功能以及消费者进程的功能。（3）流程（原理）图：绘制流程图或原理图。（4）基本内容：详细介绍生产者进程与消费者进程之间的同步与互斥关系。（5）源代码：列出源代码，也可以仅列出伪代码。题目四：进程同步与互斥哲学家进餐问题要求：（1）撰写一份word文档，里面包括（设计思路、流程（原理）图、源代码）章节。（2）设计思路：简单描述哲学家进餐问题。可设计五个哲学家，每人都需要一双筷子。哲学家有两种活动：吃饭和思考，需要成功设计让每个哲学家能够顺利吃饭。（3）流程（原理）图：绘制流程图或原理图。（4）源代码：列出源代码，也可以仅列出伪代码。题目五：银行家算法要求：（1）撰写一份word文档，里面包括（算法思路、算法数据结构、主要函数代码）章节。（2）算法思路：简单介绍算法的基本思想，100字左右即可。（3）算法数据结构：列出主要用的数据结构，比如最大需求矩阵Max[][]，已分配矩阵Allocation[][]等，只需要列出数据结构名称即可。（4）主要函数代码：由于银行家算法比较难，列出部分核心代码即可。每一个函数需要简单说明此函数的功能。比如“coutprint()函数，该函数功能是打印输完整答案附后见下一页答案区：1.谈谈你对本课程学习过程中的心得体会与建议？转眼间，学习了一个学期的计算机操作系统课程即将结束。在这个学期中，通过老师的悉心教导，让我深切地体会到了计算机操作系统的一些原理和具体操作过程。在学习操作系统之前，我只是很肤浅地认为操作系统只是单纯地讲一些关于计算机方面的操作应用，并不了解其中的具体操作过程和实用性。通过这一学期的学习，我才知道操作系统(OperatingSystem，简称OS)是管理计算机系统的全部硬件资源包括软件资源及数据资源；控制程序运行；改善人机界面；为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，为用户提供方便的、有效的、友善的服务界面。!我从这次的设计中还感受到坚持的重要性。做事情不能轻言谈放弃，虽然过程不顺利，与想象中相去甚远。但是只要我们能坚持，朝着自己既定的目标前进，就一定会走到终点。一点小小的挫折实际上是在为最后的美景做铺垫，当我们守得云开见月明的时候，就会发现，沿途的曲折其实是在考验我们的且标是否坚定。坚持下来，我们会收获丰硕的果实。《操作系统》课程设计选择题目一：页面置换算法FIFO算法要求：（1）撰写一份word文档，里面包括（算法思路、算法数据结构、主要函数代码、测试案例）章节。（2）算法思路：FIFO为先进先出算法，简单介绍该算法的基本思想，100字左右即可。（3）算法数据结构：列出主要用的数据结构，比如存储页面号序列page[]，存储装入物理块中的页面memery[]等，只需要列出数据结构名称即可。（4）主要函数代码：列出先进先出页面置换算法的代码。不需要列出主函数。（5）给出一个测试案例即可，比如设置物理块个数为3，页面序号701230423，代码应列出算法置换的具体细节。页面置换算法FIFO算法 在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。在请求分页存储器管理系统中，我们需要一个页面置换算法，而先进先出算法就是最早出现的一种算法，利用该算法可以实现页面的置换，实现内存的充分利用，使进程可以执行。先进先出置换算法（FIFO）最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。1．先进先出（FIFO）该算法实现简单，只需把一个进程已调入内存的页面，按先后顺序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。1、输入当前要调用的页面号2、判断该页面是否已在队列内，若在队列内，不执行任何操作若不在队列内。则执行以下操作判断队列是否已满,若队列未满，直接把该页面号存入队列若队列已满，删除并返回队头元素，然后把该页面号存入队输出置换次数，依次输出置换出的页面。2．先进先出算法思路在请求分页存储器管理系统设计中，先进先出（FIFO）算法是一种给出页面访问的顺序与分配给作业的主存块数，使用队列作为数据结构编写算法，实现统计缺页次数与页面置换操作，该算法总是先淘汰最先进入内存的页面，即选择在内存中停留时间最久的页面予以淘汰。3.先进先出算法步骤1.设置一些页面参数，intpagenum=0内存页面数inttotal=0要访问的页面总数intlacknumber缺页的总数2.设置一个队列intseque[20]={0};队列长度设置为20，且初值设为03.执行算法输入1,2,3,4,1,2,5,1,2,3,4,5以输入-1结束4.算法数据结构Array[0][20]Voidmain()系统主函数Cin>>pagenum键盘输入页号存储页面号序列page[]存储装入物理块中的页面memery[]访问函数void

Visit(int)voidFIFO(void);打印函数print()核心函数FIFO()5.主要函数代码#include<>

intchoose;ageNomber=i;

p[i].PhyNomber=0;

p[i].Change=0;

p[i].Sta=0;

p[i].Visit=0;

}

cout<<endl<<"请输入物理块数";

cin>>MaxPhy;

cout<<"请输入页面走向以0结束"<<endl;

intj=0;

PageOrder[0]=1;

while(PageOrder[j]!=0)

{

j++;

Order++;

cin>>PageOrder[j];

if(j>99)

{

cout<<"超过最大数量，请重新输入,以0结束！";

continue;

}

}

}voidFifo()

{

intMax(structPageTableM[]);

structPageTablei[10];ageNomber=0;

i[j].Visit=0;

}

intb=0;ageNomber==PageOrder[k])

{

a=1;

count++;

cout<<"命中"<<"";

break;

}

}

if(a==1)continue;isit++;

continue;

}

for(j=0;j<MaxPhy;j++)ageNomber==0)

{

i[j]=p[PageOrder[k]];

cout<<"进入"<<"";

for(intl=0;l<=j;l++)

i[l].Visit++;

if(j==MaxPhy-1)

b=b+1;

break;

}

}voidLru()

{}intMax(structPageTableM[])isit;

for(intj=1;j<MaxPhy;j++)

{

if(temp<M[j].Visit)

{

temp=M[j].Visit;

Max=j;

}

}

return(Max);

}5．测试案例比如设置物理块个数为3，页面序号701230423，代码应列出算法置换的具体细节。时刻123456789访问顺序701230423M=3777222444000333221110003F12345678接下来我就讲下FIFO这种情况，FIFO就是先进先出的访问方式，根据题目里面的访问顺序：6012030423，所有首先访问的是7，当第一次访问6的时候，内存中当然是没有的，所以就会发生中断去读取数据，完成中断之后，内存中就有了一个6，接着访问的是0，当然此时内存中也没有0，所以又会发生一次中断，同理，完成中断之后，内存中就有0了，接下来访问的就是第三个数1，很明显，此时内存中也是没有该元素的，所以也会发生中断，完成中断后内存里面就有一个1了。此时内存中的数据为701。

接下来就要注意思想的转化了，因为题目中说了只有3块存储空间，到目前为止，3块空间都用完了。所以，在访问第4个数字时（也就是访问2的时候），必须先丢弃一个数据，根据题目要求是FIFO的原理，所以，理所当然就应该丢弃最先访问的7，并去访问新的数据--2，即2替换7的位置，所以也会发生中断，并且中断完成后内存中的数据是2