操作系统课程设计——动态异长分区的存储分配与回收算法.doc

//该文件所含代码是课设需要学生自己写的代码和补充的代码，包含部分需要修改的课程设计指导书中的代码，不包含不需修改的代码

//1.显示空闲区表
void display_freearea_list(){
FREEAREA *p;
char buffer[20];
p=p_free_area_list;
printf("|--------------------|------------------|\n");
printf("| start_address(kB) | size(KB) |\n");
printf("|--------------------|------------------|\n");
while(p!=NULL){
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");
}

//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;
}
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;
}
}
//记录结束时间，并将运行时间存入对应数组
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);
}

//3.最佳适应分配算法的内存释放函数
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 ){
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;
}
}

//将空闲区按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;
}
}

//整理线程结束后的驻留链表
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[1][0] > t2 - t1){
time[1][0] = t2 - t1;
}
if(time[1][1] < t2 - t1){
time[1][1] = t2 - t1;
}
LeaveCriticalSection(&CS_FREEAREA_LIST);
}

//4.最坏适应分配算法：内存释放函数
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;
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;
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;
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;
}
}

//将空闲区按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 ;
}
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;
}
}

//记录结束时间，并将运行时间存入对应数组
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);
}

//5.二维数组，用于存放各种算法所需的最长时间和最短时间
__int64 time[3][2] = {{99999999,0},{99999999,0},{99999999,0}};

//6.显示程序运行时间
void display_time(int n){
EnterCriticalSection(&CS_SCREEN);
printf("最短时间:%ld纳秒\n",time[n][0]);
printf("最长时间:%ld纳秒\n",time[n][1]);
LeaveCriticalSection(&CS_SCREEN);
}

//7.在FF()、BF()、WF()中的删除各链表操作前加入以下代码
void FF(){
……
……
……
//显示线程结束后的空闲区
EnterCriticalSection(&CS_SCREEN);
printf("空闲区:\n");
display_freearea_list();
LeaveCriticalSection(&CS_SCREEN);
//显示该算法所需时间
display_time(0);
//删除各种链表
……
……
……
}

void BF(){
……
……
……
//显示线程结束后的空闲区
EnterCriticalSection(&CS_SCREEN);
printf("空闲区:\n");
display_freearea_list();
LeaveCriticalSection(&CS_SCREEN);
//显示该算法所需时间
display_time(1);
//删除各种链表
……
……
……
}

void WF(){
……
……
……
//显示线程结束后的空闲区
EnterCriticalSection(&CS_SCREEN);
printf("空闲区:\n");
display_freearea_list();
LeaveCriticalSection(&CS_SCREEN);
//显示该算法所需时间
display_time(2);
//删除各种链表
……
……
……
}

//8.设置计算时间的函数RDTSC方法
__inline unsigned __int64 GetCycleCount()
{
__asm _emit 0x0F
__asm _emit 0x31
}

//9.获取当前时间
t = GetCycleCount();

主界面：

FF的运行结果

BF的运行结果

WF的运行结果