一定時間の操作による賢いメモリ管理?

Question

固定サイズのブロックを含む 2 つの基本的なメモリ割り当て操作を実行できるメモリ セグメント (ファイルのように、必要に応じてサイズを拡大または縮小できる) について考えてみましょう。

• 1ブロックの割り当て
• 以前に割り当てられ、もう使用されなくなったブロックを解放します。

また、要件として、メモリ管理システムは現在割り当てられているブロックを移動することはできません。インデックス/アドレスは変更しないでください。

最も単純なメモリ管理アルゴリズムでは、グローバル カウンター (初期値 0) をインクリメントし、その新しい値を次の割り当てのアドレスとして使用します。ただし、割り当てられたブロックがわずかしか残っていない場合、これではセグメントを短縮することはできません。

より良いアプローチ:カウンタは保持しますが、割り当て解除されたブロックのリストを保持し (一定時間で実行できます)、それが空でない限り、新しい割り当てのソースとして使用します。

次は何？一定時間の割り当てと割り当て解除という制約がある中で、メモリ セグメントをできるだけ短く保つような何か賢い方法はあるでしょうか?

(目標は、現在割り当てられていない最小アドレスのブロックを追跡することかもしれませんが、一定時間内に実行するのは不可能のようです…)

Answer 1

固定サイズのブロックでは、あなたが説明したことは、 フリーリスト. 。これは非常に一般的なテクニックですが、次のような工夫が加えられています。フリー ブロックのリストは、フリー ブロック自体に保存されます。C コードでは、次のようになります。

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

これは、割り当てられたすべてのブロックが同じサイズであり、そのサイズがポインタのサイズの倍数である限り、うまく機能し、位置合わせが保持されます。割り当てと割り当て解除は一定時間です (つまり、メモリ アクセスや基本的な追加と同様に一定時間です。現代のコンピュータでは、メモリ アクセスにはキャッシュ ミスや仮想メモリ、つまりディスク アクセスが含まれる可能性があるため、「一定時間」かなり大きくなる可能性があります)。メモリのオーバーヘッドはありません (追加のブロックごとのポインターなどはありません)。割り当てられたブロックは連続しています)。また、割り当てポインタが指定されたポイントに到達するのは、一度に多くのブロックを割り当てる必要があった場合のみです。割り当てではフリー リストの使用が優先されるため、現在のポインタの下のスペースがクロック フルである場合にのみ割り当てポインタが増加します。そういう意味では、これは、 最適な 技術。

減少中 解放後の割り当てポインタは、より複雑になる可能性があります。これは、予測不可能な順序で空きブロックを検索する空きリストに従うことによってのみ、空きブロックを確実に識別できるためです。可能な場合に大きなセグメント サイズを減らすことが重要である場合は、より多くのオーバーヘッドを伴う別の手法を使用することもできます。割り当てられた 2 つのブロックの間に「穴」を置きます。ホールは、メモリ順に二重リンク リストでリンクされます。ホールの終了位置を知ることでホールの開始アドレスを特定できるようなホールのデータ形式が必要です。また、メモリ内でホールが始まる場所がわかっている場合はホールのサイズも特定できるようにする必要があります。次に、ブロックを解放すると、次の穴と前の穴とマージする穴が作成され、すべての穴の順序付きリストが (定数時間内に) 再構築されます。オーバーヘッドは、割り当てられたブロックごとに約 2 ポインタ サイズのワードになります。しかし、その価格で、「最後の穴」の発生を確実に検出できます。大きなセグメントサイズを縮小する機会です。

さまざまなバリエーションが考えられます。優れた入門書は、 動的ストレージ割り当て:調査と批判的レビュー ウィルソン著 他。

Answer 2

この回答は一般的なメモリ管理手法に関するものです。質問がすべてのブロックが同じサイズである（そして整列している）場合について尋ねていることを見逃していました。

---

知っておくべき基本的な戦略は、first-fit、next-fit、best-fit、および バディシステム. 。私が書いた 短い要約 私が教えたコースで一度だけなので、読みやすいと思います。私はそこを指さします かなり徹底的な調査.

実際には、これらの基本戦略にさまざまな変更が加えられていることがわかります。しかし、これらはどれも実際には一定時間ではありません。限られた量のメモリを使用している間は、最悪の場合それは不可能だと思います。

Answer 3

見てみるのもいいかもしれません 償却分析 特に動的配列。実際には各ステップで操作が一定時間で実行されない場合でも、長期的にはそのように見えます。