1

練習用に独自の malloc() を作成しようとしています。このスレッドから以下のコードを取得しました。

typedef struct free_block {
    size_t size;
    struct free_block* next;
} free_block;

static free_block free_block_list_head = { 0, 0 };

// static const size_t overhead = sizeof(size_t);

static const size_t align_to = 16;

void* malloc(size_t size) {
    size = (size + sizeof(free_block) + (align_to - 1)) & ~ (align_to - 1);
    free_block* block = free_block_list_head.next;
    free_block** head = &(free_block_list_head.next);
    while (block != 0) {
        if (block->size >= size) {
            *head = block->next;
            return ((char*)block) + sizeof(free_block);
        }
        head = &(block->next);
        block = block->next;
    }

    block = (free_block*)sbrk(size);
    block->size = size;

    return ((char*)block) + sizeof(free_block);
}

void free(void* ptr) {
    free_block* block = (free_block*)(((char*)ptr) - sizeof(free_block ));
    block->next = free_block_list_head.next;
    free_block_list_head.next = block;
}

メモリ チャンクをリンク リストとして扱うことについて混乱しています。基本的に、メモリが必要になるたびに sbrk() を呼び出し、以前に要求したメモリの一部がその間に解放されていないかどうかを確認しているようです。

しかし、他のプロセスに属する他のメモリ チャンクをチェックする方法はありません。以前に要求してリンク リストに追加したメモリのみをチェックします。

もしそうなら、これは最適ですか？これが標準の malloc() の仕組みですか? ヒープ上のすべてのメモリを操作する方法はありますか?

私が 5 歳のように説明してください。この概念を理解するのに苦労しています。

4

1 に答える 1

5

プロセス データ セグメントを拡張しても、他のプロセスには影響しません。ほとんどの (最近の) アーキテクチャでは、プロセス メモリ モデルはフラットです。つまり、各プロセスにはvirtualアドレス空間 (2^32または2^64バイト) があります。プロセスが追加のメモリ (ページ) を要求するvirtualと、プロセスにメモリが追加されます。実際、これは物理メモリの割り当てが発生するという意味ではありません。virtualメモリをスワップ ファイルにマップしたり、使用する前に完全にマップ解除したりできるためです (アドレスはプロセスに指定されますが、実際のリソースは割り当てられません)。virtualカーネルは、必要性やリソースの可用性に応じて、物理アドレスを 1 つにマッピングします。

アルゴリズムは何をしますか？

ユーザーが呼び出すとmalloc、アルゴリズムは利用可能な空のブロックを見つけようとします。最初は何もないため、アルゴリズムはプロセス データ セグメントを拡張しようとします。

ただし、仮想メモリを解放しないことがわかりfreeます (割り当てほど簡単ではないため)。代わりに、このreleasedブロックを未使用ブロックのリストに追加します。

そのため、プレリリースされたブロックがある場合malloc、データ セグメントを拡張する代わりにそれらを再利用しようとします。

標準mallocは上記のように機能しますか: いいえ。あなたが提供した例は単純ですが、実際には非効率的です。メモリ管理にはさまざまなアルゴリズムを使用できます。小さなブロック ヒープ (一定量までデータを割り当てるとO(1)パフォーマンスが向上する場合)、スレッド固有のアロケータ (複数のスレッドからヒープにアクセスする際の輻輳を軽減する)、大きなチャンクを事前に割り当てるアロケータと、次に、それらを使用します（上記と同様ですが、より効率的です）およびその他。

詳細については、「メモリヒープの実装」を試してみてください。

于 2013-04-13T21:41:53.010 に答える