首页 > 代码库 > 内存分配
内存分配
#include <iostream>
#include <map>
#include <tuple>
#include <string>
#include <math.h>
using namespace std;
#define MAX_ORDER 11
map<string,tuple<int,int,struct page*>> process_info;
struct page{
struct page *lru;
};
struct list_head{
struct page *next;
};
struct free_area{
struct list_head free_list;
unsigned long nr_free;
};
struct zone{
struct free_area free_area[MAX_ORDER];
};
bool list_empty(struct free_area *area){
if(area->nr_free==0)
return true;
else
return false;
}
struct page* list_entry(struct free_area *area){
return area->free_list.next;
}
void list_del(struct free_area *area){
struct page *page = area->free_list.next;
area->free_list.next=page->lru;
area->nr_free--;
}
void list_add(struct page *page,struct free_area *area){
page->lru=area->free_list.next;
area->free_list.next=page;
area->nr_free++;
}
unsigned int power2(unsigned int current_ord)
{
unsigned int temp=1;
for(unsigned int i=0;i<current_ord;i++)
{
temp*=2;
}
return temp;
}
unsigned int order_init(unsigned int size){
int order,i;
double s = (size+0.0) / 4.0;
for(order=0;order <= 10;order++)
{
if(s>pow(2,order-1)&&s<=pow(2,order))
{
return order;
}
}
}
bool isBuddy(unsigned int page1,unsigned int order1,unsigned int page2,unsigned int order2){
int res;
if(order1==order2)
{
if(page1 >= page2 )
{
if(page2%(int)pow(2,order1+1)==0)
{
res = page1 - page2;
if(res==pow(2,order1))
{
return true;
}
else
return false;
}
else
return false;
}
else
{
if(page1%(int)pow(2,order1+1)==0)
{
res = page2 - page1;
if(res==pow(2,order1))
{
return true;
}
else
return false;
}
else
return false;
}
}
else
return false;
}
struct page* alloc_memory(unsigned int order,struct zone *zone){//内存分配函数
struct page *new_page;
struct free_area *area=NULL;//zone的free_area数组中存放了每个free_area的地址，对链表进行遍历只需要在数组上稍加操作即可，这里定义了一个free_area 结构体指针，用来操作链表
unsigned int current_order;
for (current_order=order; current_order<MAX_ORDER; ++current_order) {//根据计算的order的值从相应地方开始寻找满足要求的空闲块
area = zone->free_area + current_order;//free_area数组的首地址加上对应的order阶就是所求阶的地址，从这个地址开始往下寻找满足要求的空闲块
if (!list_empty(area)){//判断area这个起始地址所在的链表是否为空，不为空则继续
new_page=list_entry(area);//获取area第一个空闲页块的地址
list_del(area);//删除area第一个空闲页块，进行内存分配
struct page *buddy;
//高阶order，将多余的内存添加到对应的链表
if(current_order>0){
current_order--;//高阶order往后依次进行剩余内存的链接
while(current_order>=order){
area = zone->free_area + current_order;//获取要链接的该阶的起始地址
buddy= new_page+power2(current_order);//第一个空闲页块的起始地址加上该阶层应该分配的内存大小就是该阶应该链接上的空闲内存块
list_add(buddy,area);//在该阶添加空闲块
if(current_order==0)//链接完退出
break;
else
current_order--;//链接未完，继续向低一阶链接
}
}
return new_page;//返回该空闲页块的地址
}
}
return NULL;
}
void release_memory(unsigned int order,struct zone *zone,struct page *new_page,struct page *addr){
struct page *temp=NULL;
struct free_area *area=NULL;
struct page *page=NULL;
unsigned int page_count,page_count2;
while(order<MAX_ORDER){
area=zone->free_area+order;
page=area->free_list.next;
page_count=(int)(new_page-addr);
bool buddy_flag=false;
while(page!=NULL){
page_count2=(int)(page-addr);
buddy_flag=(bool)isBuddy(page_count,order,page_count2,order);
if(buddy_flag)
{
if(order==MAX_ORDER-1)
break;
if(temp==NULL)
area->free_list.next=page->lru;
else
temp->lru=page->lru;
area->nr_free--;
if(page_count>page_count2){
new_page=page;
}
break;
}
temp=page;
page=page->lru;
}
if(buddy_flag)
order++;
else
break;
}
list_add(new_page, area);
return;
}
void check_memory(struct zone *zone,struct page *addr){
struct free_area *area;
for(int i=0;i<11;i++){
area=zone->free_area+i;
cout<<"order:"<<i;
cout<<" nr_free:"<<area->nr_free<<endl;
struct page* page=area->free_list.next;
while(page!=NULL){
cout<<" "<<page-addr<<"~"<<page-addr+power2(i)-1<<endl;
page=page->lru;
}
}
}
void check_process(struct page *addr){
map<string,tuple<int,int,struct page*>>::iterator it;
for(it=process_info.begin();it!=process_info.end();++it){
cout<<"ID: "<<it->first<<endl;
cout<<"size:"<<get<0>(it->second)<<"KB"<<endl;
unsigned int order=get<1>(it->second);
cout<<"order:"<<order<<endl;
cout<<"addr:"<<get<2>(it->second)-addr<<"~"<<get<2>(it->second)-addr+power2(order)-1<<endl;
}
}
int main(int argc, const char * argv[]) {
struct zone *zone=(struct zone*)malloc(sizeof(struct zone));
struct free_area *area=NULL;
struct page *addr=(struct page*)malloc(62*1024*sizeof(struct page));
for(int i=0;i<10;i++){
area=zone->free_area+i;
area->nr_free=0;
area->free_list.next=NULL;
}
area=zone->free_area+10;
area->free_list.next=addr;
area->nr_free=64;
struct page *init_page=addr;
for(int i=0;i<63;i++){
init_page->lru=init_page+1024;
init_page=init_page->lru;
}
cout<<"Memory Init Completed!"<<endl;
/*
* check_memory:
* 0
* alloc_memory:
* 1 size process_id
* release_memory:
* 2 process_id
* check_process:
* 3
* quit:
* default
* size 单位为kb
*/
int option;
unsigned int size;
string process_id;
while(true){
cout<<"-For check_memory: 0"<<endl;
cout<<"-For alloc_memory: 1 size(KB) process_name"<<endl;
cout<<"-For release_memory: 2 process_name"<<endl;
cout<<"-For check_process: 3"<<endl;
cout<<"-For quit: default"<<endl;
cout<<"Input your command: ";
cin>>option;
cout << endl;
switch (option) {
case 0:
check_memory(zone, addr);
break;
case 1:{
cin>>size>>process_id;
unsigned int order=order_init(size);
if(process_info.find(process_id)==process_info.end()){
struct page *new_page=alloc_memory(order, zone);
if(new_page==NULL){
cout<<"No enough memory,please release memory first!"<<endl;
}
else{
process_info[process_id]=make_tuple(size,order,new_page);
cout<<"Alloc Memory Completed!"<<endl;
cout<<"ID: "<<process_id<<endl;
cout<<"size:"<<size<<"KB"<<endl;
cout<<"order:"<<order<<endl;
cout<<"addr:"<<new_page-addr<<"~"<<new_page-addr+power2(order)-1<<endl;
}
}
else
cout<<"Process "<<process_id<<" is existed!"<<endl;
break;
}
case 2:{
cin>>process_id;
if(process_info.find(process_id)!=process_info.end()){
unsigned int order=get<1>(process_info[process_id]);
struct page *new_page=get<2>(process_info[process_id]);
release_memory(order, zone, new_page, addr);
process_info.erase(process_id);
cout<<"Process "<<process_id<<" has been released!"<<endl;
}
else
cout<<"Process "<<process_id<<" is not existed!"<<endl;
break;
}
case 3:
check_process(addr);
break;
default:
return 0;
}
cout << endl;
}
return 0;
}
#include <map>
#include <tuple>
#include <string>
#include <math.h>
using namespace std;
#define MAX_ORDER 11
map<string,tuple<int,int,struct page*>> process_info;
struct page{
struct page *lru;
};
struct list_head{
struct page *next;
};
struct free_area{
struct list_head free_list;
unsigned long nr_free;
};
struct zone{
struct free_area free_area[MAX_ORDER];
};
bool list_empty(struct free_area *area){
if(area->nr_free==0)
return true;
else
return false;
}
struct page* list_entry(struct free_area *area){
return area->free_list.next;
}
void list_del(struct free_area *area){
struct page *page = area->free_list.next;
area->free_list.next=page->lru;
area->nr_free--;
}
void list_add(struct page *page,struct free_area *area){
page->lru=area->free_list.next;
area->free_list.next=page;
area->nr_free++;
}
unsigned int power2(unsigned int current_ord)
{
unsigned int temp=1;
for(unsigned int i=0;i<current_ord;i++)
{
temp*=2;
}
return temp;
}
unsigned int order_init(unsigned int size){
int order,i;
double s = (size+0.0) / 4.0;
for(order=0;order <= 10;order++)
{
if(s>pow(2,order-1)&&s<=pow(2,order))
{
return order;
}
}
}
bool isBuddy(unsigned int page1,unsigned int order1,unsigned int page2,unsigned int order2){
int res;
if(order1==order2)
{
if(page1 >= page2 )
{
if(page2%(int)pow(2,order1+1)==0)
{
res = page1 - page2;
if(res==pow(2,order1))
{
return true;
}
else
return false;
}
else
return false;
}
else
{
if(page1%(int)pow(2,order1+1)==0)
{
res = page2 - page1;
if(res==pow(2,order1))
{
return true;
}
else
return false;
}
else
return false;
}
}
else
return false;
}
struct page* alloc_memory(unsigned int order,struct zone *zone){//内存分配函数
struct page *new_page;
struct free_area *area=NULL;//zone的free_area数组中存放了每个free_area的地址，对链表进行遍历只需要在数组上稍加操作即可，这里定义了一个free_area 结构体指针，用来操作链表
unsigned int current_order;
for (current_order=order; current_order<MAX_ORDER; ++current_order) {//根据计算的order的值从相应地方开始寻找满足要求的空闲块
area = zone->free_area + current_order;//free_area数组的首地址加上对应的order阶就是所求阶的地址，从这个地址开始往下寻找满足要求的空闲块
if (!list_empty(area)){//判断area这个起始地址所在的链表是否为空，不为空则继续
new_page=list_entry(area);//获取area第一个空闲页块的地址
list_del(area);//删除area第一个空闲页块，进行内存分配
struct page *buddy;
//高阶order，将多余的内存添加到对应的链表
if(current_order>0){
current_order--;//高阶order往后依次进行剩余内存的链接
while(current_order>=order){
area = zone->free_area + current_order;//获取要链接的该阶的起始地址
buddy= new_page+power2(current_order);//第一个空闲页块的起始地址加上该阶层应该分配的内存大小就是该阶应该链接上的空闲内存块
list_add(buddy,area);//在该阶添加空闲块
if(current_order==0)//链接完退出
break;
else
current_order--;//链接未完，继续向低一阶链接
}
}
return new_page;//返回该空闲页块的地址
}
}
return NULL;
}
void release_memory(unsigned int order,struct zone *zone,struct page *new_page,struct page *addr){
struct page *temp=NULL;
struct free_area *area=NULL;
struct page *page=NULL;
unsigned int page_count,page_count2;
while(order<MAX_ORDER){
area=zone->free_area+order;
page=area->free_list.next;
page_count=(int)(new_page-addr);
bool buddy_flag=false;
while(page!=NULL){
page_count2=(int)(page-addr);
buddy_flag=(bool)isBuddy(page_count,order,page_count2,order);
if(buddy_flag)
{
if(order==MAX_ORDER-1)
break;
if(temp==NULL)
area->free_list.next=page->lru;
else
temp->lru=page->lru;
area->nr_free--;
if(page_count>page_count2){
new_page=page;
}
break;
}
temp=page;
page=page->lru;
}
if(buddy_flag)
order++;
else
break;
}
list_add(new_page, area);
return;
}
void check_memory(struct zone *zone,struct page *addr){
struct free_area *area;
for(int i=0;i<11;i++){
area=zone->free_area+i;
cout<<"order:"<<i;
cout<<" nr_free:"<<area->nr_free<<endl;
struct page* page=area->free_list.next;
while(page!=NULL){
cout<<" "<<page-addr<<"~"<<page-addr+power2(i)-1<<endl;
page=page->lru;
}
}
}
void check_process(struct page *addr){
map<string,tuple<int,int,struct page*>>::iterator it;
for(it=process_info.begin();it!=process_info.end();++it){
cout<<"ID: "<<it->first<<endl;
cout<<"size:"<<get<0>(it->second)<<"KB"<<endl;
unsigned int order=get<1>(it->second);
cout<<"order:"<<order<<endl;
cout<<"addr:"<<get<2>(it->second)-addr<<"~"<<get<2>(it->second)-addr+power2(order)-1<<endl;
}
}
int main(int argc, const char * argv[]) {
struct zone *zone=(struct zone*)malloc(sizeof(struct zone));
struct free_area *area=NULL;
struct page *addr=(struct page*)malloc(62*1024*sizeof(struct page));
for(int i=0;i<10;i++){
area=zone->free_area+i;
area->nr_free=0;
area->free_list.next=NULL;
}
area=zone->free_area+10;
area->free_list.next=addr;
area->nr_free=64;
struct page *init_page=addr;
for(int i=0;i<63;i++){
init_page->lru=init_page+1024;
init_page=init_page->lru;
}
cout<<"Memory Init Completed!"<<endl;
/*
* check_memory:
* 0
* alloc_memory:
* 1 size process_id
* release_memory:
* 2 process_id
* check_process:
* 3
* quit:
* default
* size 单位为kb
*/
int option;
unsigned int size;
string process_id;
while(true){
cout<<"-For check_memory: 0"<<endl;
cout<<"-For alloc_memory: 1 size(KB) process_name"<<endl;
cout<<"-For release_memory: 2 process_name"<<endl;
cout<<"-For check_process: 3"<<endl;
cout<<"-For quit: default"<<endl;
cout<<"Input your command: ";
cin>>option;
cout << endl;
switch (option) {
case 0:
check_memory(zone, addr);
break;
case 1:{
cin>>size>>process_id;
unsigned int order=order_init(size);
if(process_info.find(process_id)==process_info.end()){
struct page *new_page=alloc_memory(order, zone);
if(new_page==NULL){
cout<<"No enough memory,please release memory first!"<<endl;
}
else{
process_info[process_id]=make_tuple(size,order,new_page);
cout<<"Alloc Memory Completed!"<<endl;
cout<<"ID: "<<process_id<<endl;
cout<<"size:"<<size<<"KB"<<endl;
cout<<"order:"<<order<<endl;
cout<<"addr:"<<new_page-addr<<"~"<<new_page-addr+power2(order)-1<<endl;
}
}
else
cout<<"Process "<<process_id<<" is existed!"<<endl;
break;
}
case 2:{
cin>>process_id;
if(process_info.find(process_id)!=process_info.end()){
unsigned int order=get<1>(process_info[process_id]);
struct page *new_page=get<2>(process_info[process_id]);
release_memory(order, zone, new_page, addr);
process_info.erase(process_id);
cout<<"Process "<<process_id<<" has been released!"<<endl;
}
else
cout<<"Process "<<process_id<<" is not existed!"<<endl;
break;
}
case 3:
check_process(addr);
break;
default:
return 0;
}
cout << endl;
}
return 0;
}
内存分配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。