动态异长分区内存分配与去配算法的设计-最先适应算法
1.1 设计目的
理解存储管理的功能，掌握动态异长分区内存管理中的最先适应算法。
1.2 设计要求
本设计要求模拟最先适应算法的分配算法和回收算法。
1.3 设计步骤
1.3.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来衡量。
|
起始地址 |
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 空闲区域表 |
|
|
线程名称 |
请求大小 (KB) |
预计驻留 时间( 秒) |
|
thread_1 |
20 |
4 |
|
thread_2 |
10 |
5 |
|
thread_3 |
5 |
6 |
|
图1-7 内存申请表 |
||
|
线程名称 |
驻留区始址 |
驻留区大小 |
|
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 最先适应算法线程驻留区表 |
||
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 最先适应分配法的函数及其功能 |
|
尝试写一下这个代码（应该都是直接到这里了吧）
代码也是参考了一些文章啊什么的弄出来的，放在这里是以学习为目的
#include "variable_partition.h"
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, 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;istart_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;ithread_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;ithread_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",((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,"get memory:");
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 = 0; //定义空闲区起始地址为0
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) { //如果空闲区大小等于指针指向的空闲区大小
start_address = p_next->start_address; // 起始地址就等于该指针指向的空闲区的起始地址
if (p_next == p_free_area_list)
p_free_area_list = p_next->next; //空闲区头a指针后移
else
p->next = p_next->next;
free(p_next);
break;
} else if (size < p_next->size) {
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; // 让temp也可插到队首前面
while(p->next != NULL){
if(p->next->start_address > temp->start_address){ //插入到p后面
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){ //p->next后为空，则释放p->next
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){ //如果q->next是驻留链尾
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;
}
然后是.h文件，这两个要在一起才能运行成功的（按理来说我应该放在上面）
名字是这个variable_partition.h
#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,135,15}, {NULL,180,20} }; //测试数据：初始空闲区表 REQUIRE_MEMORY init_thread_require_memory_table[3]={ {NULL,"thread_1",20,4}, {NULL,"thread_2",10,5}, {NULL,"thread_3",5,6} }; //测试数据：初始内存申请表 THREAD_RESIDENCE_MEMORY init_thread_residence_memory_table[5]={ {NULL,"a",0,10}, {NULL,"b",20,20}, {NULL,"c",60,10}, {NULL,"d",86,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_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(); //最先适应分配算法的初始化函数
大概就是这个样子吧