《页面置换算法操作系统课程设计报告.doc》由会员分享，可在线阅读，更多相关《页面置换算法操作系统课程设计报告.doc（55页珍藏版）》请在三一办公上搜索。
1、计算机与信息学院操作系统综合设计报告设计题目：页面置换算法学生姓名：学 号：专业班级：计算机科学与技术班2015 年 7月一、设计题目3二、开发环境与工具3三、设计原理31.最佳（Optimal）置换算法32.先进先出（FIFO）页面置换算法43.最近最久未使用（LRU）页面置换算法4四、重要算法51.算法流程图52. 关键代码8五、设计结果22六、设计体会24七、附录24一、设计题目第15题：页面置换算法1. 建立相应的数据结构；2. 在屏幕上显示页面的状况；3. 时间的流逝可以用下面几种方法模拟：（a） 按键盘，每按一次可以认为过一个时间单位；（b） 相应WM_TIMER；4. 将一批页的
2、置换情况存入磁盘文件，以后可以读出并重放；5. 计算页面的缺页次数、缺页后的页面置换次数；6. 支持算法：FIFO、LRU、最佳置换算法。二、开发环境与工具开发环境：Windows开发工具：VC6.0 、 Eclipse三、设计原理1.最佳（Optimal）置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或是在未来最长时间内不再被访问的页面。采用最佳置换算法通常可以保证获得最低的缺页率，但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以用该算法去评价其他算
3、法。现举例说明如下：假定系统为某进程分配了三个物理快，并考虑有以下的页面号引用串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1进程运行时，先将7,0,1三个页面放入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法将将选择页面7予以淘汰。这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面7则要在第18次页面访问是才需调入。下次访问页面0时，因它已在内存而不必产生缺页中断。当进程访问页面3时，又讲引起页面1被淘汰；因为它在现在的1,2,0三个页面中，将是以后最晚才被访问的。
4、图1示出了采用最佳置换算法时的置换图。由图可以看出，采用最佳置换算法发生了6次页面置换。 页面号70120304230321201701物理快1777222227物理快200004000物理快311333112.先进先出（FIFO）页面置换算法FIFO算法是最早出现的置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最长的页面予以淘汰。该算法实现简单，只需要把已经调入内存的页面按先后次序排成一个队列，当发生缺页时，将队首页面出队，再将找到的页面入队，这样就完成了页面置换的任务。以书上的为例有如下表格：70 1 2 0 3 4 2 30 3 2 1 2 0 1 7 0 77722
5、2444000000077000033222221111101111003333322222但该算法与程序的运行规律不相适应，它忽视了程序运行的局部性原理。有可能造成需要访问的页面经常性的被置换。3.最近最久未使用（LRU）页面置换算法FIFO算法性能较差，它是根据页面进入的先后次序进行置换，并不能反映页面的使用情况。最近最久未使用（LRU）算法的基本思想是利用“最近的过去”来预测“最近的未来”，这个也是根据程序运行的局部性原理。由于最佳置换算法只有理论价值，实际系统中是无法使用的，所以就利用最近的过去来预测未来。该算法每访问一个字段，记录一个自上次以来被访问以来所经历的时间t。当需要淘汰一个
6、页面时，选择所有页面中t值最大的，即最近最久未使用的页面予以置换。以书上为例，有如下表格：70 1 2 0 3 4 2 30 3 2 1 2 0 1 7 0 777222444000111111000000033333300001113322222222277四、重要算法1.算法流程图FIFO算法流程图：Yi+把pi的内容直接装入最上面一个空内存块，i+把page中最先装入的页面置换出去.i+Page是否有空当前p中第i个元素是否已在内存中页面走向存入数组p中，内存块用page表示初始化为0开始NYN输出当前内存块状态结束LRU算法流程图： 开始页面走向存入数组p中，内存块用page表示初始化
7、为0Y当前p中第i个元素是否已在内存i+NNPage是否有空Y结束把pi的内容直接装入最上面一个空内存块，i+输出当前内存块状态把page中最近最久未使用的页面置换出去.i+OPT算法流程图： 开始Yi+ 结束输出当前内存块状态把page中以后一段时间都不使用或是使用时间离现在最远的换出.i+把pi的内容直接装入最上面一个空内存块，i+Page是否有空当前p中第i个元素是否已在内存页面走向存入数组p中，内存块用page表示初始化为0NNY2. 关键代码1. FIFO算法代码：public class FIFOControl /private int num = 7,0,1,2,0,3,0,4,
8、2,3,0,3,2,1,2,0,1,7,0,1;/使用无参构造函数private int num = new int50;private int numLength;private int pg = new int10;private int timepg = new int10;private int PageNum;public int store;FIFOControl()this.PageNum = 3;numLength = 20;int numtemp = 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1;for( int i = 0; i numLe
9、ngth; i+ )numi = numtempi;for(int i = 0; i 10; i+)pgi = -1;timepgi = 1;store = new intnumLengthPageNum+1;for( int i = 1; i PageNum+1; i+)for( int j = 0; j numLength; j+ )storeji = -1;for( int k = 0; k numLength; k+ )storek0 = 0;FIFOControl( int nump, int n, int nlength )/参数：1.物理块数 2.页面序列号 3.页面序列号数组长
10、度 meiyongthis.PageNum = nump;numLength = nlength;for(int j = 0; j nlength; j+)numj = nj;for(int i = 0; i 10; i+)pgi = -1;timepgi = 1;store = new intnumLengthPageNum+1;for( int i = 1; i PageNum+1; i+)for( int j = 0; j numLength; j+ )storeji = -1;for( int k = 0; k numLength; k+ )storek0 = 0;private bo
11、olean checkInPage( int p, int plength, int keynum )for( int jj = 0; jj plength; jj+)timepgjj+;for(int j = 0; j plength; j+)if( keynum = pj )return true;return false;private void caculate()/将物理页框装满int timer = 0;/横着的指针for( int i = 0; i PageNum; i+ )pgi = numi;for( int j = 0; j i; j+)/加时间timepgj+;for(i
12、nt jj = 0; jj PageNum; jj+)/数据放到store中去storetimerjj+1 = pgjj;timer+;/把后面的数据按先进先出的顺序放到物理块中for( int i = PageNum; i numLength; i+ )if( checkInPage( pg, PageNum, numi ) )/如果在物理框中将对应位时间置为1for(int j = 0; j PageNum; j+)/把这次物理块中的数据存储起来storetimerj+1 = pgj;timer+;else/否则找出时间最长的，将其置换，并将对应位的时间置为1int max = timep
13、g0;int maxvalue = pg0;int maxindex = 0;int temp;for( int n = 1; n = max )max = temp;maxvalue = pgn;maxindex = n;/System.out.println( max + max );/System.out.println( maxindex + maxindex );pgmaxindex = numi;timepgmaxindex = 1;for(int j = 0; j PageNum; j+)/把这次的数据存储起来storetimerj+1 = pgj;storetimer0 = m
14、axindex+1;timer+;/测试查看结果/for( int i = 0; i PageNum+1; i+)/se shi/for( int j = 0; j numLength; j+ )/System.out.print(storeji + );/System.out.println();/public int getStore()this.caculate();return store;public class FIFOControl /private int num = 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1;/使用无参构造函数privat
15、e int num = new int50;private int numLength;private int pg = new int10;private int timepg = new int10;private int PageNum;public int store;FIFOControl()this.PageNum = 3;numLength = 20;int numtemp = 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1;for( int i = 0; i numLength; i+ )numi = numtempi;for(int i = 0
16、; i 10; i+)pgi = -1;timepgi = 1;store = new intnumLengthPageNum+1;for( int i = 1; i PageNum+1; i+)for( int j = 0; j numLength; j+ )storeji = -1;for( int k = 0; k numLength; k+ )storek0 = 0;FIFOControl( int nump, int n, int nlength )/参数：1.物理块数 2.页面序列号 3.页面序列号数组长度 meiyongthis.PageNum = nump;numLength
17、= nlength;for(int j = 0; j nlength; j+)numj = nj;for(int i = 0; i 10; i+)pgi = -1;timepgi = 1;store = new intnumLengthPageNum+1;for( int i = 1; i PageNum+1; i+)for( int j = 0; j numLength; j+ )storeji = -1;for( int k = 0; k numLength; k+ )storek0 = 0;private boolean checkInPage( int p, int plength,
18、int keynum )for( int jj = 0; jj plength; jj+)timepgjj+;for(int j = 0; j plength; j+)if( keynum = pj )return true;return false;private void caculate()/将物理页框装满int timer = 0;/横着的指针for( int i = 0; i PageNum; i+ )pgi = numi;for( int j = 0; j i; j+)/加时间timepgj+;for(int jj = 0; jj PageNum; jj+)/数据放到store中去
19、storetimerjj+1 = pgjj;timer+;/把后面的数据按先进先出的顺序放到物理块中for( int i = PageNum; i numLength; i+ )if( checkInPage( pg, PageNum, numi ) )/如果在物理框中将对应位时间置为1for(int j = 0; j PageNum; j+)/把这次物理块中的数据存储起来storetimerj+1 = pgj;timer+;else/否则找出时间最长的，将其置换，并将对应位的时间置为1int max = timepg0;int maxvalue = pg0;int maxindex = 0;
20、int temp;for( int n = 1; n = max )max = temp;maxvalue = pgn;maxindex = n;/System.out.println( max + max );/System.out.println( maxindex + maxindex );pgmaxindex = numi;timepgmaxindex = 1;for(int j = 0; j PageNum; j+)/把这次的数据存储起来storetimerj+1 = pgj;storetimer0 = maxindex+1;timer+;public int getStore()t
21、his.caculate();return store;2. LRU算法代码：public class LRUControl /private int num = 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1;/使用无参构造函数private int num = new int50;/使用有参构造函数private int numLength;private int PageNum;private Page pg = new Page10;public int store;public int temp1; LRUControl()PageNum = 3;nu
22、mLength = num.length;store = new intnumLengthPageNum;for( int i = 0; ithis.PageNum; i+ )pgi = new Page();if( this.pgi != null )this.pgi.setValue(-1);this.pgi.setTime(0);elseSystem.out.println( 对象创建失败！ +rn);LRUControl( int nump, int n, int nlength )/参数：1.物理块数 2.页面序列号 3.页面序列号数组长度 meiyongthis.PageNum =
23、 nump;numLength = nlength;for(int j = 0; j nlength; j+)numj = nj;store = new intnumLengthPageNum+1;/gai dongtemp1 = new intnumLengthPageNum+1;for( int i = 0; ithis.PageNum; i+ )pgi = new Page();if( this.pgi != null )this.pgi.setValue(-1);this.pgi.setTime(0);elseSystem.out.println( 对象创建失败！ +rn);priva
24、te boolean checkInPage( Page p, int plength, int keynum )for( int jj = 0; jj plength; jj+)pjj.setTime( pjj.getTime()+1 );for(int j = 0; j plength; j+)if( keynum = pj.getValue() )return true;return false;void caculate()int timer = 0;/前PageNum个，先将物理快装满for( int i = 0; i PageNum; i+ )pgi.setValue( numi
25、);pgi.setTime( 1 );for( int j = 0; j i; j+)pgj.setTime( pgj.getTime()+1 );for(int j = 0; j PageNum; j+)storetimerj = pgj.getValue();timer+;for( int i = 0; i PageNum; i+)storeiPageNum = 0;/num数组后面的页面检查每一个是否在前面出现过，有置该页框时间为1，没有则在原基础上加1for( int i = PageNum; i numLength; i+ )if( checkInPage( pg, PageNum,
26、 numi ) )/如果在物理框中将对应位时间置为1for( int m = 0; m PageNum; m+ )/把numi和pg中相等的物理块时间置1if( numi = pgm.getValue() )pgm.setTime(1);break;for(int j = 0; j PageNum; j+)/把这次物理块中的数据存储起来storetimerj = pgj.getValue();storetimerPageNum = 0;timer+;else/否则找出时间最长的，将其置换，并将对应位的时间置为1int max = pg0.getTime();int maxindex = 0;i
27、nt temp;for( int n = 1; n = max )max = temp;maxindex = n;/System.out.println( max + max );/System.out.println( maxindex + maxindex );pgmaxindex.setTime(1);pgmaxindex.setValue(numi);for(int j = 0; j PageNum; j+)/把这次的数据存储起来storetimerj = pgj.getValue();storetimerPageNum = maxindex+1;timer+;void display
28、()for( int i = 0; iPageNum; i+)for(int j = 0; j numLength; j+)System.out.print( storeji + );System.out.println();private void adjustStore()for( int i = 1; iPageNum+1; i+)for(int j = 0; j numLength; j+)temp1ji = storeji-1;for(int k = 0; k numLength; k+)temp1k0 = storekPageNum;public int getStore()adj
29、ustStore();return temp1;3. OPT算法代码：int Optimal(int page, int page_num, int memory_num, int process)/参数(访问页面数组,访问页面的总数,内存块数) int max;/未来最长时间内不被访问的页面距下次被访问的时间 int max_page;/未来最长时间内不被访问的页面号 int memory_null;/内存中的空位号(没有空位时为-1) int lack = 0;/记录缺页次数 /int process = new int5050;/记录置换过程 Memory memory = new Me
30、mory10;/创建内存 /记录置换过程数组初始化 for(int a=0;a=memory_num;a+) for(int b=0;bpage_num;b+) processab = -1; /内存块初始化 for(int m=0;mmemory_num;m+) memorym = new Memory(); memorym.page = -1; memorym.next = 0; for(int i=0;ipage_num;i+)/依次读取页面 System.out.println(n读取:+pagei); if(isMemory(pagei, memory, memory_num)/【页
31、面已在内存中】 System.out.println(页面已在内存中); /记录 process0i = 0;/没有置换 for(int n=1;n=memory_num;n+) processni = processni-1; else /【页面不在内存中】 memory_null = isNull(memory, memory_num);/获取内存中的空位号(没有空位时为-1) if(memory_null=-1)/内存中没有空位 /获取各内存块中页面距下次被访问的时间 for(int j=0;jmemory_num;j+) memoryj.next = nextAccess(memory
32、j.page, page, page_num, i); /输出各内存块中页面距下次被访问的时间 System.out.print(next:); for(int y=0;ymemory_num;y+) System.out.print(memoryy.next+ ); System.out.println(); /获取未来最长时间内不被访问的页面号 max = memory0.next; max_page = 0; for(int j=0;jmax) max = memoryj.next; max_page = j; /将未来最长时间内不被访问的页面号置换为新页面 System.out.pri
33、ntln(置换+memorymax_page.page+-+pagei); memorymax_page.page = pagei;/置换 lack+;/更新缺页次数 /记录 process0i = max_page+1;/发生置换 processmax_page+1i = pagei; for(int n=1;n=memory_num;n+) if(n!=max_page+1) processni = processni-1; else /内存中有空位 System.out.println(内存中有空位+memory_null); memorymemory_null.page = pagei; /将新页面放入内存块的空位中 for(int x=0;xmemory_num;x+) System.out.print(m
