最先适应算法

#include #include #include #include #include #include #include #define MAX_THREAD 3typedef struct freearea /表示空闲区域的数据结构struct freearea *next; /指向下一个结点的指针int start_address; /空闲区起始地址int size; /空闲区大小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 thread_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,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_thread_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_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(); /删除空闲区链表REQUIRE_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_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.hvoid print_space(int num) /显示若干个空格int i;for(i=0;istart_address);itoa( p-start_address, 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);void display_thread_residence_memory_list() /显示驻留线程链表THREAD_RESIDENCE_MEMORY *p;char buffer20; p=p_thread_residence_memory_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_address, 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 num) FREEAREA *temp; FREEAREA *head=NULL; FREEAREA *tail=NULL; int i; for(i=0;istart_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-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_MEMORY *init_table,int num) REQUIRE_MEMORY *temp; REQUIRE_MEMORY *head=NULL; REQUIRE_MEMORY *tail=NULL; int i; for(i=0;ithread_name,init_tablei.thread_name); temp-size=init_tablei.size; temp-duration=init_tablei.duration; 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_thread_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_RESIDENCE_MEMORY *tail=NULL; int i; for(i=0;ithread_name,init_tablei.thread_name); 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-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_thread_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 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(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_memory_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();LeaveCriticalSection(&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=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(sizesize) /分割空闲区结点 start_address=p_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);/请读者自己实现这段代码/_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 = 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(change = 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;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-size = 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_memo