操作系统存储器管理——最佳适应算法

1、存储管理上机作业最佳适应算法以最佳适应为例，给出可变式分区的分配回收算法。源程序如下：#include<stdio.h>#define N 5struct freeareaint startaddress;int size;int state;freeblockN=20,20,1,80,30,1,160,10,1,200,40,0,250,50,1;int allocate(int applyarea)int i,tag=0;for(i=0;i<N;i+)if(freeblocki.size>applyarea&&freeblocki.state=1)f

2、reeblocki.startaddress=freeblocki.startaddress+applyarea; freeblocki.size=freeblocki.size-applyarea;tag=1;/有满足条件的分区时，tag置1return freeblocki.startaddress-applyarea;else if(freeblocki.size=applyarea&&freeblocki.state=1)freeblocki.state=0;tag=1;/有满足条件的分区时，tag置1return freeblocki.startaddress;if(

3、tag=0)return -1;void set_free()int i,j,s,l,tag1=0,tag2=0,tag3=0;printf("please input the start address you want to set free:n");scanf("%d",&s);printf("please input the size:n");scanf("%d",&l);for(i=0;i<N;i+)if(freeblocki.startaddress+freeblocki.size

4、=s&&freeblocki.state=1) /释放区与某一空闲块的高地址相邻接l=freeblocki.size+l;tag1=1;/释放区与某一空闲块的高地址相邻接for(j=0;j<N;j+) /内层循环用于检测释放区是否同时与两个空闲块相邻接if(freeblockj.startaddress=freeblocki.startaddress+l &&freeblockj.state=1)freeblockj.size=l+freeblockj.size;freeblockj.startaddress=freeblocki.startaddress

5、;freeblocki.state=0;tag2=1;/标记同时与两个空闲块相接break; if(tag2=0) freeblocki.startaddress=s; freeblocki.size=l; break; /forif(tag1=0)/不与空闲块的高地址相接for(i=0;i<N;i+)/检测是否与某空闲块的低地址相接if(s+l=freeblocki.startaddress&&freeblocki.state=1)freeblocki.startaddress=s;freeblocki.size=freeblocki.size+l;tag3=1;bre

6、ak; if(tag3=0)/不与任何空闲块相接 for(j=0;j<N;j+) if(freeblockj.state=0) freeblockj.startaddress=s; freeblockj.size=l; freeblockj.state=1; break; void adjust()int i,j;struct freearea temp;for(i=0;i<N;i+)for(j=i;j<N;j+)if(freeblocki.size>freeblockj.size)temp.size=freeblocki.size; temp.startaddress

7、=freeblocki.startaddress; temp.state=freeblocki.state; freeblocki.size=freeblockj.size; freeblocki.startaddress=freeblockj.startaddress; freeblocki.state=freeblockj.state; freeblockj.size=temp.size; freeblockj.startaddress=temp.startaddress; freeblockj.state=temp.state;for(i=0;i<N;i+)if(freeblock

8、i.state=0&&freeblocki+1.state=1)temp.size=freeblocki.size;temp.startaddress=freeblocki.startaddress;temp.state=freeblocki.state;freeblocki.size=freeblocki+1.size;freeblocki.startaddress=freeblocki+1.startaddress;freeblocki.state=freeblocki+1.state;freeblocki+1.size=temp.size;freeblocki+1.sta

9、rtaddress=temp.startaddress;freeblocki+1.state=temp.state;void print()int i;printf("%5s%15s%13s%12s","block_id","start_address","size","state");printf("n");for(i=0;i<N;i+)printf("%5d%15d%15d%10dn",i,freeblocki.startaddress,free

10、blocki.size,freeblocki.state);void main()int start;int choice;int applyarea;while(1)printf("*n");printf("1:I want to request for memory.n");printf("2:I want to set free some memory.n");printf("3:exit.n");printf("Please input your choice:n");printf(&q

11、uot;*n");scanf("%d",&choice);if(choice=1)printf("At first the free memory table is:n"); print(); printf("Please input the request memory size:n"); scanf("%d",&applyarea);adjust();start=allocate(applyarea);if(start=-1) printf("There is not eno

12、ugh memory,please wait.n"); else printf("Your request is being submitted.job size is :%dn",applyarea);printf("job is running.job's start address is:%dn",start);printf("After allocation,the memory table is:n");adjust();print(); if(choice=2)set_free();printf("After setfree,the memory table is:n");adjust();print();if(choice=3)break;进入程序主界面如下：测试用例如下：当输入选择1时，进入内存请求界面，并且显示现在的空闲块分布情况如下（state为零标记该空闲内存块不可用）：输入请求的内存空间大小（例如大小为5）：由最佳适应算法把起始地址为160，大小为5的内存分配给请求进程，分配后的内存表如上图，同时返回程序的主界面；输入选择为2时，提示输入将要释放区间的起始地址