《操作系统》实验二(可打印修改).pdf

实验二实验二 存储管理存储管理1、实验目的、实验目的通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。2、实验内容、实验内容实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1)最佳置换算法（Optimal）2)先进先出法（Fisrt In First Out）3)最近最久未使用（Least Recently Used）4)最不经常使用法（Least Frequently Used）5)最近未使用法（No Used Recently）其中，命中率页面失效次数页地址流长度。试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比较。3、实验分析、实验分析对于伙伴算法对于伙伴算法，用随机函数仿真进程进行内存申请，并且以较为随机的次序进行释放。对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。对于虚拟存储区和内存工作区的不同算法对于虚拟存储区和内存工作区的不同算法，其中主要的流程：首先用 srand()和 rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。实验可先从一个具体的例子出发。1）通过随机数产生一个指令序列，共 320 条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的B：25%的指令是均匀分布在前地址部分C：25%的指令是均匀分布在后地址部分具体的实施方法是：A：在0，319的指令地址之间随机选取一起点 mB：顺序执行一条指令，即执行地址为 m+1 的指令C：在前地址0,m+1中随机选取一条指令并执行，该指令的地址为 mD：顺序执行一条指令，其地址为 m+1E：在后地址m+2，319中随机选取一条指令并执行F：重复步骤 A-E，直到 320 次指令2）将指令序列变换为页地址流设：页面大小为 1K；用户内存容量 4 页到 32 页；用户虚存容量为 32K。在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为：第 0 条-第 9 条指令为第 0 页（对应虚存地址为0，9）第 10 条-第 19 条指令为第 1 页（对应虚存地址为10，19）第 310 条-第 319 条指令为第 31 页（对应虚存地址为310，319）按以上方式，用户指令可组成 32 页。4、实验代码、实验代码1、内存分配与释放：#include#include#include#define MEMORY 2048int available100,avaiNum=0,avaiMemory=MEMORY;int fragment100,fragNum=0;typedef struct MemoryTreestruct MemoryTree*left;struct MemoryTree*right;struct MemoryTree*father;int tab;int thisMemory;int used;TreeNode,*Mtree;int AlloMemory(int toBeAllo,Mtree root)if(toBeAllo avaiMemory)return 0;else if(toBeAllo root-thisMemory)return-1;else if(toBeAllo root-thisMemory/2)if(root-left=NULL)&(root-tab=0)root-tab=1;root-used=toBeAllo;return 1;elsereturn-1;else if(root-tab=1)return-1;elseif(root-left=NULL)root-left=(Mtree)malloc(sizeof(TreeNode);root-left-tab=0;root-left-thisMemory=root-thisMemory/2;root-left-used=0;root-left-left=NULL;root-left-right=NULL;root-left-father=root;root-right=(Mtree)malloc(sizeof(TreeNode);root-right-tab=0;root-right-thisMemory=root-thisMemory/2;root-right-used=0;root-right-left=NULL;root-right-right=NULL;root-right-father=root;if(AlloMemory(toBeAllo,root-left)!=1)return AlloMemory(toBeAllo,root-right);elsereturn 1;void ReleaseMemory(int toBeRele,Mtree root)Mtree temp;if(root!=NULL)ReleaseMemory(toBeRele,root-left);ReleaseMemory(toBeRele,root-right);if(root-left=NULL)if(root-tab=0)&(root-father!=NULL)if(root-father-left-tab=0)&(root-father-right-tab=0)&(root-father-left-left=NULL)&(root-father-right-left=NULL)temp=root-father;temp-left=NULL;temp-right=NULL;else if(root-tab=1)&(root-used=toBeRele)root-used=0;root-tab=0;if(root-father-left-tab=0)&(root-father-right-tab=0)&(root-father-left-left=NULL)&(root-father-right-left=NULL)temp=root-father;temp-left=NULL;temp-right=NULL;void Delete(int a,int num)int i=num;while(ai!=0)ai=ai+1;i+;void ScanMemory(Mtree root)if(root-left=NULL)if(root-tab=0)availableavaiNum+=root-thisMemory;elsefragmentfragNum+=root-thisMemory-root-used;elseScanMemory(root-left);ScanMemory(root-right);int main()int times,i,j,n,releNum;int allocated,released;int label;/表明分配后的结果int haveAllo256;Mtree init=NULL;printf(The size of memory is:%d.nPlease input the times you will allocate the memory:,MEMORY);scanf(%d,);n=times;releNum=0;init=(Mtree)malloc(sizeof(TreeNode);init-tab=0;init-thisMemory=MEMORY;init-used=0;init-left=NULL;init-right=NULL;init-father=NULL;srand(time(NULL);for(i=0;i times;i+)allocated=rand()%600;printf(The size of memory to be allocated:%dn,allocated);label=AlloMemory(allocated,init);ScanMemory(init);avaiMemory=avaiMemory-allocated;fragmentfragNum=0;availableavaiNum=0;if(label=1)haveAlloreleNum+=allocated;printf(Allocation succeed!n);j=0;if(available0=0)printf(There is no available memory.);elseprintf(Now,the memory available are:n)while(availablej!=0)printf(%d,availablej+);avaiNum=0;printf(n);j=0;if(fragment0=0)printf(There is no fragment);elseprintf(The framgment are:n);while(fragmentj!=0)printf(%d,fragmentj+);printf(n);fragNum=0;else if(label=0)n-;printf(Allocation failed!Short of memory!n);elsen-;printf(Allocation failed!Too many fragment!n);haveAlloi=0;printf(nnnNow,release!n);times=n;for(i=0;i times;i+)releNum=rand()%n;n-;released=haveAlloreleNum;Delete(haveAllo,releNum);ReleaseMemory(released,init);ScanMemory(init);avaiMemory=avaiMemory+released;fragmentfragNum=0;availableavaiNum=0;printf(The memory to be released is:%dnReleasion succeed!n,released);j=0;if(available0=0)printf(There is no available memory.);elseprintf(Now,the memory available are:n);while(availablej!=0)printf(%d,availablej+);avaiNum=0;printf(n);j=0;if(fragment0=0)printf(There is no fragment);elseprintf(The framgment are:n);while(fragmentj!=0)printf(%d,fragmentj+);printf(n);fragNum=0;system(pause);2、页面置换算法：#include#include#include#define ADDRESS 320#define PAGENUM 32#define FRAMENUM 10#define MAX ADDRESS*2int addrADDRESS,pagePAGENUM;void init_addr(void)int i=0,x,m1,m2;srand(time(NULL);while(i ADDRESS)x=rand()%ADDRESS;if(x=ADDRESS-1)addri+=x;elseaddri+=x+1;m1=rand()%(x+1);addri+=m1;addri+=m1+1;m2=(rand()%(ADDRESS-(m1+2)-1)+(m1+2);if(m2=ADDRESS-1)addri+=m2;elseaddri+=m2+1;void init_page(void)int i;for(i=0;i PAGENUM;i+)pagei=-1;int isIn(int a)/判断地址为 a 的指令是否在页中int ifor(i=0;i PAGENUM;i+)if(pagei=a/FRAMENUM)return i;return-1;int find_max(int num,int data)/找出 data 序列中第一个最大值的序号int i,temp,max=-1;for(i=0;i num;i+)if(max datai)max=datai;temp=i;return temp;int find_min(int num,int data)/找出 data 序列中第一个最小值的序号int i,temp,min=MAX;for(i=0;i datai)min=datai;temp=i;return temp;float optimal(void)int page_fault=0;int i,t,j,bad;int tempPAGENUM;for(i=0;i PAGENUM;i+)tempi=MAX;/初始化距离所有页面最大for(i=0;i ADDRESS;i+)t=isIn(addri);if(t=-1)bad=find_max(PAGENUM,temp);pagebad=addri/FRAMENUM;for(j=0;j PAGENUM;j+)if(tempj MAX)tempj-;for(j=i+1;j ADDRESS;j+)if(addrj/FRAMENUM)=pagebad)tempbad=j-i;break;tempbad=MAX;page_fault+;elsefor(j=0;j PAGENUif(tempj MAX)tempj-;for(j=i+1;j ADDRESS;j+)if(addrj/FRAMENUM)=paget)tempt=j-i;break;tempt=MAX;return 1-(float)(page_fault)/ADDRESS;float FIFO(void)int i,count=0,page_fault=0;for(i=0;i ADDRESS;i+)if(isIn(addri)=-1)pagecount=addri/FRAMENUM;count=(count+1)%PAGENUM;page_fault+;return 1-(float)(page_fault)/ADDRESSfloat LRU(void)int too_long=0,i,page_fault=0,t,j;int tempPAGENUM;for(i=0;i PAGENUM;i+)tempi=0;for(i=0;i ADDRESS;i+)t=isIn(addri);if(t=-1)too_long=find_max(PAGENUM,temp);pagetoo_long=addri/FRAMENUM;for(j=0;j PAGENUM;j+)tempj+;temptoo_long=0;page_fault+;elsefor(j=0;j PAGENUM;j+)tempj+;tempt=0;return 1-(float)page_fault/ADDRESS;float LFU(void)int temp1ADDRESS/FRAMENUM=0,temp2PAGENUM=0;int i,t,bad,page_fault=0;for(i=0;i ADDRESS;i+)temp1addri/FRAMENUM+;for(i=0;i ADDRESS;i+)t=isIn(addri);if(t=-1)bad=find_min(PAGENUM,temp2);pagebad=addri/FRAMENUM;temp2bad=temp1addri/FRAMENUM;page_fault+;return 1.0-(float)(page_fault)/ADDRESS;int main()float optimal_fault,FIFO_fault,LRU_fault,LFU_fault;init_addr();init_page();optimal_fault=optimal();init_page();FIFO_fault=FIFO();init_page();LRU_fault=LRU();init_page();LFU_fault=LFU();printf(The page is%d.nThe optimal_fault is%.2f.nThe FIFO_fault is%.2f.nThe LRU_fault is%.2f.nThe LFU_fault is%.2f.n,PAGENUM,optimal_fault,FIFO_fault,LRU_fault,LFU_fault);system(pause);return 0;5、测试结果、测试结果