最坏适应算法 c语言

/**------------------------------------------------------

进入程序后可以根据菜单选项进入不同的模块

1.使用首次适应算法分配空间

2.使用最佳适应算法分配空间

3.释放一块空间

4.显示内存分配情况

5.退出系统

----------------------------------------------------------**/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <conio.h>

#define MEMSIZE 100 /*定义内存大小为100*/

#define MINSIZE 2 /*如果小于此值 将不再分割内存*/

typedef struct _MemoryInfomation{/* 内存空间分区表 结构*/

int start/*起始地址*/

int size /*大小*/

char info /*状态 F:空闲(Free) U:占用(Used) E 结束(end)*/

}MEMINFO

MEMINFO MemList[MEMSIZE]//内存空间信息表

void Display()

/*--------------------------------------------------------

函数名:InitALL()

功 能:初始化所有变量

--------------------------------------------------------*/

void InitAll(){

int i

MEMINFO temp={0,0,'e'}

for(i=0i<MEMSIZEi++) //初始化空间信息表

MemList[i]=temp

MemList[0].start=0 //起始地址为0

MemList[0].size=MEMSIZE//空间初始为最大的

MemList[0].info='f'//状态为空闲

}

/*--------------------------------------------------------

函数名:FirstFit_new()

功 能:首次适应算法分配内存

--------------------------------------------------------*/

void FirstFit_new(){

int i,j,size

char temp[10]

printf("FirstFit_new:How many MEMORY requir?")

gets(temp)

size=atoi(temp)//将字符串转化为整数

for(i=0i <MEMSIZE-1 &&MemList[i].info != 'e'i++) //到了空间尾且没有空间分配

{

if(MemList[i].size >= size &&MemList[i].info=='f') //满足所需要的大小，且是空闲空间

{

if(MemList[i].size - size <= MINSIZE) //如果小于规定的最小差则将整个空间分配出去

MemList[i].info='u'//标志为使用

else

{

for(j = MEMSIZE-2j >ij--) //将i后的信息表元素后移

{

MemList[j+1]=MemList[j]

}

//将i分成两部分，使用低地址部分

MemList[i+1].start= MemList[i].start+size

MemList[i+1].size = MemList[i].size-size

MemList[i+1].info='f'

MemList[i].size=size

MemList[i].info='u'

}

break

}

}

if(i == MEMSIZE-1 || MemList[i].info=='e') //没有找到符合分配的空间

{

printf("Not Enough Memory!!\n")

getchar()

}

Display()

}

/*--------------------------------------------------------

函数名:BestFit_new()

功 能:最佳适应算法分配内存

--------------------------------------------------------*/

void BestFit_new()

{

int i,j,k,flag,size

char temp[10]

printf("BestFit_new How many MEMORY requir?")

gets(temp)

size=atoi(temp)//将字符串转化为整数

j=0

flag=0//标志是否有合适的空间分配，0无，1有

k=MEMSIZE//用来保存满足要求的最小空间

for(i=0i<MEMSIZE-1 &&MemList[i].info!='e'i++)

{

if(MemList[i].size >= size &&MemList[i].info == 'f') //符合要求

{

flag=1

if(MemList[i].size <k) //比符合要求的最小空间小，则交换

{

k=MemList[i].size

j=i

}

}

}

i=j

if(flag == 0) //没找到

{

printf("Not Enough Memory!\n")

getch()

j=i

}

else if(MemList[i].size - size <= MINSIZE) //小于规定的最小差，将整个空间分配

MemList[i].info='u'

else

{

for(j = MEMSIZE-2j >ij--) //后移

MemList[j+1]=MemList[j]

MemList[i+1].start=MemList[i].start+size

MemList[i+1].size=MemList[i].size-size

MemList[i+1].info='f'

MemList[i].size=size

MemList[i].info='u'

}

Display()

}

/*--------------------------------------------------------

最坏适应算法

*/

void BadFit_new()

{

int i,j,k,flag,size

char temp[10]

printf("BadFit_new How many MEMORY requir?")

gets(temp)

size=atoi(temp)

j=0

flag=0

k=0//保存满足要求的最大空间

for(i=0i<MEMSIZE-1&&MemList[i].info!='e'i++)

{

if(MemList[i].size>=size&&MemList[i].info=='f')

{

flag=1

if(MemList[i].size>k)

{

k=MemList[i].size

j=i

}

}

}

i=j

if(flag=0)

{

printf("Not Enough Memory!\n")

getch()

j=i

}

else if(MemList[i].size-size<=MINSIZE)

MemList[i].info='u'

else

{

for(j=MEMSIZE-2j>ij--)

MemList[j+1]=MemList[j]

MemList[i+1].start=MemList[i].start+size

MemList[i+1].size=MemList[i].size-size

MemList[i+1].info='f'

MemList[i].size=size

MemList[i].info='u'

}

Display()

}

/*--------------------------------------------------------

函数名:del()

功 能:释放一块内存

--------------------------------------------------------*/

void del()

{

int i,number

char temp[10]

printf("\nplease input the NUMBER you want stop:")

gets(temp)

number=atoi(temp)

if(MemList[number].info == 'u') //输入的空间是使用的

{

MemList[number].info = 'f'//标志为空闲

if(MemList[number+1].info == 'f') //右空间为空则合并

{

MemList[number].size+=MemList[number+1].size//大小合并

for(i=number+1i <MEMSIZE-1 &&MemList[i].info !='e'i++)/* i后的空间信息表元素前移 */

if(i>0)

MemList[i]=MemList[i+1]

}

if(number >0 &&MemList[number-1].info=='f') //左空间空闲则合并

{

MemList[number-1].size+=MemList[number].size

for(i=numberi<MEMSIZE-1&&MemList[i].info!='e'i++)

MemList[i]=MemList[i+1]

}

}

else

{

printf("Thist Number is Not exist or is Not used!\n ")

getchar()

}

Display()

}

/*--------------------------------------------------------

函数名:Display()

功 能:显示内存状态

--------------------------------------------------------*/

void Display(){

int i,

used=0//记录可以使用的总空间量

/* clrscr()*/

printf("\n----------------------------------------------\n")

printf("%5s%15s%15s","Number","start","size","Info")

printf("\n----------------------------------------------\n")

for(i=0i <MEMSIZE &&MemList[i].info != 'e'i++)

{

if(MemList[i].info == 'u')

used+=MemList[i].size

printf("%5d%15d%15d%15s\n",i,MemList[i].start,MemList[i].size,MemList[i].info=='u'?"USED":"FREE")

}

printf("\n----------------------------------------------\n")

printf("Totalsize:%-10d Used:%-10d Free:%-10d\n",MEMSIZE,used,MEMSIZE-used)

printf("\n\n Press Any Key to return...")

getch()

}

/*--------------------------------------------------------

函数名:main()

功 能:主函数

--------------------------------------------------------*/

void main(){

char ch

InitAll()

while(1){

printf("========================================================\n")

printf(" 1.Get a block use the FISTFIT method\n")

printf(" 2.Get a block use the BESTFIT method\n")

printf(" 3.Get a block use the BadFIT method\n")

printf(" 4.Free a block\n")

printf(" 5.Display Mem info \n")

printf(" 6.Exit \n")

printf("========================================================\n")

ch=getch()

switch(ch){

case '1':FirstFit_new()break//首次适应算法

case '2':BestFit_new()break//最佳适应算法

case '3':BadFit_new()break//最坏适应算法

case '4':del()break //删除已经使用完毕的空间

case '5':Display()break //显示内存分配情况

case '6':exit(0)

}

}

}

考的是内存的动态划分区域内容，很好写啊

1.可以用数字来模拟内存区域划分情况，比如建一个100大小的数组（结构为struc （区号，值），值为0表示空闲，值为1表示占用，初始化几个已确定占有的分区，分区一，1-5 占有，6-12 空闲，。。。。。。。，并建立空闲区域表，很简单，从头到尾对数组扫描下就知道了

2.最先适应：从内存开始地址找到第一个大于请求大小的连续空闲区域，如请求5个空间，那就在刚开始6-12空闲处建立分区二 ，6-11 ，占用

3.最佳适应：指所有空闲块最适应请求大小的那块，min（空闲块大小-请求大小）

4.最坏：指适应请求大小，且最大的那块空闲区域

最佳适应算法产生的碎片是：外部碎片，因为最佳适应算法虽然称为“最佳”，但是性能通常很差，所以每次最佳的分配会留下很小的难以利用的内存块，它会产生最多的外部碎片。

并且最坏适应算法与最佳适应算法相反，选择最大的可用块，这看起来最不容易产生碎片，但是却把最大的连续内存划分开，会很快导致没有可用的大的内存块，因此性能也非常差。

所以首次适应算法可能比最佳适应法效果好，而它们两者一定比最大适应法效果好。另外注意,在算法实现时,分配 *** 作中最佳适应法和最大适应法需要对可用块进行排序或遍历查找，而首次适应法和邻近适应法只需要简单查找。

回收 *** 作中，当回收的块与原来的空闲块相邻时，需要将这些块合并。在算法实现时，使用数组或链表进行管理。除了内存的利用率，这里的算法开销也是 *** 作系统设计需要考虑的一个因素。

最佳适应算法中动态分区的分配策略是：

在进程装入或换入主存时，如果内存中有多个足够大的空闲块， *** 作系统必须确定分配哪个内存块给进程使用，这就是动态分区的分配策略。

1、首次适应：地址递增，顺序查找，第一个能满足的即分配给进程。

2、最佳适应：容量递增，找到第一个能满足要求的空闲分区。

3、最坏适应：容量递减，找到第一个能满足要求的分区。

4、邻近适应：循环首次适应算法。

---