1、操作系统实验二实验二 存储管理1、实验目的通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。2、实验内容实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1) 最佳置换算法（Optimal）2) 先进先出法（Fisrt In First Out）3) 最近最久未使用（Least Recently Used）4) 最不经常使用法（Least Frequently Used）5) 最近未使用
2、法（No Used Recently）其中，命中率页面失效次数页地址流长度。试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比较。3、实验分析对于伙伴算法，用随机函数仿真进程进行内存申请，并且以较为随机的次序进行释放。对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。对于虚拟存储区和内存工作区的不同算法，其中主要的流程：首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。实验可先从一个具体的例子出发。1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述
3、原则生成：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 条
4、-第 9 条指令为第0页（对应虚存地址为0，9）第10条-第19条指令为第1页（对应虚存地址为10，19）第310条-第319条指令为第31页（对应虚存地址为310，319）按以上方式，用户指令可组成32页。4、实验代码1、内存分配与释放：#include#include#include#defineMEMORY2048intavailable100,avaiNum=0,avaiMemory=MEMORY;intfragment100,fragNum=0;typedefstructMemoryTreestructMemoryTree*left;structMemoryTree*right;st
5、ructMemoryTree*father;inttab;intthisMemory;intused;TreeNode,*Mtree;intAlloMemory(inttoBeAllo,Mtreeroot)if(toBeAlloavaiMemory)return0;elseif(toBeAlloroot-thisMemory)return-1;elseif(toBeAlloroot-thisMemory/2)if(root-left=NULL)&(root-tab=0)root-tab=1;root-used=toBeAllo;return1;elsereturn-1;elseif(root-
6、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-t
7、hisMemory/2;root-right-used=0;root-right-left=NULL;root-right-right=NULL;root-right-father=root;if(AlloMemory(toBeAllo,root-left)!=1)returnAlloMemory(toBeAllo,root-right);elsereturn1;voidReleaseMemory(inttoBeRele,Mtreeroot)Mtreetemp;if(root!=NULL)ReleaseMemory(toBeRele,root-left);ReleaseMemory(toBeR
8、ele,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;elseif(root-tab=1)&(root-used=toBeRele)root-used=0;root-tab=0;if(root-fat
9、her-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;voidDelete(inta,intnum)inti=num;while(ai!=0)ai=ai+1;i+;voidScanMemory(Mtreeroot)if(root-left=NULL)if(root-tab=0)availableavaiNum+=root-thisMemory;elsefr
10、agmentfragNum+=root-thisMemory-root-used;elseScanMemory(root-left);ScanMemory(root-right);intmain()inttimes,i,j,n,releNum;intallocated,released;intlabel;/表明分配后的结果inthaveAllo256;Mtreeinit=NULL;printf(Thesizeofmemoryis:%d.nPleaseinputthetimesyouwillallocatethememory:,MEMORY);scanf(%d,);n=times;releNum
11、=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;itimes;i+)allocated=rand()%600;printf(Thesizeofmemorytobeallocated:%dn,allocated);label=AlloMemory(allocated,init);ScanMemory(init);avaiMemory
12、=avaiMemory-allocated;fragmentfragNum=0;availableavaiNum=0;if(label=1)haveAlloreleNum+=allocated;printf(Allocationsucceed!n);j=0;if(available0=0)printf(Thereisnoavailablememory.);elseprintf(Now,thememoryavailableare:n)while(availablej!=0)printf(%d,availablej+);avaiNum=0;printf(n);j=0;if(fragment0=0)
13、printf(Thereisnofragment);elseprintf(Theframgmentare:n);while(fragmentj!=0)printf(%d,fragmentj+);printf(n);fragNum=0;elseif(label=0)n-;printf(Allocationfailed!Shortofmemory!n);elsen-;printf(Allocationfailed!Toomanyfragment!n);haveAlloi=0;printf(nnnNow,release!n);times=n;for(i=0;itimes;i+)releNum=ran
14、d()%n;n-;released=haveAlloreleNum;Delete(haveAllo,releNum);ReleaseMemory(released,init);ScanMemory(init);avaiMemory=avaiMemory+released;fragmentfragNum=0;availableavaiNum=0;printf(Thememorytobereleasedis:%dnReleasionsucceed!n,released);j=0;if(available0=0)printf(Thereisnoavailablememory.);elseprintf
15、(Now,thememoryavailableare:n);while(availablej!=0)printf(%d,availablej+);avaiNum=0;printf(n);j=0;if(fragment0=0)printf(Thereisnofragment);elseprintf(Theframgmentare:n);while(fragmentj!=0)printf(%d,fragmentj+);printf(n);fragNum=0;system(pause);2、页面置换算法：#include#include#include#defineADDRESS320#define
16、PAGENUM32#defineFRAMENUM10#defineMAXADDRESS*2intaddrADDRESS,pagePAGENUM;voidinit_addr(void)inti=0,x,m1,m2;srand(time(NULL);while(iADDRESS)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;elsea
17、ddri+=m2+1;voidinit_page(void)inti;for(i=0;iPAGENUM;i+)pagei=-1;intisIn(inta)/判断地址为a的指令是否在页中intifor(i=0;iPAGENUM;i+)if(pagei=a/FRAMENUM)returni;return-1;intfind_max(intnum,intdata)/找出data序列中第一个最大值的序号inti,temp,max=-1;for(i=0;inum;i+)if(maxdatai)max=datai;temp=i;returntemp;intfind_min(intnum,intdata)/
18、找出data序列中第一个最小值的序号inti,temp,min=MAX;for(i=0;idatai)min=datai;temp=i;returntemp;floatoptimal(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 / FR
19、AMENUM;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
20、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
21、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
22、 / 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_fa
23、ult+;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、测试结果
