操作系统实验报告6-页面置换算法模拟

实 验 报 告

, 2013 / 2014学年 第1学期,

课程名称 操作系统原理 实验名称 实验6:页面置换算法模拟

2013 12 10 实验时间 年 月 日 指导单位 软件工程系 指导教师 杨 健 学生姓名 班级学号

计算机软件与服务外包 学院(系) 软件工程系 专 业

实验名称 实验1:Linux操作、使用、编程与进程创建 指导教师 杨健 实验类型 实验 实验学时 2 实验时间 2013.12.10 一、 实验目的

1(通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。 2(掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。

3(通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。

二、实验环境(实验设备) Windows 2000 Visual Studio 三、实验内容

设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换: 1. 先进先出的算法(FIFO) 2. 最近最久未使用算法(LRU)

3. 最佳置换算法(OPT) 实验分析

在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。

一个好的页面置换算法，应该有较低的页面更换频率。 1

假设分给一作业的物理块数为3 ，页面数为20个。 页面号为(20个):

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 1(先进先出(FIFO)置换算法的思路

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。

2(最近久未使用(LRU)置换算法的思路

最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进

行淘汰。

3.最佳(OPT)置换算法的思路

其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。 4(FIFO页面置换算法

当需要访问一个新的页面时，首先调用findExist(i)函数来查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则调用display函数直接显示，不需要替换页面;如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入;若没有空

2

闲物理块，则调用findReplace函数替换页面。并将物理块中所有页面timer++。

5(LRU页面置换算法

当需要访问一个新的页面，首先调用findExist(i)函数查看物理块中是否就有这个页面。

6. OPT页面置换算法

当需要访问一个新的页面，首先调用findExist(i)函数来查看物理块中是否有这个页面。

7(寻找置换页面函数findReplace比较三个物理块中的时间标记timer，找到时间最久的。

代码

#include #include #include

#define BLOCK_MAX_SIZE 20//最?大洙?物?理え?块é大洙?小? enum{FIFO=1,LRU,OPT}; struct node_page{

int address;//指?令?地?址? int page_num;//页?面?号?

int next_order;//下?一?次?访?问ê的?次?序ò }*page; 3

//物?理え?块é定?义? typedef struct BlockNode{

int page_index;//page数簓组哩?的?下?标括? struct BlockNode * next; }BlockNode; struct{

int length;//当獭?前?物?理え?块é长?度è

int miss_flag;//缺ø?页?标括?志?，?若?为a1，?则ò缺ø?页? int miss_count;//缺ø?页?次?数簓 BlockNode*front; BlockNode*rear; }Block;

//本?程ë序ò中D全?局?变?量?名?均õ由 ?两?个?单蹋?词洙?组哩?成é，?且ò开a头 ?字?母?大洙?写′

int BlockSize = 5;//物?理え?块é大洙?小? int PageCount = 200;//页?面?总哩?数簓 int PageSize = 1024;//页?面?大洙?小? int AddrRange = 8*1024;//访?问ê地?址?范?围?

int get_num(int down,int up)//得?到?一?个?down~up之?间?的?整?数簓 { int num;

4

char str[111]; while(1){

fgets(str,111*sizeof(int),stdin);

num=atoi(str);//把?字?符?串?中D的?数簓字?转羇换?为a整?数簓 if(num>=down&& num<=up) break;

printf(\"输?入?范?围?有瓺误ó,请?重?新?输?入?:\"); }//while return num; }

void init_block()//构1造ë一?个?空?的?物?理え?块é队ó列 {

Block.rear=Block.front=(BlockNode*)malloc(sizeof(BlockNode)); if(!Block.front){

printf(\"内ö存?分?配?失骸?败悒?\\n\"); exit(0); }

Block.length=0; Block.miss_count=0; Block.rear->next=NULL; }

void enqueue(int page_index)//入?队ó 5

{

BlockNode*node=(BlockNode*)malloc(sizeof(BlockNode)); if(!node){

printf(\"内ö存?分?配?失骸?败悒?\\n\"); exit(0); }

node->page_index=page_index; node->next=NULL; Block.length++; Block.rear->next=node; Block.rear=node; }

void dequeue()//出?队ó {

BlockNode*node; node=Block.front->next; Block.front->next=node->next; if(node== Block.rear) Block.rear=Block.front; free(node); Block.length--; 6 }

void clear_block()//清?空?物?理え?块é

{

while(Block.rear=Block.front->next){ Block.front->next=Block.rear->next; free(Block.rear); Block.length--; }

Block.rear=Block.front; Block.length=0; Block.miss_count=0; }

void destroy_block()//销ö毁õ物?理え?块é {

while(Block.rear=Block.front){ Block.front=Block.front->next; free(Block.rear); }

free(page); }

void init_page()//初?始?化ˉ页?面?系μ列 7 { int i,j;

srand(time(NULL));//用?当獭?前?系μ统?时骸?间?来ぁ?初?始?化ˉ随?机ö种?子哩?

page=(struct node_page*) malloc(PageCount*sizeof(struct node_page)); for(i=0;ipage[i].page_num=page[i].address/PageSize; }

for(i=0;iif(page[i].page_num== page[j].page_num){ page[i].next_order=j; break; }//if }//for

if(j== PageCount)//说μ明ôpage[i]以?后ó都?不?会á再õ访?问ê page[i].next_order= PageCount; }//for }

void print_page()//打洙?印?页?面?系μ列 { int i; 8

printf(\"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\n\"); printf(\"页?面?系μ列 为a:阰\\n\"); for(i=0;iprintf(\"[%-2d,%-4d]\

if((i+1)%5== 0){ printf(\"\\n\"); }//if }

printf(\"\\n\"); }

void FIFO_Replace(int page_index)//FIFO置?换? {

BlockNode*node; if(!Block.length){ enqueue(page_index); Block.miss_flag=0; return; }

node=Block.front; while(node=node->next){

if(page[node->page_index].page_num==page[page_index].page_num){ 9

Block.miss_flag=0; return; } }

if(Block.lengthBlock.miss_flag=0; return; }

dequeue();

enqueue(page_index); Block.miss_flag=1; Block.miss_count++; }

void LRU_Replace(int page_index)//LRU置?换? {

BlockNode*node,*last_node; if(!Block.length){ enqueue(page_index); Block.miss_flag=0; return; } 10

last_node=node=Block.front; while(node=node->next){

if(page[node->page_index].page_num== page[page_index].page_num){ last_node->next=node->next; Block.length--; if(node== Block.rear) Block.rear=last_node;

enqueue(node->page_index); free(node); Block.miss_flag=0; return; }

last_node=node; }

if(Block.lengthdequeue();

enqueue(page_index); Block.miss_flag=1; 11

Block.miss_count++; }

void OPT_Replace(int page_index)//OPT置?换? {

BlockNode*node;

BlockNode*max_node,*max_node_last; if(!Block.length){ enqueue(page_index);

Block.miss_flag=0; return; }

node=Block.front; while(node=node->next){

if(page[node->page_index].page_num== page[page_index].page_num){ node->page_index=page_index; Block.miss_flag=0; return; } }

if(Block.lengthBlock.miss_flag=0; return; }

node=Block.front; max_node=node->next;

while(node=node->next){//寻?找òBlock中Dnext_order值μ最?大洙?的?节ö点?

if(page[max_node->page_index].next_orderpage_index].next_order)

max_node=node;

}

node=Block.front; max_node_last=node;

while(node=node->next){//寻?找òBlock中Dnext_order值μ最?大洙?的?节ö点?的?上?一?个?节ö点?

if(node== max_node) break;

max_node_last=node; }

max_node_last->next= max_node->next; Block.length--;

if(max_node== Block.rear) Block.rear=max_node_last; free(max_node); enqueue(page_index); 13

Block.miss_flag=1; Block.miss_count++; }

void page_replace(int num) { int i,j; BlockNode*node;

char str[3][5]={\"FIFO\

printf(\"======================%s=========================\\n\-1]);

printf(\"页?面?号?*\"); for(i=0;i< BlockSize;i++) printf(\" \");

printf(\"* 是?否?缺ø?页? *\\n\");

printf(\"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\n\"); for(i=0;iprintf(\" %-4d*\if(num== FIFO) FIFO_Replace(i); else if(num == LRU) LRU_Replace(i); else if(num == OPT) 14

OPT_Replace(i); node=Block.front; while(node=node->next)

printf(\"%-2d\for(j=Block.length;jprintf(\"* %s *\\n\\n\}

printf(\"\\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\n\");

printf(\"缺ø?页?数簓:%d,缺ø?页?率

ê:%%%.2f\\n\\n\*100);

printf(\"按恪?回?车μ键?继ë续?!\\n\\n\"); getchar(); }

void confige()//程ë序ò设Θ?置? { int num; while(1){

printf(\"\\n***************************************************\\n\"); printf(\"* 程ë序ò设Θ?置? *\\n\");

printf(\"***************************************************\\n\"); printf(\"* 1,设Θ?置?物?理え?块é大洙?小?(默?认?5) *\\n\"); 15

printf(\"* 2,设Θ?置?访?问ê地?址?范?围? (默?认?8K) *\\n\"); printf(\"* 3,设Θ?置?页?面?大洙?小?(默?认?1K) *\\n\"); printf(\"* 4,设Θ?置?页?面?总哩?数簓(默?认?200) *\\n\"); printf(\"* 5,显?示?各ô项?设Θ?置?值μ *\\n\"); printf(\"* 6,返う?回? *\\n\");

printf(\"***************************************************\\n\"); printf(\"请?输?入?您ö的?选?择?:\"); num=get_num(1,6); if(num==6)

break; if(num==1){

printf(\"请?输?入?物?理え?块é大洙?小?(1~%d):\BlockSize=get_num(1,BLOCK_MAX_SIZE); printf(\"设Θ?置?成é功|!\\n\\n\"); }//if

else if(num==2){

printf(\"请?输?入?访?问ê地?址?范?围?(1~%d)K: \AddrRange=get_num(1,999)* 1024; printf(\"设Θ?置?成é功|!\\n\\n\"); }//elseif else if(num==3){

printf(\"请?输?入?页?面?大洙?小?(1~%d)K: \16

PageSize=get_num(1,AddrRange/1024)* 1024; printf(\"设Θ?置?成é功|!\\n\\n\"); }//elseif else if(num==4){

printf(\"请?输?入?页?面?总哩?数簓(1~%d):\PageCount=get_num(1,32767); printf(\"设Θ?置?成é功|!\\n\\n\"); }//elseif else if(num==5){

printf(\"---------------------------------------------------\\n\");

printf(\"*当獭?前?物?理え?块é大洙?小?:%d\\n\printf(\"*当獭?前?访?问ê地?址?范?围?:%d K\\n\printf(\"*当獭?前?页?面?大洙?小?:%d K\\n\printf(\"*当獭?前?页?面?总哩?数簓%d\\n\

printf(\"---------------------------------------------------\\n\"); } }

free(page); init_page(); }

void begin() { 17 int num; print_page(); while(1){

printf(\"\\n***************************************************\\n\"); printf(\"* 页?面?置?换?算?法ぁ?*\\n\");

printf(\"***************************************************\\n\"); printf(\"* 1,先è进?先è出?置?换?算?法ぁ?FIFO) *\\n\"); printf(\"* 2,最?近?最?久?未′使?用?置?换?算?法ぁ?LRU) *\\n\"); printf(\"* 3,最?佳?置?换?算?法ぁ?OPT) *\\n\"); printf(\"* 4,返う?回? *\\n\");

printf(\"***************************************************\\n\");

printf(\"请?输?入?您ö的?选?择?:\"); num=get_num(1,4); if(num== 4) break;

page_replace(num); clear_block(); }

free(page); init_page(); } 18 int main() { int num; init_block(); init_page(); while(1){

printf(\"\\n***************************************************\\n\"); printf(\"* 存?储洹?器ô管?理え?模,拟a系μ统? *\\n\");

printf(\"***************************************************\\n\"); printf(\"* 1,进?入?页?面?置?换?算?法ぁ?*\\n\"); printf(\"* 2,进?入?程ë序ò设Θ?置? *\\n\"); printf(\"* 3,退?出? *\\n\");

printf(\"***************************************************\\n\");

printf(\"请?输?入?您ö的?选?择?:\"); num=get_num(1,3); if(num== 3) break; if(num== 1) begin();

else if(num == 2) confige(); } 19

destroy_block(); return 0; } 截图

20

21

22

四、实验小结,针对实验内容逐项小结实验中发现的问题、自己的解决方法、心得体会等,

一开始做这个实验时，首先是看书，先把书上的替换算法知识点弄明白，要明白各种算法的优缺点和相互之间衍生互补关系。这四个算法中，难以实现的是LRU算法，因为它涉及到访问时间的计算，而且它的开销也比较大。OPT算法次难，它需要计算最近访问时间，并替换最近访问时间最大的页。而FIFO和CLOCK实现起来比较容易，FIFO算法的实现和CLOCK算法的实现很相似，FIFO可视为CLOCK的退化版。我先写了CLOCK算法，再删去一些约束条件就退化为FIFO算法。这就是两者的相同之处。理论上，CLOCK算法需要维持一个循环的主存缓冲区，需要一个循环队列去实现，并且，FIFO算法保持先进先出，因此需要一个先进先出队列。但是，我实现这两个算法只用到了单向链表的数据结构，剩下的由其中的指针去把握了。因此，必须对指针使用有敏锐的感觉。

五、指导教师评语 成 绩 批阅人 日 期 23