先进先出算法

操作系统题目： 存储管理 学生姓名： 庞丽华 学院：计算机与电子信息学院专业班级：计算机科学技术与网络工程类2008级（3）学 号： 0807100346 指导老师： 覃海生 时 间： 2010年7月3日存储管理FIFO算法一、实验目的：虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。在虚拟存储器系统中，作业无需全部装入，只要装入一部分就可运行。本实验使用请求分页存储管理。建立一个页表，要访问页面时,先查页表，若当前页在内存中，直接访问，不在内存中则调入该页到内存中，同时用FIFO算法淘汰最先进入内存的页。二、实验题目：先进先出(FIFO)页面置换算法三.实验源程序文件名:先进先出算法.c执行文件名:先进先出算法・exe、实验分析:程序设计过程中，只实现了页面的调入，淘汰等模拟过程，没有涉及到地址变换，所以程序中去掉了关于主存块号，磁盘上的位置等内容，程序相对简单。卞面是对程序相关内容说明：定义页数和内存块数存define1115 //m表示页数存definen3 //n表示物理块数页表与物理块由于页表里的内容我只保留了两项，一个时页号，一个是标志，所以将页表演变为一个一维数组mtPageTable[m]擞组PageTablek小为m,分别存储对应页面的状态，表示该页面是否在内存中。状态位=1表示该页在物理块中，=0表示不在内存中，默认处置为0。如PageTable[O]=l表示页面1在物理块中，PageTable[2]=0表示表示页面3不在物理块中。用一个一维数组表示n个物理块中的内容intBlock[n];数组中数值表示对应物理块中装入的页的编号。数组初始值都为0,表示没有装入页。如Elock[3]={3,1,2},则表示物理块中当前装入页为第1，2,3页。访问页面访问页面通过一个访问函数实现voidVisit(mt);访问过程中会遇到三种情况访问页时没有命中，且内存未装满，产生缺页中断，直接调入访问页需要进行的操作有：产生缺页中断，中断次数加1,将访问页调入内存，修改此页的状态，mteimpt-H-; 〃缺页中断次数加1PageTable[x-l]=l;〃修改状态位Block[i]=x; 〃页x调入物理块访问页时命中，此时直接访问访问页时内存已装满，且没有命中，产生缺页中断，调入该页至内存，淘汰最先进入的页。需要进行的操作有：产生缺页中断，中断次数加1,淘汰最先进入的页(即淘汰页指针所指的页）并修改淘汰页的状态位，调入访问页到物理块并修改调入页的状态位，最后还要修改淘汰页指针指向下一次需要淘汰的页iiitenupt-H-; 〃缺页中断次数加1PageTable[Block[k]-l]=0: 〃页Block[k]被淘汰，状态位修改为0Block[k]=x; 〃页x调入物理块PageTable[x-l]=l;〃页x状态位修改为1k=（k+l）%n; 〃修改下次被淘汰页指针主函数在主函数中输入页面走向，将其存入进程访问序列process[20]进程访问序列，然后依次访问即可。2）源代码#includeHstdafx.hH#iiiclude<iostieam.h>#iiiclude<iomanip.h>#definem5 //m表示页数#definen3 //n表示物理块数floatinteniipt=O;mtk=0;〃产生缺页中断的次数〃指向最先进入内存的页，即被淘汰的页mtPageTablefm];认处置为0mtBlock[n];〃定义页表，数组中数值=1表示该页在内存中，=0表示不在内存中，默〃定义物理块，数组中数值表示对应物理块中装入的页的编号mtprocess[20];//进程访问序列iiitnumbei-1;voidVisit(iiit);voidmain(void)〃用于标志访问次数〃访问函数mtmput;coi】t«喋进程共有页,请输入进程访问序列（范围八yvm«；用0表示结束）:cin»mput;fbr(intlength=O;iiiput!=0;length-H-) 〃将输入序列存入process数组,长度为length{process[length]=mput;ciii»input;}fbr(intj=Oj<lengthJ-H-)Visit(process[j]);〃依次访问页processfj]cout«n共H«length«H次访问，产生Y<in忙次缺页中断，缺页率为}voidVisit(iiitx){intij；cout«senv(2)«number«M:访问页<x«HH;〃第number次访问，访问页xfdr(i=0;i<n;i++)if(Block[i]==0)〃访问页x时没有命中，且内存未装满，产生缺页中断，直接调入访问页{mternipt++； 〃缺页中断次数加1PageTable[x-l]=l;〃修改状态位Block[i]=x; 〃页x调入物理块cout«"缺页中断内存未满调入页物理块内的页为”；for(j=Oj<=iJ++)cout«Block|j]«H”； //输出物理块内的页号cout«M\nH;break;}if(PageTable[x-1]==1) 〃访问页x时命中{cout«M命中 物理块内的页为”；fbr(j=Oj<n&&Block|J]!=0;j++)cout«Block[j]«H”； //输出物理块内的页号cout«M\nM;break;}}〃访问页x时内存已装满，且没有命中，调入该页至内存，淘汰最先进入的页{cout<y缺页中断淘汰页H«Block[k]«n调入页物理块内的页为H;mtenupt-H-; 〃缺页中断次数加1PageTable[Block[k]-i]=0;〃页Block[k]被淘汰，状态位修改为0Block[k]=x; 〃页x调入物理块PageTable[x-l]=l;//页x状态位修改为1k=(k+1)%n; 〃修改下次被淘汰页指针foi(j=Oj<nj++)cout«Block|j]«H”； //输出物理块内的页号cout«H\nH;}number++;〃访问次数加1}调试结果井音二二:-Mxi222323131414545151>東士口示表0.用-51••围范列问访®0”3断断输请5霄缺缺黑缺缺缺缺缺缺缺11115552223为为为为为为为为为为为■f&MAa」ARi■2eR・X」■ALJ內內內內內內內內內內內ftfefefefefefefefefeft1里里里里里里里里里里里WI-1-1-1-TI-1-f-1-1-T>-i-9物物物物物物物物物物物90•035142513入入入入入入入入率1235142缺亠升汰汰汰汰汰汰汰断^^<中e贝inu折折折折折折折折:u心mKIM.UklHuhNuhbunn口口口口口口口口aco,42缺缺翼缺缺缺缺缺缺翼yto®>e5112235142513‘k有M贾问y共3程2i?vl?vl?廿l?l?vl?v»