操作系统课程设计-页面置换算法模拟程序报告

操作系统课程设计-页面置换算法模拟程序报告 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