操作系统页面置换算法.docx
- 文档编号:10033872
- 上传时间:2023-05-23
- 格式:DOCX
- 页数:24
- 大小:333.18KB
操作系统页面置换算法.docx
《操作系统页面置换算法.docx》由会员分享,可在线阅读,更多相关《操作系统页面置换算法.docx(24页珍藏版)》请在冰点文库上搜索。
操作系统页面置换算法
操作系统
课程设计报告
院(系):
信息与数学学院
专业:
信息与计算科学
姓名:
三
班级:
_信计11402
学号:
122914
题目:
页面置换算法
指导教师:
庆生
2017年5月27日
一、课程设计目的
《Linux操作系统课程设计》是在学完《操作系统》课程之后的实践教学环节,是复习和检验所学课程的重要手段。
通过实验环节,加深学生对操作系统基本原理和工作过程的理解,提高学生独立分析问题、解决问题的能力,增强学生的动手能力。
二、课程设计的任务和要求
由于具体的操作系统相当复杂,不可能对所有管理系统进行详细地分析。
因此,选择了操作系统中最重要的管理之一存储器管理,作为本设计的任务。
页面置换算法是虚拟存储管理实现的关键,要求在充分理解存页面调度机制的基础上,模拟实现OPT、FIFO、LRU几种经典页面置换算法,比较各种置换算法的效率及优缺点,从而了解虚拟存储实现的过程。
具体任务如下:
1)分析设计容,给出解决方案
①要说明设计实现的原理;
②采用的数据结构:
定义为进程分配的物理块;定义进程运行所需访问的页面号;定义页的结构;
2)模拟三种页面置换算法;
3)比较各种算法的优劣。
4)对程序的每一部分要有详细的设计分析说明。
5)源代码格式要规。
6)设计合适的测试用例,对得到的运行结果要有分析。
任务要求:
Linux平台下实现(Windows+VMware+Ubuntu)
三、课程的详细设计
1)系统设计
在进程运行过程中,若其所要访问的页面不在存而需把它们调入存,但存已无空闲空间时,为了保证该进程能正常运行,系统必须从存中调出一页程序或数据,送磁盘的对换区中。
但应将哪 个页面调出,须根据一定的算法来确定。
通常,把选择换出页面的算法称为页面置换算法。
一个好的页面置换算法,应具有较低的页面更换频率。
从理论上讲,应将那些以后不再会访问的页面换出,或将那些在较长时间不会再访问的页面调出。
2)主程序流程图
主流程图
3)先进先出(FIFO)页面置换算法
算法的基本思想:
该算法总是淘汰最先进入存的页面,即选择在存中驻留时间最久的页面予以淘汰。
该算法实现简单只需把一个进程已调入存的页面,按先后次序存入一个时间数组,并将其中时间值最大的页面进行淘汰,并替换入新的页面就可以实现。
算法流程图:
FIFO置换算法
4)最佳页面置换置换算法(OPT)
算法的基本思想:
其所选择的被淘汰页面,将是永不使用的,或者是在最长时间不再被访问的页面。
可保证获得最低的缺页率。
但由于人们目前还无法预知一个进程在存的若干个页面中,哪一个页面是未来最长时间不再被访问的,因而该算法也是无法实现的。
但是可利用该算法去评价其它算法。
算法流程图:
OPT页面置换算法
5)最近最久未使用页面置换算法LRU
算法的基本思想:
当需要淘汰某一页时,选择离当前时间最近的一段时间最久没有使用过的页先淘汰。
该算法的主要出发点是,如果某页被访问了,则它可能马上还被访问。
或者反过来说,如果某页很长时间未被访问,则它在最近一段时间不会被访问。
算法流程图:
LRU页面置换算法
四、源程序代码
#include"stdio.h"
#include"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;
q->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->next;
}
printf("\n");
}
intsearch(intn)/*判断链表中是否有n*/
{
page*p;
inti=0;
p=head;
while(p->next)
{
if(p->next->address==n)
{
printf("Getitatthepage%d\n",i+1);
run=p;
return1;
}
p=p->next;
i++;
}
return0;
}
voidchangeOPT(intn,intposition)
{
inti;
inttotal=0;
intflag=1;/*默认链表填满*/
intdistance[num];/*用于存放距离*/
intMAX;
intorder=0;
page*p,*q;
p=head->next;
q=head->next;
for(i=0;i { distance[i]=100; } i=0; while(p)/*判断链表中是否填满*/ { if(p->address==-1) { flag=0; break; } p=p->next; i++; } if(! flag)/*链表没有填满的情况*/ { p->address=n; printf("Changethepage%d\n",i+1); } else/*链表已经填满的情况*/ { while(q)/*计算距离*/ { for(i=position+1;i { if(q->address==A[i]) { distance[total]=i-position; break; } } total++; q=q->next; } MAX=distance[0]; for(i=0;i { if(distance[i]>MAX) { MAX=distance[i]; order=i;/*记录待替换的页面的位置*/ } } printf("Changethepage%d\n",order+1); i=0; p=head->next; while(p)/*页面替换*/ { if(i==order) { p->address=n; } i++; p=p->next; } } } voidchangeFIFO(intn,intposition) { inti=0; intflag=1;//默认队列已满 page*p,*delect; p=head->next; while(p) { if(p->address==-1)//队列未满 { flag=0; p->address=n; printf("Changethepage%d\n",i+1); break; } p=p->next; i++; } if(flag)//队列已满 { delect=head->next; delect->address=n; head->next=delect->next; printf("Delectfromthehead,andaddnewtotheend.\n"); rear->next=delect; rear=delect; rear->next=NULL; } } voidchangeLRU(intn,intposition) { inti; inttotal=0; intflag=1;/*默认为已满*/ intdistance[num]; intMAX; intorder=0; page*p,*q; p=head->next; q=head->next; for(i=0;i { distance[i]=100; } i=0; while(p)/*判断链表是否已满*/ { if(p->address==-1) { flag=0; break; } p=p->next; i++; } if(! flag)/*链表没有满的情况*/ { p->address=n; printf("Changethepage%d\n",i+1); } else/*链表已满的情况*/ { while(q) { for(i=position-1;i>=0;i--)/*向前计算距离*/ { if(q->address==A[i]) { distance[total]=position-i; break; } } total++; q=q->next; } MAX=distance[0]; for(i=0;i { if(distance[i]>MAX) { MAX=distance[i]; order=i; } } printf("Changethepage%d\n",order+1); i=0; p=head->next; while(p)/*页面替换*/ { if(i==order) { p->address=n; } i++; p=p->next; } } } floatOPT() { inti; intlose=0; floatlosef; floatpercent; for(i=0;i { if(search(A[i])==0) { lose++; changeOPT(A[i],i); } print(); } losef=(float)lose; percent=1-(losef/N); returnpercent; } floatLRU() { inti; intlose=0; floatlosef; floatpercent; for(i=0;i { if(search(A[i])==0) { lose++; changeLRU(A[i],i); } print(); } losef=(float)lose; percent=1-(losef/N); returnpercent; } floatFIFO() { inti; intlose=0; floatlosef; floatpercent; page*p; for(i=0;i { if(search(A[i])==0) { lose++; changeFIFO(A[i],i); } else { p=run->next; run->next=p->next; rear->next=p; rear=p; rear->next=NULL; printf("Moveittoendofqueue.\n"); } print(); } losef=(float)lose; percent=1-(losef/N); returnpercent; } voidmain()/*主函数部分*/ { floatpercent; intchoice; printf("Selectthearithmetic: \n (1)OPT\n (2)LRU\n(3)FIFO\nyourchoiceis: "); scanf("%d",&choice);/*选择页面置换算法*/ initial();/*创建进程*/ if(choice==1)/*采用OPT算法置换*/ { percent=OPT();/*计算OPT时的缺页率*/ printf("ThepercentofOPTis%f\n",percent); } elseif(choice==2)/*采用LRU算法置换*/ { percent=LRU();/*计算LRU时的缺页率*/ printf("ThepercentofLRUis%f\n",percent); } elseif(choice==3)/*采用FIFO算法置换*/ { percent=FIFO();/*计算FIFO时的缺页率*/ printf("ThepercentofFIFOis%f\n",percent); } else { printf("Yourchoiceisinvalid."); } } 五、 调试结果显示 (1)OPT置换算法 (2)LRU置换算法 LRU FIFO置换算法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 页面 置换 算法