页面置换算法实验报告

页面置换算法实验报告（精选4篇）

页面置换算法实验报告 篇1

计算机体系结构

实验报告

班级：计科姓名：张华敏学号：

0902班

0909090814

FIFU算法

一，实验内容：

编写一段程序来模拟页面置换算法中的FIFU算法的实现 二，算法设计：

设置一个产生随机数的函数rand()产生随机数来模拟程序所需访问的页面的标号，如果页面需要被访问则把页面中的一个标志位设为in表示他已经被调入内存，如果再次需要访问此页面是只需检查此页面的标志位是否为in就可判断它是否已经存在在内存中了，如果已经存在则可直接使用，如果不存在则需调入，在调入新页面是先检查内存空间是否已满，如果未满则直接调入，如果已经满了则需选择一个页面将其调出，调出时就把页面的标志位设为out。选择页面的规则是：将进入内存时间最久的页面调出去，为了达到这一目的，在页面中设置一个计数器，每当有新页面调入内存时则将内存中已经存在的页面计数器自动加一，调出页面时就选择那个计数器最大值的页面，调出后重新将计数器设为零。三，遇到的问题及解决方案：

在做此实验时遇到了一些小问题,如在C语言中函数名定义为export()则会报错。在调用有返回值的函数是如果直接int s=use(pag)则会运行出错,要先分开写如：int s,s=use(pag).四，源代码 头文件.cpp #include #include

int t;//全局变量，用来盛放rand()函数产生的随机数

enum boolean{in,out};//定义一个枚举类型 /////////如果把in，out换成 true,false则会处错误

typedef struct { int num;//页面编号 char content;//页面内容

enum boolean flog;//判断此页面是否页调入，调入为true,否则为false;int count;//页面计数器

int usebit;//使用位，被使用过值为1，否则为0 }page;

FIFU.cpp #include #include #include #include“头文件.cpp”

int capacity=3;//设置内存最多可以容纳的页面数

void initialize(page p[])//初始化页面函数 { for(int i=0;i<5;i++)//初始化页面，页面内容分别为小写字母 abcde,计数器全部为0 {p[i].num=i;p[i].content=i+97;p[i].flog=out;p[i].count=0;} }

int use(page p[]){ t=rand()%5;//产生一个0-5的随机数，if(p[t].flog==in){ printf(“tt%d页面命中n”,t);//for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 // { // if(p[i].flog==in)// p[i].count++;// } return(1);} else return(0);}

void import(page p[])//调入页面的函数 { /* int t=rand()%5;//产生一个0-5的随机数，if(p[t].flog==in)printf(“tt%d页面命中n”,t);*/ // if(p[t].flog==out)//如果此页面未被调入内存则立即调入 p[t].flog=in;capacity--;//调入后内存空间减少一叶

for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 { if(p[i].flog==in&&p[i].num!=t)p[i].count++;} printf(“页面%d被调入内存n”,t);}

void port(page p[])//调出页面的函数，，，，，，，，，，，如果函数名定义为export则处错误 { int x=0,y;//x用来暂时存放计数器 中的最大值，y存放此页面的页面号 for(int i=0;i<5;i++)//寻找计数器值最大的 页面 { if(p[i].count>x){ x=p[i].count;y=i;} }

p[y].flog=out;//修改调入符号 p[y].count=0;capacity++;//调入后内存空间增加一叶 printf(“ttt页面%d被调出内存n”,y);}

main(){ int s;long t3,t1,t2;page pag[5];//定义五个页面，，，，，，，，，，，如果这个定义在子函数之前那么不用通过参数 子函数便可以直接访问 t3=time(NULL);initialize(pag);do { t1=time(NULL);s=use(pag);//，，，，，，，，，，，，，，如果这里写成int s=use(pag)则会运行出错

//printf(“s=%d capacity=%dn”,s,capacity);if(capacity>0&&s==0)import(pag);else { if(capacity==0&&s==0){ port(pag);import(pag);} } t2=time(NULL);while(t2-t1<1){ t2=time(NULL);} }while(t2-t3<20);system(“pause”);}

五，测试结果：

LFU算法

一,实验内容：

编写一段程序来模拟页面置换算法中的LFU算法的实现 二,算法设计：

设置一个产生随机数的函数rand()产生随机数来模拟程序所需访问的页面的标号，如果页面需要被访问则把页面中的一个标志位设为in表示他已经被调入内存，如果再次需要访问此页面是只需检查此页面的标志位是否为in就可判断它是否已经存在在内存中了，如果已经存在则可直接使用，如果不存在则需调入，在调入新页面是先检查内存空间是否已满，如果未满则直接调入，如果已经满了则需选择一个页面将其调出，调出时就把页面的标志位设为out。选择页面的规则是：将最近一段时间未被访问过的页面调出。为了达到这一目的在页面中设置一个标志位，如果页面在近期只要被访问过则将该标志位设置为1（默认为0），在选择调出页面时只需将标志位为0的页面调出即可。三,遇到的问题及解决方案： 未遇到什么问题

四,实验感悟：

遇到问题后上网查资料和有效,及时查不到自己想要的但是也可从相关结果中获得启发给自己灵感来想到解决问题的方法.四，源代码

FLU.cpp #include #include #include #include“头文件.cpp”

int capacity=3;

//设置内存最多可以容纳的页面数

void initialize(page p[])

//初始化页面函数

{

for(int i=0;i<5;i++)

//初始化页面，页面内容分别为小写字母 abcde,计数器全部为0

{p[i].num=i;

p[i].content=i+97;

p[i].flog=out;

p[i].count=0;

p[i].usebit=0;

}

}

int use(page p[]){

t=rand()%5;

//产生一个0-5的随机数，if(p[t].flog==in)

{

printf(“tt%d页面命中n”,t);

p[t].usebit=1;

//for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1

//

{

//

if(p[i].flog==in)

//

p[i].count++;

//

}

return(1);

}

else

return(0);

}

void import(page p[])//调入页面的函数

{

int t=rand()%5;

//产生一个0-5的随机数，//if(p[t].flog==in)

// {

//

printf(“tt%d页面命中n”,t);

//

p[t].usebit=1;

// }

// if(p[t].flog==out)

//如果此页面未被调入内存则立即调入

p[t].flog=in;

capacity--;

//调入后内存空间减少一叶

for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1

{

if(p[i].flog==in&&p[i].num!=t)

p[i].count++;

}

printf(“页面%d被调入内存n”,t);

}

void port(page p[])

//调出页面的函数

////////////////////////////////如果函数名定义为export则处错误

{

int x=0,y;//x用来暂时存放计数器 中的最大值，y存放此页面的页面号

int z=-1;

//用来判断近期是否有未被访问过的页面

int g=0;

for(int i=0;i<5;i++)//寻找计数器值最大的 页面

{

if(p[i].count>x)

{

x=p[i].count;

y=i;

}

}

for(int i=0;i<5;i++)

{

if(p[i].flog==in&&p[i].usebit==0)

{

z=i;

g++;

}

}

if(z==-1||g==3)//如果所有页面均为1则按照FIFO算法置换页面 //如果g=3则表明页面使用位全为零，此时也按照FIFO算法置换页面

{

p[y].flog=out;//修改调入符号

p[y].count=0;

capacity++;

//调入后内存空间增加一叶

p[y].usebit=0;

for(int i=0;i<5;i++)//将所有页面置0

p[i].usebit=0;

printf(“ttt页面%d被调出内存n”,y);

}

else

//如果有页面为0则将此页面置换出来

{

p[z].flog=out;//修改调入符号

p[z].count=0;

capacity++;

//调入后内存空间增加一叶

printf(“ttt页面%d被调出内存n”,z);

}

}

main(){

int s;

long t3,t1,t2;

page pag[5];//定义五个页面

///////////////////如果这个定义在子函数之前那么不用通过参数 子函数便可以直接访问

t3=time(NULL);

initialize(pag);

do

{

t1=time(NULL);

s=use(pag);

if(capacity>0&&s==0)

import(pag);

else

{

if(capacity==0&&s==0)

{

port(pag);

import(pag);

}

}

t2=time(NULL);

while(t2-t1<1)

{

t2=time(NULL);

}

}while(t2-t3<20);

system(“pause”);}

六,实验结果

总结

通过本次试验我对各种页面置换算法有了更深入的了解,也使得自己认识到平常学习到某些东西觉得懂了会了可是一旦实际动手操作起来就会发现总会存在这样或者那样的错误，只有多动手实际操作才会发现不足发现错误并且改正。查漏补缺提高自己的实际动手能力。

页面置换算法实验报告 篇2

在系统运行过程中，若程序所要访问的页面不在内存而需要把他们调入内存，但内存已经没有空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的交换区中，这个过程称为页面置换。决定将哪个页面调出，需根据一定的算法来确定，通常，把选择换出页面的算法成为页面置换算法。

置换算法的好坏，将直接影响到系统的性能。当发生缺页中断时，虽然可以随机地选择一个页面置换，但是如果一个被频繁使用的页面被置换出内存，很可能它在很短时间内又要被调入内存，这会带来不必要的开销。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面置换出，或者把那些在较长时间内不会再访问的页面调出。这对提高系统性能极其重要。

1 常见的页面置换算法

1.1 最优页面置换算法

1.1.1 算法思想介绍

最佳页面置换算法(Optimal Page Replacement Algorithm,OPT)是一种理想情况下的页面置换算法，它在所有页面置换算法中产生的页错误率最低，但实际上该算法是不可能实现的。

该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问(也就是下一条指令要访问的那一页)，而其他页面则可能要到10、100或者1 000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。

最佳页面置换算法规定：标记最大的页应该被置换。例如，如果某页在800万条指令内不会被使用，另一页在600万条指令内不会被使用，则置换前一个页面。这个算法惟一的一个问题就是它无法实现，因为当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然最佳页面置换算法不可能实现，但是该算法可以用于对可实现算法的性能进行衡量比较。如果一个页面置换算法不是最优的，但是它的性能与最优置换相比相差不大(如仅有2%的性能差距)，那么就可以判定该算法是有实用价值的。

1.1.2 算法分析

从理论上说，当置换一个页面出内存时，被置换出的页面在将来仍然需要被访问，那个时候将发生缺页中断。既然不好的事情(缺页中断)总会发生，计算机也和人一样，希望把不愉快的事情尽可能地向后拖延。一个最好的页面置换算法应该把因为需要调入这个页面而发生的缺页中断推迟到将来，越久越好。因此选择最久之后才会被访问的页面换出内存是理论上最佳的，这也是这个算法被称为最优置换的原因。

1.2 先进先出页面置换算法（FIFO)

1.2.1 算法思想介绍

FIFO算法总是淘汰在内存中停留得最久的那个页面。具体实现方法是由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头页面并把新调入的页面加到表尾。FIFO页面置换算法容易理解和实现，但是其性能并不总是很好。

1.2.2 算法分析

FIFO算法仅仅考虑到在内存中滞留了很久的页面的需求性可能比新进入的页面更小。就像在超级市场中，新引进的商品往往比已经库存了很久的商品更容易被购买，因此当新引进商品时，通常淘汰那个库存了最久的商品。

但是这种考虑显然不太准确，谁说新上架的东西一定比库存很久的东西更有用呢?考虑一个页面，它在很早的时候被调入内存，之后被频繁的引用，这个页面很容易被FIFO算法当作没用的页面从而被淘汰。因此纯粹的FIFO算法很容易淘汰重要的页面，实际很少使用。

1.3 第二次机会页面置换算法

1.3.1 算法思想介绍

第二次机会页面置换算法是对FIFO算法的改进。它在FIFO的基础上进行了修改，其性能较FIFO有了很大的提高，避免了把经常使用的页面置换出去。

和FIFO算法一样，操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当需要置换页面是，检查最老页面的R位，如果它为0，表示它最近未被使用，也就是说，它又老又没用，可以立即置换。如果是1，则把R位置为0，并把该页面放在链表尾端(即把它作为刚装入的页面一样)，然后继续搜索。

1.3.2 算法示例

如图1(a)所示，页面A到页面H按照进入内存的时间先后顺序保存在链表中。页面上的数字是该页面进入内存时的时间。第二次机会算法的一个执行示例过程如下：

(1)在时间20发生了一次缺页中断;

(2)检查最老的页面A，如果A的R位为0，则将它淘汰出内存;

(3)现在页面A的R位为1，则将A放到链表的尾部，并且重新设置页面的进入时间为当前时刻，并置A的R位为0。即让A页面好像是刚刚调入内存一样;

(4)检查当前最老的页面B，重复以上过程。

可以看出在上面的过程中，如果A到H页面都被访问过了，那么在遍历了一次之后，仍然是页面A被淘汰，此算法就变成了纯粹的FIFO算法。

1.3.3 算法分析

该算法的思想是找到一个最近的时钟滴答中从来没有被访问过的页面，而且这个页面是最老的(最先调入内存)，这样综合了两个方面的考虑：

(1)老的页面比新的页面需求量小(FIFO算法的想法)

(2)局部性：最近未被访问的页面今后也可能不被访问

并且算法优先考虑局部性，例如在上面的过程中，如果A～H页面都被访问过了，那么在遍历了一次之后，仍然是最老的页面A被淘汰，此算法就变成了纯粹的FIFO算法。

当选择置换页面时，依然和FIFO一样，选择最早置入内存的页面。但是二次机会法还设置了一个访问状态位。所以还要检查页面的的访问位。如果是0，就淘汰这页;如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置为1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过(或者也给了第二次机会)。因此，如果一个页面经常使用，它的R位总保持为1，它就从来不会被淘汰出去。算法的这个特点使它被称为第二次机会算法。

1.4 时钟页面置换算法

时钟页面置换算法是对第二次机会算法的改进，也是现实中最常用的页面置换算法之一。第二次机会算法比较合理，但是效率较低，由于它经常需要在链表中移动页面。因此，时钟页面置换算法改进了链表的组织方式。它将所有页面放置在一个类似钟面的环形链表中，用一个表针指向最老的页面。

当发生缺页中断时，算法首先检查表指针指向的页面，如果它的R位是0就淘汰该页面，并把置换进来的新的页面插入到这个位置，然后把表针前移一个位置。如果R位是1，那么清除R位并把表针前移一个位置。重复这个过程直到找到了一个R位为0的页面为止。

算法的示意图如图2所示。

1.5 最近最少使用页面置换算法（LRU)

1.5.1 算法思想介绍

LRU算法基于这样的原理：在前面几条指令中频繁使用的页面很可能在后面几条指令中被使用。而已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。

因此，可以置换未使用时间最长的页面。这个策略就是LRU(最近最少未使用)页面置换算法的核心。显然，LRU算法的主要问题是如何找出最近未被使用时间最长的页面。

1.5.2 LRU算法的实现方法

方式1：硬件有一个64位的计数器C，它在每条指令执行完后自动加1。每个页表项中有一个足够容纳这个计数器值的域。在每次访问内存之后，将当前的C值保存到被访问页面的页表项中。发生缺页中断时，操作系统检查所有页表项中计数器的值，找到一个该值最小的页面，这个页面显然就是最近最少使用的页面。

方式2：在一个有n个页帧的机器中，LRU硬件维持一个初值都为0的n×n位矩阵。当访问到页帧k时，硬件首先把k行的位都置为1，再把第k列的位都置为0。在任何时刻，二进制数值最小的行就是最近最少使用的，第二小的行是下一个最近最少使用的，以此类推。

1.5.3 LRU算法的优缺点

LRU的优点是性能很好，它提供了对最优页面置换算法很好的近似，并且它在理论上可以实现。但是LRU算法的缺点在于它实际上实现很难。因为以上讨论的实现方式都需要硬件的参与，在现实中只有非常少的计算机拥有这种硬件。通常在实践中，人们使用软件方案实现一个LRU的近似算法。最著名的近似LRU算法是最不经常使用页面置换算法(NFU)和老化算法。

1.6 最不经常使用页面置换算法（NFU)

1.6.1 算法思想介绍

最不经常使用页面置换算法(NFU)是一种用软件实现的对LRU粗略的近似。

算法的基本思想是每个页面拥有一个软件计数器，计数器的初始值为0。每次时钟中断时，操作系统扫描内存中的所有页面，将每个页面的R位加到它的计数器上。(R为1则代表在最近的一个时钟周期内页面被访问了，因此页面的该计数器值大致代表了该页面被访问了多少次)。在N个时钟周期内，如果页面有m次R位为1，则表示N个时钟周期内，在m个时钟周期里该页面被访问了，因此这个计数器跟踪了该页面被访问的频繁程度。发生缺页中断时，将置换计数器值最小的页面。

算法蕴含的思想是：统计从程序开始运行到现在为止，每个页面被访问的频繁程度。换页时，选择访问最不频繁的页面换出内存。

1.6.2 NFU算法的问题

NFU算法的问题，用一句话简单概括就是：它从来不忘记任何事情。

例如，可能某页面一开始被频繁使用，其计数器值可能已经高达10 000，但是这个页面在程序运行后期就很少使用了。但是由于前期的频繁访问，它的计数器值已经很高了，因此按NFU算法的原理，它很难被换出，尽管它应该在程序执行的后期被换出才是合理的。

1.7 老化算法

1.7.1 算法思想介绍

老化算法是对NFU的一个修改，实现了对LRU的很好的近似。

对NFU的修改：

在R位被加进之前先将计数器右移1位。

将R位加到计数器最左端的位而不是最右端的位。

发生缺页中断时，将置换计数器值最小的页面。

1.7.2 算法示例

如图3所示，一开始5个页面的计数器值均为0。第0个时钟周期内，各个页面的R位分别为1,0,1,0,1,1，将其加到计数器的最左端得到图3(a)。第1个时钟周期内，各个页面的R位分别为1,1,0,0,1,0，将其加到计数器的最左端得到图3(b)。依此类推，如果图3(e)时发生缺页中断，那么计数器值最小的页面3将被置换。

1.7.3 算法分析

这个算法解决了NFU的问题，如果一个页面前期频繁访问，如值为11111111，但是后期不再被访问，它的计数器值会越来越小，从01111111到00111111到00011111到00001111……;相反，如果一个页面前期不被访问，后期频繁访问，它的计数器值会越来越大，从00000000到10000000到11000000到11100000……。

一个在最近一个时钟周期内被访问的页面获得的计数器增量是最大的(左端加1，相当于给计数器加了10000000)，由于页面最近一次时钟周期被访问了，表示以后可能也要被访问，这个信息的参考价值是最大的，应该提供最大的计数器增量，这是很合理的。而在前一个时钟周期内被访问的页面获得的计数器增量会慢慢变小，由于这个访问记录逐渐成为了历史，可参考价值越变越低，这样设计也是很正常的。这就是蕴含在算法背后的思想。

为什么说老化算法只是LRU的一个近似?下面用一个例子来说明。页面A和页面B的计数器分别为00100000和00101000。它们都是在最近的两个时钟周期内未被访问，但是没有精确的记录。

LRU中是按指令而不是时钟周期记录的，老化算法中只知道它们都是在最近的两个时钟周期内未被访问，但是不知道具体的先后顺序(一个时钟周期有多个指令，A,B总有一个更先被访问)。因此在老化算法中只能看它们计数器值的大小来决定，不是真正的最近最少使用算法，仅仅是它的一个近似。

第二个与LRU的区别是，老化算法的计数器只有有限位数，限制了其对以往页面访问历史的记录。

2 系统颠簸的分析与解决

2.1 系统颠簸的概念

颠簸(Thrashing)(又称抖动)就是指当内存中已无空闲空间而又发生缺页中断时，需要从内存中调出一页程序或数据到磁盘的交换区中，如果算法不适当，刚被换出的页面很快被访问，需重新调入，因此需再选一页调出，而此时被换出的页面很快又要被访问，因而又需将它调入，如此频繁更换页面，以致花费大量的CPU时间，极大地降低系统的效率，我们称这种现象为“颠簸”(或“抖动”)。一般如果每执行几条指令程序就会发生一次缺页中断，那么就可以称这个程序发生了颠簸。

2.2 系统颠簸的产生

2.2.1 局部页面置换算法与全局页面置换算法

页面置换算法可以分为两大类，全局置换和局部置换。全局置换允许一个进程从所有页帧集合中选择一个页帧置换，而不管该帧是否已经分配给其他进程，即一个进程可以从另一个进程中拿到帧。局部置换要求每个进程仅从自己的分配帧中进行选择。局部置换和全局置换的一个示例如下：如图4所示，三个进程A,B,C构成了可运行进程的集合。假设页面置换算法是LRU算法，每个页面的生存时间列在页面的右边。当进程A产生缺页中断时，如果采用全局置换算法，将选择所有页面中生存时间最少的页面B3进行置换。如果采用局部替换算法，将选择分配给A的所有页面中生存时间最少的页面A6进行置换。

2.2.2 因为物理内存不足而产生系统颠簸

采用全局页面置换时容易产生系统颠簸，即使是使用最优页面置换算法的全局页面置换也不例外。因为当某个进程需要更多的页帧时，为了增加该进程的页帧数目，可能直接导致另一进程的页帧数目减少。当整个系统的物理块不能满足所有进程的需要时，缺页率将持续维持于一高水平值，意味着颠簸的产生。其具体表现形式如下：

(1)进程竞争临界资源

考虑这样的情况：系统中已不存在空闲物理块，而进程A却要求增加物理块，于是，中断处理程序只得将原属于进程B的物理块分配给进程A;同样地，进程B又分配到原属于进程C的物理块，如此下去。在一定时候，各缺页进程都将被阻塞，就绪队列为空，颠簸从此形成。

(2)增加多道程序度

当CPU利用率处于低水平时，为提高多道程序度，调度程序要求从后备输入队列选择进程加载到内存。图5可清楚地说明这种情形下颠簸的形成原因。首先，随着多道程序度的增加，CPU利用率随之增加而达到一个理论极值。但在极值点右边，再增加多道程序度，因为进程事实上只能从已加载的进程处获得页帧，从而使得更多的进程因缺页而阻塞，随着更多的进程执行内外存的I/O操作，CPU利用率反而更低;为提高CPU利用率，调度程序又要求调入新进程.如此形成恶性循环，系统诸进程都将缺页，颠簸形成。

2.2.3 因为页面置换算法而产生颠簸

基于局部性原理，几乎所有的页面置换算法总是试图从当前正在引用的页面去”预测”将要引用的页面，据此产生淘汰页和置换页。大多数情形下，这种预测的命中率可以很高。但对于特定的程序(如有大量的跳转语句的程序)，命中率将很低，其结果很可能是所选择的淘汰页却是即将要引用的页;而从磁盘置换到内存的页面在最近很长时间却不会被引用。不得已，继续进行页面置换，反反复复，颠簸形成。当然，不应用局部性原理的页面置换算法在大多数的情形下都有可能产生颠簸。

2.3 系统颠簸的解决

解决系统颠簸主要有3个方式：好的页面替换算法;减少运行的进程数;增大内存。

这里主要分析如何使用好的页面替换算法尽量避免颠簸的发生。

(1)局部置换

采用局部置换算法，当某个进程产生缺页中断时，只允许从本进程分配的页帧中选择置换页面，而不能从其他进程处拿到帧，就不会使其他进程也发生颠簸，可将颠簸框定在一个特定的、较小的范围内。

当然，这种方法并不理想。全局置换提供了更好的性能，这与局部分配本身是矛盾的。另外，它并不能从根本上防止颠簸，只能局限其范围。如果某个进程处于颠簸状态，则其将长期处于阻塞队列，不断地进行内外存交换，又必然会影响其他进程进行缺页处理。

(2)动态调整页面置换算法

页面置换算法与实际应用相关，对于大多数的进程，与置换算法同时吻合了局部性原理，从而缺页率低。而其余少数进程因与局部性原理相背，而使”预测”失效，其缺页率偏高可能引发颠簸。

因此，我们可以在一个系统中预备2种以上不同的选择淘汰页和置换页策略的置换算法，并定义一个缺页率的临界值，在缺页处理程序中设置一个判断，当缺页率大于临界值时改用另一种页面置换算法。

(3)跟踪缺页率

根据局部性原理，绝大多数时候，进程是从一个局部区域转移到另一个局部区域执行。所以，必须有足够的页帧供使用，以减少缺页，避免颠簸。到底应为每个进程分配多少页帧呢，实际上，它是系统拥有总的页帧数目与当前系统实际应用相关的一个经验值。这从缺页率与所分配的页帧数关系曲线得到证实。(如图6所示)在拐点附近，每增加(减少)进程的页帧数目都能显著地改变缺页率。

而一定时间以后，即使再增加页帧，缺页率变化也不明显。拐点左边缺页率非常高的区域就是本来的颠簸，拐点就是理想的页帧数目。据此，可对系统中的进程定义其缺页率的上限和下限阀值，此区间内的页帧数是进程拥有的相对合理的页帧数，缺页率高于上限时说明其分配到的页帧太少应当追加;而当缺页率低于下限时说明该进程所拥有的页帧数太多，可收回一部分。

3 算法间的关系

在页面置换的过程中，选择好的页面置换算法是提高系统整体性能的关键。本文分析了常见的7种页面置换算法的原理和思想，并对一些算法给出了实例。

另外作者对各个算法的本质提出了个人的见解，从为什么会有这样的算法?算法解决了什么问题?算法的优点和问题是什么?算法和其他算法之间的联系是什么?等多个方面剖析了页面置换算法的方方面面。

图7小结了各个页面置换算法之间的关系。

4 结语

作者简介：潘亮铭男，1992年出生，湖北人。研究方向为操作系统。汪梦泽女，1992年出生，辽宁人。研究方向为操作系统。系统颠簸也是内存管理中的一个重要问题，本文详细分析了系统颠簸产生的原因并阐述了如何使用好的页面置换算法尽量避免颠簸的产生。

参考文献

[1][荷]TANENBAUM A S.现代操作系统[M].陈向群^,马洪兵^,译.北京^:机械工业出版社^,2009.

[2]张尧学,史美林,张高.计算机操作系统教程[M].北京:清华大学出版社,2006.

[3]GALVIN P B,GAGNE G.操作系统概念[M].郑扣根,译.北京:高等教育出版社,2011.

[4][美]BRYANT R E,O’HALLARON D R.深入理解计算机系统[M].龚奕利,雷迎春,译.北京:机械工业出版社,2010.

[5]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997.

[6]NULL L,LOBUR J.计算机组成与体系结构[M].北京:机械工业出版社,2004.

[7]李芳,徐丽,陈亮亮.LRU近似算法的研究[J].现代电子技术,2009,32(3):36-38.

[8]王凌飞,王保保.Java虚拟机内存管理分析[J].现代电子技术,2007,30(5):172-174.

[9]刘小军,李秀娟.嵌入式操作系统VxWorks的内存管理技术研究[J].电子科技,2008(6):62-65.

算法实验报告 篇3

实验报告

班级

姓名

学号

****年**月**日

目录

实验一

二分查找程序实现…………………………………………………………………03页

实验二

棋盘覆盖问题（分治法）.…………………………………………………………08页

实验三

0-1背包问题的动态规划算法设计……………………………………………….11页

实验四

背包问题的贪心算法………………………………………………………………14页

实验五

最小重量机器设计问题（回溯法）………………………………………………17页

实验六

最小重量机器设计问题（分支限界法）…………………………………………20页

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验一：二分查找程序实现

一、实验时间：2013年10月8日，星期二，第一、二节地点：J13#328

二、实验目的及要求

目的：

建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。要求：

1、用c/c++语言实现二分搜索算法。

2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。

三、实验环境

平台：Win7 32位操作系统 开发工具：Codeblocks10.05

四、实验内容

对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素x。

五、算法描述及实验步骤

算法描述：

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。确定算法复杂度基本步骤：

1、首先设定问题规模n；

2、随即产生递增数列；

3、在n个有序数中随机取一个作为待查找量，搜索之；

4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组重复10次；

5、改变问题规模n重复上述步骤2~4，n取100、200……1000；

6、依实验数据作图，并与理论图作比较；

7、二分搜索算法平均查找次数： 问题规模为n时，平均查找次数为： A(n)=Int(logn)+ 1/2 // Int()函数为向下取整

即二分搜索算法对于含有n个数据的有序表L平均作了约Int(logn)+1/2次的查找操作。

实验步骤：

1.初始化生成递增随机数列： for(int j=100;j <=1000;j+=100){

array[0]=10+rand()%15;

for(int i=1;i

array[i]=array[i-1]+1+rand()%3+rand()%10;

} } 2.定义二分查找算法：

int BinarySearch(const int b[], int searchKey, int low, int high);其中，返回值为int类型，数组b[]为待查递增序列，searchKey为所查数据，low为数组b[]左下标，hight为数组b[]右下标。该算法实现过程为：

将数组b[]的n个元素分成个数大致相同的两半，取b[n/2]与searchKey作比较。如果searchKey=b[n/2]，则找到searchKey，算法终止；如果searchKeyb[n/2]，则只要在数组b的右半部继续搜索searchKey。

3.实现主函数并完成所有代码。4.算法复杂性分析：

容易看出，没执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O（logn）次。循环体内运算需要O（1）时间，因此整个算法在最坏情况下的计算时间复杂性为O（logn）。

六、调试过程及实验结果

输出结果为：

Every array repeat search times: 10 Number of Elements

理论平均查找次数

实际平均查找次数

6.5

6.1

200

7.5

7.3

300

8.5

7.4

400

8.5

7.4

500

8.5

7.5

600

9.5

8.2

700

9.5

8.8

800

9.5

8.7

900

9.5

8.8

1000

9.5

9.4

七、总结

二分查找在搜索有序表时，效率比较高。通过这次实验我对二分查找算法的认识又有了新的提高。本想写个图形界面，但由于种种原因，没有实现，下次做加密算法时，要写一个图形化界面。

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验二：分治法解决棋盘问题

一、实验时间：2013年10月22日，星期二，第一、二节地点：J13#328

二、实验目的及要求

1、用c/c++语言实现分治法解决棋盘问题算法。

2、实现棋盘化以及棋盘覆盖

三、实验环境

Windows 2007 操作系统

以及code blocks软件

四、实验内容

在一个2^k*2^k的方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一个特殊方格。用分治法将整个棋盘除特殊方格以外的方格覆盖。

五、算法描述及实验步骤 将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：

左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格 右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格 左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格 右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格 当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。

六、调试过程及实验结果

七、总结

由于覆盖一个2k*2k棋盘所需的L型骨牌个数为（4k-1）/3，故此算法是一个在渐近意义下最优的算法。

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验三：0-1背包问题的动态规划算法设计

一、实验目的及要求

1.了解并掌握动态规划算法的设计思想。

2.利用动态规划算法的设计思想实现0-1背包问题的算法设计。

二、实验环境

使用C++语言；

在windows环境下使用CodeBlocks调试并运行。

三、实验内容

1.了解并掌握动态规划的设计思想。

2.利用动态规划算法的思想解决0-1背包问题。

四、算法描述及实验步骤

每种物品一件，可以选择放1或不放0。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} “将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

五、调试过程及实验结果

六、总结

0-1背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0-1背包问题求解。通过这次实验我对动态规划算法的认识又有了新的提高。

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验四：背包问题的贪心算法

一、实验目的：

运用贪心算法思想，设计解决上述问题的算法，找出最大背包价值的装法。

二、实验要求

1.用c++语言实现背包问题的贪心算法。

2.掌握贪心思想的应用。

三、实验原理

在贪心算法中采用逐步构造最优解的办法，在每个阶段，都做出一个看上去最优的决策（在一定的标准下），决策一旦做出就不可更改。

四、实验过程(步骤)1.定义背包结构体： struct stone { int name;int weight;//物品的剩余重量

int weight_t;//物品的重量

float benefit;//物品的价值

//float b;};2.定义函数void sort(stone *data,int num)//计算物品的单位重量的价值，并进行排序 3.定义主函数并完成贪心选择。4.分析算法复杂性分析：

该算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（n*logn）。

与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，可以选择物品i 可以选择物品 的一部分，而不一定要全部装入背包，1≤i≤n。这2类问题都具有最优子结构，最优子结构性质，极为相似，但 最优子结构 背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

五、运行结果

六、实验分析与讨论 贪心法的基本思路：

——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题：

1.不能保证求得的最后解是最佳的； 2.不能用来求最大或最小解问题；

3.只能求满足某些约束条件的可行解的范围。实现该算法的过程：

1.Begin 从问题的某一初始解出发； 2．while 能朝给定总目标前进一步 do 3.求出可行解的一个解元素；

4.由所有解元素组合成问题的一个可行解

七、实验心得

贪心算法通过一系列的选择来得知问题的解，它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。通过背包问题的解决，进一步掌握了贪心算法的思想，并能在解问题时灵活运用。

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验五：最小重量机器设计问题（回溯法）

一、实验目的

建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。

二、实验要求

1、用c++语言实现最小重量机器设计的回溯算法。

2、分析算法的计算复杂性

三、实验原理

首先，应该明确的确定问题的解空间。确定了解空间的组织结构后，发从开始节点（根节点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，向纵深方向搜索移至一个新的结点。这个新结点成为新的活结点，并成为新的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点成为死结点。此时，应往回移动（回溯）至最近的活结点，并使这个活结点成为当前的扩展结点。回溯以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。

四、实验过程(步骤)由于题目已经给出总价格的上限，因此算法通过使用回溯来选择合适的机器使得在总价格不超过d时得到的机器重量最小。首先初始化当前价格cp=0,当前重量cw=0,此外，还要设置一个变量sum表示选择机器的总重量，初始化其为每个部件从1号供应商购买的重量。在循环选择i号机器时，判断从j号供应商购买机器后的价格是否大于总价格，如果不大于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得到的总重量是否比之前的sum小，如果小就赋给sum，然后从这一步开始，回溯到上一机器，选择下一合适供应商，继续搜索可行解，直到将整个排列树搜索完毕。这样，最终得到的sum即为最优解。

数据说明：

N：零件数量

m：不同的零件商

W[][]:是从供应商j处购得的部件i的重量

c[][]：相应的价值 算法设计：

a.部件有n个，供应商有m个，分别用w[i][j]和c[i][j]存储从供应商j 处购得的部件i的重量和相应价格，d为总价格的上限。

b.用递归函数backtrack(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。

① 若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。

② 若cw>=sum，则不是最优解，剪去相应子树，返回到i-1层继续执行。

③ 若i>n，则算法搜索到一个叶结点，用sum对最优解进行记录，返回到i-1层继续执行；

④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m）。

c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程，最终得到的sum即为所求最小总重量。

五、运行结果

六、实验心得

通过这次试验我明白了回溯法的思想，回溯法借助想象出来的树的结构，把问题简单化，使得解问题更方便。通过剪枝函数和约束函数对于求问题的解有很大的帮助，但要把一些限制条件把剪枝函数抽象化。

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验六：最小重量机器设计问题（分支限界法）

一、实验时间：2013年11月12日，星期二，第一、二节地点：J13#328

二、实验目的及要求

1、了解分支限界法的基本思想。

2、运用分支限界法解决最小重量机器设计问题。

三、实验环境

平台：win7操作系统

开发工具：codeblocks10.05

四、实验内容

最小重量机器设计问题：设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计

五、算法描述及实验步骤

算法描述：

解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的，故cv=0，cw=0，position=0，peer=0，1≤i≤n。x[1:n]记录供应商的选择while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展结点。并且花费不超过c并加以扩展，队列为空时则结束循环。当peer=n时，此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。若peer

实验步骤：

1.定义一个优先队列LinkQueue：

void InitQueue(LinkQueue &Q);//创建一个队列-----首尾结点 void DestroyQueue(LinkQueue &Q);//销毁一个队列 void ClearQueue(LinkQueue &Q);//清空队列

int QueueEmpty(LinkQueue &Q);//判断队列是否为空，空则返回TURE，否则返回FLASE int QueueLength(LinkQueue &Q);//求队列的长度

void EnQueue(LinkQueue &Q,QElemType &e);//拆入e为新的队尾元素 void DeQueue(LinkQueue &Q,QElemType &e);//用e返回队列的对头元素 bool IsEmpty(LinkQueue &Q)//判断队列是否为空 2.定义类MinWeight，实现函数有：

void Add(int wt,int ct,int i);//往队列插入节点 int FindBest();//实现最小重量机器的查找 void setMW();//函数初始化 void printMW();//打印输出结果 3 实现主函数并完成所有代码。

六、调试过程及实验结果

七、总结

利用分支限界法解决最小重量机器问题，就是构造一个优先队列，按照规定的优先级按最大效益优先的方式查找解空间树，找出满足要求的最优解。通过利用分支限界法解决最小重量机器问题，熟练了对分支限界法的使用。

指导教师对实验报告的评语

成绩：

指导教师签字：

页面置换算法实验报告 篇4

课 程 实 验 报 告

课程名称：

专业班级： CS1306班 学 号： U14967 姓 名： 段沛云 指导教师： 报告日期：

计算机科学与技术学院

目录

1 实验目的 ........................................................ 1

2 实验原理 ........................................................ 1

3 算法设计与流程框图 .............................................. 2

4 源程序 .......................................................... 4

5 程序运行 ........................................................ 7

6 结果分析 ........................................................ 7

7 实验体会 ........................................................ 7

1 实验目的

掌握Romberg公式的用法，适用范围及精度，熟悉Romberg算法的流程，并能够设计算法计算积分

31

得到结果并输出。 1x

2 实验原理

2.1 取k=0,h=b-a,求T0=

数)。 2.2 求梯形值T0(

b-a

),即按递推公式(4.1)计算T0。 k

2

h

[f(a)+f(b)]，令1→k,(k记区间[a，b]的二分次2

2.3 求加速值，按公式(4.12)逐个求出T表的第k行其余各元素Tj(k-j)

(j=1,2,….k)。

2.4 若|Tk+1-Tk|

n-1

11T2n=[Tn+hn∑f(xi+)]

22i=0

1

Sn=T2n+(T2n-Tn)

31

Cn=S2n+(S2n-Sn)

151

Rn=C2n+(C2n-Cn)

63

3 算法设计与流程框图

算法设计：(先假定所求积分二分最大次数次数为20) 3.1 先求T[k][0] 3.2 再由公式T

(k)m

4m(k+1)1)=mTm-1-mTm(k-1(k=1,2,) 求T[i][j] 4-14-1

3.3 在求出的同时比较T[k][k]与T[k-1][k-1]的大小，如果二者之差的绝对

值小于1e-5，就停止求T[k][k];此时的k就是所求的二分次数，而此时的T[k][k]就是最终的结果 3.4 打印出所有的T[i][j]; 程序流程图

4 源程序

#include #include #include #include int main(void) {

float f(float(x)) {

float y; y=1/x; return y; }

float a,b,e,h,s,k,x,T1=0,T2=0,S1=0,S2=0,C1=0,C2=0,R1=0,R2=0; int i=0;

printf(“请输入积分下限 : ”); scanf(“%f”,&a);

printf(“ 请输入积分上限 :”); scanf(“%f”,&b);

printf(“ 请输入允许误差 :”); scanf(“%f”,&e); k大学网=1; h=b-a;

T1=h*(f(a)+f(b))/2;

printf(“____________________________________________ ”); printf(“计算结果如下 : ”);

printf(“ k T2 S2 C2 R2 ”); printf(“%d %10.7f %10.7f %10.7f %10.7f ”,i,T1,S1,C1,R1); do {

x=a+h/2; s=0; while(x

{ s=s+f(x); x=x+h; }

T2=(T1+s*h)/2; S2=T2+(T2-T1)/3; if(k==1) {

T1=T2; S1=S2; h=h/2; k=k+1; }

else if(k==2) {

C2=S2+(S2-S1)/15; C1=C2; T1=T2; S1=S2; h=h/2; k=k+1; }

else if(k==3) {

R2=C2+(C2-C1)/63; C2=S2+(S2-S1)/15; C1=C2; T1=T2; S1=S2; h=h/2; k=k+1; } else {

C2=S2+(S2-S1)/15;

R2=C2+(C2-C1)/63; if(fabs(R2-R1)

printf(“%d %10.7f %10.7f %10.7f %10.7f ”,i+1,T2,S2,C2,R2);

break;

} else { R1=R2; C1=C2; T1=T2; S1=S2; h=h/2; k=k+1; } } i++;

printf(“%d %10.7f %10.7f %10.7f %10.7f ”,i,T2,S2,C2,R2); } while(1); system(“pause”); return 0; }

5 程序运行

6 结果分析

如上所示的结果与课本中求得的结果完全一样，表明程序编写正确，且符合要求，事实上，只要再将所求值的.精度设置得更小，则所求的结果将更加准确，最终将无限接近于标准值，由上表也可以看出用龙贝格积分法求函数的积分值在精度比较低的情况下就能求到很准确的值!

7 实验体会

本次实验较为简单，主要时间是耗费在循环判断上面，因为书上已经给了流程图，都是基本的C语言，难度不大。过程中唯一遇到的一点障碍就是在写循环判断时由于多重判断多重循环导致混乱，幸好最后改

正了，最后得到的结果经检验与给定的结果相同。通过这次实验上机，