最佳適應算法
從全部空閑區中找出能滿足作業要求的，且大小最小的空閑分區，這種方法能使碎片盡量小。
問題描述
- Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most efficient use of memory?
問題解決
為212k分配空間：
找到第一個跟212k大小最接近的空閑區找到第四個空閑區300>212k，剩余88k空閑區為417k分配空間：
找到第一個跟417k大小最接近的空閑區找到第二個空閑區500>417，剩余83k空閑區為112k分配空間：
找到第一個跟112k大小最接近的空閑區找到第三個空閑區200>112k，剩余88k空閑區為426k分配空間：
找到第一個跟426大小最接近的空閑區找到第五個空閑區600k>426，剩余74k空閑區
code
#include<stdio.h>
#include<stdlib.h>#define N 5
#define M 5int buf[N]={100,500,200,300,600};
int need_dis[M]={212,417,112,426,200};
typedef struct LNode *List;struct LNode{int order;int buffer;LNode *next;
};List list_init(){List head,p,m;int i;for(i=0;i<N;i++){if(i==0){m=(LNode*)malloc(sizeof(struct LNode));if(!m){printf("Error:memory!\n");exit(0);}m->order=i;m->buffer=buf[i];m->next=NULL;head=p=m;}else{m=(LNode*)malloc(sizeof(struct LNode));if(!m){printf("Error:memory wrong\n");exit(0);}m->order=i;m->buffer=buf[i];m->next=NULL;p->next=m;p=p->next;}}return head;
}void best_fit(List head){int i,j,k;int min;int order;List p;for(i=0;i<M;i++){min=-1;order=-1;p=head;while(p){if(p->buffer>=need_dis[i]){if(min<0){min=p->buffer-need_dis[i];order=p->order;}else{if(min>p->buffer-need_dis[i]){min=p->buffer-need_dis[i];order=p->order;}}}p=p->next;} if(order==-1){printf("\n");printf("分配完成%d個\n",i);printf("第%d個進程失敗\n",i+1);printf("\n");break; }else{p=head;while(p){if(p->order==order)p->buffer-=need_dis[i];p=p->next;}}}
}void print(List p){while(p){printf("%d:%d\n",p->order,p->buffer);p=p->next;}
}int main(){List p;p=list_init();printf("分配內存前\n"); print(p);best_fit(p);printf("分配內存后\n");print(p);return 0;
} 
)
