课程设计最先适应算法.docx
《课程设计最先适应算法.docx》由会员分享，可在线阅读，更多相关《课程设计最先适应算法.docx（22页珍藏版）》请在冰点文库上搜索。
课程设计最先适应算法
课程设计：
最先适应算法
设计1动态异长分区内存分配与去配算法的设计-最先适应算法
1.1设计目的
理解存储管理的功能，掌握动态异长分区内存管理中的最先适应算法。
1.2设计要求
本设计要求模拟最先适应算法的分配算法和回收算法。
1.3设计步骤
1.3.1数据结构分析
空闲区域首址
空闲区域长度
…
…
addr
size
…
…
图1-1空闲区域表
为了实现存储资源的分配和回收，操作系统需要记录内存资源使用情况，即哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程等。
为此一般需要两个表，一个为分配表,另外一个为空闲区域表。
前者记录已经分配的区域,后者记录着所有当前未被进程占用的空闲区域,如图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是最先适应算法分配情况。
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.头文件部分：
#include
#include
#include
#include
#include
#include
#defineMAX_THREAD3
typedefstructfreearea{//表示空闲区域的数据结构
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_delete_freearea_list（）;//删除空闲区链表
REQUIRE_MEMORY*FF_initialize_require_memory_list（REQUIRE_MEMORY*init_table,intnum）;//初始化内存申请链表
voidFF_delete_require_memory_list（）;//删除内存申请链表
THREAD_RESIDENCE_MEMORY*FF_initialize_thread_residence_memory_list（THREAD_RESIDENCE_MEMORY*init_table,intnum）;//初始化线程驻留区链表
voidFF_delete_thread_residence_memory_list（）;//删除线程驻留区链表
voidFF_thread（void*data）;//线程函数
intFF_require_memory（intsize）;//内存申请函数
voidFF_release_memory（intstart_address,intsize）;//内存释放函数
voidFF（）;//最先适应分配算法的初始化函数
2.源文件部分
#include"variable_partition.h"
voidprint_space（intnum）{//显示若干个空格
inti;
for（i=0;iprintf（""）;
}
}
voiddisplay_thread_residence_memory_list（）{//显示驻留线程链表
THREAD_RESIDENCE_MEMORY*p;
charbuffer[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",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（buffer））;
printf（"|%d",p->size）;
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,intnum）{
FREEAREA*temp;
FREEAREA*head=NULL;
FREEAREA*tail=NULL;
inti;
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;
}
};
returnhead;
}
//最先适应分配法：
删除空闲区链表
voidFF_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,intnum）{
REQUIRE_MEMORY*temp;
REQUIRE_MEMORY*head=NULL;
REQUIRE_MEMORY*tail=NULL;
inti;
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;
}
};
returnhead;
}
//最先适应分配法：
删除内存申请链表
voidFF_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,intnum）{
THREAD_RESIDENCE_MEMORY*temp;
THREAD_RESIDENCE_MEMORY*head=NULL;
THREAD_RESIDENCE_MEMORY*tail=NULL;
inti;
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;
returnhead;
}
//最先适应分配法：
删除线程驻留区链表
voidFF_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;
}
//线程：
申请内存，驻留一段时间，释放内存
voidFF_thread（void*data）{
intstart_address=-1;
THREAD_RESIDENCE_MEMORY*temp;
EnterCriticalSection（&CS_SCREEN）;//互斥
printf（"createthread:
%s\n",（（REQUIRE_MEMORY*）（data））->thread_name）;
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",（（REQUIRE_MEMORY*）（data））->thread_name,"getmemory:
"）;
printf（"显示线程驻留区链表\n"）;
display_thread_residence_memory_list（）;
LeaveCriticalSection（&CS_SCREEN）;
Sleep（（（REQUIRE_MEMORY*）（data））->duration）;
//释放内存
FF_release_memory（start_address,（（REQUIRE_MEMORY*）（data））->size）;
}
//最先适应分配法：
内存申请函数
/*******************************************************************************************************************/
intFF_
升级会员 