操作系统课程
-页面置换算法模拟程序报告
1 引 言 ..................................................... 1 1.1 问题的提出 .......................................................... 1 1.2国内外研究的现状 .................................................... 1 1.3任务与
.......................................................... 2 2 需求分析 ................................................... 2
2.1页面置换算法概念 ........................................................................................................................ 2
2.2关于页面置换算法的一些基本思想 ........................................................................................ 3
2.2.1先进先出(FIFO)页面置换算法 .............................................. 3
2.2.2最近最久未使用(LRU)置换算法 ............................................. 3
2.2.3最佳(Optimal)置换算法 ................................................... 4 2.3需求分析 ............................................................ 5 3 程序运行平台 ....................................................... 5 4总体设计 ................................................... 5
5详细设计 ................................................... 6
5.1界面设计 .................................................................... 6
5.2随机产生长度为20的页面走向 ............................................... 6
5.3 FIFO算法设计 ............................................................... 8
5.4 LRU算法设计 ............................................................... 11
6 系统测试 .................................................. 15
6.1测试的数据 ................................................................. 17
6.2测试小结 ................................................................... 21
总 结 ................................................................ 23 致 谢 ....................................................... 24
参考文献 ............................................................. 24
页面置换算法模拟
摘 要
随着计算机的普及,人们生活得到极大改善,人们在精神方面也同样需要提高,所以越来越多的人进行着各种各样的学习。操作系统是计算机中最重要的环节之一,也是计算机专业学生的一门重要的专业课程。操作系统的好坏,直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大的扩展计算机的功能,充分发挥系统中的各种设备的使用效率,提高系统的可靠性。由于操作系统中各种软硬件资源的管理,内容比较繁琐,具有很强的实践性,要学号这门课程,必须把理论和实践紧密结合,才能取得教好的学习效果。
本次课程设计是在学习完《操作系统教程》后,进行的一次全面的综合训练,通过课程设计,让学生更好的掌握操作系统的原理以及实现方法,加深对操作系统基础理论和重要算法的理解,加强对学生的动手能力。
熟悉页面置换算法及其实现,引入计算机操作性能评价方法的概念。
关键词,页面置换算法,LRU算法,OPT算法,FIFO算法
页面置换算法模拟 1 引 言
1.1 问题的提出
在存储器管理方式中,有一个特点,就是当要求作业全部装入内存才能运行。但是这样就存在两种情况:
(1)有的作业很大,不能全部装入内存,致使作业无法进行。
(2)有大量作业要求运行时,内存容量不足容纳所有作业,而虚拟内存技术正是下哦那个逻辑上扩充内存容量,将会解决以上两个问题。
所以,可以当进程开始运行时,先将一部分程序装入内存,另一部分暂时留在外存;当要执行的指令不在内存时,由系统自动完成将它们从外存调入内存的工作;当没有足够的内存空间时系统自动选择部分内存空间,将其中原有的内容交换到磁盘上,并释放这些内存空间供其它进程使用
通常,把选择换出页面的页面的算法称为页面置换算法,模拟页面置换算法用以客观解决内存不足的矛盾。
1.2国内外研究的现状
1961年英国曼彻斯特大学推出了“虚拟存储”管理技术,并在ATRAS计算机上实现这一技术,70年代以后,这一技术才真正广泛使用,目前许多大型计算机均采用此技术。虚拟存储管理技术的关键在于页面置换算法的选择。1966年Belady在理论上提出最优页面置换算法(Optimal Replacement Algorithm, OPT),此外还有先进先出置换算法(first input first output, FIFO) ,最近最少使用页面置换算法(least recently used, LRU),最少使用页面置换算法(least frequent used, LFU,或最不常用算法),时钟置换算法(clock,或称最近未使用页面置换算法(not used recently, NUR)),页面缓冲(page buffering)置换算法等。
-1-
页面置换算法模拟 1.3任务与分析
本课程设计完成一个简单页面置换算法的模拟,加深理解页面置换算个算法对于存储器内存扩展使用的原理以及对于不同置换算法的使用的优缺点。在此次课程设计中完成的只是一个小小的模拟算法,对于操作系统中对于置换算法的选择远远不止这些。 用随机数方法产生页面走向,页面走向长度为L。
根据页面走向,分别采用FIFO和LRU算法进行页面置换,统计缺页率;为简化操作,在淘汰一页时,只将该页在页表中抹去,而不再判断它是否被改写过,也不将它写回到辅存。
假定可用内存块和页表长度 (作业的页面数)分别为m和k,初始时,作业页面都不在内存。
随机数产生程序:
function random: real:
begin Seed: =125.0 (seed+1.0)
Seed: =Seed 8192.0 trunc (seed/8192)
random: = (Seed+0.5)/8192 end;
上述随机数发生函数产生的随机数为0.0,1.0,稍另变化就可得到0,n 1之间的随机数。
程序开始时,应对变量Seed (实型)赋初值。
2 需求分析
2.1页面置换算法概念
所谓页面置换算法,是操作系统中对于页式存储管理中的一种软件虚拟存储管理方式实现的一种具体的算法操作,页面置换算法的优劣将会影响虚拟存储系统的性能,进而影响整个系统的性能。
-2-
页面置换算法模拟 2.2关于页面置换算法的一些基本思想
2.2.1先进先出(FIFO)页面置换算法
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择
在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已
调入内存的页面,按照先后次序链接成一个队列,并设置一个指针,称为替换
指针,使它总指向最老的页面。但该算法与进程实际运行的规律不相适应,因
为在进程中,有些页面经常被访问,比如,含有全局变量、常用函数、例程等
的页面,FIFO算法并不能保证这些页面不被淘汰。
以下为采用FIFO算法进行页面置换的例子(图1)。当进程第一次访问页
面2时,将把第7页置换出,因为它是最先被调入内存的;在第一次访问页面
3时,又将把页0置换出,因为它在现有的2,0,1三个页面中是最老的页。
由图1可以看出,利用FIFO算法时进行了12次页面置换。
引用率
70120304230321201701
7 7 7 2 2 2 4 4 4 0 0 0 7 7 7
0 0 0 3 3 3 2 2 2 1 1 1 0 0
1 1 1 0 0 0 3 3 3 2 2 2 1 页框
图1 利用FIFO置换算法时的置换图
2.2.2最近最久未使用(LRU)置换算法
FIFO置换算法性能之所以较差,是因为它所依据的条件是各个页面调入内存的时间,而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法,是根据页面调入内存后的使用情况进行决策的。由于无法预测各页将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来
一个页面自上次被访问以来所经历的时间t,当须淘汰一个
-3-
页面置换算法模拟 页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。
利用LRU算法对上例进行页面置换算法的结果如图2所示。当进程第一次对页面2进行访问时,由于页面7是最近最久未访问的,故将它置换出去。当进程第一次对页面3进行访问时,第1页成为最近最久未使用的页,将它换出。根据各页以前的使用情况来判断,页面过去和未来的走向之间并无必然的关系。
引用率
70120304230321201701
7 7 7 2 2 4 4 4 0 1 1 1
0 0 0 0 0 0 3 3 3 0 0
1 1 3 3 2 2 2 2 2 7 页框
图1 利用LRU置换算法时的置换图
2.2.3最佳(Optimal)置换算法
最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰的页面,将是以后永不使用的,或是在最长(未来)时间内不再被访问的页面。采用最佳置换算法,通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中,哪一个页面是将来最长时间内不再访问的,因而该算法时无法实现的,但可以利用该算法评价其他算法。现举例说明如下(图3)。
进程运行时,先将前三个页面装入内存。以后,当进程要访问页面2时,将会产生缺页中断。此时OS根据最佳置换算法,将选择页面7予以淘汰。这是因为页面0将作为第5个被访问的页面,页面1是第14个被访问的页面,而页面7则要在第18次页面访问时才需要调入。下次访问页面0时,因它已在内存而不必产生缺页中断。当进程第一次访问页面3时,又将引起页面1被淘汰,因为,它在现有的1,2,0三个页面中,将是以后最晚才被访问的。由图可以看出,采用最佳置换算法发生了6次页面置换。
-4-
页面置换算法模拟 引用率
70120304230321201701
7 7 7 2 2 2 2 2 7
0 0 0 0 4 0 0 0
1 1 3 3 3 1 1 页框
图1 利用LRU置换算法时的置换图
2.3需求分析
在进程中运行过程中,若所要访问的页面不在内存中,需要调入页面时,选择内存中的那个物理页面将其调出。通常只能再局部性原理指导下,把未来不再使用的页面调出。如何选择调度策略即页面置换算法至关重要,置换算法的好坏,直接影响着系统的性能,因此我们有必要将常见的FIFO、LRU、OPT三种算法进行比较,分析性能。因此我们需要选择一种好的算法来对内存虚拟扩充的一种有效方法,提高内存利用率。
3 程序运行平台
Windows 7或Windows xp及以上版本 Java JDK NeatBeans6.5的版本上运行 NetBeans IDE6.5,JDK1.6。
4总体设计
开始
产生页面中页面
走向的随机数
选择FIFO选择LRU
算法 算法
-5-
页面置换算法模拟 5详细设计
5.1界面设计
由于此次程序是使用JAVA程序设计语言所写,所以为了外表美观,便于用户操作,改程序使用了GUI设计,界面主要由1个JFrame、1个JPanel、57个JLabel组件、2个JButton组件、2个JRadioButton组件、6个JTextField组件组成,界面如下:
5.2随机产生长度为20的页面走向
5.2.1主要设计思想
由于GUI设计的特殊性,所以为了界面的显示和美观,则产生20个随机数并不是像C语言那样用一个函数就可以搞定的,而是需要定义20个线程来产生20个数(页号),每一个线程产生一个随机数并且控制一个JLabel组件的输出。然后利用一个JButton组件“开始”,产生一组随机数,然后再用JButton组件“停止”显示输出结果。
-6-
页面置换算法模拟
5.2.2主要代码
由于20个线程的代码基本相同,因此现将其中一个线程的代码列出如下:
class mylabel2 implements Runnable{//内部类-----代表一个线程
public boolean stop;//
public void run(){//线程的run方法
stop=false;
int j;
for(;;){
j=(int)(Math.random()*10);///////////////????????????????!!!!!!!!!!!!!!!!!!!!!1找的我好辛苦,一定要加括号
jLabel2.setText(Integer.toString(j));
try {
Thread.sleep(100);
} catch (InterruptedException ex) {
Logger.getLogger(main_frame.class.getName()).log(Level.SEVERE, null, ex);
}
if(stop)
break;
}//for
}//run
}
5.2.3主要流程图
stop=false
j=(int)(Math.random()*10
)
N
stop=false?
Y
break;
-7-
页面置换算法模拟
5.2.4产生随机数结果
5.3 FIFO算法设计
5.3.1主要思想
首先初始化页表信息,将所有页的block_num属性赋值为-1,表示开始的时候任何页都不在内存中;其次再初始化内存表信息,将所有页的page_num属性赋值为-1,表示开始时候内存块中没有任何一页。然后,利用一个for循环 循环20次,实现20次访问页面。由于置换的算法是FIFO(先进先出)算法,所以将内存中四个块建立成一个队列,访问页面时依次将页面调入内存。如果内存中没有空间了则将队首内存块中的页面置换出去,将将要访问的页面调入该内存块,然后依次这样继续下去,直到20次访问结束。最后再在每次循环结束后判断是否发生缺页,如果缺页则计数器自动加1,如果不缺页计数器就不变。
-8-
页面置换算法模拟
5.3.2 FIFO程序模块代码
class run_FIFO implements Runnable{///////////执行FIFO算法线程//////////////
public Page[] table=new Page[10];//具有十个页面的页表
public Memary[] memary=new Memary[4];//内存中有四个块
run_FIFO(){
int i;
for(i=0;i<10;i++){
table[i]=new Page(i,-1,0);
}
for(i=0;i<4;i++){
memary[i]=new Memary(i,-1,i);
}
}
public void run(){
///显示两个表的信息
num++;
int i,j,n=0,visit_page;//当前访问页
Memary temp;//中间变量
for(i=0;i<20;i++){//循环20次
if(stop==true){
// JOptionPane.showMessageDialog(null, " 如果执行此操作\n\n将终止当前正在执行运行的FIFO算法");
return;
}
jTextField5.setText(Integer.toString(i+1));//显示执行次数
visit_page=visit[i];
j=4;
if(table[visit_page].flag==0){//表示当前页不在内存,缺页
n++;//记录缺页次数
if(memary[3].page_num==-1){
for(j=0;j<4;j++){//查找内存中是否有空位
if(memary[j].page_num==-1)
break;
}//for
}//if
if(j<4){//有空位
table[visit_page].flag=1;//修改页表
table[visit_page].block_num=memary[j].block_num;
memary[j].page_num=visit_page;//修改内存表
}
else{//没有空位,进行替换
-9-
页面置换算法模拟
table[memary[0].page_num].flag=0;//将内存表中第一个结点替换出去,并修
改页表信息
table[memary[0].page_num].block_num=-1;
table[visit_page].block_num=memary[0].block_num;
table[visit_page].flag=1;
memary[0].page_num=visit_page;//修改内存表信息
temp=memary[0];//将头节点插到队尾
memary[0]=memary[1];
memary[1]=memary[2];
memary[2]=memary[3];
memary[3]=temp;
}
jTextField1.setText(Integer.toString(n));//时刻显示缺页率
}//if
//else{}//不缺页,不做任何处理
jTextField2.setText(Float.toString((float)n/(i+1)*100));
init_jLabel_FIFO(memary);
try {
Thread.sleep(1500);
} catch (InterruptedException ex) {
Logger.getLogger(main_frame.class.getName()).log(Level.SEVERE, null, ex);
}
}//for
JOptionPane.showMessageDialog(null,"\nFIFO算法执行结束~\n");
jTextField1.setText(Integer.toString(n));
jTextField2.setText(Float.toString((float)n/20*100));
}//run
}//run_FIFO
-10-
页面置换算法模拟
5.3.3 FIFO算法程序流程图
创建两个表
初始化表信息
i=0
Y visit[i].flag=0?
N 该页调入内存
n++
num++,i++
Y i<20
N
结束
5.4 LRU算法设计
5.4.1主要思想
首先初始化页表信息,将所有页的block_num属性赋值为-1,表示开始的时候任何页都不在内存中;其次再初始化内存表信息,将所有页的page_num属性赋值为-1,表示开始时候内存块中没有任何一页。然后,利用一个for循环 循环20次,实现20次访问页面。由于置换的算法是LRU(最近最少使用)算法,所以将内存中四个块建立成一个队列,访问页面时依次将页面调入内存。如果内存中没有空间了则将队首内存块中的页面置换出去,将将要访问的页面调入该内存块,然后依次这样继续下去,直到20次访问结束。需要强调的是,LRU算法在有一方面与FIFO算法不一样,那就是当被访问的页
-11-
页面置换算法模拟 面已在内存中,FIFO算法不做任何处理,但是LRU算法需要将该存有该页面的内存块放到队尾。最后再在每次循环结束后判断是否发生缺页,如果缺页则计数器自动加1,如果不缺页计数器就不变。
5.4.2 LRU程序模块代码
class run_LRU implements Runnable{///////////执行FIFO算法线程//////////////
public Page[] table=new Page[10];//具有十个页面的页表
public Memary[] memary=new Memary[4];//内存中有四个块
run_LRU(){
int i;
for(i=0;i<10;i++){
table[i]=new Page(i,-1,0);
}
for(i=0;i<4;i++){
memary[i]=new Memary(i,-1,i);
}
}
public void run(){
///显示两个表的信息
num++;
int i,j,k,l,h,n=0,visit_page;//当前访问页
Memary temp;//中间变量
for(i=0;i<20;i++){//循环20次
if(stop==true){
//JOptionPane.showMessageDialog(null, " 如果执行此操作\n\n将终止当前正在执行运行的LRU算法");
return;
}
jTextField6.setText(Integer.toString(i+1));//显示执行次数
visit_page=visit[i];
j=5;
if(memary[3].page_num==-1){//此目的是判断当内存中已经满了就不用查找,降低复杂度
for(j=0;j<4;j++){//查找内存中是否有空位
if(memary[j].page_num==-1)
break;
}//for
}//if
if(table[visit_page].flag==0){//表示当前页不在内存,缺页
n++;//记录缺页次数
-12-
页面置换算法模拟
if(j<4){//有空位
table[visit_page].flag=1;//修改页表
table[visit_page].block_num=memary[j].block_num;
memary[j].page_num=visit_page;//修改内存表
}
else{//没有空位,进行替换
table[memary[0].page_num].flag=0;//将内存表中第一个结点替换出去,并修改页表信息
table[memary[0].page_num].block_num=-1;
table[visit_page].block_num=memary[0].block_num;
table[visit_page].flag=1;
memary[0].page_num=visit_page;//修改内存表信息
temp=memary[0];//将头节点插到队尾
memary[0]=memary[1];
memary[1]=memary[2];
memary[2]=memary[3];
memary[3]=temp;
}
jTextField3.setText(Integer.toString(n));//时刻显示缺页次数
}//if
else{//不缺页,需要将当前结点从当前位置移到队列的存在的已存的最后一页位置上,而当前页以后的页就依次前移
k=0;
for(j=0;j<4;j++){//查找
if(memary[j].page_num==visit_page)//查找被访问页在内存中的位置
k=j;//k记录被访问页在内存中的位置
if(memary[j].page_num==-1)//记录内存中最后一页的位置,即为j-1
break;
}//for
if(j-1==k){//说明被访问结点是最后一个结点
;//不做任何操作
}
else{//进行替换操作
temp=memary[k];
for(l=k+1;l
工程项目打开,实例如图6.0.1:
图表 6.0.1打开项目界面
-15-
页面置换算法模拟
然后再运行运行该项目,进入模拟程序界面,界面如图6.0.2:
图表 6.0.2
-16-
页面置换算法模拟
点击“开始”按钮,产生一组长度为20的随机数,也即长度为20的页面走向,如图6.0.3:
图表 6.0.3
6.1测试的数据
现在利用图表6.0.3产生的测试数组进行测试,由该图可以看出,产生的页面走向是如下序列:
6 1 7 2 5 3 9 8 1 3 1 6 7 3 9 5 5 3 3 1
在图6.0.3中可以看出有两种置换方式,即LRU算法和FIFO算法,在演示的过程中看以动态的看到页面的访问次数(执行次数)、缺页次数、缺页率,并且为了比较两种算法的结果,可以同时进行两种算法的演示,也可以先后进行。由于程序是动态进行的,所以只能随机截几张图,并不能依次的截图演示,如下图所示。
-17-
页面置换算法模拟
1、如图6.1.1可以看出,当FIFO算法执行3次的时候,缺页数为3次,缺页率是100%。而此时由于LRU不是与FIFO算法同时开始,所以只执行了2两次,缺页次数也是2次,缺页率为100%。
图表6.1.1
-18-
页面置换算法模拟
2、如图6.1.2所示,当FIFO算法执行了10次时,缺页次数是9次,缺页率是90%;而此时LRU算法执行了9次,缺页次数是9次,所以缺页率还是100%。
图表 6.1.2
-19-
页面置换算法模拟
3、如图6.1.3,可以看出当最后两种算法都执行结束时FIFO算法缺页次数是15次,缺页率是75%;LRU算法缺页次数是14,缺页率是70%。
图表 6.1.3
-20-
页面置换算法模拟 6.2测试小结
根据以上演示,可以看出在访问次数有限的情况下,LRU算法与FIFO算法的缺页次数结果基本相似,所以这两中算法差别不大,下面再给几组测试以说明结论。
1、如图6.2.1,可以看出当页面走向是:
0 1 4 3 7 7 4 3 0 6 2 4 5 61 4 3 3 5 9
最后两种算法都执行结束时FIFO算法缺页次数是13次,缺页率是65%;LRU算法缺页次数是13,缺页率是65%。
-21-
页面置换算法模拟
1、如图6.2.2,可以看出当页面走向是:
0 9 7 8 5 5 2 3 8 4 7 7 9 0 4 6 4 2 4 0
最后两种算法都执行结束时FIFO算法缺页次数是14次,缺页率是70%;LRU算法
缺页次数是13,缺页率是65%。
图表 6.2.2
-22-
页面置换算法模拟
总 结
页面置换算法是操作系统中对虚拟存储技术中必不可少的一种置换算法,由于本次设计中要求用先进先出(FIFO)和最近最少使用(LRU)算法来模拟,因此对其他的一些算法就没有涉及到,但是在学习操作系统的时候,都有涉及一些其他的算法,这是在完成课程同时需要掌握的内容。页面走向是根据用户输入页面走向长度和页表长度随机上的布局有产生的,在编写程序的时候要确保自己把算法写对了,就要多次进行数据验证,有时FIFO和LRU产生的缺页数和缺页率会相同,这都是可以存在的。本次设计中对于界面的设计点不是很漂亮,需要进一步的改进。
通过这次课程设计的实现操作,真切的感受到文件系统对一个操作系统的重要性, 其作用领域几乎涵盖了操作系统的所有文件,所有属性等,对各种文件的操作都是基于文件系统来完成的,体现出了文件系统在目前任何操作系统的意义和重要性。
另外在本次课程设计的过程中,通过向指导老师请教,在网上以及图
馆搜索相关信息大大的加深了对操作系统文件管理的理解和认识,并对操作系统某些领域的产生了兴趣,为以后的继续深研操作系统打下了理论、实践和兴趣基础,收益很大~
-23-
页面置换算法模拟
致 谢
首先感谢李老师为我安排的这次课程设计,通过这次课程设计的安排和为我讲解的一些知识,解决的一些问题,我收获了很多,在很多方面得到了锻炼、提高。例如,对于计算机是如何利用很小的内存空间运行很大的应用程序,以前对这个概念是懵懵懂懂,但要自己真正的描述出来肯定是摸不着头脑的,只知道是利用了虚拟存储技术。但是通过此次课程设计对两种典型的虚拟存储技术的描绘,模拟,深深理解了它的方式方法及其所有优点、可行性,并通过不断地调试加深了印象。同时也要感谢教我们操作系统的唐老师和JAVA课上的周老师,没有这两门课程的学习我是不可能顺利的完成此次课程设计;还要感谢帮助过我的同学,其实在没有上机的时候我也在做课程设计,但此时也遇到了一些问题不能及时请老师解决,所以我就请同学帮忙。我知道其他同学也很忙,也要做很多学习作业,但是他们还是很主动的帮助了我,真的很感谢他们,没有他们,我也不可能这么顺利地完成此次课程设计~
参考文献
[1] 张尧学等编著. 计算机操作系统教程 .北京:清华大学出版社,2006.02
[2] 汤子瀛等编著. 计算机操作系统 .西安:西安电子科技出版社,1996.12
[3] 陈向群 编著. 操作系统教程 .北京:北京大学出版社,2007.01
[4] 罗宇 等编著. 操作系统课程设计 .北京:机械工业出版社,2005.9
[5]叶乃文等编著. Java语言程序设计教程 .北京:机械工业出版社,2010.1
附录:
由于代码是工程文件,所以不能粘贴在此处,在与报告同目录的文件夹下,名为“页面置换算法模拟”。
-24-