1

实验5 动态异长分区的存储分配与回收算法

实验目的

理解存储管理的功能，掌握动态异长分区的存储分配与回收算法。 存储器是计算机系统中的关键资源，存储管理一直是操作系统的最主要功能之一。存储管理既包括内存资源管理，也包括用于实现分级存储体系的外存资源的管理。通常， 内存与外存可采用相同或相似的管理技术，如内存采用段式存储管理，则外存也采用段式存储管理。存储管理需要完成如下功能： 存储分配、存储共享、存储保护、存储扩充、地址映射。 当一个作业进入内存时，由操作系统将其变为进程,并为进程分配存储空间。进程运行结束时, 由操作系统将其所占用的存储空间收回。

不同的操作系统对内存空间的划分与分配方法是不同的，通常分为两类：静态等长分区的分配和动态异长分区的分配。静态等长分区常用于页式存储管理方式与段页式存储管理方式，存储空间被静态地划分为若干个长度相等的区域，每个区域被称作一个页面。 动态异长分区常用于界地址存储管理方式与段式存储管理方式，存储空间被动态地划分为若干个长度不等的区域。

5.2 实验要求

本实验要求模拟动态异长分区的分配算法、回收算法和碎片整理算法。

最先适应分配法：内存释放函数

void FF_release_memory(int start_address,int size){

EnterCriticalSection(&CS_FREEAREA_LIST);

__int64 t1, t2; //记录该算法起止时间 t1 = GetCycleCount(); //记录起始时间

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;

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

}

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; } } //记录结束时间，并将运行时间存入对应数组 t2 = GetCycleCount(); if(time[0][0] > t2 - t1){ time[0][0] = t2 - t1; } if(time[0][1] < t2 - t1){ time[0][1] = t2 - t1; } LeaveCriticalSection(&CS_FREEAREA_LIST);

最佳适应分配算法的内存释放函数

void BF_release_memory(int start_address,int size){

EnterCriticalSection(&CS_FREEAREA_LIST);

__int64 t1, t2; //记录该算法起止时间 t1 = GetCycleCount(); //记录起始时间

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 ){

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

p->next = NULL; } else{ p->next = p->next->next; } } if(p->next == NULL){ break; } else{ p = p->next ; } } if(change == 0){ break; } } //将空闲区按SIZE由小到大排序，以便符合BF算法 while(1){ int change = 0; p = p_free_area_list; if(p->size > p->next->size){ pp = p->next; p->next = pp->next; pp->next = p; p_free_area_list = pp; change = 1; } while(p->next->next != NULL){ if(p->next->size > p->next->next->size ){ 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; } } //整理线程结束后的驻留链表

}

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; } } //记录结束时间，并将运行时间存入对应数组 t2 = GetCycleCount(); if(time[1][0] > t2 - t1){ time[1][0] = t2 - t1; } if(time[1][1] < t2 - t1){ time[1][1] = t2 - t1; } LeaveCriticalSection(&CS_FREEAREA_LIST);

最坏适应分配算法：内存释放函数

void WF_release_memory(int start_address,int size){

EnterCriticalSection(&CS_FREEAREA_LIST);

__int64 t1, t2; //记录该算法起止时间 t1 = GetCycleCount(); //记录起始时间

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;

} } 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; temp->start_address = start_address; temp->size = size; temp->next = NULL; p = new FREEAREA; 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;

} } 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; } //将空闲区按SIZE由大到小排序，以便符合WF算法 while(1){ int change = 0; p = p_free_area_list; if(p->size < p->next->size){ pp = p->next; p->next = pp->next; pp->next = p; p_free_area_list = pp; change = 1; } while(p->next->next != NULL){ if(p->next->size < p->next->next->size ){ pp = p->next->next; p->next->next = pp->next; pp->next = p->next; p->next = pp; change = 1; } p = p->next ;

} } //整理线程结束后的驻留链表 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;

}

}

//记录结束时间，并将运行时间存入对应数组

t2 = GetCycleCount();

if(time[2][0] > t2 - t1){

time[2][0] = t2 - t1;

}

if(time[2][1] < t2 - t1){

time[2][1] = t2 - t1;

}

LeaveCriticalSection(&CS_FREEAREA_LIST);

}