操作系统实验报告6-页面置换算法模拟综述

1、课程名称实验名称实验时间指导单位指导教师学生姓名 学院（系）班级学号软件工程系专 业计算机软件与服务外包实验报告（2013 / 2014 学年第1学期）操作系统原理实验6:页面置换算法模拟2013年 12 月 10 日软件工程系杨健实验名称实验1 : Linux操作、使用、编程与进程创建指导教师杨健实验类型实验实验学时2实验时间2013.12.10一、实验目的1.通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。2 .掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想， 并至少用二种算法来模拟实现。3.通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更 换频率来

2、对比它们的效率。二、实验环境（实验设备）Win dows 2000Visual Studio三、实验内容设计 个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置 换：1. 先进先出的算法（FIFO）2. 最近最久未使用算法（LRU3. 最佳置换算法（OPT实验分析在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内 存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存 中调出 页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据 定的算法来确定，算法的好坏，直接影响到系统的性能。一个好的页面置换算法，应该有较低的页面更换频率。假设分给一作业的物理块数为3，页面数

3、为20个。页面号为（20个）:7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 11 .先进先出（FIFO）置换算法的思路该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的 页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按 照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页 面。2. 最近久未使用（LRU）置换算法的思路最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况 来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自 上次被访问以来所经历的时间，当需淘汰一个页

4、面的时候选择现有页面中 其时间值最大的进行淘汰。3. 最佳（OPT置换算法的思路其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内 不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。4. FIFO页面置换算法当需要访问一个新的页面时，首先调用fin dExist（i）函数来查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则调用display函数直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需 要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则调用fin dReplace函数替换页面。并将物理块中所有页面timer+。5. LR

5、U页面置换算法当需要访问一个新的页面，首先调用fin dExist(i)函数查看物理块中是否就有这个页面。6. OPT页面置换算法当需要访问一个新的页面，首先调用fin dExist(i)函数来查看物理块中是否有这个页面。7. 寻找置换页面函数findReplace比较三个物理块中的时间标记timer， 找到时间最久的。代码#include #include #include #define BLOCK_MAX_SIZE 20最？大洙？物？理元？块e大洙?小？en u%FIFO=1 丄 RU,OPT;struct no de_pageint address; / 指？令?地?址int page

6、_num;/ 页？面？号?int next_order; / 下?一?次?访？问。的?次？序6*page;/物？理元？块e定义？typedef struct BlockNodeint pagendex; /page数簓组哩？的？下？标括？struct BlockNode * next;BlockNode;struct int length; /当獭？前物？理元？块e长O度0int miss_flag; / 缺o?页？标括？志？, ？若?为al, ?则。缺？页？int miss_count; / 缺 0？页？次？数簓BlockNode*fro nt;BlockNode*rear;Block;?字

7、?母？大洙？写/本？程序。中全？局？变？量？名？炕口屯？两？个？单蹋？词洙？组哩？成e,？且。开埶int BlockSize = 5;/ 物？理元？块e 大洙?小？int PageCount = 200; / 页？面？总哩？数簓int PageSize = 1024;/ 页？面？大洙？小？int AddrRange = 8*1024; / 访？问 e 地址范？围int get_num( int down, int up) / 得？到?一?个?downup之?间？的？整？数簓int num;char str111;while (1)fgets(str,111* sizeof (int ),std

8、in);num=atoi(str); /把？字？符？串？中D的?数簓字？转羇换？为a整?数簓if (num=down& num next=NULL;void enqueue( int page index) / 入？队6BlockNode*node=(BlockNode*)malloc( sizeof (BlockNode);if (!node)printf(内 u 存?分?配？失骸？败悒?n);exit(O);no de-page_ in dex=page_ in dex;n ode- next=NULL;Block .len gth+;Block.rear- n ext=no de;Blo

9、ck.rear=no de;void dequeue。/ 岀？队 6BlockNode* node;no de=Block.fr ont-n ext;Block.fr ont-n ext=no de-n ext;if (node= Block.rear)Block.rear=Block.fro nt;free( no de);Block.le ngth-;void clear_block() / 清？空？物？理元？块ewhile (Block.rear=Block.front-next)Block.fr ont-n ext=Block.rear- n ext;free(Block.rear);

10、Block.le ngth_;Block.rear=Block.fro nt;Block.le ngth=0;Block.miss_cou nt=O;void destroy_block() / 销。毁d物理元？块0while (Block.rear=Block.front)Block.fr on t=Block.fro nt-n ext;free(Block.rear);free(page);void init_page() / 初？始?化-页？面？系 u 列int i,j;srand(time(NULL); /用？当獭？前系卩统？时骸？间？来厉？初?始？化-随？机。种?子哩？ page=(

11、struct node_page*) malloc(PageCount*sizeof (struct node_page);for (i=O;iPageCount;i+)pagei.address=ra nd()%AddrRa nge;pagei.page_ num=pagei.address/PageSize;for (i=O;iPageCount;i+)for (j=i+1;jPageCount;j+)if (pagei.page_num= pagej.page_num)pagei. next_order=j;break;/if/forif (j= PageCount) / 说卩明* pa

12、gei以？后o都?不?会0再d访问epagei. next_order= PageCou nt;/forvoid print_page() / 打洙？印？页?面?泵 口 列int i;prin tf( n printf(页？面?爭.叮.Ma：阰 n);for (i=0;inext)if (pagenode-page_index.page_num=pagepage_index.page_num) return ;if (Block.lengthnext)if (pagenode-page_index.page_num= pagepage_index.page_num) last_ no de-n

13、 ext=no de-n ext;Block.le ngth-;if (node= Block.rear)Block.rear=last_ no de;en queue (no de-page_ in dex);free( no de);returnlast_ node=no de;if (Block.lengthnext)if (pagenode-page_index.page_num= pagepage_index.page_num) no de-page_ in dex=page_ in dex;Block.miss_flag=0;return ; if (Block.lengthn e

14、xt;while (node=node-next) / 寻找 oBlock 中Dnext_order 值卩最？大洙？的？节。点？if (pagemax_node-page_index.next_orderpage_index.next_order)max_node=no de;no de=Block.fr ont;max_no de_last=no de;while (node=node-next) / 寻找 oBlock 中Dnext_order 值卩最？大洙？的？节。点?的?上?一?个?节。点?if (node= max_node)break;max_no de_last=no de;ma

15、x_no de_last- n ext= max_no de-n ext;Block.le ngth-;if (max_node= Block.rear)Block.rear=max_ no de_last;free(max_ no de);en queue(page in dex);Block.miss_flag=1;Block.miss_cou nt+;void page_replace( int num) int i,j;BlockNode* node;char str35= FIFO , LRU , OPT ;24printf(%s:,snrn um-1);printf（页？面？号?*

16、）;for (i=0;i BlockSize;i+)printf(“);printf(是？否?缺d?页？ *n）;)nprintf( for (i=O;inext)printf( %-2d ,pagenode-page_index.page_num);for (j=Block.length;jBlockSize;j+) printf( “)；printf( * %s *nn ,(Block.miss_flag=1 ? Yes: No);printf(printf( 缺 a ? 页 ？ 数 簓 :%d, 缺 a ? 页 %.2fnn ,Block.miss_count,( float )Bloc

17、k.miss_count/PageCount *100);printf（按恪？回？车卩键u继绩!nn）;getchar();void confige() / 程序。设置?int num;while (1)printf(*n);printf( * 程序6设已置？ *n);printf(H*n);printf（ * 1,设E?置？物？理元？块e大洙?小?（默？认?5） *n）;printf（ * 2,设?置?访?问0 地?址范？围 （默？认?8K） *n）;printf（ * 3,设E ?置？页？面?大洙？小？（默？认？1K） *n）;printf（ * 4,设E ?置？页？面？总哩？数簓（默?认

18、?200） *n）;printf（ * 5,显？示？各+项？设E ?置?值卩*n）;printf（ * 6,返刁？回？ *n）;printf(*nprintf(请?输?入?您。的?选?择?:）;n um=get_ num(1,6);if (num=6)break;if (num=1)printf(请?输?入?物？理元？块e 大洙?小？(1%d): ,BLOCK_MAX_SIZE);BlockSize=get_ num(1,BL0CK_MAX_SIZE);printf(设E?置?成e功!nn);/ifelse if (num=2)printf(请?输?入?访？问 e 地址范？围 (1%d)K:

19、,999);AddrRa nge=get_ num(1,999)* 1024;printf(设E?置?成e功!nn);/elseifelse if (num=3)printf(请？输?入?页?面?大洙?小?(1%d)K: ,AddrRange/1024);PageSize=get_ num(1,AddrRa nge/1024)* 1024;printf(设E?置?成e功!nn);/elseifelse if (num=4)printf(请?输?入?页?面?总哩？数簓(1%d): ,32767);PageCou nt=get_ num(1,32767);printf(设E?置?成e功!nn);/

20、elseifelse if (num=5)printf( n);printf( * 当獭？前 物？理元？块 e 大洙?小?:%dn ,BlockSize);printf( * 当獭？前 访？问 0地?址范？围 :%d Kn ,AddrRange/1024);printf( * 当獭？前页？面？大洙？小?:%d Kn ,PageSize/1024);printf( * 当獭？前页？面？总哩？数簓dn,PageCount);printf( n);free(page);in it_page();void begin()int num;prin t_page();while (1)printf(*n）

21、；printf（ *页？面？置？换？算？法厉?*n）;printf(H*n）；printf（ * 1,先 0 进?先 e 出?置?换？算？法鬲?FIFO） *n）;printf（ * 2,最？近u最?久?未使？用?置 ?换？算？法厉？LRU） *n）;printf( * 3,最？佳?置?换?算?法厉?OPT) *n);printf( * 4,返刁？回？ *n);printf(H*n);printf（请？输?入?您。的?选?择?:）;n um=get_ num(1,4);if (num= 4)break;page_replace( num); clear_block();free(page);i

22、n it_page();int main()int num;in it_block();in it_page();while (1) n um=get_ num(1,3);printf(、n*n)；printf(*存？储洹？器+管u理元？模拟a系卩统？ *n);printf(*n)；printf(* 1,进？入？页？面?置?换?算?法厉?*n);printf(* 2,进？入？程序6设已置？ *n);printf(* 3,退？岀？ *n);printf(*n)；printf(请?输？入？您。的?选?择?:);if (num= 3) break;if (num= 1) begi n();else

23、if (num = 2) con fige();destroy_block();return 0;截图T4 ,748 (b .515 H2 ,443 Hl ,492 1? ,?80】【5,706 .3031,1966 ,35514,505H2 ,302117,133? ,714 6 ,795 3 ,544 112 ,741Hl ,381(2 .650 Hl .1002111 ,550 1 5 ,26 JH0 ,649 1C? .775 7 .715 JL5 ,923 1【3 ,10051C4 ,222 1(2 ,627 H7 ,654 H2 ,246 .20H2 ,591 H4 ,114 【0

24、 ,289H2 ,934 HSJEB ,1210 ,667 0 ,552 H3 ,163 E4 ,10190 ,780 J6 ,575 JL3 ,104 5 ,549 Hl .S81 ? .?27 H4 ,903 3 ,110 H6 ,906L5 ,258 0 ,293 【5 ,568 0 ,9512 a016H3 .10201E3 ,674 3 ,9277 ,549 H2 ,892 2 ,852 ? ,1030 ,116 H0 A006H5 ,851 ? ,536页面置换算法* 先进先出置題算& -* 2曇近量久未濾用亶硕算法RIO義*苑慧佳畫换畀法 * 4,返回*请输入您的选择；1 m7421*MoGM?421GMWes *9421&0*Ves 00421&0*No 7*21&07*Ves *G*21076*No *2 *10762*Mo*71