首次适应算法
例如有4个作业，分别为200k,500k,400k,600k,有如下空闲区（自下往上查找）
|500k|
|200k|
|600k|
|400k|
1.为200k分配空间：
找到400k，剩200k
2.为500k分配空间：
找到600k，剩100k
3.为400k分配空间：
找到500k，剩100k
4.为600k分配空间：
找不到，等待其他作业释放
即在查找的时候碰到合适的空闲区就分配
最佳适应算法
例子同上
1.为200k分配空间：
找到200k，剩0k
2.为500k：
找到500k
3.为400k：
找到400k
4.为600k：
找到600k
即将剩余的空闲区域控制到最小
最坏适应算法
和最佳适应算法相反
C语言实现最佳适应算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
typedef struct free_table{ /*定义未分配区表*/
long address;
long size;
struct free_table *next;
}Node,*NodeList ;
NodeList head;
void createLink()
{
NodeList p;
int n; //链表长度(节点数目)
head=(NodeList)malloc(sizeof(Node));
p=head;
printf("请输入空闲区域数：");
scanf("%d", &n); //链表长度(节点数目)
while( n-- ) {
p->next = (NodeList)malloc(sizeof(Node)); //创建1个新的链表节点 ///分配一个新的节点，sizeof(Node)控制该节点所占的内存，malloc()返回该节点的指针
p = p->next; //链表游标 -> 后移一个节点
scanf("%d", &p->address);
scanf("%d", &p->size);
}
p->next = NULL; //链表最后一个节点指向下一个节点的指针 --> 指向空NULL
}
void Best_allocate(int request)/*最佳适应分配函数，根据申请的request字节数来分配空间*/
{
NodeList current = head->next; //current 指向头节点后的一个节点
NodeList bestFit = NULL;
long minSize = LONG_MAX; //LONG_MAX是一个常量，值为long类型的最大值
while (current != NULL) {
if (current->size >= request && current->size < minSize) {
// 当遇到更合适的空闲区时对bestFit进行更新
bestFit = current;
minSize = current->size;
}
current = current->next;
}
}
void Link_printf()
{
NodeList temp1;
temp1=head->next;
printf("分配后的空闲表如下：\n" );
while(temp1){
printf("空闲起始地址为：%d；长度为：%d\n",temp1->address,temp1->size );
temp1=temp1->next ;
}
}
main()
{
int a,request;
createLink();
//调用createlink()
printf("请输入作业申请长度：");
scanf("%d",&request);
Best_allocate(request);
Link_printf();
}
|