最先適應算法綜述

1、#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;int duration;REQUIRE_MEMORY;typedef struct th

2、read_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; / 測試數(shù)據(jù)：初始空閑區(qū)表/表示空閑區(qū)域的數(shù)據(jù)結(jié)構(gòu)/指向下一個結(jié)點的指針 /空閑區(qū)起始地址/空閑區(qū)大小/記錄線程申請內(nèi)存的數(shù)據(jù)結(jié)構(gòu)/指向下一個結(jié)點的指針

3、/線程名/申請內(nèi)存大?。ㄒ?KB 為單位）/在內(nèi)存的駐留時間（以秒為單位）/描述線程駐留區(qū)的數(shù)據(jù)結(jié)構(gòu)/指向下一個結(jié)點的指針/線程名/駐留區(qū)起始地址/駐留區(qū)大小REQUIRE_MEMORY init_thread_require_memory_table3=NULL,thread_1,20,4,NULL,thread_2,10,5,NULL,thread_3,5,6; / 測試數(shù)據(jù)：初始內(nèi)存申請表THREAD_RESIDENCE_MEMORY init_thread_residence_memory_table5= NULL,a,0,10,NULL,b,20,20,NULL,c,70,10,NU

4、LL,d,85,60, NULL,e,160,20;/ 測試數(shù)據(jù)：初始線程駐留區(qū)表FREEAREA *p_free_area_list=NULL;/ 空閑區(qū)鏈首REQUIRE_MEMORY *p_thread_require_memory_queue=NULL;/內(nèi)存申請隊列隊首THREAD_RESIDENCE_MEMORY *p_thread_residence_memory_list=NULL; / 線程駐留鏈首 THREAD_RESIDENCE_MEMORY *tail_thread_residence_memory_list=NULL;/保護線程駐留區(qū)鏈表的臨界區(qū)/保護屏幕的臨界區(qū) /

5、保護空閑區(qū)鏈表的臨界區(qū)/線程句柄數(shù)組/輸出若干個空格/顯示線程駐留區(qū)表/線程駐留區(qū)鏈尾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();/最先適應分配法的函數(shù)FREEAREA *FF_initiali

6、ze_freearea_list(FREEAREA *init_table,int num); /初始化空閑區(qū)鏈表void FF_delete_freearea_list();/ 刪除空閑區(qū)鏈表REQUIRE_MEMORY *FF_initialize_require_memory_list(REQUIRE_MEMORY *init_table,int num); / 初始化內(nèi)存申請鏈表void FF_delete_require_memory_list(); / 刪除內(nèi)存申請鏈表 THREAD_RESIDENCE_MEMORY *FF_initialize_thread_residence_

7、memory_list (THREAD_RESIDENCE_MEMORY *init_table,int num);/初始化線程駐留區(qū)鏈表void FF_delete_thread_residence_memory_list();/ 刪除線程駐留區(qū)鏈表void FF_thread(void *data); / 線程函數(shù) int FF_require_memory(int size); / 內(nèi)存申請函數(shù) void FF_release_memory(int start_address,int size);/內(nèi)存釋放函數(shù)void FF();/ 最先適應分配算法的初始化函數(shù)#include vari

8、able_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() THRE

9、AD_RESIDENCE_MEMORY *p; char buffer20;/顯示駐留線程鏈表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(buffe

10、r);printf(| %d,p-size); itoa(p-size, buffer, 10 ); print_space(17-strlen(buffer); printf(|n);p=p-next;printf(|nn);/最先適應分配法：初始化空閑區(qū)鏈表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

11、_address; temp-size=init_tablei.size;temp-next=NULL; if(head=NULL) head=tail=temp;elsetail-next=temp; tail=tail-next;return head;/最先適應分配法：刪除空閑區(qū)鏈表 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=

12、temp; p_free_area_list=NULL;/最先適應分配法：初始化內(nèi)存申請鏈表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=ini

13、t_tablei.duration;temp-next=NULL;if(head=NULL)head=tail=temp;elsetail-next=temp; tail=tail-next;return head;/最先適應分配法：刪除內(nèi)存申請鏈表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_m

14、emory_queue); p_thread_require_memory_queue=temp; p_thread_require_memory_queue=NULL;/最先適應分配法：初始化線程駐留區(qū)鏈表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_MEM

15、ORY *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;elsetail-next=temp;tail=tail-next;tail_thread_residence_memory_list=tail;return head;/最先適應分配法：刪除線程駐留區(qū)鏈表 void FF_de

16、lete_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

17、;/線程：申請內(nèi)存，駐留一段時間，釋放內(nèi)存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)/ 申請內(nèi)存start_address=FF_require_memory(REQUIRE_MEMORY *)(data)-si

18、ze); 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_THREA

19、D_MEMORY_LIST);/加入線程駐留區(qū)鏈表tail_thread_residence_memory_list=tail_thread_residence_memory_list-next;LeaveCriticalSection(&CS_THREAD_MEMORY_LIST);/顯示線程駐留區(qū)鏈表EnterCriticalSection(&CS_SCREEN);printf(after %s %sn,(REQUIRE_MEMORY *)(data)-thread_name,get memory:); display_thread_residence_memory_list();Leav

20、eCriticalSection(&CS_SCREEN);Sleep(REQUIRE_MEMORY *)(data)-duration);/釋放內(nèi)存 FF_release_memory(start_address,(REQUIRE_MEMORY *)(data)-size);/最先適應分配法：內(nèi)存申請函數(shù)/剛好滿足要求，刪除空閑區(qū)int FF_require_memory(int size) /請讀者自己實現(xiàn)這段代碼 int start_address=-1; FREEAREA *p; FREEAREA *p_next; EnterCriticalSection(&CS_FREEAREA_LI

21、ST); p=p_next=p_free_area_list; while(p_next!=NULL) if(size=p_next-size)結(jié)點start_address=p_next-start_address;if(p_next=p_free_area_list)p_free_area_list=p_next-next;elsep-next=p_next-next;free(p_next);break;else if(sizesize)/ 分割空閑區(qū)結(jié)點start_address=p_next-start_address; p_next-start_address+=size;p_ne

22、xt-size-=size;break;elsep=p_next;p_next=p_next-next;LeaveCriticalSection(&CS_FREEAREA_LIST);return start_address;/最先適應分配法：內(nèi)存釋放函數(shù)void FF_release_memory(int start_address,int size)EnterCriticalSection(&CS_FREEAREA_LIST);/請讀者自己實現(xiàn)這段代碼/ _int64 t1, t2;/記錄該算法起止時間/ t1 = GetCycleCount();/記錄起始時間FREEAREA *temp

23、,*p,*pp;/將空閑區(qū)按 start_address 由小到大排序，以便整合相鄰空閑區(qū) 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-

24、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;/插入空閑區(qū)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-ne

25、xt-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;/整理線程結(jié)束后的駐留鏈表THREAD_RESIDENCE_MEMORY *q;q = p_thread_residence_memory_list; if(q-start_ad