课程设计：最先适应算法.docxVIP

课程设计：最先适应算法 设计1 动态异长分区内存分配与去配算法的设计-最先适应算法 1.1 设计目的 理解存储管理的功能，掌握动态异长分区内存管理中的最先适应算法。 1.2 设计要求 本设计要求模拟最先适应算法的分配算法和回收算法。 1.3 设计步骤 1.3.1 数据结构分析 空闲区域首址空闲区域长度…… 空闲区域首址 空闲区域长度 … … addr size … … 图1-1 空闲区域表 显然, 没有记录于表中的区域即为已被进程所占用的非空闲区域，在实际的操作系统中，这些区域登记在进程的PCB中。而PCB中除了关于内存资源的信息外，还有其它大量信息。 由于本设计是对存储管理算法的模拟，所以用一个线程来代表一个进程，用线程驻留区域表来描述线程占用的内存空间，如图1-2所示。 线程名称 驻留区始址 驻留区大小 a 0 10 b 20 20 …… …… …… 图1-2 线程驻留区表 同时，需要一张表来记录各个线程对内存的请求信息，如图1-3所示。 线程名称 请求大小(KB) 预计驻留时间( 秒) thread_1 20 4 thread_2 10 5 …… …… …… 图1-3 内存申请表 1.3.2 算法分析 对于存储申请命令, 选取满足申请长度要求且起始地址最小的空闲区域。在实现时, 可将系统中所有的空闲区域按照起始地址由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分的长度为原长度与分配长度之差, 将其仍记录于空闲区域表中。 回收时，按回收区的首地址查询空闲区表，若有与回收区相临的空闲区，则将其合并到相临区中，否则，把回收区按照地址从低到高的顺序插入到空闲区域表的适当位置。 1.3.3 设计并分析测试数据 假设初始内存布局如图1-4，图中的起始地址以及大小都以KB来衡量。 起始地址 0 10 20 40 70 80 85 145 160 180 占用者 a b c d e 大 小 10 10 20 30 10 5 60 15 20 20 图1-4初始内存布局 由图1-4可见，初始时共有五个线程驻留在内存，它们是a,b,c,d,e，线程驻留区表如图1-5；还有五个空闲区，空闲区域表如图1-6。 假设现在有三个线程提出内存申请，申请情况见图1-7。经过分析我们得到在每种分配算法下这三个线程所申请到的内存情况。图1-8是最先适应算法分配情况。 线程名称驻留区始址 线程名称 驻留区始址 驻留区大小 a 0 10 b 20 20 c 70 10 d 85 60 e 160 20 图1-5 线程驻留区表 空闲区首址 空闲区长度 10 10 40 30 80 5 145 15 180 20 图1- 6 空闲区域表 线程名称 线程名称 驻留区始址 驻留区大小 a 0 10 b 20 20 c 70 10 d 85 60 e 160 20 thread_1 40 20 thread_2 10 10 thread_3 60 5 图1-8 最先适应算法线程驻留区表 线程名称 线程名称 请求大小 (KB) 预计驻留 时间( 秒) thread_1 20 4 thread_2 10 5 thread_3 5 6 图1-7 内存申请表 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是线程驻留区链尾，由于线程驻留区链表被内存分配函数和内