基于一個簡單定長內存池的實現方法詳解

2020-01-26 16:16:46

字體：大中小

來源：轉載

供稿：網友

主要分為 3 個部分，memoryPool 是管理內存池類，block 表示內存塊，chunk 表示每個存儲小塊。它們之間的關系為，memoryPool 中有一個指針指向某一起始 block，block 之前通過 next 指針構成鏈表結構的連接，每個 block 包含指定數量的 chunk。每次分配內存的時候，分配 chunk 中的數據地址。

內存池設計文檔

主要數據結構設計：

Block：

復制代碼代碼如下:

struct block {
    block * next;//指向下一個block指針
    unsigned int numofChunks;
    unsigned int numofFreeChunks;//剩余free的chunk數量
    unsigned int blockNum;//該block的編號
    char * data;
    queue<int> freepos; //記錄可用chunk序號
};

MemoryPool：

復制代碼代碼如下:

class memoryPool {
    unsigned int initNumofChunks; //每個block的chunk數量
    unsigned int chunkSize;//每個chunk的數據大小
    unsigned int steps;//每次擴展的chunk數量
    unsigned int numofBlocks;//當前管理多少個blocks
    block * blocksPtr;//指向起始block
    block * blocksPtrTail;//指向末尾block
    block * firstHasFreeChunksBlock;//指向第一個不為空的block
};

Chunk：

ChunkNum：該 chunk 所在 block 里的編號

blockAddress: 該 chunk 所對應的 block，主要用于 free 這個 chunk 的時候，能夠快速找到所屬 block，并進行相應更新

data：實際供使用的數據起始位置

關鍵操作說明：

內存分配：

從 firstHasFreeChunksBlock 開始查找第一個有 free 位置的 block，如果找到，則則獲取該 block 的 freepos 的隊首元素，返回該元素序號對應的 chunk 的數據地址，并將 freepos 的隊首元素彈出，其他相關屬性更新。如果找不到，則新增 steps 個 chunk，再重復上面的過程。

內存釋放：

傳入待釋放的地址指針p，通過對p的地址移動可以找到chunk中的 ChunkNum 和 blockAddress 兩個數據，通過 blockAddress 可以找到該 chunk 所屬的 block，然后將ChunkNum 添加到該 block 的 freepos 中，其他相應屬性更新。

使用方法：

復制代碼代碼如下:

memoryPool * mp = new memoryPool (256);   
  char * s = (char *)mp->allocate(); 
  // 一些操作 
  mp->freeMemory(s);     
  delete mp;

不足：

沒考慮線程安全問題，該實現方案在單線程下可以正常運行。

程序源代碼：

復制代碼代碼如下:

#include <iostream>
#include <queue>
#include <string.h>
#include <ctime>
using namespace std;

struct block {
    block * next;
    unsigned int numofChunks;//指向下一個block指針
    unsigned int numofFreeChunks;//剩余free的chunk數量
    unsigned int blockNum;//該block的編號
    char * data;
    //記錄可用chunk序號
    queue<int> freepos;
    block(unsigned int _numofChunks ,unsigned int _chunkSize, unsigned int _blockNum){
        numofChunks = _numofChunks;
        numofFreeChunks = _numofChunks;
        blockNum = _blockNum;
        next = NULL;
        data = new char [numofChunks * (sizeof(unsigned int) + sizeof(void *) + _chunkSize)];
        char * p = data;
        //每個chunk的結構：4byte的chunk序號 + 4byte的所屬block地址 + 真正的數據
        for(int i=0;i<numofChunks;i++){
            char * ptr = p + i * (_chunkSize + sizeof(unsigned int) + sizeof(void *));
            unsigned int * num = (unsigned int *)(ptr);
            *num = i;
            ptr += sizeof(void *);
            int * blockpos = (int *) ptr;
            *blockpos = (int)this;
            freepos.push(i);
        }
    }
    ~block(){
        delete [] data;
    }
};

class memoryPool {
public :
    memoryPool(unsigned int _chunkSize = 256, unsigned int _initNumofChunks = 4096, unsigned int _steps = 64){
        initNumofChunks = _initNumofChunks;
        chunkSize = _chunkSize;
        steps = _steps;
        numofBlocks = steps;
        //創建內存池時，初始化一定數量的內存空間
        block * p = new block(initNumofChunks, chunkSize, 0);
        blocksPtr = p;
        for(int i=1;i<steps;i++){
            p->next = new block(initNumofChunks, chunkSize, i);
            p = p->next;
            blocksPtrTail = p;
        }
        firstHasFreeChunksBlock = blocksPtr;
    }
    ~memoryPool(){
        block * p = blocksPtr;
        while(blocksPtr!=NULL){
            p = blocksPtr->next;
            delete blocksPtr;
            blocksPtr = p;
        }
    }

    /*
    從firstHasFreeChunksBlock開始查找第一個有free位置的block，
    如果找到，則則獲取該block的freepos的對首元素，
    返回該元素序號對應的chunk的數據地址，并將freepos的隊首元素彈出，
    其他相關屬性更新。如果找不到，則新增steps個chunk，再重復上面的過程。
    */
    void * allocate(){
        block * p = firstHasFreeChunksBlock;
        while(p != NULL && p->numofFreeChunks <= 0) p = p->next;
        if(p == NULL){
            p = blocksPtrTail;
            increaseBlocks();
            p = p->next;
            firstHasFreeChunksBlock = p;
        }
        unsigned int pos = p->freepos.front();
        void * chunkStart = (void *)(p->data + pos * (chunkSize + sizeof(unsigned int) + sizeof(void *)));
        void * res = chunkStart + sizeof(unsigned int) + sizeof(void *);
        p->freepos.pop();
        p->numofFreeChunks --;
        return res;
    }

    void increaseBlocks(){
        block * p = blocksPtrTail;
        for(int i=0; i<steps; i++){
            p->next = new block(initNumofChunks, chunkSize, numofBlocks);
            numofBlocks++;
            p = p->next;
            blocksPtrTail = p;
        }
    }
    /*
    傳入待釋放的地址指針_data，
    通過對_data的地址移動可以找到chunk中的ChunkNum和blockAddress兩個數據，
    通過blockAddress可以找到該chunk所屬的block，
    然后將ChunkNum添加到該block的freepos中，其他相應屬性更新。
    */
    void freeMemory(void * _data){
        void * p = _data;
        p -= sizeof(void *);
        int * blockpos = (int *) p;
        block * b = (block *) (*blockpos);
        p -= sizeof(unsigned int);
        int * num = (int *) p;
        b->freepos.push(*num);
        b->numofFreeChunks ++;
        if (b->numofFreeChunks > 0 && b->blockNum < firstHasFreeChunksBlock->blockNum)
            firstHasFreeChunksBlock = b;
    }

private :
    unsigned int initNumofChunks; //每個block的chunk數量
    unsigned int chunkSize;//每個chunk的數據大小
    unsigned int steps;//每次擴展的chunk數量
    unsigned int numofBlocks;//當前管理多少個blocks
    block * blocksPtr;//指向起始block
    block * blocksPtrTail;//指向末尾block
    block * firstHasFreeChunksBlock;//指向第一個不為空的block
};

//test
void echoPositionNum(char * p){
    p -= (sizeof(void *) + sizeof(unsigned int));
    int * num = (int *) p;
    cout<<*num<<endl;
}

//測試
void test0(){
    memoryPool mp;
    char * s1 = (char *)mp.allocate();
    char * s2 = (char *)mp.allocate();

    char str [256];
    char str2 [256];
    char str3 [256];
    for(int i=0; i<255; i++) {
        str[i] = 'a';str2[i] = 'b';str3[i] = 'c';
    }
    str[255] = '/0';
    str2[255] = '/0';
    strcpy(s1,str);
    strcpy(s2,str2);
    str3[255] = '/0';
    echoPositionNum(s1);

    cout<<s1<<endl;
    mp.freeMemory(s1);
    echoPositionNum(s2);
    cout<<s2<<endl;
    char * s3 = (char *)mp.allocate();
    strcpy(s3,str3);

echoPositionNum(s3);
cout<<s3<<endl;

}

void test1(){
    clock_t clock_begin = clock();
    const int N = 50000;
    char * s[N];
    int round = 100;
    while(round>=0){
        round --;
        for(int i=0;i<N;i++){
            s[i] = new char[256];
        }
        for(int i=0;i<N;i++){
             delete [] s[i];
        }
    }
    clock_t clock_end = clock();
    cout<<"Time cost/t"<<clock_end - clock_begin<<endl;
}

void test2(){

    memoryPool mp(256);
    clock_t clock_begin = clock();
    const int N = 50000;
    char * s[N];
    int round = 100;
    while(round>=0){
        round --;
        for(int i=0;i<N;i++){
            s[i] = (char *)mp.allocate();
        }
        for(int i=0;i<N;i++){
            mp.freeMemory(s[i]);
        }
    }
    clock_t clock_end = clock();
    cout<<"Time cost/t"<<clock_end - clock_begin<<endl;

}
int main()
{
    test0();
    test1();
    test2();
    return 0;
}

運行結果：