内存分配

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