动态异长分区内存分配与去配算法的设计-最先适应算法-

操作系统课程设计指导设计1动态异长分区内存分配与去配算法的设计-最先适应算法.............11.1设计目的.....................................................................................................11.2设计要求.....................................................................................................11.3设计步骤.....................................................................................................11.3.1数据结构分析....................................................................................11.3.2算法分析............................................................................................21.3.3设计并分析测试数据........................................................................21.3.4程序设计..........................................................................................31.3.5源代码（直接使用）........................................................................3设计1动态异长分区内存分配与去配算法的设计-最先适应算法1.1设计目的理解存储管理的功能，掌握动态异长分区内存管理中的最先适应算法。1.2设计要求本设计要求模拟最先适应算法的分配算法和回收算法。1.3设计步骤1.3.1数据结构分析为了实现存储资源的分配和回收，操作系统需要记录内存资源使用情况，即哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程等。为此一般需要两个表，一个为分配表,另外一个为空闲区域表。前者记录已经分配的区域,后者记录着所有当前未被进程占用的空闲区域,如图1-1所示。显然,没有记录于表中的区域即为已被进程所占用的非空闲区域，在实际的操作系统中，这些区域登记在进程的PCB中。而PCB中除了关于内存资源的信息外，还有其它大量信息。由于本设计是对存储管理算法的模拟，所以用一个线程来代表一个进程，用线程驻留区域表来描述线程占用的内存空间，如图1-2所示。线程名称驻留区始址驻留区大小a010b2020………………图1-2线程驻留区表同时，需要一张表来记录各个线程对内存的请求信息，如图1-3所示。线程名称请求大小(KB)预计驻留时间(秒)thread_1204空闲区域首址空闲区域长度……addrsize……图1-1空闲区域表thread_2105………………图1-3内存申请表1.3.2算法分析对于存储申请命令,选取满足申请长度要求且起始地址最小的空闲区域。在实现时,可将系统中所有的空闲区域按照起始地址由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时,系统由表的头部开始查找,取第一个满足要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同,则将该区域全部分配给申请者。否则将该区域分割为两部分,一部分的长度与所申请的长度相同,将其分配给申请者；另一部分的长度为原长度与分配长度之差,将其仍记录于空闲区域表中。回收时，按回收区的首地址查询空闲区表，若有与回收区相临的空闲区，则将其合并到相临区中，否则，把回收区按照地址从低到高的顺序插入到空闲区域表的适当位置。1.3.3设计并分析测试数据假设初始内存布局如图1-4，图中的起始地址以及大小都以KB来衡量。起始地址0102040708085145160180占用者abcde大小1010203010560152020图1-4初始内存布局由图1-4可见，初始时共有五个线程驻留在内存，它们是a,b,c,d,e，线程驻留区表如图1-5；还有五个空闲区，空闲区域表如图1-6。假设现在有三个线程提出内存申请，申请情况见图1-7。经过分析我们得到在每种分配算法下这三个线程所申请到的内存情况。图1-8是最先适应算法分配情况。线程名称驻留区始址驻留区大小a010b2020c7010d8560e16020图1-5线程驻留区表空闲区首址空闲区长度101040308051451518020图1-6空闲区域表线程名称请求大小(KB)预计驻留时间(秒)thread_1204thread_2105thread_356图1-7内存申请表线程名称驻留区始址驻留区大小a010b2020c7010d8560e16020thread_14020thread_21010thread_3605图1-8最先适应算法线程驻留区表1.3.4程序设计程序包含两个文件，一个是头文件variable_partition.h，另一个是源程序文件variable_partition.cpp。在头文件中定义了宏、数据结构、全局变量、函数声明，源程序中含有各个函数的实现。在头文件中，结构体FREEAREA、REQUIRE_MEMORY、THREAD_RESIDENCE_MEMORY分别对应于图1-1、图1-2、图1-3中的一行，不同之处是为了构成链表在三个结构体中都有前向指针。数组init_free_area_table对应于图1-6，数组init_thread_require_memory_table对应于图1-5，数组init_thread_residence_memory_table对应于图1-7，为了实现动态分配与释放，用链表重新组织空闲区域表、线程驻留区表和内存申请表，全局变量p_free_area_list是空闲区链首，p_thread_require_memory_queue是内存申请队列的队首，p_thread_residence_memory_list是线程驻留区链首，tail_thread_residence_memory_list是线程驻留区链尾，由于线程驻留区链表被内存分配函数和内存释放函数共享，故用临界区变量CS_THREAD_MEMORY_LIST来保护，同理，屏幕是所有线程共享的，所以用临界区变量CS_SCREEN来保护,空闲区链表被内存分配函数和内存释放函数共享，故用临界区变量CS_FREEAREA_LIST来保护。h_thread是线程句柄数组，用来存放各个线程的句柄。程序共包含12个函数，按照作用可以将它们分成五组。第一组包括函数print_space()和函数display_thread_residence_memory()，前者用来显示若干个空格，后者用来显示线程驻留区表；第二组共十个函数，用来实现最先适应分配法，它们的名称及功能如图1-9。函数名称函数功能FF_initialize_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_release_memory内存释放函数FF()初始化函数：创建线程并等待它们结束图1-9最先适应分配法的函数及其功能1.3.5源代码#includewindows.h#includeconio.h#includestdlib.h#includestdio.h#includeio.h#includestring.h#defineMAX_THREAD3typedefstructfreearea{//表示空闲区域的数据结构structfreearea*next;//指向下一个结点的指针intstart_address;//空闲区起始地址intsize;//空闲区大小}FREEAREA;typedefstructrequire_memory{//记录线程申请内存的数据结构structrequire_memory*next;//指向下一个结点的指针charthread_name[10];//线程名intsize;//申请内存大小（以KB为单位）intduration;//在内存的驻留时间（以秒为单位）}REQUIRE_MEMORY;typedefstructthread_residence_memory{//描述线程驻留区的数据结构structthread_residence_memory*next;//指向下一个结点的指针charthread_name[10];//线程名intstart_address;//驻留区起始地址intsize;//驻留区大小}THREAD_RESIDENCE_MEMORY;FREEAREAinit_free_area_table[5]={{NULL,10,10},{NULL,40,30},{NULL,80,5},{NULL,145,15},{NULL,180,20}};//测试数据：初始空闲区表REQUIRE_MEMORYinit_thread_require_memory_table[3]={{NULL,thread_1,20,4},{NULL,thread_2,10,5},{NULL,thread_3,5,6}};//测试数据：初始内存申请表THREAD_RESIDENCE_MEMORYinit_thread_residence_memory_table[5]={{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_SECTIONCS_THREAD_MEMORY_LIST;//保护线程驻留区链表的临界区CRITICAL_SECTIONCS_SCREEN;//保护屏幕的临界区CRITICAL_SECTIONCS_FREEAREA_LIST;//保护空闲区链表的临界区HANDLEh_thread[MAX_THREAD];//线程句柄数组voidprint_space(intnum);//输出若干个空格voiddisplay_thread_residence_memory_list();//显示线程驻留区表//最先适应分配法的函数FREEAREA*FF_initialize_freearea_list(FREEAREA*init_table,intnum);//初始化空闲区链表voidFF_d