1. 课程设计题目与内容

  1. 题目：采用五个算法，各自作业在1024kB空间上分配情况。
  1. 内存可变分区分配仿真算法：首次适应，下次适应，最佳适应，最坏适应和快速分配。

使用的结构体数组表示起始地址，内存块大小，内存块状态（0空闲，1占用）

#include #include#include#include#define L 10//宏定义，即把N的值定义为10struct Info{int startadress;int size;int state;};typedef struct Lnode{//定义了一个Lnode结构体，其中包括起始地址，大小，状态;iint startaddress;//起始地址int size;//内存块大小int state;//内存块状态}LNode;// typedef把struct Lnode这个结构体类型名字重新定义为LnodeLNode P[L]={{0,100,0},{100,200,0},{300,300,0},{600,400,0}};//LNode K[L]={{0,100,0},{100,200,0},{300,300,0},{600,400,0}};//定义两个是为了最坏适应算法 int N=4;//定义N的起始值为4

void bubbleprint(struct Info info[])函数是为了内存块大小从小到大排序，就可以用循环的方法更好地查找到作业所需要的内存大小。也为了输出屏幕看到的内存数列有序。

void print()函数就是打印当前内存分配情况。

void bubbleprint(struct Info info[]) //内存从小到大排序，就可以用循环的方法{int i,s;Info a[1];for(i=0;i<21;i++){for(s=0;sinfo[s+1].startadress&&s<20) {a[0]=info[s];info[s]=info[s+1];info[s+1]=a[0];}}}printf("Startaddress\tsize\tstate\n");for(i=0;i<21;i++){if(info[i].size!=0){printf("%3d\t%8d\t%4d\n",info[i].startadress,info[i].size,info[i].state);}}}void print(){//定义一个print()函数，打印空间状态 int i ,size;LNode j[10];int s=0;for(i=0;i<N;i++){for(s=0;sP[s+1].startaddress&&s<N-1) {j[0]=P[s];P[s]=P[s+1];P[s+1]=j[0];}}}for(i=0;i0;size=size-100){if( P[i].state == 1){x+=1;printf("\t1111111111\t已占用\n");}elseprintf("\t~~~~~~~~~~\n");}}printf("Startaddress\tsize\tstate\n");//在屏幕上打印Startaddress size state并换行for(i=0;i<N;i++)//用for循环，显示内存块的分配状况{printf("%3d\t%8d\t%4d\n",P[i].startaddress,P[i].size,P[i].state);}}

  1. 算法原理

  1. 首次适应分配算法

最先适应(first fit)分配算法。该算法顺序查找未分配区表或链表，直至找到第一个能满足长度要求的空闲区为止，分割此分区，一部分分配给作业，另一部分仍为空闲区(若有)。采用这一分配算法时，未分配区表或链表中的空闲区通常按地址从小到大排列。这样，为进程分配内存空间时从低地址部分的空闲区开始查找，可使高地址部分尽可能少用，以保持一个大空闲区，有利于大作业装入；但这样做会使内存低地址和高地址两端的分区利用不均衡，也将给回收分区带来麻烦，需要搜索未分配区表或链表来确定它在表格或链表中的位置且要移动相应登记项。

优点：优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。

缺点：低址部分不断被划分，会留下许多难以利用的，很小的空闲分区，称为碎片。而每次查找又都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销。

以下是首次适应算法函数：

void First(){//定义一个FirstO函数{int i,l=0,m;//li用于循环内存块的块数;1为标识符，用于显示分配成功; m为要分配的内存大小printf("Please input the memory size:");scanf("%d",&m);//输入要分配的内存大小for(i=0;i<N;i++)//用循环依次寻找内存块的大小是否满足输入要分配的内存大小{/遍历是否满足内存块的大小大于所输入的要分配的内存大小{if(P[i].size<m) continue;//如果小于的话，跳到下一次的循环;直到找到大于等于为止，不然就退出该循环else if (P[i].size==m&&P[i].state!=1){//如果内存块的大小等于所输入要分配的内存大小，则将P[i].state=1;//该块的内存块的状态修改为1;l=1;break;//退出循环，直接跳到if (1==1||im&&P[i].state!=1) //如果该内存块的大小大于所输入要分配的内存大小{P[N].startaddress=P[i].startaddress+m;//该内存块的起始地址与要输入的分配的内存块天小之和的值赋予N块的起始地址P[N].size=P[i].size-m;//该内存块的起始地址减去要输入的分配的内存块大小所得的值赋N块的内存夫小P[i].size=m;//把所输入的分配的内存块大小的值赋给该块的内存大小P[i].state=1;//该块的内存块状态设置为1l=1;//l设置为1N++;//将N个地址块变为N+1个地址块的块号break;//退出循环，直接跳到if (1==1||i<N）处}}if(l==1||i<N)//如果 {printf("Address allocate successful\n\n");printf("state!!!!!!!!!!\n");print(); }else printf("No used memory space!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");}
  1. 下次适应分配算法

下次适应(next fit)分配算法。该算法总是从未分配区的上次扫描结束处顺序查找未分配区表或链表，直至找到第一个能满足长度要求的空闲区为止，分割这个未分配区，一部分分配给作业，另一部分仍为空闲区(若有)。这一算法是最先适应分配算法的变种，能够缩短平均查找时间，且存储空间利用率更加均衡，不会导致小空闲区集中于内存一端。

特点：能使内存中的空闲区分布得较均匀。

以下是下次适应分配算法函数：

void Next(){int i=0,t=0,l=0,m,s,n;LNode j[10],Max[1]={0,0,0};printf("\n Plase input the size\n");scanf("%d",&n);m=n;for(i=0;i<N;i++)//找出最大的内存的容量 {if(Max[0].size<K[i].size)Max[0].size=K[i].size;}for(i=0;i<N;i++){if(K[i].sizem){for(int x=i;xm&&K[i].state!=1){K[N].startaddress=K[i].startaddress+m;//该内存块的起始地址与要输入的分配的内存块天小之和的值赋予N块的起始地址K[N].size=K[i].size-m;//该内存块的起始地址减去要输入的分配的内存块大小所得的值赋N块的内存夫小K[N].state=0;K[i].size=m;//把所输入的分配的内存块大小的值赋给该块的内存大小K[i].state=1;//该块的内存块状态设置为1l=1;//l设置为1N++;//将N个地址块变为N+1个地址块的块号for(int min=N-1;min>i+1;min--){j[0]=K[min];K[min]=K[min-1];K[min-1]=j[0]; }break;}}if(l==1||i<N)//如果 {printf("Address allocate successful\n\n");printf("state!!!!!!!!!!\n");}else printf("No used memory space!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");memcpy(P,K,sizeof(K));}
  1. 最优适应分配算法

最优适应(best fit)分配算法。该算法扫描整个未分配区表或链表，从空闲区中挑选一个能满足用户进程要求的最小分区进行分配。此算法保证不会分割一个更大的区域，使得装入大作业的要求容易得到满足，同时，通常把空闲区按长度递增顺序排列，查找时总是从最小一个空闲区开始，直至找到满足要求的分区为止，这时最优适应分配算法等同于最先适应分配算法。此算法的内存利用率好，所找出的分区如果正好满足要求则是最合适的；如果比所要求的分区略大则分割后会使剩下的空闲区很小，难以利用，其查找时间也是最长的。

优点：每次分配给文件的都是最合适该文件大小的分区。

缺点：内存中留下许多难以利用的小的空闲区（外碎片）

以下是最优适应算法函数：

void Best(){int i,t=0,l=0,m,s;LNode j[10],a[10];printf("\n Plase input the size\n");scanf("%d",&m);for(i=0;i<N;i++){j[i]=P[i];}for(i=0;i<N;i++){for(s=0;sj[s+1].size&&s<N-1) {a[0]=j[s];j[s]=j[s+1];j[s+1]=a[0];}}}for(i=0;i<N;i++){if(j[i].size=m&&j[i].state!=1){j[i].state=1;for(int p=0;pm){P[N].startaddress=j[i].startaddress+m;//该内存块的起始地址与要输入的分配的内存块天小之和的值赋予N块的起始地址P[N].size=j[i].size-m;//该内存块的起始地址减去要输入的分配的内存块大小所得的值赋N块的内存夫小j[i].size=m;//把所输入的分配的内存块大小的值赋给该块的内存大小for(int p=0;p<N;p++){if(P[p].startaddress==j[i].startaddress)P[p].size=m;}l=1;//l设置为1N++;//将N个地址块变为N+1个地址块的块号}l=1;break;} }if(l==1||i<N) {printf("Address allocate successful\n\n");printf("state!!!!!!!!!!\n");}else printf("No used memory space!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");}
  1. 最坏适应分配算法

最坏适应(worst fit)分配算法。该算法扫描整个未分配区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是使剩下的空闲区不致过小，对中小型作业有利。采用此分配算法可把空闲区按长度递减顺序排列，查找时只需看第一个分区能否满足进程要求，这样使最坏适应分配算法的查找效率很高，此时，最坏适应分配算法等同于最先适应分配算法。

特点：尽可能的分配大的分区。

缺点：使得内存缺乏大分区，可能使得后续到来的大作业无法装入内存。

以下是最坏适应算法函数：

void Worst(){int i,t=0,l=0,m,s;LNode j[10],a[10];printf("\n Plase input the size\n");scanf("%d",&m);for(i=0;i<N;i++){j[i]=P[i];}for(i=0;i<N;i++){for(s=0;s<N-i;s++){if(j[s].size<j[s+1].size&&s<N-1) {a[0]=j[s];j[s]=j[s+1];j[s+1]=a[0];}}}for(i=0;i<N;i++){if(j[i].size=m&&j[i].state!=1){j[i].state=1;for(int p=0;pm){P[N].startaddress=j[i].startaddress+m;//该内存块的起始地址与要输入的分配的内存块天小之和的值赋予N块的起始地址P[N].size=j[i].size-m;//该内存块的起始地址减去要输入的分配的内存块大小所得的值赋N块的内存夫小j[i].size=m;//把所输入的分配的内存块大小的值赋给该块的内存大小for(int p=0;p<N;p++){if(P[p].startaddress==j[i].startaddress)P[p].size=m;}l=1;//l设置为1N++;//将N个地址块变为N+1个地址块的块号}l=1;break;} }if(l==1||i<N) {printf("Address allocate successful\n\n");printf("state!!!!!!!!!!\n");}else printf("No used memory space!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");}
  1. 快速适应分配算法

快速适应(quick fit)分配算法。该算法为那些经常用到的长度的空闲区设立单独的空闲区链表。例如，有一个n项的表，此表第一项是指向长度为2KB的空闲区链表表头的指针，第二项是指向长度为4KB的空闲区链表表头的指针，第三项是指向长度为8KB的空闲区链表表头的指针，依此类推。像9KB这样的空闲区既可放在8KB的链表中也可放在一个特殊的空闲区链表中。此算法查找十分快速，只要按进程长度直接搜索能容纳它的最小空闲区链表并取第一块分配，但归还内存空间时与相邻空闲区的合并既复杂又费时。

优点：该算法在分配时，不会对任何分区产生分割，所以能保留大的分区，也不会产生内存碎片。

缺点：在分区归还主存时算法复杂，系统开销较大。在分配空闲分区时是以进程为单位，一个分区只属于一个进程，存在一定的浪费。空间换时间。

以下是快速适应分配算法的初始化函数，本函数是1024kb内存初始化，因为快速适应算法类似于二分法，剩余内存取决于第一个作业的大小且都是2的幂（1，2，4，8，16…..）。

void init(struct Info info[] , int num)//本函数是1024kb内存初始化，因为快速适应算法类似于二分法。 {int i,j;for(i=0; i<11; i++){if(pow(2,9)<=num && num<pow(2,10)){info[i].size = 1024;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 1024 - num;info[i+1] .startadress = info[i].size;info[i+1].state = 0;i=1;break;}if(pow(2,8)<=num && num<pow(2,9))//300{info[i].size = 512;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 512;info[i+1] .startadress = 512;info[i+1].state = 0;i=2;break;}if(pow(2,7)<=num && num<pow(2,8)){info[i].size = 256;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 256;info[i+1] .startadress = 256;info[i+1].state = 0;info[i+2].size = 512;info[i+2] .startadress =512;info[i+2].state = 0;i=3;break;}if(pow(2,6)<=num && num<pow(2,7)){info[i].size = 128;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 128;info[i+1] .startadress = 128;info[i+1].state = 0;info[i+2].size = 256;info[i+2] .startadress = 256;info[i+2].state = 0;info[i+3].size = 512;info[i+3] .startadress = 512;info[i+3].state = 0;i=4;break;}if(pow(2,5)<=num && num<pow(2,6)){info[i].size = 64;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 64;info[i+1] .startadress = 64;info[i+1].state = 0;info[i+2].size = 128;info[i+2] .startadress = 128;info[i+2].state = 0;info[i+3].size = 256;info[i+3] .startadress = 256;info[i+3].state = 0;info[i+4].size = 512;info[i+4] .startadress = 512;info[i+4].state = 0;i=5;break;}if(pow(2,4)<=num && num<pow(2,5)){info[i].size = 32;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 32;info[i+1] .startadress = 32;info[i+1].state = 0;info[i+2].size = 64;info[i+2] .startadress = 64;info[i+2].state = 0;info[i+3].size = 128;info[i+3] .startadress = 128;info[i+3].state = 0;info[i+4].size = 256;info[i+4] .startadress = 256;info[i+4].state = 0;info[i+5].size = 512;info[i+5] .startadress = 512;info[i+5].state = 0;i=6;break;}if(pow(2,3)<=num && num<pow(2,4)){info[i].size = 16;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 16;info[i+1] .startadress = 16;info[i+1].state = 0;info[i+2].size = 32;info[i+2] .startadress = 32;info[i+2].state = 0;info[i+3].size = 64;info[i+3] .startadress = 64;info[i+3].state = 0;info[i+4].size = 128;info[i+4] .startadress = 128;info[i+4].state = 0;info[i+5].size = 256;info[i+5] .startadress = 256;info[i+5].state = 0;info[i+6].size = 512;info[i+6] .startadress = 512;info[i+6].state = 0;i=7;break;}if(pow(2,2)<=num && num<pow(2,3)){info[i].size = 8;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 8;info[i+1] .startadress = 8;info[i+1].state = 0;info[i+2].size = 16;info[i+2] .startadress = 16;info[i+2].state = 0;info[i+3].size = 32;info[i+3] .startadress = 32;info[i+3].state = 0;info[i+4].size = 64;info[i+4] .startadress = 64;info[i+4].state = 0;info[i+5].size = 128;info[i+5] .startadress = 128;info[i+5].state = 0;info[i+6].size = 256;info[i+6] .startadress =256;info[i+6].state = 0;info[i+7].size = 512;info[i+7] .startadress = 512;info[i+7].state = 0;i=8;break;}if(2<num && num<=4){info[i].size = 4;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 4;info[i+1] .startadress = 4;info[i+1].state = 0;info[i+2].size = 8;info[i+2] .startadress = 8;info[i+2].state = 0;info[i+3].size = 16;info[i+3] .startadress = 16;info[i+3].state = 0;info[i+4].size = 32;info[i+4] .startadress = 32;info[i+4].state = 0;info[i+5].size = 64;info[i+5] .startadress = 64;info[i+5].state = 0;info[i+6].size = 128;info[i+6] .startadress = 128;info[i+6].state = 0;info[i+7].size = 256;info[i+7] .startadress = 256;info[i+7].state = 0;info[i+8].size = 512;info[i+8] .startadress = 512;info[i+8].state = 0;i=9;break;}if(num==2){info[i].size = 2;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 2;info[i+1] .startadress = 2;info[i+1].state = 0;info[i+2].size = 4;info[i+2] .startadress = 4;info[i+2].state = 0;info[i+3].size = 8;info[i+3] .startadress =8;info[i+3].state = 0;info[i+4].size = 16;info[i+4] .startadress = 16;info[i+4].state = 0;info[i+5].size = 32;info[i+5] .startadress = 32;info[i+5].state = 0;info[i+6].size = 64;info[i+6] .startadress = 64;info[i+6].state = 0;info[i+7].size = 128;info[i+7] .startadress = 128;info[i+7].state = 0;info[i+8].size = 256;info[i+8] .startadress = 256;info[i+8].state = 0;info[i+9].size = 512;info[i+9] .startadress = 512;info[i+9].state = 0;i=10;break;}if(num==1){info[i].size = 1;info[i] .startadress = 0;info[i].state = 1;info[i+1].size = 1;info[i+1] .startadress = 1;info[i+1].state = 0;info[i+2].size = 2;info[i+2] .startadress = 2;info[i+2].state = 0;info[i+3].size = 4;info[i+3] .startadress = 4;info[i+3].state = 0;info[i+4].size = 8;info[i+4] .startadress =8;info[i+4].state = 0;info[i+5].size = 16;info[i+5] .startadress = 16;info[i+5].state = 0;info[i+6].size = 32;info[i+6] .startadress = 32;info[i+6].state = 0;info[i+7].size = 64;info[i+7] .startadress = 64;info[i+7].state = 0;info[i+8].size = 128;info[i+8] .startadress = 128;info[i+8].state = 0;info[i+9].size = 256;info[i+9] .startadress = 256;info[i+9].state = 0;info[i+10].size = 512;info[i+10] .startadress = 512;info[i+10].state = 0;i=11;break;}}struct Info q[10];int s=0,size;for(int j=0;j0;size=size-100){if( info[j].state == 1){x+=1;printf("\t1111111111\t已占用\n");}elseprintf("\t~~~~~~~~~~\n");}}printf("Startaddress\tsize\tstate\n");for(int j=0;j<i;j++)//用for循环，显示内存块的分配状况{printf("%3d\t%8d\t%4d\n",info[j].startadress,info[j].size,info[j].state);}}

以下是快速适应分配算法函数：

void buddy(struct Info info[], int num){int i, j, k,n;for(i=0; i= num&&info[i].state == 0&&info[i].size/2 info[i].size){continue;}else if(info[i].size >= num&&info[i].state == 0&&info[i].size/2 >=num){for(int y=0;info[i].size/2>=num;y++){if(info[i].size/2>=num){info[i].size/=2;info[i].state=1;for(int l=0;l<21;l++){if(info[l].size==0){info[l].startadress=info[i].startadress+info[i].size;info[l].size=info[i].size;break;}}}}break;}}}

主函数代码块：

int main(){//主函数main()int k=0;//定义一个整型变量k，用于选择方法与退出printf("Please choose the method\n");while(k!=6)//当k不等于3时{printf("\n~~~~~~~~~~~~~Memorymethods~~~~~~~~~~~~~~~~");printf("\nl.First method\n2.Best method\n3.Worst method\n4.Next method\n5.Buddy method");//第一种方法是最先适应内存分配法，第二种方法是最优适应内存分配法printf("\n6.Exit\n");//3为退出程序printf("Please choose the method!");//提示输入数字选择哪种方法或退出程序scanf("%d",&k);//输入k的值switch(k){case 1:while(1){printf("\n Initialization(~~~~~~~表示内存):\n");//打印此字符串，用于提示内存初始化print();First();if(getchar()=='e'){return 0;}}break;case 2:while(1){printf("\n Initialization(~~~~~~~表示内存):\n");//打印此字符串，用于提示内存初始化print();Best();if(getchar()=='e'){return 0;}}break;case 3:while(1){printf("\n Initialization(~~~~~~~表示内存):\n");//打印此字符串，用于提示内存初始化print();Worst();if(getchar()=='e'){return 0;}}break;case 4:while(1){printf("\n Initialization(~~~~~~~表示内存):\n");//打印此字符串，用于提示内存初始化print();Next();if(getchar()=='e'){return 0;}}break;continue;case 5:{int num,x=0;struct Info info[21]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};printf("|1024|");printf("\nPlease input the size:");scanf("%d", &num);x+=num;init(info, num);while(1){printf("\nPlease input a num:");scanf("%d", &num);x+=num;fflush(stdin);if(x > 1023) {printf("The num is too big , try littler\n");break;}else buddy(info,num);bubbleprint(info);}system("pause");}case 6:break;default:printf("Choose error\n");} }}

运行结果：