内存管理伙伴算法模拟程序

#include 
#include
using namespace std;
#include
#include
#include
#include
struct Block
{
int start;
int end;
Block()
{
start=0;
end =0;
}
int operator<(Block b)
{
return this->end }
};
#define BLOCKTYPE 10
struct MemBlock
{
int num;
int base;
list memBlockList;
MemBlock()
{
num = 0;
base = 0;
memBlockList.clear();
}
};
struct Job
{
int start;
int end;
int index;
Job()
{
start=0;
end =0;
}
};
list jobList;
int jobindex = 0;
MemBlock arr[BLOCKTYPE];
bool isMemInit = false;//是否初始化过内存

//回收所有内存
void MemEnd()
{
int i = 0;
for(i = 0;i{
arr[i].base = 0;
arr[i].memBlockList.clear();
}
jobList.clear();
jobindex = 0;
isMemInit = false;
}

//初始化分配内存
void MemInit( int PoolSize )
{

int i = BLOCKTYPE - 1;
int n = 0;
int j = 0;
int base;
for(;PoolSize >=8 && i>=0;i--)
{
base = (int)pow(2.0,i+3);
arr[i].num = 0;
n = PoolSize/base;
PoolSize = PoolSize%base;
if(n > 0)
{
arr[i].num = n;
for(j = n;j>0;j--)
{
Block block;
arr[i].memBlockList.push_back(block);
}
}
}
int start = 0;
int end = 0;
list::iterator it;
for(i = 0;i{
base = (int)pow(2.0,i+3);
arr[i].base = base;
if(arr[i].num>0)
{
it = arr[i].memBlockList.begin();
while(it != arr[i].memBlockList.end())
{
end = start+base-1;
(*it).start = start;
(*it).end = end;
start = end+1;
it++;
}
}

}
isMemInit = true;
}

//合并连续内存
void mergeMem(int index)
{
int i = index;
if(i>=BLOCKTYPE -1)//超过最大了
{
return;
}
if(arr[i].num > 1)
{
list::iterator it1 = arr[i].memBlockList.begin();
list::iterator it2 = arr[i].memBlockList.begin();
it2++;
while(it2 != arr[i].memBlockList.end())
{
if(it1->end == it2->start-1)
{
Block block;
block.start = it1->start;
block.end = it2->end;
arr[i+1].memBlockList.push_back(block);
arr[i+1].num++;
arr[i].memBlockList.erase(it1);
arr[i].memBlockList.erase(it2);
arr[i+1].memBlockList.sort();
arr[i].num--;
arr[i].num--;
break;
}
it1++;
it2++;
}
}
mergeMem(i+1);
}

//分割多余内存
void divdeMem(int start,int end,int index)
{
int i = index;
if(start > end)
{
//合并内存
mergeMem(i+1);
return;
}

Block block;
block.end = end;
block.start = end - arr[i].base+1;
end = block.start -1;
arr[i].memBlockList.push_back(block);
arr[i].memBlockList.sort();
arr[i].num++;

divdeMem(start,end,i-1);


}



//申请内存
bool MemAlloc( int MemSize )
{
if(MemSize > 4096 || MemSize <1)
{
return false;
}
int size = 0;
int i = 0;
int n = 0;
for(;i{
if(MemSize <= arr[i].base)
{
if(0 == size)
{
size = arr[i].base;//实际分配的大小
}

//有空闲块
if(arr[i].num > 0)
{
//空闲块链表应该是有序的
Block block = arr[i].memBlockList.front();
jobList.back().start = block.start;
jobList.back().end = block.start+size-1;

//分配了一块内存 
arr[i].memBlockList.pop_front();
arr[i].num--;

//分割多余内存
int start = block.start + size;
int end = block.end;
divdeMem(start,end,i-1);
return true;
}

}
}
return false;
}

//释放指定内存
void MemFree( int start,int end )
{
int size = end - start +1;
int i = 0;
for(;i{
if(arr[i].base == size)
{
Block block;
block.start = start;
block.end = end;
arr[i].memBlockList.push_back(block);
arr[i].memBlockList.sort();

arr[i].num++;
mergeMem(i);

}
}
}
void menu()
{
cout <<"空闲内存伙伴算法程序模拟" <cout <<"1.初始化内存分配" <cout <<"2.作业分配申请内存" <cout <<"3.作业释放内存" <cout <<"4.查看当前内存使用情况" <cout <<"0.退出模拟程序" <}

//获得要初始化的内存大小
bool getRequestMem(int &n)
{
if(isMemInit)
{
cout <<"内存已经被初始化,将重新初始化分配内存,所有数据将会丢失,确定要继续吗,Y/N?" <char c;
cin >> c;
if(toupper(c) == 'Y')
{

}
else if(toupper(c) == 'N')
{
return false;
}
else
{
cout <<"非法输入,返回主程序" <return false;
} 
MemEnd();
}
cout <<"请输入分配的内存大小" <cin >> n;
return true;
}

//为作业分配内存
void assignMemForJob()
{
Job job;
job.index = jobindex++;
jobList.push_back(job);
cout <<"请输入申请内存大小" <int n;
cin >> n;
if(MemAlloc(n))
{
cout <<"作业申请内存成功,起始地址为job" <}
else
{
jobindex--;
jobList.pop_back();
cout <<"当前没有足够内存,请释放一定内存后再试" <}

}

void checkMem()
{
cout <<"内存空闲块:" <int i = 0;
list::iterator it;
for(;i{
printf("%d : 有%d个空闲内存块    起始地址分别为:",arr[i].base,arr[i].num);
for(it = arr[i].memBlockList.begin();it!=arr[i].memBlockList.end();it++)
{
printf("%d~%d ",it->start,it->end);
}
printf("\n");
}

cout <<"作业占用内存:" <list::iterator job = jobList.begin();
while(job != jobList.end())
{
printf("作业%d 大小:%d 内存地址:%d~%d\n",job->index,job->end - job->start+1,job->start,job->end);
job++;
}
}

//释放作业内存
void retrieveMemFromJob()
{
cout <<"请输入要释放的作业编号" <int n = -1;
cin >> n;
if(n <0)
{
cout <<"不存在该编号的作业,作业释放内存失败" <}
else
{
list::iterator it = jobList.begin();

while(it != jobList.end())
{
if(it->index == n)
{
Job job = *it;
jobList.erase(it);

//释放作业内存
MemFree(job.start,job.end);
break;
}
it++;
}
cout <<"作业释放内存成功" <}
}
int main()
{

int choice = -1;
int size = 0;

while(1)
{
menu();
cin >> choice;
if(0 == choice)
{
break;
}
switch(choice)
{
case 1:
if(getRequestMem(size))
{
MemInit(size);
cout <<"初始化内存成功" <}
else
{
cout <<"初始化内存失败" <}
break;
case 2:
assignMemForJob();
break;
case 3:
retrieveMemFromJob();
break;
case 4:
checkMem();
break;
default:
cout <<"非法选项" <break;
}

}
cout <<"退出模拟程序" <return 0;
}