3

O（1）でメモリを割り当てて解放できるC ++メモリプール（特定のクラスのみ）を設計する方法はありますか？

クラスTがあるとしましょう。必要に応じて、100 * sizeof（T）のチャンクのみを割り当てることを考えていました。しかし、特定のオブジェクトがチャンクで削除されたときに発生する断片化にどのように対処できますか？スロットが占有されているかどうかを判断するために、各スロットにブール値を設定できますが、次の空きスロットを取得するためのアルゴリズムが必要です。

O（1）でこれを実装する標準的な方法はありますか？これはかなり一般的なことだと思います

編集：画像を使用して、私が何を意味するかを確認します 写真

4

3 に答える 3

4

この解決策は、追加のメモリを使用しています（これは、必要なものである場合とそうでない場合があります）。また、チャンクを2回続けて解放しようとすると、問題が発生します。

十分なメモリを事前に割り当てます。オブジェクトごとに1つずつ、チャンクに分割します。空きチャンクのリストを保持します。新しいオブジェクトを割り当てるときは、空きチャンクリストの一番上からチャンクを選択します。オブジェクトを解放するときは、そのチャンクを解放されたチャンクのリストに追加します。これらの操作は両方ともO（1）です。

次のようになります。

初期化：

char* mem = new char[CHUNK_SIZE * OBJ_COUNT];
std::list<char*> free_chunks;
for (char* c = mem, int i = 0; i < OBJ_COUNT; ++i)
{
   free_chunks.push_back(c);
   c += CHUNK_SIZE;
}

割り当て用の新しいチャンクを取得する：

   if(free_chunks.size() > 0)
   {
    char* c = free_chunks.back();
    free_chunks.pop_back();
    return c;
   }
   else{ // Error, not enough memory... }

割り当て解除後にチャンクを返す：

free_chunks.push_back(c);
于 2012-11-09T20:11:54.523 に答える
1

O（1）オブジェクトの取得を使用して、単純なオブジェクトプールを実装できます。ただし、オブジェクトには次のオブジェクトへの内部ポインタが必要です。プールのコンストラクター内でいくつかの事前計算：

pool.reserve(capacity); //std::vector<Object*>
for (int i = 0; i < capacity; ++i) {
    pool.push_back(new Object());
}
for (int i = 0; i < capacity-1; ++i) {
    pool[i]->setNext(pool[i+1].get());
}
first_available = pool[0].get(); //variable where you store first free object 
pool[capacity-1]->setNext(NULL);

次に、getObject方法は次のとおりです。

getObject* getObject()
{
    getObject* obj = first_available;
    first_available = first_available->getNext();
    return obj;
}

void returnObject(Object* obj)
{
    obj->setNext(first_available);
    first_available = obj;
}

それが役に立てば幸い。

于 2012-11-09T20:13:21.360 に答える
1

任意の長さのブロックが要求される一般的なメモリ割り当ての問題に対してのみ断片化があります。ここでの問題は、このメモリレイアウトが与えられた場合です。

@@@@@@---@--@-@@@@

（ここで@、は使用中を-意味し、無料を意味します）

合計6つの空きブロックがありますが、4つの連続ブロックを割り当てることはできません。したがって、管理対象スペースの合計量を増やす必要があります（可能な場合）。また、この一般的なシナリオでは、どのアドレスを選択するかを決定することは簡単ではなく、断片化の程度に影響を与えるいくつかの戦略（ファーストフィット、ワーストフィットなど）があります。

あなたの場合、割り当てたい領域は常に整数のサイズになることがわかっているので、問題は非常に簡単ですk（たとえばk = sizeof(T)）。これは、あなたが好きなように整理する完璧にフィットするブロックを常に持っていることを意味します。空き領域をリンクリストであるかのように処理し、常にリストの最初の項目を使用してメモリ割り当て要求に応答します。

@@@---@@@------@@@@@@@@@---@@@ (k=3)

これで、割り当てを償却するために大きなブロックで割り当てたい場合は、特定のブロックが空になったときにそのブロックを解放するために、特定のブロックで使用されているスロットの数の追加カウンターを保持できます（スロットのリザーバーを縮小したい場合！ ）。

最も使用されているブロックから常に新しいメモリブロックを配布することを主張する場合は、どのブロックが最もいっぱいであるかを示す追加のリストを使用してこれを行うことができます。O(1)使用するスロットの数は常に1つしか変更できないため、隣接するノードを交換するだけで、そのリストを並べ替えておくことができます。

于 2012-11-09T20:38:29.813 に答える