はじめに

本記事は、C言語でよく使われるmallocについて、OSレベルで理解できるようにできる限り簡単に説明した記事です。この記事が理解できれば、mallocはなぜ早いのか、OSってどのようにメモリを管理しているのかがわかるようになります。
構成は、
1. mallocとは
 2. ヒープ領域などのメモリ領域の種類について
 3. プロセスと論理アドレスの関係
 4. ページテーブルとは何か
 5. なぜ論理アドレス空間を使うのか
 6. ページフォールトとは
 7. mallocとcallocの違い
となっています。

筆者の勉強のためにも間違いや分かりづらい箇所がありましたら積極的にコメントをいただけたら嬉しいです。

1.mallocとは

Wikipediaによると、mallocとは、

動的メモリ確保を行うC言語の標準ライブラリの関数である。確保したメモリの解放にはfree関数を使用する。mallocは領域を確保するだけで、その領域は初期化されていない。

とあります。
動的メモリ確保とは、

メモリ管理のひとつである、プログラムを実行しながら、並行して必要なメモリ領域の確保と解放を行う仕組みである。

とありますので、要するに、
mallocは、C言語のプログラム中でメモリの確保が必要になった場合、それをとあるメモリ領域(ヒープ領域)に確保する関数です。
ヒープ領域というメモリ領域はプログラム内でメモリを確保し、プログラム内で解放もできる特別な領域です。

ここで、mallocで動的にメモリを確保すると、その領域はたとえその配列の役目を終えてもヒープ領域に残り続けます。確かにプログラムが終わればメモリは解放されますが、もし大量のメモリをmallocで確保していた場合、他の処理でヒープ領域が必要になった場合にメモリが足りなくなってしまいます。ですので、mallocで確保した配列が不要になった段階で、free関数を呼んでメモリを解放する必要があります。

また、callocは、

メモリ確保と同時に初期化を行う。

とあります。つまり、簡単に言うとmallocは初期化されていないが、callocは初期化されているという違いがあり、これが原因となってmallocよりcallocの方が遅くなっています。本記事では、この部分について深く掘り下げていきます。
(ここで言う「遅い」とは、「mallocの処理が呼ばれてから処理が終わるまでの時間より、callocの処理が呼ばれてから処理が終わるまでの時間の方が遅い」と言う意味で使用しています。)

まずは上記の説明で分かりづらかったであろうヒープ領域について次のセクションで詳しく説明していきます。

2.ヒープ領域などのメモリ領域の種類について

まず、普段書くプログラムで使用するメモリには大きく分けて3つの領域があるということを理解しなければなりません。その3つとは、
・静的領域(大域/静的変数の確保される領域)
・局所領域(局所変数の確保される領域)
・ヒープ領域
です。
静的領域とは、プログラム開始時にメモリに確保され、プログラムが終わるまで解放されないメモリ領域です。グローバル変数などがここに確保されます。
局所領域とは、関数開始時にメモリに確保され、その関数の終了時に解放されるメモリ領域です。関数内で定義された変数などがここに確保されます。
ヒープ領域とは、上記の二つと異なり、確保するタイミングも解放されるタイミングも任意です。つまり、確保したいタイミングでmallocを呼び、不要になったらそのメモリ領域はfreeすることで再利用可能になるということです。
このことを指して動的メモリ確保と呼んでいます。

3.プロセスと論理アドレスの関係

本記事のメインは6章ですが、その章のために3,4,5章で知識を整理しておきましょう。
まず、プロセスについて説明します。
プロセスとは、プログラムが起動した時にできるもので、プログラムを管理する単位のようなものだと思ってください。プログラムを起動すると、論理アドレス空間が生成されるとともに、mainスレッドが生成されます。そしてプログラムが実行されるとスレッドが生成されていきます。即ち、**「プロセス=論理アドレス空間 + スレッド」**です。

さて、わからない単語が出てきました。「論理アドレス」と「スレッド」です。
先にスレッドについて簡単に説明します。

スレッドとは、プログラムの処理の実行単位の一つです。分かりにくいですね。簡単な例を出しましょう。
例えば、あるプログラム内でネットワークのパケットを受信しているとします。同時に複数のところからパケットを受信したい場合、Aという場所からパケットを受信するスレッドと、Bという場所からパケットを受信するスレッドの二つを生成します。すると、この二つのスレッドはまるで別のプログラムで動いているかのように「同時に」「並行して」動きます。通常プログラムは書いてある順に上から一つずつ実行されていきます。しかし、スレッドは複数の処理が同時に行われます。これにより、プログラムは(mainスレッドにより)書いてある順に上から実行されるが、新たなスレッドが生成されると、mainスレッドと同時にそのスレッドも起動し、同時並行でプログラムが処理されます。

また、論理アドレスの説明は物理アドレスと比較しながら説明すると分かりやすいので、比較していきます。

物理アドレスとは、メモリハードウェアが理解するアドレスのことです。可能な物理アドレスは0〜(搭載メモリ量-1)であり、当然各アドレスは計算機に一つだけ存在します。みなさんが「アドレス」と聞いて一番最初に思い浮かべるのがこの「物理アドレス」だと思われます。

対して論理アドレスとは、プログラムが理解するアドレスのことです。可能な論理アドレスは4GB(= 2^32 - 1 B)など、とても大きな値であり物理メモリ量に依りません。また、論理アドレス空間は複数存在し、論理アドレス空間Aの10000番地と論理アドレス空間Bの10000番地が同時に存在し得ます。しかし、それらは同じ物理アドレスやディスクのアドレスとは対応していません。
例えば、


//プログラムA
int main(){
    int *p = 10000;
    printf("%d\n", p); //10000番地にアクセス

    return 0;
}

と、


//プログラムB
int main(){
    int *p = 10000;
    printf("%d\n", p); //10000番地にアクセス

    return 0;
}

としてアクセスする10000番地は、どちらも論理アドレスの10000番地です。しかし、プログラムが理解するアドレスは論理アドレスであり、物理アドレスではありません。なので、プログラムAが10000番地だと思ってアクセスした場所とプログラムBが10000番地だと思ってアクセスした場所は異なっています。

物理アドレスはメモリハードウェアが理解するアドレスです。しかし、実際にプログラムが理解してアクセスする10000番地は、メモリハードウェア的な10000番地ではありません。では、プログラムの10000番地はメモリハードウェアの何番地に対応するのでしょうか？それを記述しているのがページテーブルです(詳しくは4章参照)。

このページテーブルは、プロセスごとに生成されます。つまり、
論理アドレス空間の数 = ページテーブルの数 = プロセスの数
となります。

4.ページテーブルとは何か

3章でいきなりページテーブルというワードを出しましたが、そもそも「ページ」とは何か？何のために使うのかなどが説明されていませんでした。

ページとは、ハードウェアが保護属性、アドレス変換、などを保持する単位で、典型的には4096バイト、8192バイトなどの連続したアドレスの範囲です。保護属性についても話すと少し長くなるので省略しますが、簡単に言うと「ここは読んでいい、ここは読んではいけない」などの設定のことです。

ここではアドレス変換について説明します。
例えば、
プログラムAの10000番地はメモリ上ではどこ？
プログラムAの10001番地はメモリ上ではどこ？
プログラムAの10002番地はメモリ上ではどこ？
プログラムAの10003番地は.....
と逐一覚えていたら正直それだけで異常なほどの容量を食ってしまいます。そこで、連続する4096バイト、8192バイトは同じページであるとして、ページ単位で管理するようにしよう、というのがページの考え方です。例えば、0~4095バイトは1ページ目、4096~8191バイトは2ページ目として管理します。
そして、ページテーブルは、論理アドレス空間IDと論理ページ番号から、そのページがどこの物理メモリ内のページに対応するかを持っているので、その対応づけから本当にアクセスしたい物理アドレスにアクセスできる、ということになっています。
論理アドレス空間内のページは全く同じ形で物理アドレス空間にも存在するので、例えばプロセスAの4097バイト目をアクセスする場合、ページテーブルによって「論理アドレス空間Aの2ページ目」は「物理アドレスの20000番地から始まるページに存在するよ」ということが分かったとします。あとは、プロセスAの4097バイト目は論理アドレス空間Aの2ページ目の2バイト目なので、物理アドレスの20000番地から始まる2バイト目、即ち20001番地にマッピングされる、ということです。

まとめると、ページテーブルとは論理アドレス空間IDと論理ページ番号をキーとして、物理ページ番号(と属性)を値とする表のことです。

5.なぜ論理アドレス空間を使うのか

ここまで読んだら一つとても自然な疑問が生まれると思います。なんでプログラムとメモリで認識するアドレスが異なるの？面倒臭くない？ということだと思います。

答えは様々考えられます。
もし、論理アドレス空間が存在しないと、プログラムは物理メモリ上のアドレスを意識しなければならず、例えば細切れな物理メモリのみが残ってしまっていた場合、大きな配列を確保できないことがあります。しかし、論理アドレス空間を使用すれば、そのような細切れのメモリーを連続した仮想メモリーとしてプログラム側に提供することができるのでそのような事態には陥り辛くなります。

また、論理アドレス空間が存在しないと、複数のプロセスが起動していて、それらが同時に配列を確保しようとした場合、競合発生しやすくなってしまいます。ですので、OSがメモリーを管理することで、この競合状態をできる限り起こり辛くする仕組みというのも備わっています。

他にも、セキュリティの観点からも論理アドレス空間があると良い事があります。
例えば、あるプログラムで使用するデータを他のプロセスからは覗き見られたくないとします。その時に、OSがそのプロセスを他のプロセスと重ならないように割り当てることで、他プロセスはその物理メモリにアクセスできなくなるので、セキュリティが高まるという考え方もあります。

6.ページフォールトとは

さて、3章で論理アドレス空間について説明した際、「論理アドレス空間は4GBなどと、とても大きい」と説明しました。つまり、8つの論理アドレス空間が存在したら、32GB程度になってしまう、ということになります。そして、パソコンの物理メモリの搭載量は大体4~32GB程度に収まることが多いです。
ということは、「8つのプロセスが走り、8つの論理アドレス空間が生成された場合、もうメモリがいっぱいいっぱいになってしまい、それ以上プロセス/論理アドレス空間を生成できない」ということなのでしょうか？

これは当然正しくないです。
まず、8つの4GB論理アドレス空間が存在したら当然32GB程度になってしまい、それらを全て物理メモリ上に置いたら(置けたとしたら)いっぱいいっぱいになってしまいます。
しかし、実際にはたいていのプロセスは4GBも論理アドレス空間を使用していないので、そもそも誤りです。
では、物理メモリを覆い尽くすほどたくさん論理アドレス空間を作成した場合、それ以上プロセスを走らせることはできなくなってしまうのでしょうか？
これも誤りで、「OSはメモリをページ単位で管理している」という事実を思い出すと、「物理メモリ内に乗っているページのうち、あまり使われていないページは二次記憶に待避させ、他のページが物理メモリを使えるようにする」というのが合理的だと考えられます。

実際その通りで、使用したいページがあっても既に物理メモリが一杯の場合は、起動しているプロセスの中でも、最近は使用されていないページを一旦二次記憶(HDDやSSDなど)に待避させて物理メモリに空き領域を作り、そこにその使用するページを入れます(ページイン)。
そして、その二次記憶に待避したページが使用される場面になったら、そのページを再び物理メモリにページインします。同時に、物理メモリ上にあるページのうち、最近は使用されていないものを二次記憶に待避させます(ページアウト)。

このように、「プロセスが起動しているからといって、そのプロセスのページ全てが物理メモリ上に乗っているとは限らず、直近でよく使っているものが優先的に物理メモリ上にあり、使わないものは二次記憶に待避させます。使用する場面が来たら、二次記憶から物理メモリにページインし、逆に物理メモリ上で最近使用していないページを二次記憶へページアウトさせる」という仕組みが成り立っています。

この仕組みにおいて、「使用したいと思ったページが(最近使用されていないせいで)二次記憶に待避させられており、物理メモリ上に存在しないこと」をメジャーページフォールトと呼びます。
ページフォールトとは、「物理メモリに目的のページがあると思ってアクセスしたら、実はなかった」ということを指しますので、メジャーページフォールトは「二次記憶に該当ページがある場合のページフォールト」だと言えます。

メジャーページフォールトがあるということはマイナーページフォールトもあります。
そして、マイナーページフォールトこそが「二次記憶に該当ページがあると思ってアクセスしたが、実はないページフォールト」です。つまり、目的のページが「物理メモリにも二次記憶にも存在しない」のがマイナーページフォールトということになります。

マイナーページフォールトはどのような場合に起きるのでしょうか？
例えばプログラム内で、Mバイトのメモリを要求してアドレスAが返ってきたとします。それは、アドレスA〜A+M-1 のM個の番地を使う(読み書きする)「権利」を得たということであり、ほとんどの場合においてそのアドレスに対応する物理メモリは確保されていません(論理アドレスは確保されます)。そして、「実際にアドレスAに0と書き込んでください」と言われて初めてそのアドレスAが含まれるページを物理メモリ上に確保します。
このように、「あるページを(論理アドレス空間に)割り当ててから初めてそのページのどこかにアクセスした時にページフォールトが発生し、それを受けたOSがそのページに対応する物理ページを割り当てる」時のページフォールトをメジャーページフォールトと区別してマイナーページフォールトと呼びます。
そして、このマイナーページフォールトこそがmallocがcallocよりも圧倒的に速い理由なのです。

7.mallocとcallocの違い

ここまで読めばなぜmallocがcallocに比べて速いか想像がつくと思います。
mallocは、Mバイトのメモリを要求したら、Mバイトを論理アドレス空間にのみ確保し、実際の物理メモリには確保しません。そして、その論理アドレス空間内に確保されたメモリ領域の先頭へのアドレスを返します。そして、実際にそのメモリにアクセスして初めてマイナーページフォールトが起きて物理メモリにページが存在するようになります。

対してcallocは、Mバイトのメモリを要求したら、Mバイトを論理アドレス空間に確保すると同時にそのMバイトに0を代入するので、いきなりマイナーページフォールトを起こし物理メモリの確保が必要になります。そして、その論理アドレス空間内に確保されたメモリ領域の先頭へのアドレスを返します。

以上より、callocはcallocした段階で物理メモリにページを確保しに行くので遅い、対してmallocは実際にその確保したアドレスにアクセスするまで物理メモリにページを確保しない(これをデマンドページングと呼びます)ので速い、と言えます。(しかし、厳密にはデマンドページングを伴わないmallocというのも存在しますが、本記事の趣旨とはずれてしまいますので、割愛させていただきます。)

そして、デマンドページングの仕組みにより、mallocが実際にそのページが必要となりマイナーページフォールトが発生すると、OSはそのページを物理メモリ上に確保しますが、その割り当てたページの値を0で埋めてから、そのページにアクセスしてきたスレッドが再開されます。

この記事の結論として、mallocはデマンドページングの考え方により、実際にページを使用するまで物理メモリの確保を先延ばしにするので、callocと比べると速くなります。