页面置换算法代码实现.doc

实验原理：
在内存运行过程中,若其所要访问得页面不在内存而需要把她们调入内存，但内存已经没有空闲空间时，为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据送磁盘得对换区中。但应将那个页面调出，需根据一定得算法来确定.通常，把选择换出页面得算法成为页面置换算法.置换算法得好坏,将直接影响到系统得性能。
一个好得页面置换算法，应具有较低得页面更换频率.从理论上讲，应将那些以后不再会访问得页面置换出，或者把那些在较长时间内不会在访问得页面调出.目前存在着许多种置换算法（如FIFO，OPT，LRU)，她们都试图更接近理论上得目标。
实验目得:
１．熟悉ＦIFO,ＯPＴ与ＬRU算法
2.比较三种算法得性能优劣
实验内容:
写出FIFO,OＰT与ＬＲU算法得程序代码,并比较它们得算法性能.
实验步骤：
代码如下:
#incｌｕde ＜stdio、h>
＃define　M　４ 　 ／／物理页数
＃dｅfine N 2０ﻩ//需要调入得页数
ｔypeｄef struct page
｛
int nｕｍ;
ｉnt time;
｝Page; ﻩ//物理页项,包括调入得页号与时间
Ｐaｇｅ mm［M]； //4个物理页
int　quｅue1[２0],queｕe2［20］,queue３［20];ﻩ／／记录置换得页
int Ｋ=0，S=0，Ｔ＝0；ﻩ//置换页数组得标识
int pos＝0；//记录存在最长时间项
／/初始化内存页表项及存储内存情况得空间
voｉd INＩT（）｛
int i；
for(i=0;i<Ｍ；i++）｛
ﻩmm［ｉ]、ｎum =-1；
ﻩﻩmｍ［i]、tiｍｅ　=0；
}
｝
//取得内存中存在时间最久得位置
iｎt GetＭax（){
ﻩｉnt ｍax=—１；
ｉnt　i;
foｒ(i=0；i〈Ｍ;i++）{
ﻩﻩif（ｍm［i]、tｉme 〉　max)｛
ﻩｍａｘ=mm［i］、time ；
ﻩ poｓ=i；
ﻩ｝
｝
ﻩrｅturｎ pos;
}
/／检查最长时间不使用页面
int　ｌoｎgesttimｅ(int　fold）
｛
ﻩinｔ ｉ;
int ｍax＝－1;
ﻩｆor(ｉ＝fold；i〈N；i++)｛
ﻩﻩif(ｍm[0］、ｎum！=i)｛
ﻩmm[0]、ｔｉmｅ++；
｝ﻩ
ﻩﻩif（mm［1]、ｎum！=i)｛
ﻩﻩﻩmm[１]、tiｍe++；
ﻩ}ﻩ
ﻩﻩｉf(mm［2]、num！=i）{
ﻩ mm［2]、tｉme++;
ﻩﻩ}ﻩ
ﻩif(mｍ［3］、num！＝i)｛
ﻩ ｍm[3］、time++;
ﻩ ｝ﻩ
}
ｆor(i=０;ｉ〈Ｍ;ｉ＋+)｛
ｉｆ(mm［i］、tiｍe>mａｘ）{
ﻩ max=mm［i]、time；
ﻩﻩﻩpoｓ=ｉ;
ﻩ ｝
｝
ﻩｒetuｒn pos;
｝
／/检查某页就是否在内存
int Ｅquａｔiｏｎ(int　fold)｛
int i;
ｆor（i=０；i〈M;i＋+)｛
if(ｍｍ［i]、num =＝　ｆｏld)
ﻩﻩｒeturn i；
ﻩ}
ﻩreturｎ　-1；
}
/／检查物理内存就是否已满，－1表满，其她不满
ｉnt Ｃheｃk（）｛
ﻩｉnt i;
ﻩfｏr（i＝0;i＜M；i+＋）｛
if（mｍ[i]、num　== －1)
ﻩ ﻩreturｎ i;
}
reｔurn　—1；
}
//先进先出
vｏiｄ FIFO（int fold)｛
ｉnt i;
ﻩiｎt　ａ,b,c；
ﻩa=Ｅqｕａtiｏn(fｏlｄ）；
ﻩ／/页已存在
iｆ（a !＝ -1）{}
//页不存在
else{
ﻩb＝Cｈeck(）；
／/内存还有空闲
ﻩﻩif（ｂ ！= －1）{
ｍm[ｂ］、nuｍ　=　fold;
ﻩﻩ｝
ﻩﻩ／/内存已满,需要置换
ﻩelse　{
ﻩ ｃ＝GｅtＭax(）；
ﻩ mｍ［c］、num = ｆold；
ﻩmm［c］、tｉmｅ = 0；
ﻩﻩ｝
ﻩﻩqｕｅuｅ1[K++]＝folｄ；
ﻩ}
ｆoｒ(i=0;i<M；i++）｛
ﻩiｆ（mｍ[i］、num　！＝ —1)｛
ﻩﻩmm［i]、tｉme +＋；
｝
ﻩ}
}
vｏid OPＴ(inｔ foｌd）
{
int a，b,ｃ；
ﻩa=Eqｕatiｏn（ｆold）；
ﻩif(a =＝ —１）{/／页不在内存
ﻩ b=Chｅcｋ（);
//内存还有空闲
ﻩﻩiｆ(b != -1)｛
ﻩ mm［ｂ]、num　= ｆｏld；
ﻩ｝
ﻩﻩ//内存已满,需要置换
ﻩ eｌsｅ｛
ﻩ c=longesｔtime(fｏld）;
mｍ［c]、ｎum = ｆｏlｄ;
ﻩﻩ mm［c]、ｔime ＝ 0；
ﻩﻩ｝
ﻩｑuｅue３［T+＋]=ｆoｌd;
}
｝
vｏiｄ ＬRU（iｎt　fold)
{
ﻩiｎt i；
ｉnt　ａ，b；
inｔ p；
ﻩａ=Eqｕatiｏn（foｌd);
if（a ！= —1）／/页已在内存
｛
ﻩ //把此项移动到链表最后一项
ﻩﻩif（a==３）／/此项已经在最后，不需要做任何改动
ﻩ return;
ﻩﻩelｓe
ﻩﻩ{
ﻩ ﻩｐ＝Equatiｏn（-1);
ﻩ ｉf(p＝=-1）//链表就是满得
{
ﻩﻩ ｆoｒ（；ａ<3;a++）
ﻩ ﻩﻩﻩmm[ａ]、num=mm［a＋1］、num;
ﻩﻩmｍ［3]、ｎum=foｌｄ;
ﻩ }
ﻩﻩﻩeｌsｅ if(ｐ〈＝3）//链表不满
ﻩ ﻩ{
ﻩ ｆor(；a<p－1;a＋＋)
ﻩ mm［ａ］、num=mｍ［a+1］、num；
ﻩﻩﻩ mm［a]、nｕｍ=fold;
ﻩﻩ}
ﻩﻩ}
ﻩ}
else
ﻩ{
ﻩﻩｂ=Cheｃk();
ﻩﻩif（b！=－1)／/不满
ﻩﻩ mｍ[ｂ］、nuｍ＝fold;
ﻩ ｅlｓe
｛
ﻩﻩ ｆoｒ（ｉ=0;i〈3；i++)
ﻩﻩﻩﻩmｍ［ｉ]、num＝mm[i＋1]、num；
ﻩﻩﻩmm[3］、num=fold; ﻩﻩ
ﻩﻩ}
ﻩquｅue2[S＋＋］=fold;
ﻩ}
｝
voiｄ mａin（)
｛
ﻩiｎt Ａ［Ｎ]，B［N]；
int i；
INIT（）;
pｒintf(”请依次输入%d个页面号:＼n"，Ｎ)；
for(i＝0；i〈N;i+＋）｛
ﻩ scanf（"％d",＆A［ｉ]）；
ﻩ}
／/FIＦO
for(ｉ=0;i＜N;i++){
B［i］=A［ｉ］;
｝
fｏr（ｉ=0；i<Ｎ;i+＋){
FIFO（ B[ｉ］ ）;ﻩ ﻩ
ﻩ}
printf(”FＩFO得"）;
prｉntf（"调入队列为:”）;
ﻩfｏr（ｉ=0；ｉ<K;i+＋)
ﻩﻩprｉntｆ（＂%3d”，queue1［i］);
priｎtｆ(”\n缺页次数为：％6d\n缺页率:%16。6f＼n\ｎ"，K，（fｌoａt)K/N)；
／/LRU
IＮＩT（）；
ﻩfor(i＝0；i<N；i++）{
ﻩB[ｉ]＝Ａ［ｉ]；
ﻩ｝
foｒ（i=0；ｉ<Ｎ;i++）{
ﻩLRU（ Ｂ[i］ ）； ﻩ
ﻩ}
ﻩprintf（＂ＬRＵ得”);
ﻩprｉｎtf（＂调入队列为：＂);
ﻩfｏｒ(i=0;i＜Ｓ;i＋+）
ﻩ pｒiｎtf（"%3d＂，qｕｅｕe2［i］）;
pｒintf(＂＼n缺页次数为：％６d\n缺页率:%16.6f\n＼n”，S，（ｆloaｔ）Ｓ/N）；
／/OPＴ
ﻩＩNIT(）；
for(i＝0；i＜Ｎ;i＋＋）｛
ﻩB[ｉ]=A[i]；
}
for（i=0;ｉ〈Ｎ;ｉ++）｛
ﻩOＰＴ( B［i] ）；
ﻩ｝
ﻩprintf(＂OPT得＂)；
ﻩprｉnｔｆ（＂调入队列为：”);
for(ｉ=0；i＜Ｔ;i++）
ﻩﻩｐrintf（”％3d”,ｑuｅue3[ｉ])；
ﻩprｉｎtf("＼n缺页次数为:％６ｄ\n缺页率：%16。6f\n\n”,T，（float)T/N);
｝