动态异长分区的存储分配与回收算法

1、实验5 动态异长分区的存储分配与回收算法5.1 实验目的理解存储管理的功能，掌握动态异长分区的存储分配与回收算法。存储器是计算机系统中的关键资源，存储管理一直是操作系统的最主要功能之一。存储管理既包括内存资源管理，也包括用于实现分级存储体系的外存资源的管理。通常， 内存与外存可采用相同或相似的管理技术，如内存采用段式存储管理，则外存也采用段式存储管理。存储管理需要完成如下功能： 存储分配、存储共享、存储保护、存储扩充、地址映射。当一个作业进入内存时，由操作系统将其变为进程,并为进程分配存储空间。进程运行结束时, 由操作系统将其所占用的存储空间收回。 不同的操作系统对内存空间的划分与分配方法是不

2、同的，通常分为两类：静态等长分区的分配和动态异长分区的分配。静态等长分区常用于页式存储管理方式与段页式存储管理方式，存储空间被静态地划分为若干个长度相等的区域，每个区域被称作一个页面。 动态异长分区常用于界地址存储管理方式与段式存储管理方式，存储空间被动态地划分为若干个长度不等的区域。5.2 实验要求本实验要求模拟动态异长分区的分配算法、回收算法和碎片整理算法。5.3 实验步骤5.3.1 数据结构分析空闲区域首址空闲区域长度addrsize图5-1 空闲区域表为了实现存储资源的分配和回收，操作系统需要记录内存资源使用情况，即哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程等。为此一般需要两

3、个表，一个为分配表, 另外一个为空闲区域表。前者记录已经分配的区域, 后者记录着所有当前未被进程占用的空闲区域, 如图5-1所示。显然, 没有记录于表中的区域即为已被进程所占用的非空闲区域，在实际的操作系统中，这些区域登记在进程的PCB中。而PCB中除了关于内存资源的信息外，还有其它大量信息。由于本实验是对存储管理算法的模拟，所以用一个线程来代表一个进程，用线程驻留区域表来描述线程占用的内存空间，如图5-2所示。线程名称驻留区始址驻留区大小a010b2020图5-2 线程驻留区表同时，需要一张表来记录各个线程对内存的请求信息，如图5-3所示。线程名称请求大小(KB)预计驻留时间( 秒)thre

4、ad_1204thread_2105图5-3 内存申请表5.3.2 算法分析常用的动态异长分区的分配算法有：最先适应算法、最佳适应算法和最坏适应算法。 1. 最先适应算法(First Fit，FF)对于存储申请命令, 选取满足申请长度要求且起始地址最小的空闲区域。在实现时, 可将系统中所有的空闲区域按照起始地址由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分的长

5、度为原长度与分配长度之差, 将其仍记录于空闲区域表中。回收时，按回收区的首地址查询空闲区表，若有与回收区相临的空闲区，则将其合并到相临区中，否则，把回收区按照地址从低到高的顺序插入到空闲区域表的适当位置。 2. 最佳适应算法(Best Fit，BF)分配时取满足申请要求且长度最小的空闲区域。在实现时, 可将系统中所有的空闲区域按照长度由小到大的次序依次记录于空闲区域表中。与最先适应算法相类似, 当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所

6、申请的长度相同, 将其分配给申请者；另一部分即剩余部分的长度为原长度与分配长度之差, 由于剩余部分的长度已经改变，所以应重新将其按长度从小到大的顺序插入到空闲区域表中。回收时，不仅要按回收区的首地址查询空闲区表，找到与回收区相临的空闲区，将其合并到相临区中，而且要把合并后的回收区按照长度递增的顺序插入到空闲区域表的适当位置。 3. 最坏适应算法(Worst Fit，WF)分配时取满足申请要求且长度最大的空闲区域。在实现时, 可将系统中所有的空闲区域按照长度由大到小的次序依次记录于空闲区域表中。当进程申请存储空间时, 取第一个表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区

7、域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分即剩余部分的长度为原长度与分配长度之差, 由于剩余部分的长度已经改变，所以应重新将其按长度递减的顺序插入到空闲区域表中。回收时，不仅要按回收区的首地址查询空闲区表，找到与回收区相临的空闲区，将其合并到相临区中，而且要把合并后的回收区按照长度递减的顺序插入到空闲区域表的适当位置。5.3.3 设计并分析测试数据假设初始内存布局如图5-4，图中的起始地址以及大小都以KB来衡量。起始地址0102040708085145160180占用者abcde大 小1010203010560152020图5-

8、4初始内存布局由图5-4可见，初始时共有五个线程驻留在内存，它们是a,b,c,d,e，线程驻留区表如图5-5；还有五个空闲区，空闲区域表如图5-6。假设现在有三个线程提出内存申请，申请情况见图5-7。经过分析我们得到在每种分配算法下这三个线程所申请到的内存情况。图5-8是最先适应算法分配情况，图5-9是最佳适应算法分配情况，图5-10是最坏适应算法分配情况。空闲区首址空闲区长度101040308051451518020图5- 6 空闲区域表线程名称驻留区始址驻留区大小a010b2020c7010d8560e16020图5-5 线程驻留区表线程名称驻留区始址驻留区大小a010b2020c7010

9、d8560e16020thread_14020thread_21010thread_3605图5-8 最先适应算法线程驻留区表线程名称请求大小(KB)预计驻留时间( 秒)thread_1204thread_2105thread_356图5-7 内存申请表线程名称驻留区始址驻留区大小a010b2020c7010d8560e16020thread_14020thread_218010thread_31455图5-10最坏适应算法线程驻留区表线程名称驻留区始址驻留区大小a010b2020c7010d8560e16020thread_118020thread_21010thread_3805图5-9最

10、佳适应算法线程驻留区表5.3.4 程序设计程序包含两个文件，一个是头文件variable_partition.h，另一个是源程序文件variable_partition.cpp。在头文件中定义了宏、数据结构、全局变量、函数声明，源程序中含有各个函数的实现。在头文件中，结构体FREEAREA、REQUIRE_MEMORY、THREAD_RESIDENCE_MEMORY分别对应于图5-1、图5-2、图5-3中的一行，不同之处是为了构成链表在三个结构体中都有前向指针。数组init_free_area_table对应于图5-6，数组init_thread_require_memory_table对应于

11、图5-5，数组init_thread_residence_memory_table对应于图5-7，为了实现动态分配与释放，用链表重新组织空闲区域表、线程驻留区表和内存申请表，全局变量p_free_area_list是空闲区链首，p_thread_require_memory_queue是内存申请队列的队首，p_thread_residence_memory_list是线程驻留区链首，tail_thread_residence_memory_list是线程驻留区链尾，由于线程驻留区链表被内存分配函数和内存释放函数共享，故用临界区变量CS_THREAD_MEMORY_LIST来保护，同理，屏幕是所

12、有线程共享的，所以用临界区变量CS_SCREEN来保护,空闲区链表被内存分配函数和内存释放函数共享，故用临界区变量CS_FREEAREA_LIST来保护。h_thread是线程句柄数组，用来存放各个线程的句柄。程序共包含25个函数，按照作用可以将它们分成五组。第一组是主函数main()，其作用是显示主菜单并根据用户的选择执行相应功能；第二组包括函数print_space()和函数display_thread_residence_memory()，前者用来显示若干个空格，后者用来显示线程驻留区表；第三组共十个函数，用来实现最先适应分配法，它们的名称及功能如图5-11。函数名称函数功能FF_ini

13、tialize_freearea_list初始化空闲区链表：按地址从低到高排序FF_delete_freearea_list删除空闲区链表FF_initialize_require_memory_list初始化内存申请链表FF_delete_require_memory_list删除内存申请链表FF_initialize_thread_residence_memory_list初始化线程驻留区链表FF_delete_thread_residence_memory_list删除线程驻留区链表FF_thread线程函数：申请内存；驻留内存；释放内存FF_require_memory内存申请函数FF

14、_release_memory内存释放函数FF()初始化函数：创建线程并等待它们结束图5-11 最先适应分配法的函数及其功能第四组共六个函数，用来实现最佳适应分配法，它们的名称及功能如图5-12。函数名称函数功能BF_initialize_freearea_list初始化空闲区链表：按长度递增排序BF_thread线程函数：申请内存；驻留内存；释放内存BF_require_memory申请一段内存，成功时返回起始地址，失败时返回空BF_release_memory释放一段内存BF_insert_freearea将空闲区按大小递增的次序插入到空闲区链表中BF()初始化函数：创建线程并等待它们结束

15、图5-12 最佳适应分配法的函数及其功能第五组共六个函数，用来实现最坏适应分配法，它们的名称及功能如图5-13。函数名称函数功能WF_initialize_freearea_list初始化空闲区链表：按长度递减排序WF_thread线程函数：申请内存；驻留内存；释放内存WF_require_memory申请一段内存，成功时返回起始地址，失败时返回空WF_release_memory释放一段内存WF_insert_freearea将空闲区按大小递减的次序插入到空闲区链表中WF()初始化函数：创建线程并等待它们结束图5-13 最坏适应分配法的函数及其功能5.3.5 参考源代码5.3.5.1 win

16、dows下的参考源程序下面是完整的程序清单。头文件 variable_partition.h 的清单#include #include #include #include #include #include #define MAX_THREAD 3#define BF_initialize_require_memory_list FF_initialize_require_memory_list#define WF_initialize_require_memory_list FF_initialize_require_memory_list#define BF_initialize_thre

17、ad_residence_memory_list FF_initialize_thread_residence_memory_list#define WF_initialize_thread_residence_memory_list FF_initialize_thread_residence_memory_list#define WF_delete_freearea_list FF_delete_freearea_list#define BF_delete_freearea_list FF_delete_freearea_list#define WF_delete_require_memo

18、ry_list FF_delete_require_memory_list#define BF_delete_require_memory_list FF_delete_require_memory_list#define WF_delete_thread_residence_memory_list FF_delete_thread_residence_memory_list#define BF_delete_thread_residence_memory_list FF_delete_thread_residence_memory_listtypedef struct freearea /表

19、示空闲区域的数据结构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_res

20、idence_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_requi

21、re_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_me

22、mory_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; /保护空闲

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

24、ory_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(v

25、oid *data); /线程函数int FF_require_memory(int size); /内存申请函数void FF_release_memory(int start_address,int size); /内存释放函数void FF(); /最先适应分配算法的初始化函数/最佳适应分配算法的函数void BF_thread(void *data); /线程函数int BF_require_memory(int size); /内存申请函数void BF_release_memory(int start_address,int size); /内存释放函数void BF_insert

26、_freearea(FREEAREA *free_node); /空闲区结点插入函数void BF(); /初始化程序void BF_initialize_freearea_list(FREEAREA *init_table,int num); /初始化空闲区链表/最坏适应分配算法的函数void WF_thread(void *data); /线程函数void WF_insert_freearea(FREEAREA *free_node); /空闲区结点插入函数void WF_initialize_freearea_list(FREEAREA *init_table,int num); /初始

27、化空闲区链表int WF_require_memory(int size); /内存申请函数void WF_release_memory(int start_address,int size); /内存释放函数void WF(); /初始化程序源程序文件 variable_partition.cpp 的清单#include variable_partition.hint main(int argc,char *argv)char select;while(1)printf(|-|n);printf(| 1:first fit allocation |n);printf(| 2:best fit

28、 allocation |n);printf(| 3:worst fit allocation |n);printf(| 4:exit |n);printf(|-|n);printf(select a function(14):);doselect=(char)getch();while(select!=1&select!=2&select!=3&select!=4);system(cls);switch(select)case 1:FF();break;case 2:BF();break;case 3:WF();break;case 4:return 0;printf(nPress any

29、key to return to main menu.);getch();system(cls);return 0;void print_space(int num) /显示若干个空格int i;for(i=0;ithread_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, 1

30、0 ); 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.si

31、ze; 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;/最先适应

32、分配法：初始化内存申请链表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-ne

33、xt=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

34、_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

35、 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_threa

36、d_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;/线程：申请内存，驻留

37、一段时间，释放内存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(star

38、t_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)

39、; /加入线程驻留区链表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_thr

40、ead_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_

41、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;elseif(sizesize) /分割空闲区结点start_address=p_next-start_address;p_next-start_addres

42、s+=size;p_next-size-=size;break;elsep=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);/请读者自己实现这段代码LeaveCriticalSection(&CS_FREEAREA_LIST);/最先适应分配算法的初始化程序vo

43、id FF()int i=0; REQUIRE_MEMORY *p; HANDLE h_threadMAX_THREAD;InitializeCriticalSection(&CS_THREAD_MEMORY_LIST); InitializeCriticalSection(&CS_FREEAREA_LIST);InitializeCriticalSection(&CS_SCREEN);printf(最先适应分配算法n); p_free_area_list=FF_initialize_freearea_list(init_free_area_table,5);p_thread_require_

44、memory_queue=FF_initialize_require_memory_list(init_thread_require_memory_table,3);p_thread_residence_memory_list=FF_initialize_thread_residence_memory_list(init_thread_residence_memory_table,5); p=p_thread_require_memory_queue; while(p!=NULL) h_threadi=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(FF_thread),p,0,NULL); i+; p=p-next; ; WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1); /等待所有线程结束EnterCriticalSection(&CS_SCREEN);printf(after all threads have finished: