操作系统页面置换算法文档格式.docx
《操作系统页面置换算法文档格式.docx》由会员分享,可在线阅读,更多相关《操作系统页面置换算法文档格式.docx(21页珍藏版)》请在冰点文库上搜索。
![操作系统页面置换算法文档格式.docx](https://file1.bingdoc.com/fileroot1/2023-5/9/28007a23-d328-4cb4-a064-a05ac8cd19a6/28007a23-d328-4cb4-a064-a05ac8cd19a61.gif)
页面置换算法是虚拟存储管理实现的关键,要求在充分理解内存页面调度机制的根底上,模拟实现OPT、FIFO、LRU几种经典页面置换算法,比拟各种置换算法的效率与优缺点,从而了解虚拟存储实现的过程。
具体任务如下:
1)分析设计内容,给出解决方案
①要说明设计实现的原理;
②采用的数据结构:
定义为进程分配的物理块;
定义进程运行所需访问的页面号;
定义页的结构;
2〕模拟三种页面置换算法;
3〕比拟各种算法的优劣。
4〕对程序的每一局部要有详细的设计分析说明。
5〕源代码格式要规X。
6〕设计适宜的测试用例,对得到的运行结果要有分析。
任务要求:
Linux平台下实现〔Windows+VMware+Ubuntu〕
三、课程的详细设计
1〕系统设计
在进程运行过程中,假如其所要访问的页面不在内存而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据,送磁盘的对换区中。
但应将哪
个页面调出,须根据一定的算法来确定。
通常,把选择换出页面的算法称为页面置换算法。
一个好的页面置换算法,应具有较低的页面更换频率。
从理论上讲,应将那些以后不再会访问的页面换出,或将那些在较长时间内不会再访问的页面调出。
2〕主程序流程图
主流程图
3〕先进先出(FIFO)页面置换算法
算法的根本思想:
该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单只需把一个进程已调入内存的页面,按先后次序存入一个时间数组,并将其中时间值最大的页面进展淘汰,并替换入新的页面就可以实现。
算法流程图:
FIFO置换算法
4〕最优页面置换置换算法〔OPT〕
其所选择的被淘汰页面,将是永不使用的,或者是在最长时间内不再被访问的页面。
可保证获得最低的缺页率。
但由于人们目前还无法预知一个进程在内存的假如干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法也是无法实现的。
但是可利用该算法去评价其它算法。
OPT页面置换算法
5〕最近最久未使用页面置换算法LRU
当需要淘汰某一页时,选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。
该算法的主要出发点是,如果某页被访问了,如此它可能马上还被访问。
或者反过来说,如果某页很长时间未被访问,如此它在最近一段时间不会被访问。
LRU页面置换算法
四、源程序代码
#include"
stdio.h"
malloc.h"
#defineN20
#definenum3
/*进程分配物理块数目*/
intA[N]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
typedefstructpage/*页表映像*/
{
intaddress;
/*页面地址*/
structpage*next;
}page;
structpage*head,*run,*rear;
voidinitial()/*进程分配物理块*/
inti=1;
page*p,*q;
head=(page*)malloc(sizeof(page));
p=head;
for(i=1;
i<
=num;
i++)
{
q=(page*)malloc(sizeof(page));
p->
next=q;
q->
address=-1;
next=NULL;
p=q;
}
rear=p;
}
voidprint()
page*p=head->
next;
while(p)
if(p->
address!
=-1)/*防止输出-1*/
printf("
%d\t"
p->
address);
p=p->
\n"
);
intsearch(intn)/*判断链表中是否有n*/
page*p;
inti=0;
while(p->
next)
if(p->
next->
address==n)
printf("
Getitatthepage%d\n"
i+1);
run=p;
return1;
p=p->
i++;
return0;
voidchangeOPT(intn,intposition)
inti;
inttotal=0;
intflag=1;
/*默认链表填满*/
intdistance[num];
/*用于存放距离*/
intMAX;
intorder=0;
p=head->
q=head->
for(i=0;
num;
i++)/*初始化距离*/
distance[i]=100;
i=0;
while(p)/*判断链表中是否填满*/
address==-1)
flag=0;
break;
if(!
flag)/*链表没有填满的情况*/
address=n;
Changethepage%d\n"
else/*链表已经填满的情况*/
while(q)/*计算距离*/
for(i=position+1;
N;
if(q->
address==A[i])
distance[total]=i-position;
total++;
q=q->
MAX=distance[0];
i++)/*计算最大距离*/
if(distance[i]>
MAX)
MAX=distance[i];
order=i;
/*记录待替换的页面的位置*/
order+1);
while(p)/*页面替换*/
if(i==order)
voidchangeFIFO(intn,intposition)
//默认队列已满
page*p,*delect;
while(p)
address==-1)//队列未满
if(flag)//队列已满
delect=head->
delect->
head->
next=delect->
Delectfromthehead,andaddnewtotheend.\n"
rear->
next=delect;
rear=delect;
voidchangeLRU(intn,intposition)
/*默认为已满*/
while(p)/*判断链表是否已满*/
flag)/*链表没有满的情况*/
else/*链表已满的情况*/
while(q)
for(i=position-1;
i>
=0;
i--)/*向前计算距离*/
distance[total]=position-i;
i++)/*计算最远距离*/
floatOPT()
intlose=0;
floatlosef;
floatpercent;
if(search(A[i])==0)
lose++;
changeOPT(A[i],i);
print();
losef=(float)lose;
percent=1-(losef/N);
returnpercent;
floatLRU()
changeLRU(A[i],i);
floatFIFO()
page*p;
changeFIFO(A[i],i);
else
p=run->
run->
next=p->
next=p;
Moveittoendofqueue.\n"
voidmain()/*主函数局部*/
intchoice;
Selectthearithmetic:
\n
(1)OPT\n
(2)LRU\n(3)FIFO\nyourchoiceis:
"
scanf("
%d"
&
choice);
/*选择页面置换算法*/
initial();
/*创建进程*/
if(choice==1)/*采用OPT算法置换*/
percent=OPT();
/*计算OPT时的缺页率*/
ThepercentofOPTis%f\n"
percent);
elseif(choice==2)/*采用LRU算法置换*/
percent=LRU();
/*计算LRU时的缺页率*/
ThepercentofLRUis%f\n"
elseif(choice==3)/*采用FIFO算法置换*/
percent=FIFO();
/*计算FIFO时的缺页率*/
ThepercentofFIFOis%f\n"
else
Yourchoiceisinvalid."
五、
调试结果显示
(1)OPT置换算法
(2)LRU置换算法
LRU