1. 要求
建立空闲块构成的链表，每个块包含该块的字节数和指向链表中下个块的指针。从每个块起始处存放它们。要分配指定大小的块时，采用最先适应算法，取出所需要的块，接着更新链表。该块被释放时，把该块添加到链表的尾部。
2. C程序
#include <stdlib.h> #include <sys/mman.h> #include <stdio.h> #define WSIZE 4 /* word size (bytes) */ #define DSIZE 8 /* double word size (bytes) */ #define OVERHEAD 12 /* overhead of header and footer (bytes) */ struct segment { int length; struct segment *link; } ; struct segment *head; /* 声明结构函数allocblock()和无值型函数dealloc() */ struct segment *allocblock(int x); void print(struct segment *phead); struct segment *find_fit(int x); void dealloc(struct segment *blo); int main() { int size; struct segment *freelist,*p,*q,*block1; size=100; head=NULL; freelist=(struct segment *)mmap( NULL,4096,PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS,-1,0 ); if(freelist==MAP_FAILED) { printf("mmap faile"); } /* 建立链表 */ freelist->length=size; freelist->link=NULL; head=freelist; p=head+size+OVERHEAD; p->length=200; freelist->link=p; p->link=NULL; q=p+p->length+OVERHEAD; q->length=300; p->link=q; q->link=NULL; printf("before allocblock:\n"); print(head); size=120; block1=allocblock(size); // 分配一个size大小块block1 if (block1 == NULL) { perror("allocblock faile"); exit(1); } printf("The length of allocated block is %d\n",block1->length); printf("after allocblock:\n"); print(head); dealloc(block1); // 释放block1 printf("after dealloc:\n"); print(head); return 0; } struct segment *allocblock(int x) { int i,temp; struct segment *bp; if (x<=0) return NULL; else if (x<=DSIZE) x=OVERHEAD+ WSIZE; else x=((x+(OVERHEAD)+(DSIZE-1))/DSIZE)*DSIZE; if((bp=find_fit(x))!=NULL){ return bp; } else return NULL; } struct segment *find_fit(int x){ struct segment *m,*n,*r; int temp; m=head; if(x<=head->length){ if(((head->length)-x)<2*DSIZE) head=head->link; else{ temp=m->length; m->length=x; head=m+x+12; head->length=temp-x-12; head->link=m->link; } } else{ while(x>m->length){ n=m; m=m->link; if (m==NULL) break; } if (m!=NULL){ if(((m->length)-x)<2*DSIZE) n->link=m->link; else{ temp=m->length; m->length=x; r=m+x+12; r->length=temp-x-12; n->link=r; r->link=m->link; } } else return NULL; } return m; } void print(struct segment *phead) { struct segment *p; p=phead; while (p!=NULL){ printf("%d\n",p->length); p=p->link ; } } void dealloc(struct segment *blo) { struct segment *p; p=head; while(p->link!=NULL) p=p->link; p->link = blo; blo->link = NULL; }3. 运行结果
before allocblock:
100
200
300
The length of allocated block is 136
after allocblock:
100
52
300
after dealloc:
100
52
300
136
