C Academy · レッスン

空きリストと再利用

Q: 「空きリストと再利用」で何を学びますか？

ブロックを追跡して再利用します。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

ブロックを追跡して再利用します。

レッスン 3/413 ステップ

「空きリストと再利用」はCoddyKit上の無料C Academyレッスンです。これはレッスン3/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。

バンプアロケータの先へ

個々のブロックを解放して再利用するには、管理情報が必要です。フリーリストは利用可能なブロックをつないだリストで、アロケータは新しいメモリを取得する前にこのリストを検索します。

各ブロックにはヘッダーがあり、アロケータはそこからサイズと、リスト内の次のブロックへのリンクを取得できます。

リンク付きブロックヘッダー

ヘッダーに next ポインタと free フラグを追加します。これにより、プールがたどって移動できるブロックのリストになります。

ペイロードはメモリ上でヘッダーの直後に続きます。

typedef struct block {
    size_t size;          /* payload bytes */
    int free;             /* 1 if reusable */
    struct block *next;   /* next block in pool */
} block_t;

1つの大きな空きブロックの初期化

起動時には、プール全体が1つの巨大な空きブロックになっています。アロケーション時にはこれを分割し、解放時にはブロックを再利用可能としてマークします。

リストの先頭は、アリーナ全体を覆うこの初期ブロックです。

static unsigned char pool[4096];
static block_t *head;

void heap_init(void) {
    head = (block_t *)pool;
    head->size = sizeof(pool) - sizeof(block_t);
    head->free = 1;
    head->next = NULL;
}

First-Fit検索

最も単純な再利用戦略はfirst-fitです。リストをたどり、必要な大きさ以上の最初の空きブロックを返します。高速で、前方に小さなブロックが集まりやすいという特徴があります。

代替方式には、十分なブロックの中で最小のものを選ぶbest-fitと、worst-fitがあります。これらは速度とフラグメンテーションの傾向とのトレードオフになります。

block_t *first_fit(size_t size) {
    for (block_t *b = head; b; b = b->next)
        if (b->free && b->size >= size)
            return b;
    return NULL;
}

空きブロックからのアロケーション

適合するブロックが見つかったら、使用中としてマークし、ヘッダーの直後を指すポインタを返します。ここではブロック全体を渡します。分割については次のレッスンで扱います。

返されるポインタは block + 1 で、呼び出し側からヘッダーを隠します。

void *my_alloc(size_t size) {
    block_t *b = first_fit(size);
    if (!b) return NULL;
    b->free = 0;
    return (void *)(b + 1);
}

ブロックの解放

解放するには、ユーザーポインタからヘッダーまで戻り、freeフラグを反転します。これで、次回の検索で再利用できるブロックになります。

ペイロードからヘッダーを復元する方法は、先ほど見た1ステップのポインタ操作と同じです。

void my_free(void *p) {
    if (!p) return;
    block_t *b = (block_t *)p - 1;
    b->free = 1;
}

隣接する空きブロックの結合

解放するだけでは、プールに小さな空きブロックが多数残ります。Coalescingでは、解放したブロックの次のブロックも空いていれば両者を結合し、より大きな連続領域を作り直します。

これにより外部フラグメンテーションを抑え、今後の大きな要求にも対応できるようになります。

void coalesce(block_t *b) {
    if (b->next && b->next->free) {
        b->size += sizeof(block_t) + b->next->size;
        b->next = b->next->next;
    }
}

実行可能なフリーリストのデモ

この完成したプログラムは、プールを初期化し、2つのブロックを割り当て、最初のブロックを解放します。その後、より小さな要求に対してそのブロックを再利用し、フリーリストが機能することを確認します。

#include <stdio.h>
#include <stddef.h>

typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;

void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }

int main(void){
    heap_init();
    int *a = my_alloc(sizeof(int));
    *a = 7;
    printf("a=%d free=%d\n", *a, head->free);
    my_free(a);
    printf("after free: free=%d\n", head->free);
    return 0;
}

検索のコスト

単方向のフリーリストでは、アロケーションの計算量はブロック数に対してO(n)です。アロケーションが多くなると、処理は遅くなります。

実際のアロケータでは、サイズごとのビンに分けた分離フリーリストや木構造を使い、検索をほぼO(1)にします。再利用という原則は変わりません。

/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */

二重解放と破損

ブロックを2回空きとしてマークしたり、ブロックのサイズを超えて書き込んだりすると、隣接するヘッダーが破損します。次の検索では壊れた next ポインタをたどることになり、クラッシュします。

Cのメモリバグが非常に危険なのはこのためです。アロケータ自身のメタデータが、データのすぐ隣に置かれているのです。

再利用を組み合わせる

機能するフリーリストアロケータには、初期化、適合ブロックの選択戦略、allocate、free、そして結合が必要です。これらにより、メモリは際限なく増え続けるのではなく、プール内を循環します。

残る改良点は、大きすぎるブロックの分割とアラインメントへの対応です。これは最後のレッスンのテーマです。

クイックチェック

フリーリストがひどくフラグメント化するのを防ぐものについて考えてみましょう。

対話的なレッスンで答える

まとめ

フリーリストはヘッダーを使ってブロックをつなぎ、個々のアロケーションを解放して再利用できるようにします。First-fit検索でブロックを見つけ、解放時にフラグを反転し、結合によって隣接ブロックをまとめてフラグメンテーションを抑えます。

線形検索の計算量はO(n)です。実用的なアロケータでは速度向上のためサイズごとにビン分けします。次は分割とアラインメントを追加します。

無料で開始

AI チューターと学ぶ C — 無料

ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。

コース: 39
レッスン: 144

無料で学習を始めるコース全体を表示

よくある質問

「空きリストと再利用」レッスンは無料ですか？

はい。「空きリストと再利用」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。

「空きリストと再利用」で何を学びますか？

ブロックを追跡して再利用します。ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン3/4です。

「空きリストと再利用」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC Academyレッスンでコードを書いて実行できますか？

はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← C Academyに戻る