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

设计1 动态异长分区内存分配与去配算法的设计-最先适应算法 ............. 1 1.1 设计目的 ..................................................................................................... 1 1.2 设计要求 ..................................................................................................... 1 1.3 设计步骤 ..................................................................................................... 1 1.3.1 数据结构分析 .................................................................................... 1 1.3.2 算法分析 ............................................................................................ 2 1.3.3 设计并分析测试数据 ........................................................................ 2 1.3.4 程序设计 .......................................................................................... 3 1.3.5 源代码（直接使用） ........................................................................ 3

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

1.1 设计目的

理解存储管理的功能，掌握动态异长分区内存管理中的最先适应算法。

1.2 设计要求

本设计要求模拟最先适应算法的分配算法和回收算法。

1.3 设计步骤

1.3.1 数据结构分析

为了实现存储资源的分配和回收，操作系统需空闲区域首址 空闲区域长度 要记录内存资源使用情况，即哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程等。为此一… … 般需要两个表，一个为分配表, 另外一个为空闲区

addr size 域表。前者记录已经分配的区域, 后者记录着所有

… … 当前未被进程占用的空闲区域, 如图1-1所示。

显然, 没有记录于表中的区域即为已被进程所

图1-1 空闲区域表

占用的非空闲区域，在实际的操作系统中，这些区

域登记在进程的PCB中。而PCB中除了关于内存资源的信息外，还有其它大量信息。

由于本设计是对存储管理算法的模拟，所以用一个线程来代表一个进程，用线程驻留区域表来描述线程占用的内存空间，如图1-2所示。

线程名称 驻留区始址 驻留区大小 a b …… 0 20 …… 图1-2 线程驻留区表

10 20 …… 同时，需要一张表来记录各个线程对内存的请求信息，如图1-3所示。

线程名称 thread_1 请求大小(KB) 20 预计驻留时间( 秒) 4 thread_2 …… 10 …… 图1-3 内存申请表

5 …… 1.3.2 算法分析

对于存储申请命令, 选取满足申请长度要求且起始地址最小的空闲区域。在实现时, 可将系统中所有的空闲区域按照起始地址由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分的长度为原长度与分配长度之差, 将其仍记录于空闲区域表中。

回收时，按回收区的首地址查询空闲区表，若有与回收区相临的空闲区，则将其合并到相临区中，否则，把回收区按照地址从低到高的顺序插入到空闲区域表的适当位置。 1.3.3 设计并分析测试数据

假设初始内存布局如图1-4，图中的起始地址以及大小都以KB来衡量。

起始地址 0 占用者 大 小

10

20

40

70

80 85

145 160 180

a 10

10

b 20

30

c 10

5

d 60

15

e 20

20

图1-4初始内存布局

由图1-4可见，初始时共有五个线程驻留在内存，它们是a,b,c,d,e，线程驻留区表如图1-5；还有五个空闲区，空闲区域表如图1-6。

假设现在有三个线程提出内存申请，申请情况见图1-7。经过分析我们得到在每种分配算法下这三个线程所申请到的内存情况。图1-8是最先适应算法分配情况。

线程名称 驻留区始址 驻留区大小 空闲区首址 空闲区长度 10 10 a 0 10 40 30 b 20 20 80 5 c 70 10 145 15 d 85 60 180 20 e 160 20 图1-5 线程驻留区表 图1- 6 空闲区域表 线程名称 驻留区始址 驻留区大小 a 0 10 b 20 20 请求大小 预计驻留 线程名称 c 70 10 (KB) 时间( 秒) d 85 60 thread_1 20 4 e 160 20 thread_2 10 5 thread_1 40 20 thread_3 5 6 thread_2 10 10 图1-7 内存申请表 thread_3 60 5 图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_delete_thread_residence_memory_list FF_thread FF_require_memory FF_release_memory FF() 函数功能 初始化空闲区链表：按地址从低到高排序 删除空闲区链表 初始化内存申请链表 删除内存申请链表 删除线程驻留区链表 线程函数：申请内存；驻留内存；释放内存 内存申请函数 内存释放函数 初始化函数：创建线程并等待它们结束 图1-9 最先适应分配法的函数及其功能

FF_initialize_thread_residence_memory_list 初始化线程驻留区链表

1.3.5 源代码

#include #include #include #include #include #include

#define MAX_THREAD 3

typedef struct freearea{ //表示空闲区域的数据结构 struct freearea *next; //指向下一个结点的指针 int start_address; //空闲区起始地址 int size; //空闲区大小 }FREEAREA;

typedef struct require_memory{ //记录线程申请内存的数据结构 struct require_memory *next; //指向下一个结点的指针 char thread_name[10]; //线程名 int size; //申请内存大小（以KB为单位） int duration; //在内存的驻留时间（以秒为单位） }REQUIRE_MEMORY;

typedef struct thread_residence_memory{ //描述线程驻留区的数据结构 struct thread_residence_memory *next; //指向下一个结点的指针 char thread_name[10]; //线程名 int start_address; //驻留区起始地址 int size; //驻留区大小 }THREAD_RESIDENCE_MEMORY;

FREEAREA init_free_area_table[5]={ {NULL,10,10}, {NULL,40,30}, {NULL,80,5}, {NULL,145,15}, {NULL,180,20}

}; //测试数据：初始空闲区表

REQUIRE_MEMORY init_thread_require_memory_table[3]={ {NULL,\"thread_1\ {NULL,\"thread_2\ {NULL,\"thread_3\}; //测试数据：初始内存申请表

THREAD_RESIDENCE_MEMORY init_thread_residence_memory_table[5]={ {NULL,\"a\ {NULL,\"b\ {NULL,\"c\ {NULL,\"d\ {NULL,\"e\

};//测试数据：初始线程驻留区表

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_thread[MAX_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_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(); //最先适应分配算法的初始化函数

void print_space(int num){ //显示若干个空格 int i; for(i=0;ivoid display_thread_residence_memory_list(){ //显示驻留线程链表 THREAD_RESIDENCE_MEMORY *p; char buffer[20];

p=p_thread_residence_memory_list; printf(\"|-------------------|--------------------|------------------|\\n\"); printf(\"| thread_name | start_address(kB) | size(KB) |\\n\"); printf(\"|-------------------|--------------------|------------------|\\n\"); while(p!=NULL){

printf(\"| %s\

print_space(18-strlen(p->thread_name)); printf(\"| %d\ itoa( p->start_address, buffer, 10 ); print_space(19-strlen(buffer)); printf(\"| %d\ itoa(p->size, buffer, 10 );

print_space(17-strlen(buffer)); printf(\"|\\n\"); p=p->next; };

printf(\"|-------------------|--------------------|------------------|\\n\\n\"); }

//最先适应分配法：初始化空闲区链表

FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num){ FREEAREA *temp;

FREEAREA *head=NULL; FREEAREA *tail=NULL; int i;

for(i=0;itemp=(FREEAREA *)malloc(sizeof(FREEAREA)); temp->start_address=init_table[i].start_address; temp->size=init_table[i].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;itemp=(REQUIRE_MEMORY *)malloc(sizeof(REQUIRE_MEMORY)); strcpy(temp->thread_name,init_table[i].thread_name); temp->size=init_table[i].size; temp->duration=init_table[i].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;itemp=(THREAD_RESIDENCE_MEMORY

*)malloc(sizeof(THREAD_RESIDENCE_MEMORY)); strcpy(temp->thread_name,init_table[i].thread_name); temp->start_address=init_table[i].start_address; temp->size=init_table[i].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:%s\\n\ LeaveCriticalSection(&CS_SCREEN);

while(1){ //申请内存 start_address=FF_require_memory(((REQUIRE_MEMORY *)(data))->size);

if(start_address>=0) break; else Sleep(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 %s\\n\ 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) { //刚好满足要求，删除空闲区结点 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); 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; }

else{

p = 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; }

else{

p->next = p->next->next; } }

if(p->next == NULL){ break; }

else{

p = p->next; } }

if(change == 0){ break; } }

//整理线程结束后的驻留链表

THREAD_RESIDENCE_MEMORY *q; q = p_thread_residence_memory_list; if(q->start_address == start_address){

p_thread_residence_memory_list = p_thread_residence_memory_list->next; } else{

while(q->next !=NULL){

if(q->next->start_address==start_address){

if(q->next==tail_thread_residence_memory_list){ tail_thread_residence_memory_list = q; }

q->next = q->next->next ; break; }

q = q->next; } } LeaveCriticalSection(&CS_FREEAREA_LIST); }

//最先适应分配算法的初始化程序 void FF( ){ int i=0;

REQUIRE_MEMORY *p;

HANDLE h_thread[MAX_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_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_thread[i]=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:\\n\"); display_thread_residence_memory_list(); //显示驻留线程链表 LeaveCriticalSection(&CS_SCREEN); //删除各种链表 FF_delete_freearea_list(); FF_delete_require_memory_list(); FF_delete_thread_residence_memory_list(); getch(); printf(\"\\n\"); }

int main( ){ FF( ); return 0; }