プログラムを動かす時にメモリがどのように割り当て・解放されるのかをめちゃくちゃわかりやすいイメージ画像で解説してくれるサイト「Memory Allocation」

コンピューター上でプログラムを動作する際に必要になるのがメモリです。プログラム自体をメモリに読み込む必要があるのはもちろん、プログラムが行う動作はほとんど「メモリから値を取りだして計算し、メモリに保存する」であるといっても過言ではありません。プログラムが動作する際にメモリがどのように管理されているのかについて、ベテランプログラマーのサム・ローズさんがブログで解説しています。

Memory Allocation
https://samwho.dev/memory-allocation/

C言語の標準ライブラリには「malloc」と「free」という2つの関数が用意されています。この2つはなんと1979年のUnix v7から存在している歴史ある関数で、mallocがメモリの割り当てを担当し、freeがメモリの解放を担当しています。サム・ローズさんの解説は「この2つの関数の中身を自分で実装する」ことを念頭に進んでいきます。

そして下図がメモリのイメージ画像。1マスが1バイトに対応しており、それぞれのマス目に0～255の数字を保存することができます。今回は話を簡単にするため、メモリが全部で32バイトしかない状態を考えるとのこと。

また、プログラムによって確保されたメモリを濃いオレンジ色で表現することにします。下図は4バイトのメモリが確保されている状態というわけです。一方で、薄いオレンジ色のほうは確保されていないメモリを表現しています。

malloc関数に「何バイト分のメモリを確保したいのか」を渡すとそのバイトぶんのメモリを確保してくれます。例えばmalloc(4)を実行すると、メモリの先頭の4バイト分が使用中になりました。

さらにmalloc(5)、malloc(6)と実行すると対応するメモリが使用中になります。

mallocは「何バイト分メモリを確保すればよいのか」を渡せばOKでしたが、メモリを解放するfreeのほうはメモリの先頭アドレスを指す必要があります。

free(0x4)やfree(0x9)を実行すると対応する場所が開放されました。

この「0x」という表記は16進数表記であることを表す接頭辞です。9までの数字は通常の10進数の表記と16進数で同じ表現になります。

「10」は10進数では2桁になりますが、16進数では「a」と表現されます。

同様に15までの数字はアルファベットで表記されます。

そして16になると桁が上がり、「10」という表記になるわけです。

メモリの番地を16進数で表すとこんな感じ。本来であればすべてのマス目に「0x」という接頭辞を付けるのがよいのですが、スペースの都合で省略したとのこと。

さて、ここまでの知識を使うと自力で「malloc」関数を実装することができるようになります。一番シンプルな実装として、「空きブロックの先頭の番地を保存しておき、そこから必要な分だけメモリを確保し、確保した一番最後のメモリの次の番地を保存する」という実装を考えてみます。まずmalloc(4)を実行すると4バイト分のメモリを確保した後、その次の番地に目印が移動しました。

この実装では、メモリを割り当てる際には問題ないものの、「どこからどこまでが1ブロックなのか」という情報がないためメモリを解放することができません。プログラムの使用中に際限なくメモリの使用量が増えていくため、欠陥のある実装といえそうですが、動作が非常に軽いため、あらかじめメモリの使用量がわかっている場合には効率的な実装となる場合があるとのこと。

しかし一般的なメモリアロケーターを実装する場合にはメモリを解放する機能が必須です。今度はすべての割り当てられたメモリおよび空きメモリの番地とサイズを「割り当てリスト」「空きリスト」に保存してみます。最初は空きリストに「0x0番地、32バイト分」という情報が入っているというわけ。もちろん、「割り当てリスト」「空きリスト」の保存にもメモリが必要ですが、今回は別の場所に保存していると考えます。

mallocが呼び出されると、空きリストを上から順番に必要なメモリの量が確保できるところまで探してメモリを割り当て、割り当てリストに登録します。

割り当てリストを見れば何バイト分のメモリを解放すればよいのかがわかるため、freeを実行することが可能になりました。解放したメモリは空きリストに登録します。

この実装ではメモリの割り当て・解放を繰り返すとどんどん1ブロックの大きさが小さくなっていき、全体で見ると大きなメモリが空いているのにメモリを割り当てられないという問題が発生します。

そこでメモリの解放時に空きリストを確認し、隣のブロックが空いていれば結合(Coalescing)するように修正しました。

完璧なメモリアロケーターが完成したかに思えましたが、まだ問題が残っています。下図のように、メモリの割り当て・解放を繰り返していると「小さすぎて使いにくい」ブロックが出現します。これをメモリの断片化(fragmentation)といいます。mallocした際に割り当てられたメモリの番地がプログラムに保存されてfreeの指定に利用されるため、メモリアロケーター側で勝手にメモリの配置を変えることはできません。

こうした断片化を防ぐためにさまざまな手法が開発されています。例えば下図は「小さいバイト数のメモリを確保するような命令があった際に最低でも4バイト分を確保する」というもの。断片化が起こりにくくなりますが、必要なメモリの量が実際に利用しているメモリの量以上になるというデメリットが存在しています。

別のアプローチとして、小さい割り当て用に別の領域を確保するという手法も存在しています。この手法でも断片化を抑えることができますが、まとまった大きい割り当てが必要な際に使える領域が減ってしまうという欠点があります。なお、このアプローチを採用したアロケーターのことをスラブアロケーターと呼びます。実際には大小2種類の領域だけでなく、さまざまなサイズに対応した領域を用意して利用するとのこと。

ここまで話に出てきませんでしたが、mallocで0を指定した場合についても考えてみます。最低でも4バイト確保する単純な実装の場合、malloc(0)が呼び出された回数分だけ4バイトの領域が確保されていきかなりのメモリが無駄に消費されてしまいます。一方で、メモリアロケーターの実装によってはmalloc(0)の実行時に一貫して「ヌルポインター」を返すものもあるとのこと。プログラムがヌルポインターを指定して読み書きを実行しようとするとクラッシュしてしまうため、どちらの場合でも「malloc(0)」を使ってはいけないと述べられています。

さて、ここまでのメモリアロケーターの実装はメモリの別の領域に保存した「割り当てリスト」と「空きリスト」を利用していました。こうしたリストを利用しないアプローチも存在しています。例えば下図は割り当てのない空き領域ですが、その空き領域の前後にその領域の情報が保存されています。先頭と末尾の「29」は領域のバイト数で、2マス目の「1」はその領域が未使用であることを表しています。一見、領域のバイト数が先頭と末尾に保存されているのは無駄なように感じますが、領域を結合する際に重要になってくるとのこと。

ここに4バイト分のメモリを確保する場合、メモリアロケーターはメモリの先頭から領域を確認していき、十分なスペースの空き領域を見つけるとそこに新たな領域を作成します。

もう一回4バイトの領域を確保すると下図のようになります。

このアプローチの利点は、メモリを解放する際に先頭+1番地のフラグを「1」にセットするだけでよいという点です。

メモリを解放する際には前後のメモリの使用状況を確認し、空いている領域があれば結合する必要があります。末尾にも領域の大きさを保存することで、前の領域のどこを見ればメモリの利用状況を確認できるのかがわかるというわけです。

すべての領域が空いたため、結合されて最初の状態に戻ってきました。

サム・ローズさんはAllocator Playgroundというツールを公開しており、この記事で登場したさまざまなメモリアロケーターの実装を確認できるようになっています。また、Hello Worldなどのシンプルなプログラムの動作の際にメモリがどのように利用されるのかをイメージ図で理解できるようになっているため、気になった人はのぞいてみてください。