linux环境下几种内存调度算法模拟00.docx
《linux环境下几种内存调度算法模拟00.docx》由会员分享，可在线阅读，更多相关《linux环境下几种内存调度算法模拟00.docx（16页珍藏版）》请在冰点文库上搜索。
linux环境下几种内存调度算法模拟00
课程设计（大作业）报告
课程名称：
操作系统
设计题目：
Linux环境下几种内存调度算法模拟
院系：
信息技术学院
班级：
设计者：
学号：
指导教师：
设计时间：
2011、12、20——2011、12、28
课程设计（大作业）报告
一、两种算法的原理分析
1．FIFO内存调度算法的原理
先进先出先出置换算法是最早出现的置换算法。
该算法总是淘汰最先进入内存的页面，即选择内存中驻留时间最久的页面予以淘汰。
（1）、在分配内存页面数（AP）大于进程页面数（PP）时,所有进程需要的页面（PP个页面）按提出要求的先后次序放入内存。
（2）在分配内存页面数（AP）大于进程页面数（PP）时,当然是按提出请求的次序将最先的AP个页面放入内存。
（3）这时有需要处理新的页面，则将原在内存中的AP个页面中最先进入的调出（称为FIFO）然后放入新页面。
（4）以后如果有新页面需要调入，按（3）的规则进行。
该算法的实现方式为：
把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指向最老页面的替换指针。
但是该算法是基于CPU按线性顺序访问地址空间的假设上的。
算法实现提示如下：
要得到“命中率”，必然应该有一个常量total-instruction记录页面总共使用次数；此外，需要一个变量记录总共换入页面的次数（需要换出页面，总是因为没有命中而产生的）diseffect。
利用公式1-
*100%可以得到命中率。
1）初始化。
设置两个数组page[PP]和pagecontrol[AP]分别表示进程页面数和内存分配页面数，并产生一个随机数序列main[total-instruction]（当然这个序列有page[]的下标随机构成），表示待处理的进程页面顺序，diseffect置零。
2）看main[]中是否有下一个元素，有，就由main[]中获取该页面下标，并转到3）；没有，就转到7）。
3）如果该page页已在内存中，就转到2）；否则转到4），同时未命中的diseffect加1.
4）观察pagecontrol是否占满，如果占满需将使用队列（6）中建立的）中最先进入的（就是队列第一单元）pagecontrol单元“清干净”，同时将对应的page[]单元置为“不在内存中”。
5）将该page[]与pagecontrol[]建立关系（可以改变pagecontrol[]的标示位，也可以采用指针连接，总之至少要使对应的pagecontrol单元包含两个信息：
一个它被使用了，二是那个page[]单元使用的。
Page[]单元包含两个信息：
对应的pagecontrol单元号、本page[]单元已在内存中）。
6）将用到的pagecontrol置入使用队列（这里的队列当然是一种先进先出的数据结构了，而不是泛指），返回2）。
7）显示公式1-
*100%完成。
算法特点：
所使用的内存页面构成一个队列。
2．（其他任选一个算法）OPT内存调度算法的原理
前提是在分配的内存页面占满的情况下。
最佳置换法是一种理想状况下的算法，它要求遍历所有的CPU待处理的进程页面序列（实际上由于待处理的页面有时取决于先前处理的页面，所以，很多情况下不可能得到完整的待处理页面序列。
在这个层面上，才说该算法是理想的），在这些页面中，如果有已经在内存中，而CPU不再处理的，就将其换出。
当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。
这种算法是不可能的。
算法实现提示如下:
1）初始化。
设置两个数组page[PP]和pagecontrol[AP]分别表示进程页面数和内存分配的页面数，并产生一个随机数序列main[total_instruction]（当然这个序列由page[]的下标随机构成），表示待处理的进程页面顺序，diseffect置零。
2）看main[]中是否有下一个元素，有，就从序列main[]中获取一个CPU待处理的页面号；没有，转到6）。
3）如果该页面已经在内存中了，就转到2），否则转到4）。
4）看是否有空闲的内存页面，如果有就直接返回该页面指针；如果没有，遍历所有未处理的进程页面序列，如果有位于内存中的页面，而CPU以后不再处理的，首先将其换出，返回页面指针；如果没有这样的页面，找寻到CPU最晚处理到的页面，将其换出，返回该内存页面指针。
5）将内存页面和待处理的进程页面建立联系，返回2）。
6）输出1-total_instruction/diseffcet*100%,结束。
二、两种算法的流程图表示
1．FIFO算法的流程图
2．（其他任选一个算法）OPT内存调度算法的流程图
三、两种算法的实现代码
1．FIFO内存调度算法的代码
#defineTRUE1
#defineFLASE0
#defineINVALID-1
#defineNULL0
#definetotal_instruction320
#definetotal_vp32
#defineclear_period50
typedefstruct
{
intpn,pfn,counter,time;
}pl_type;
pl_typepl[total_vp];
structpfc_struct{
intpn,pfn;
structpfc_struct*next;
};
typedefstructpfc_structpfc_type;
pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
intdiseffect,a[total_instruction];
intpage[total_instruction],offset[total_instruction];
intinitialize（int）;
intFIFO（int）;
intmain（）
{
ints,i,j;
srand（10*getpid（））;
s=（float）319*rand（）/32767/32767/2+1;
for（i=0;i{
if（s<0||s>319）
{
printf（"wheni==%d,Error,s==%d\n",i,s）;
exit（0）;
}
a[i]=s;
a[i+1]=a[i]+1;
a[i+2]=（float）a[i]*rand（）/32767/32767/2;
a[i+3]=a[i+2]+1;
s=（float）（318-a[i+2]）*rand（）/32767/32767/2+a[i+2]+2;
if（（a[i+2]>318）||（s>319））
printf（"a[%d+2],anumberwhichis:
%dands==%d\n",i,a[i+2],s）;
}
for（i=0;i{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for（i=4;i<32;i++）
{
printf（"----%2dpageframes---\n",i）;
FIFO（i）;
}
return0;
}
intinitialize（total_pf）
inttotal_pf;
{
inti;
diseffect=0;
for（i=0;i{
pl[i].pn=i;
pl[i].pfn=INVALID;
pl[i].counter=0;
pl[i].time=-1;
}
for（i=0;i{
pfc[i].next=&pfc[i+1];
pfc[i].pfn=i;
}
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0];
return0;
}
intFIFO（total_pf）
inttotal_pf;
{
inti,j;
pfc_type*p;
initialize（total_pf）;
busypf_head=busypf_tail=NULL;
for（i=0;i{
if（pl[page[i]].pfn==INVALID）
{
diseffect+=1;
if（freepf_head==NULL）
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID;
freepf_head=busypf_head;
freepf_head->next=NULL;
busypf_head=p;
}
p=freepf_head->next;
freepf_head->next=NULL;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
if（busypf_tail==NULL）
busypf_head=busypf_tail=freepf_head;
else
{
busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf（"FIFO:
%6.4f\n",1-（float）diseffect/320）;
return0;
}
2．（其他任选一个算法）OPT内存调度算法的代码
#defineTRUE1
#defineFLASE0
#defineINVALID-1
#defineNULL0
#definetotal_instruction320
#definetotal_vp32
#defineclear_period50
typedefstruct
{
intpn,pfn,counter,time;
}pl_type;
pl_typepl[total_vp];
structpfc_struct{
intpn,pfn;
structpfc_struct*next;
};
typedefstructpfc_structpfc_type;
pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
intdiseffect,a[total_instruction];
intpage[total_instruction],offset[total_instruction];
intinitialize（int）;
intOPT（int）;
intmain（）
{
ints,i,j;
srand（10*getpid（））;
s=（float）319*rand（）/32767/32767/2+1;
for（i=0;i{
if（s<0||s>319）
{
printf（"wheni==%d,Error,s==%d\n",i,s）;
exit（0）;
}
a[i]=s;
a[i+1]=a[i]+1;
a[i+2]=（float）a[i]*rand（）/32767/32767/2;
a[i+3]=a[i+2]+1;
s=（float）（318-a[i+2]）*rand（）/32767/32767/2+a[i+2]+2;
if（（a[i+2]>318）||（s>319））
printf（"a[%d+2],anumberwhichis:
%dands==%d\n",i,a[i+2],s）;
}
for（i=0;i{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for（i=4;i<32;i++）
{
printf（"----%2dpageframes---\n",i）;
OPT（i）;
}
return0;
}
intinitialize（total_pf）
inttotal_pf;
{
inti;
diseffect=0;
for（i=0;i{
pl[i].pn=i;
pl[i].pfn=INVALID;
pl[i].counter=0;
pl[i].time=-1;
}
for（i=0;i{
pfc[i].next=&pfc[i+1];
pfc[i].pfn=i;
}
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0];
return0;
}
intOPT（total_pf）
inttotal_pf;
{
inti,j,max,maxpage,d,dist[total_vp];
pfc_type*t;
initialize（total_pf）;
for（i=0;i{
//printf（"InOPTfor1,i=%d\n",i）;
if（pl[page[i]].pfn==INVALID）
{
diseffect++;
if（freepf_head==NULL）
{
for（j=0;jif（pl[j].pfn!
=INVALID）
dist[j]=32767;
else
dist[j]=0;
d=1;
for（j=i+1;j{
if（pl[page[j]].pfn!
=INVALID）
dist[page[j]]=d;
d++;
}
max=-1;
for（j=0;jif（max{
max=dist[j];
maxpage=j;
}
freepf_head=&pfc[pl[maxpage].pfn];
freepf_head->next=NULL;
pl[maxpage].pfn=INVALID;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
}
printf（"OPT:
%6.4f\n",1-（float）diseffect/320）;
return0;
}
四、结果分析
一、结果分析
1.分析设计结果是否达到预期目标
1）在实现OPT算法时，要将栈中指定的元素移到栈顶，但是一开始这个方法在运行到一定的页面序列后会出现索引越界的异常，通过与同学一晚上的讨论，最后修改了一下算法，从而算法能够准确的实现。
2）在计算缺页率时，由于访问页面次数不是固定的，得到的缺页率可能是一个无限循环的小数，因此经过在网上查找相关资料后用，用一个方法即可只输出小数点后两位。
4）在增加了手动输入索引号后，要再次使用算法时会出现异常，经过加入异常捕获后，就可以循环输入索引号并使用算法了。
1）FIFO运行结果：
2）OPT运行结果：
2.针对同一访问序列比较两种算法的命中率
由运行结果得出，该分析设计达到了预期的目标，计算出了FIFO和OPT两种算法的页帧及其命中率。
这两种算法的命中率大致在60%~80%左右，OPT算法比FIFO算法的命中率略高。
五、实验总结及心得体会
实验总结：
在本次设计中，首先，对于FIFO和OPT两种内存调度算法的原理和实现方式有了更好的了解。
其次，通过对两种内存调度算法的模拟实现，对比运行结果发现对于同一访问序列，OPT算法的命中率比FIFO算法更高。
再次通过在linux中调试和运行程序，对linux中的使用有了更深的记忆，尤其是在linux中实现文件的共享这一功能，实现这一功能就不用每次都在Vi中重复输入代码，减少了工作量。
另外在画流程图时，一定要读懂源代码，才能正确的画出。
通过本次课程设计，我对以前学过的一些知识有了更深的记忆和理解，特别是对linux中的各种命令的使用更加熟练，也学到了很多新的有用的知识。
心得体会:
在设计过程中由于粗心大意经常因为单词拼写错误，或者是字母的大小写还有程序的格式出错都会使得程序无法调试通过，我在最后输出结果时由于输出函数的输出表述错误使得程序运行后输出的结果错误。
告诉我在做任何是的时候都应该认真严谨。
此外在平日的学习过程中我们要注意细节，在注重基础知识的学习的同时，还应不断的提高自己的操作能力，另外还要学会对所学的知识学于致用，因为这是社会对我们专业的基本要求。
升级会员 