🧠 メモリのしくみクエスト
STAGE 5 ― ヒープ ―
クリア 0 / 10
🧭 地図
STAGE 5

ヒープ

必要なときに借りて返す
🎯 ミッション
スタックとヒープの使い分けと、断片化が起きる理由を説明できるようになろう。ヒープで「空きは足りるのに借りられない」状態を作り、確認クイズに全問正解すれば合格。
未達成
ねこ博士
前のステージの最後で、スタックに置けないものが2種類あると言ったね。
うさ美
実行してみるまで大きさが分からないものと、関数が終わったあとも残しておきたいもの、でした。
ねこ博士
たとえば、ユーザーが入力した文章をしまうとき。何文字入力されるかは、プログラムを書くときには分からない。あるいは、ゲームで敵キャラクターが出てくるたびに、その敵の情報を作り、倒されるまで残しておきたい。敵を作る関数が終わったとたんに消えてしまっては困る。
うさ美
スタックの板は、関数を呼ぶときに大きさが決まっていて、関数が終わると消える。どちらにも合いません。
ねこ博士
そこで、メモリの中に、好きなときに好きな大きさを借りて、要らなくなったら返すための広い場所を用意しておく。これをヒープと呼ぶ(heap は「山積み」という意味)。C言語では、借りるときに malloc(memory allocation の略)、返すときに free を使う。
p = malloc(100); 100バイトを借りる。借りた場所の先頭の番地が返ってくる free(p); 借りていた場所を返す。返した場所は、次に誰かが借りるときに使われる
うさ美
借りたら、番地が返ってくるんですね。名前ではなく番地。
ねこ博士
そう。ヒープの場所には変数の名前が付いていない。だから、借りたときにもらった番地を、どこかに覚えておかないといけない。その「番地を覚えておく変数」がポインタで、次のステージで詳しく見るよ。今日はヒープそのものの性質を調べよう。
ねこ博士
ヒープの管理係(メモリアロケータと呼ぶ)は、どこが使用中でどこが空いているかの名簿を持っていて、「100バイト」と頼まれたら、100バイト続いた空きを探して貸す。
うさ美
続いていないとだめなんですか? 50バイトずつ2か所でもいいような。
ねこ博士
借りた側は「先頭の番地から100バイト」を、番地を1つずつ増やしながら使う。途中で別の場所に飛ぶことはできないんだ。だから、必ずひと続きで貸さないといけない。それが、ある困った現象を生む。16マスのヒープで考えよう。A・B・C・D の4人に、前から4マスずつ貸した。そのあと B と D が返した。空きは何マスで、6マスのかたまりは借りられるかな。
うさ美
空きは B の跡の4マスと D の跡の4マスで、合計8マス。でも B の跡と D の跡のあいだには C がいるので、続いている空きは最大4マス。6マスは借りられません。合計では足りているのに。
ねこ博士
空きが細切れになって、大きなかたまりが借りられなくなる。これを断片化(フラグメンテーション)と呼ぶ。
ねこ博士
ヒープの管理係は、断片化を減らすために、同じくらいの大きさのものを近くに集めたり、返された空きが隣り合ったらつなげて大きな空きにしたり、いろいろな工夫をしている。
うさ美
使っているブロックを寄せて、空きを1か所にまとめればいいのに。
ねこ博士
寄せられない理由があるんだ。借りた側は、ブロックの番地をポインタに覚えている。管理係が勝手にブロックを動かすと、その番地が指す先が、別のものになってしまう。C言語では、だれがその番地を覚えているかを管理係は知らないので、動かせないんだ。(STAGE7 で見る、自動で片付けをする言語の中には、番地を書き換えながら寄せられるものもある。)
うさ美
スタックとヒープ、どちらも使えるときは、どちらがいいんですか?
ねこ博士
使えるならスタックのほうが速い。スタックは一番上の番地を動かすだけで積み下ろしできるけれど、ヒープは空きを探したり名簿を書き換えたりする手間がかかる。それに、スタックは関数が終われば自動で片付くけれど、ヒープは返すのはプログラムの責任だ。
スタック:大きさは翻訳時に決まる・関数が終わると自動で消える・速い ヒープ:大きさは実行時に決められる・返すまで残る・空きを探す手間がある・返すのはプログラムの責任
うさ美
返すのを忘れたら、どうなるんですか?
ねこ博士
それが STAGE7 の話だ。その前に、借りた場所をたどるための道具、ポインタを見よう。

確認クイズ

Q1. スタックではなくヒープに置くべきものは?

Q2. 断片化とはどんな状態?

Q3. C言語のヒープの管理係が、使用中のブロックを寄せて空きをまとめられない理由は?