《存储器管理试验共14资料.docx》由会员分享，可在线阅读，更多相关《存储器管理试验共14资料.docx（13页珍藏版）》请在三一文库上搜索。
1、实验七 存储器管理实验1实验目的：理解操作系统虚拟存储管理的原理，理解程序执行局部性的概念。2实验内容：设计一个虚拟存储区和内存工作区 , 并使用下列算法计算访问命中率。（1） 进先出的算法（ FIFO）（2） 最近最少使用的算法（ LRU）（3） 最佳淘汰算法 （OPT）命中率=（1-页面失效次数 ）/ 页地址流长度实验要求1、理解 FIFO,LRU 算法原理，理解参考程序的原理和实现思路。2、完成程序的设计，重点完成 FIFO,LRU 算法3、分析运算结果，在分配不同的物理块情况下，各算法的缺页情况有什么规律？3. 实验指导FIFO （先进先出）页面置换算法原理阐述这是最早出现的置换算法。
2、该算法总是淘汰最先进入内存的页面， 即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一 个进程已调入内存的页面， 按先后次序链接成一个队列， 并设置一个指针， 称为替换指针，使它总是指向最老的页面。第 1 页（1）在分配内存页面数（AP）小于进程页面数（PP）时，当然是最先的AP个页面放入内存；（2） 这时有需要处理新的页面，则将原理在内存中的AP个页面中最先进入的调出（是以称为 FIFO），然后放入新页面；（3）以后如果有新页面需要调入，按（2）之规则进行。算法特点：所使用的内存页面构成一个队列图标描述假设某个进程在硬盘上被化为5个页面（PP=5，以1、2、3、4、5分别表示，
3、而下面是处理机调用它们的顺序（这取决于进程本身）：1、4、2、5、3、3、2、4、2、5而内存可以控制的页面数为 3 （AP= 3），那么在使用FIFO算法时，这3个页面的内存使用情况应该是这样的：队列第1位1425333425队列第2位142555342队列第3位14222534不难看出本例共换入页面8次，diseffect=8算法设计void FIFO(i nt total_pf) int i,j; pp_type *p,*t;initialize(total_pf);busy_pp_head=busy_pp_tail=NULL;for(i=0;i<NUMBER_OF_INSTRUC
4、TION;i+)if(vp_arraypage_of_instructioni.no_of_pp=INVALID)counter_page_default+=1;if(free_pp_head=NULL)p=busy_pp_head->next; vp_arraybusy_pp_head->no_of_vp.no_of_pp=INVALID; free_pp_head=busy_pp_head;free_pp_head->next=NULL;busy_pp_head=p;p=free_pp_head->next;free_pp_head->next=NULL;fr
5、ee_pp_head->no_of_vp=page_of_instructioni;vp_arraypage_of_instructioni.no_of_pp=free_pp_head->no_of_p p;if(busy_pp_tail=NULL)busy_pp_head=busy_pp_tail=free_pp_head;elsebusy_pp_tail->next=free_pp_head;第 3 页busy_pp_tail=free_pp_head;free_pp_head=p;printf（"FIFO 缺 页 率 ： %6.4f",（float）
6、counter_page_default/320）;return;LRU （最近最少使用）页面置换算法原理阐述在采用该算法时，应为在内存中的每个页面设置一个移位寄存器骼来 记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面为淘汰页。 在分配内存页面数（AP）小于进程页面数（PR时，当然是最先的 AP个页面放入内存； 然则当需要调页面进入内存，而当前分配的内存页面全部不空闲 时，选择其中最长时间没有用到那个页面调出，以空出内存来放置新调入 的页面（是以称为 LRU）；算法特点：每个页面都有属性表示有多长时间未被 CPU使用的信息。图表描述为了便于比较学习，例子和前面的一样。某进程在硬
7、盘上被划为 5 个页面，用 1、2、3、4、5 表示，而处理机处理它们的顺序为：1、4、2、5、3、3、2、4、2、5第 4 页而内存可以控制的页面数为 3( A9 3),那么在使用FIFO算法时，这3个页面的内存使用情况应该是这样的:最近1步使用1425332425最近2步使用142553242最近3步使用1422 /沢5334虽然页面的位置发 生改变,4-10算法设计void LRU(i nt total_pf)int mi n, minj,i,j,prese nt_time;访问时刻in itialize(total_pf);prese nt_time=0;for(i=0;i<NU
8、MBER_OF_INSTRUCTION;i+)if(vp_arraypage_of_i nstructio ni. no_of_pp=INVALID) coun ter_page_default+;if(free_pp_head=NULL) /无空闲页面mi n=M AXI;for(j=0;j<NUMBER_OF_VP;j+)if(min>vp_arrayj.time&&vp_arrayj.no_of_pp!=INVALID)min=vp_arrayj.time;minj=j;free_pp_head=&pp_controlvp_arrayminj.no_o
9、f_pp;vp_arrayminj.no_of_pp=INVALID;vp_arrayminj.time=-1;free_pp_head->next=NULL;vp_arraypage_of_instructioni.no_of_pp=free_pp_head->no_of_p p;/vp_arraypage_of_instructioni.time=present_time; free_pp_head=free_pp_head->next;elsevp_arraypage_of_instructioni.time=present_time;/使用present_time+;
10、%6.4fprintf("LRU 缺 页 率 ： ",(float)counter_page_default/320);return ;参考程序：采用C+!序实现：#include <windows.h> #include <stdio.h>#include <process.h>#define TRUE 1/指令流的指令条数#define NUMBER_OF_VP 32/进程的虚页页数/#define LINEAR_ADDRESS/有选择性的打开该宏开typedef structint no_of_vp;/虚拟页号int no_of_p
11、p;/物理页号int counter_in_period; /一周期内访问的次数int time;/访问时间vp_struct; /页面类型vp_struct vp_arrayNUMBER_OF_VP; /页面结构数组struct pp_struct/物理页面结构#define FALSE 0 #define INVALID -1 #define NULL 0 #define NUMBER_OF_INSTRUCTION 320int no_of_vp;int no_of_pp;struct pp_struct *next;typedef struct pp_struct pp_type;pp_
12、typepp_controlNUMBER_OF_VP,*free_pp_head,*busy_pp_head,*busy_pp_t ail;int counter_page_default;int address_of_instructionNUMBER_OF_INSTRUCTION;intpage_of_instructionNUMBER_OF_INSTRUCTION,offset_of_instructionNUMBER_OF_INSTRUCTION;int MAXI = 2147483647;/(1<<30)-1)*2+1;/2A31-1第 13 页2147483647voi
13、d initialize(int);void FIFO(int);/先进先出void LRU(int);/ 最近最久未 使 用页面淘汰算 法（ leastrecently used )/void OPT(int);/最佳淘汰算法int main() int S,i;srand( (int)getpid() );S=(int)rand() % 200;/#ifndef LINEAR_ADDRESSfor(i=0;i<NUMBER_OF_INSTRUCTION;i+) /* 产生指令队列*/address_of_instructioni=S;/* 任选一指令访问点 */address_of_
14、instructioni+1=address_of_instructioni+1;/* 顺序执行一条指令 */ address_of_instructioni+2=(int)rand()%200;/* 执行前地址指令 m'*/address_of_instructioni+3=address_of_instructioni+2+1; /* 执行后地址指令 */S=(int)rand()%200;/#else/ for(i=0;i<NUMBER_OF_INSTRUCTION;i+=1) /* 产生指令队 列*/ address_of_instructioni=i;/#endiffo
15、r(i=0;i<NUMBER_OF_INSTRUCTION;i+) /* 将指 令序列变换成页地址流 */page_of_instructioni=address_of_instructioni/10; offset_of_instructioni=address_of_instructioni%10;for(i=4;i<=32;i+) /* 用户内存工作 区从 4个页面到 32个页面 */printf("%2d 物理块： ",i);FIFO(i);LRU(i);/ OPT(i);printf("n");/getchar();return 0
16、;/ 先进先出淘汰算法 void FIFO(int total_pf)int i,j;pp_type *p,*t;initialize(total_pf); busy_pp_head=busy_pp_tail=NULL;for(i=0;i<NUMBER_OF_INSTRUCTION;i+)if(vp_arraypage_of_instructioni.no_of_pp=INVALID)counter_page_default+=1;if(free_pp_head=NULL) p=busy_pp_head->next;_pp=INVALID;vp_arraybusy_pp_head-
17、>no_of_vp.no_ free_pp_head=busy_pp_head; free_pp_head->next=NULL;busy_pp_head=p;p=free_pp_head->next;free_pp_head->next=NULL;free_pp_head->no_of_vp=page_of_instructioni;vp_arraypage_of_instructioni.no_of_pp=free_pp_head->no_of_p p;if(busy_pp_tail=NULL) busy_pp_head=busy_pp_tail=fre
18、e_pp_head;elsebusy_pp_tail->next=free_pp_head;busy_pp_tail=free_pp_head;free_pp_head=p;%6.4fprintf("FIFO 缺 页 率 ：",(float)counter_page_default/320);return;/ 最近最少淘汰使用算法void LRU(int total_pf)int min,minj,i,j,present_time;/ 访问时刻initialize(total_pf);present_time=0;for(i=0;i<NUMBER_OF_INST
19、RUCTION;i+)if(vp_arraypage_of_instructioni.no_of_pp=INVALID)counter_page_default+;if(free_pp_head=NULL) / 无空闲页面 min=MAXI;for(j=0;j<NUMBER_OF_VP;j+)if(min>vp_arrayj.time&&vp_arrayj.no_of_pp!=INVALID)min=vp_arrayj.time;minj=j;free_pp_head=&pp_controlvp_arrayminj.no_of_pp;vp_arrayminj
20、.no_of_pp=INVALID;vp_arrayminj.time=-1;free_pp_head->next=NULL;vp_arraypage_of_instructioni.no_of_pp=free_pp_head->no_of_p p;/vp_arraypage_of_instructioni.time=present_time;free_pp_head=free_pp_head->next;elsevp_arraypage_of_instructioni.time=present_time;/ 使用present_time+;%6.4fprintf("
21、;LRU",(float)counter_page_default/320);return ;void initialize(int total_pf)int i;counter_page_default=0; for(i=0;i<NUMBER_OF_VP;i+) vp_arrayi.no_of_vp=i; vp_arrayi.no_of_pp=INVALID; vp_arrayi.counter_in_period=0;vp_arrayi.time=-1;for(i=1;i<total_pf;i+)pp_controli-1.next=&pp_controli;
22、 / 建pp_controli-1 和 ptfi 之间的链接pp_controli-1.no_of_pp=i-1;pp_controli-1.no_of_vp = -1;pp_controltotal_pf-1.next=NULL;pp_controltotal_pf-1.no_of_pp=total_pf-1;pp_controltotal_pf-1.no_of_vp = -1;free_pp_head=&pp_control0;return;希望以上资料对你有所帮助，附励志名言 3 条：1、上帝说：你要什么便取什么，但是要付出相当的代价 2、目标的坚定是性格中最必要的力量源泉之一，也是成功的利器之一。没有它，天才会在矛盾无定的迷径中徒劳无功。3、当你无法从一楼蹦到三楼时，不要忘记走楼梯。要记住伟大的成功往往不是一蹴而就的，必须学会分解你的目标，逐步实施。