实验五-页面调度算法模拟

1、实验五：页面调度算法模拟实验学时：2学时一、 实验目的1、熟悉操作系统页面调度算法2、编写程序模拟先进先出、LRU等页面调度算法，体会页面调度算法原理二、实验基本原理1、页面的含义：分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。2、页面置换算法的含义：在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。3、置换算

2、法一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。常见置换算法：最佳置换算法(Optimal)：它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 先进先出(FIFO)页面置换算法：这是最早出现的置换算法。该算法总是淘汰最先进入内

3、存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 LRU置换算法：LRU置换算法是选择最近最久未使用的页面予以淘汰。 二、 实验参考程序先进先出页面调度算法模拟/*-程序说明：1、main函数在调用时会先产生一串随机数列，并存放在listN中；2、然后mian函数调用IsInBuf函数，把当前读到的单词x和bufi中的内容进行比较。如果x在buf中，则返回其位置j;如果x不在buf中，则返回-1。3、当x在buf中的时候，不发生缺页中断。并且开始读list中的下一个

4、单词； 当x不在buf中的时候，发生缺页中断，输出被淘汰的页面的内容bufi。把listi放到bufold中，并且old开始循环指向下一个buf的位置。FIFO算法说明：1、把数列中的数字依次放入内存中；2、数字的存放是按照先进先出的方式，即循环存储。可以用old=(old+1)%(int)B来实现。-*/#include <stdio.h>#include <stdlib.h>/#include <conio.h>#include <time.h>#define N 10/*随机数列的长度*/#define B 3/*内存页面数*/*-函数名：

5、IsInBuf()功能：返回某个数x有没有在Buf中，若在，返回其位置；若不在，则返回-1-*/int IsInBuf(int buf,int x)int i,j=-1;for(i=0;i<B;i+)if(bufi=x)/*当x在buf中，返回其位置*/j=i;break;else if(bufi=-1)/*当x不在buf中，且bufi为空，则把x填入buf，并返回其位置*/bufi=x;j=i;break;return j;/*-函数名：main功能：、随机产生list中的数字、页面中断次数的打印、退出程序-*/main()int listN;int bufB,i,fN,j;int o

6、ld=0;int change=0;/*生成随机数，并且初始化*/srand(int)time(NULL);for(i=0;i<B;i+)bufi=fi=-1;printf("n*");printf("nThe Random List:");for(i=0;i<N;i+)listi=(int) rand()%10;printf("%2d",listi);printf("n*");/*显示淘汰页面的序列*/printf("nn");printf("nthe lost in FIFO:");change=0;/*中断的次数*/for(i=0;i<N;i+)j=IsInBuf(buf,listi);if(j=-1)/*若中没有则直接插入*/printf(" %2d",bufold);bufold=listi;old=(old+1)%(int)B;/*数据在中的储存是循环的*/change+;elseprintf(&qu