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言語のヒープの管理係が、使用中のブロックを寄せて空きをまとめられない理由は?
正解! だれがどの番地を覚えているかを管理係は知らない。勝手に動かすと、ポインタが別のものを指してしまう。