最先适应算法Word版

1、#include <windows.h>#include <conio.h>#include <stdlib.h>#include <time.h>#include <stdio.h>#include <io.h>#include <string.h>#define MAX_THREAD 3typedef struct freearea /表示空闲区域的数据结构struct freearea *next; /指向下一个结点的指针int start_address; /空闲区起始地址int size; /空闲区大

2、小FREEAREA;typedef struct require_memory /记录线程申请内存的数据结构 struct require_memory *next; /指向下一个结点的指针char thread_name10; /线程名int size; /申请内存大小（以KB为单位）int duration; /在内存的驻留时间（以秒为单位）REQUIRE_MEMORY;typedef struct thread_residence_memory /描述线程驻留区的数据结构 struct thread_residence_memory *next; /指向下一个结点的指针char thre

3、ad_name10; /线程名int start_address; /驻留区起始地址int size; /驻留区大小THREAD_RESIDENCE_MEMORY;FREEAREA init_free_area_table5= NULL,10,10,NULL,40,30,NULL,80,5,NULL,145,15,NULL,180,20; /测试数据：初始空闲区表REQUIRE_MEMORY init_thread_require_memory_table3= NULL,"thread_1",20,4,NULL,"thread_2",10,5,NULL,

4、"thread_3",5,6; /测试数据：初始内存申请表THREAD_RESIDENCE_MEMORY init_thread_residence_memory_table5=NULL,"a",0,10,NULL,"b",20,20,NULL,"c",70,10,NULL,"d",85,60,NULL,"e",160,20;/测试数据：初始线程驻留区表FREEAREA *p_free_area_list=NULL; /空闲区链首REQUIRE_MEMORY *p_threa

5、d_require_memory_queue=NULL; /内存申请队列队首THREAD_RESIDENCE_MEMORY *p_thread_residence_memory_list=NULL; /线程驻留链首THREAD_RESIDENCE_MEMORY *tail_thread_residence_memory_list=NULL; /线程驻留区链尾CRITICAL_SECTION CS_THREAD_MEMORY_LIST; /保护线程驻留区链表的临界区CRITICAL_SECTION CS_SCREEN; /保护屏幕的临界区CRITICAL_SECTION CS_FREEAREA_

6、LIST; /保护空闲区链表的临界区HANDLE h_threadMAX_THREAD; /线程句柄数组void print_space(int num); /输出若干个空格void display_thread_residence_memory_list(); /显示线程驻留区表void display_freearea_list();/最先适应分配法的函数FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num); /初始化空闲区链表void FF_delete_freearea_list(); /删除空闲区链表R

7、EQUIRE_MEMORY *FF_initialize_require_memory_list(REQUIRE_MEMORY *init_table,int num); /初始化内存申请链表void FF_delete_require_memory_list(); /删除内存申请链表THREAD_RESIDENCE_MEMORY *FF_initialize_thread_residence_memory_list(THREAD_RESIDENCE_MEMORY *init_table,int num); /初始化线程驻留区链表void FF_delete_thread_residence_

8、memory_list(); /删除线程驻留区链表void FF_thread(void *data); /线程函数int FF_require_memory(int size); /内存申请函数void FF_release_memory(int start_address,int size); /内存释放函数void FF(); /最先适应分配算法的初始化函数#include "variable_partition.h"void print_space(int num) /显示若干个空格int i;for(i=0;i<num;i+)printf(" &q

9、uot;);void display_freearea_list() FREEAREA *p;char buffer20; p=p_free_area_list;printf("|-|-|n");printf("| start_address(kB) | size(KB) |n");printf("|-|-|n");while(p!=NULL)printf("| %d",p->start_address);itoa( p->start_address, buffer, 10 );print_space(

10、19-strlen(buffer);printf("| %d",p->size);itoa(p->size, buffer, 10 );print_space(17-strlen(buffer);printf("|n");p=p->next; printf("|-|-|nn");void display_thread_residence_memory_list() /显示驻留线程链表THREAD_RESIDENCE_MEMORY *p;char buffer20; p=p_thread_residence_memor

11、y_list;printf("|-|-|-|n");printf("| thread_name | start_address(kB) | size(KB) |n");printf("|-|-|-|n");while(p!=NULL) printf("| %s",p->thread_name); print_space(18-strlen(p->thread_name); printf("| %d",p->start_address); itoa( p->start_ad

12、dress, buffer, 10 ); print_space(19-strlen(buffer); printf("| %d",p->size); itoa(p->size, buffer, 10 ); print_space(17-strlen(buffer); printf("|n"); p=p->next; printf("|-|-|-|nn");/最先适应分配法：初始化空闲区链表FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int n

13、um) FREEAREA *temp; FREEAREA *head=NULL; FREEAREA *tail=NULL; int i; for(i=0;i<num;i+) temp=(FREEAREA *)malloc(sizeof(FREEAREA); temp->start_address=init_tablei.start_address; temp->size=init_tablei.size; temp->next=NULL; if(head=NULL) head=tail=temp; else tail->next=temp; tail=tail-&

14、gt;next; ; return head;/最先适应分配法：删除空闲区链表void FF_delete_freearea_list()FREEAREA *temp;temp=p_free_area_list;while(temp!=NULL)temp=p_free_area_list->next;free(p_free_area_list);p_free_area_list=temp;p_free_area_list=NULL;/最先适应分配法：初始化内存申请链表REQUIRE_MEMORY *FF_initialize_require_memory_list(REQUIRE_MEM

15、ORY *init_table,int num) REQUIRE_MEMORY *temp; REQUIRE_MEMORY *head=NULL; REQUIRE_MEMORY *tail=NULL; int i; for(i=0;i<num;i+) temp=(REQUIRE_MEMORY *)malloc(sizeof(REQUIRE_MEMORY); strcpy(temp->thread_name,init_tablei.thread_name); temp->size=init_tablei.size; temp->duration=init_tablei.d

16、uration; temp->next=NULL; if(head=NULL) head=tail=temp; else tail->next=temp; tail=tail->next; ; return head;/最先适应分配法：删除内存申请链表void FF_delete_require_memory_list()REQUIRE_MEMORY *temp;temp=p_thread_require_memory_queue;while(temp!=NULL)temp=p_thread_require_memory_queue->next;free(p_threa

17、d_require_memory_queue);p_thread_require_memory_queue=temp;p_thread_require_memory_queue=NULL;/最先适应分配法：初始化线程驻留区链表THREAD_RESIDENCE_MEMORY *FF_initialize_thread_residence_memory_list(THREAD_RESIDENCE_MEMORY *init_table,int num) THREAD_RESIDENCE_MEMORY *temp; THREAD_RESIDENCE_MEMORY *head=NULL; THREAD_

18、RESIDENCE_MEMORY *tail=NULL; int i; for(i=0;i<num;i+) temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY); strcpy(temp->thread_name,init_tablei.thread_name); temp->start_address=init_tablei.start_address; temp->size=init_tablei.size; temp->next=NULL; if(head=NULL) h

19、ead=tail=temp; else tail->next=temp; tail=tail->next; ; tail_thread_residence_memory_list=tail; return head;/最先适应分配法：删除线程驻留区链表void FF_delete_thread_residence_memory_list()THREAD_RESIDENCE_MEMORY *temp=p_thread_residence_memory_list;temp=p_thread_residence_memory_list;while(temp!=NULL)temp=p_th

20、read_residence_memory_list->next;free(p_thread_residence_memory_list);p_thread_residence_memory_list=temp;p_thread_residence_memory_list=NULL;/线程：申请内存，驻留一段时间，释放内存void FF_thread(void *data) int start_address=-1;THREAD_RESIDENCE_MEMORY *temp;EnterCriticalSection(&CS_SCREEN);printf("create

21、thread:%sn",(REQUIRE_MEMORY *)(data)->thread_name);LeaveCriticalSection(&CS_SCREEN); while(1) /申请内存start_address=FF_require_memory(REQUIRE_MEMORY *)(data)->size);if(start_address>=0)break;elseSleep(1000);temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY); strcpy

22、(temp->thread_name,(REQUIRE_MEMORY *)(data)->thread_name);temp->start_address=start_address;temp->size=(REQUIRE_MEMORY *)(data)->size;temp->next=NULL;EnterCriticalSection(&CS_THREAD_MEMORY_LIST); /加入线程驻留区链表tail_thread_residence_memory_list->next=temp;tail_thread_residence_me

23、mory_list=tail_thread_residence_memory_list->next; LeaveCriticalSection(&CS_THREAD_MEMORY_LIST); /显示线程驻留区链表EnterCriticalSection(&CS_SCREEN);printf("after %s %sn",(REQUIRE_MEMORY *)(data)->thread_name,"get memory:");display_thread_residence_memory_list();LeaveCritica

24、lSection(&CS_SCREEN);Sleep(REQUIRE_MEMORY *)(data)->duration); /释放内存FF_release_memory(start_address,(REQUIRE_MEMORY *)(data)->size);/最先适应分配法：内存申请函数int FF_require_memory(int size)/请读者自己实现这段代码int start_address=-1; FREEAREA *p; FREEAREA *p_next; EnterCriticalSection(&CS_FREEAREA_LIST); p=

25、p_next=p_free_area_list; while(p_next!=NULL) if(size=p_next->size) /刚好满足要求，删除空闲区结点 start_address=p_next->start_address; if(p_next=p_free_area_list) p_free_area_list=p_next->next; else p->next=p_next->next; free(p_next); break; else if(size<p_next->size) /分割空闲区结点 start_address=p_

26、next->start_address; p_next->start_address+=size; p_next->size-=size; break; else p=p_next; p_next=p_next->next; LeaveCriticalSection(&CS_FREEAREA_LIST); return start_address; /最先适应分配法：内存释放函数void FF_release_memory(int start_address,int size)EnterCriticalSection(&CS_FREEAREA_LIST)

27、;/请读者自己实现这段代码/_int64 t1, t2;/记录该算法起止时间/t1 = GetCycleCount();/记录起始时间FREEAREA *temp,*p,*pp;/将空闲区按start_address由小到大排序，以便整合相邻空闲区while(1)int change = 0;p = p_free_area_list;if(p->next != NULL)if(p->start_address > p->next->start_address)pp = p->next;p->next = pp->next;pp->next

28、= p;p_free_area_list = pp;change = 1;if(p->next != NULL)while(p->next->next != NULL)if(p->next->start_address > p->next->next->start_address )pp = p->next->next;p->next->next = pp->next;pp->next = p->next;p->next = pp;change = 1;p = p->next ;if(c

29、hange = 0)break;/插入空闲区temp = new FREEAREA;p = new FREEAREA;temp->start_address = start_address;temp->size = size;temp->next = NULL;p->next = p_free_area_list;while(p->next != NULL)if(p->next->start_address > temp->start_address)temp->next = p->next ;p->next = temp

30、;break;elsep = p->next ;if(p->next = NULL)p->next = temp;else if(temp->next = p_free_area_list)p_free_area_list = temp;/整合碎片while(1)int change = 0;p = p_free_area_list;if(p = NULL)break;while(p->next != NULL)if(p->start_address + p->size) = (p->next->start_address)p->si

31、ze = p->next->size + p->size;change = 1; if(p->next->next = NULL)free(p->next);p->next = NULL;elsep->next = p->next->next;if(p->next = NULL)break;elsep = p->next ;if(change = 0)break;/整理线程结束后的驻留链表THREAD_RESIDENCE_MEMORY *q;q = p_thread_residence_memory_list;if(q-&

32、gt;start_address = start_address)p_thread_residence_memory_list = p_thread_residence_memory_list->next ;elsewhile(q->next != NULL)if(q->next->start_address = start_address)if(q->next = tail_thread_residence_memory_list)tail_thread_residence_memory_list = q;q->next = q->next->

33、next ;break;q = q->next;/记录结束时间，并将运行时间存入对应数组/*t2 = GetCycleCount();if(time00 > t2 - t1)time00 = t2 - t1;if(time01 < t2 - t1)time01 = t2 - t1; */LeaveCriticalSection(&CS_FREEAREA_LIST);/最先适应分配算法的初始化程序void FF( )int i=0; REQUIRE_MEMORY *p; HANDLE h_threadMAX_THREAD;InitializeCriticalSection(&CS_THREAD_MEMORY_LIST); Ini