ヒープ領域とスタック領域の違いについて教えてください
ひとまず以下の疑問があります。
- いつ確保されるのか
- どちらが早いのか
- サイズはいつ決定されているのか
- スタックに確保されているAuto変数とはなにか
- ヒープ領域はなぜ、双方向リストによって構成されているのか
- スタック領域のデータ構造はどのようなものなのか
追記
- なぜ、データ構造に違いを与えたのか
ヒープ領域とスタック領域の違いについて教えてください
ひとまず以下の疑問があります。
追記
(一般的な話を書いたら長文になってしまいました。)
プログラムが実行時にどうメモリを使うか、については色々なやり方があって、実際に色々試されて来たのですが、その中で定番になったのが、データを寿命によって次のとおり分類する方法です。
Cの仕様では寿命をstorage durationと呼び、上の分類はそれぞれstatic、automatic、allocatedと呼んでいます。C型の言語はこのモデルを踏襲していることが多いです。そのため、現在ではOSやシステムライブラリのレベルでこのモデルをサポートすることが多くなりました。ここでもその名称を使います。 (ここでのstaticは、Cのキーワードとしてのstatic
とちょっと意味が違うので混同しないでください。Cで言うstatic変数とグローバル変数を含みます。)
staticなデータ領域については、コンパイル・リンクした時点でデータそれぞれに必要な大きさがわかりますから、メモリ上の相対位置も決めておくことが出来ます。OSがプログラムをロードした時点でその領域に必要なメモリが割り当てられます。
automaticなデータ領域は、関数の実行開始時に作り、抜ける時に破棄できます。この特徴はデータ構造としてのスタックと相性が良いのです。関数に入る時に必要な領域を「積み」、抜ける時にそれを取り除きます。呼び出しがネストしても必ず最後に積んだものから取り除けます。スタック構造は管理も簡単で(先頭のデータ位置さえ覚えておけば良い)、キャッシュとの相性も良く、automaticなデータをスタックで管理するのが一般的になり、スタック領域と呼ばれるようになりました。(歴史的には、メモリが貴重だった時代にはautomaticに相当するデータをリンクトリストで管理するシステムもあり、必ずスタックを使わねばならないということはありません。automaticなデータを管理するもっとも一般的な方法がスタックだ、ということです。)
最近の一般的なOSでは、スレッドごとにスタック領域が設定されます。スレッドが作られた時にあらかじめ決められた大きさの仮想メモリ領域が割り当てられ、そこを使います。使い切ってしまうと例外となることが多いです。言語と処理系によっては、割り当てられた領域を使い尽くしたら領域を拡張したり、一部を次に述べるヒープに自動的に移すものもあります。
そして最後のallocatedなデータ。これは、ある関数で確保して、その関数が戻っても使いつづけたい、というようなデータなので、automaticな領域に置くわけにはいきません。また、実行開始前にはどのくらい必要かわからないので、あらかじめ場所を決めておくわけにもいきません。そこで、メモリ空間の一定部分をこのデータ用にとっておき、必要に応じてそこから切り出して使います。データが作られる順番と破棄される順番はばらばらなので、どの順番で破棄されても良いように、データ構造に工夫が必要です。双方向リストを部分的に使うことも多いですが、この部分はプログラムの性能に大きな影響を与えるので、色々な工夫があります。ともかく、このallocatedなデータ用の領域をヒープ領域と呼びます。
ヒープはどのくらい大きくなるか事前にわからないので、手持ちが足りなくなったらOSからある程度まとまった単位でメモリをもらって拡張してゆく、というのが一般的です。
組み込み用などメモリが限られている場合は、プログラムをロードしてstaticなデータ領域を確保したら、残りのメモリをヒープ・スタック兼用として、メモリのアドレスの上の方からスタックとして使い、下の方からヒープとして使ってゆく、なんてやり方もあります。この場合、それぞれの領域の大きさはあらかじめ決まってはいないことになります。
プログラミング言語によっては、言語上はstatic、automatic、allocatedの区別をせず、「すべてのデータは永遠の寿命を持つ」と規定されているものもあります。現実にはそれだとメモリが足りなくなりますが、どこからもアクセスできなくなったデータはこっそり回収してしまってもプログラムの動作に影響を与えないので、そうやってシステムの方が面倒を見てくれます。現代のアーキテクチャではヒープとスタックのモデルが効率良く実行できるので、言語処理系が自動的にデータの使われ方を解析して、裏でデータをヒープとスタックにうまい具合に振り分けてくれるようになっています。
メモリ領域にはテキスト領域、静的領域、ヒープ領域、スタック領域の4つの領域がある。
テキストはプログラム、静的はグローバル変数やstatic変数、スタックは装飾しのないローカル変数、ヒープは動的に確保できる
ここでプログラムやグローバル変数は利用する数や処理が確定すれば、プログラム中でサイズが変化することはない、スタックはOSやコンパイラがサイズを指定しているため定まったサイズが与えられる、ヒープはプログラム中で確保や廃棄されるため可変となる。
スタックではプログラムの変数の宣言の直後に、確保し}
に到達すると廃棄される、これは関数を多く呼び出す構造をもたせた時、変数はスタックと同じ動作になる。正確にはブロックや関数毎に管理される。
ヒープ領域では動的確保なのでmalloc
やnew
によって確保され、free
やdelete
によって廃棄される。
スタックのほうが高速、ヒープは複雑でOSの処理が挟まれる分遅い。
また、最適化の影響を受けやすい静的領域やスタック領域ではより高速なキャッシュへデータが確保されやすい。
スタック領域はコンパイラやOSがサイズを決めています。そのため、実行時には確定しています。
ヒープ領域はmalloc内でシステムコールを呼び出し確保できた時にサイズが確定します。失敗した場合は確保されません。
自動(Auto)変数のこと。文中のブロックを抜けると自動的に開放される変数のこと。
OSのメモリ管理に使われているデータ構造のため。ヒープ領域はmalloc内のシステムコールでOSにより確保されている、メモリ管理のデータ構造はリストの構造として与えられる利用時はアドレスが連続しているようにOSにより見せられるため意識する必要はない。OSのアドレスとのプログラムでのアドレスとの差を埋める方法としてはアドレッシング・モードがある。
スタック。削除するとき最後に入ってき関数を削除する。関数毎にスタックフレームとして管理される。スタック領域を全て使用し切るとスタックオーバーフローとなる。
確保を担当しているプログラムの違いがデータ構造に違いを与えているため
特に主記憶ではスワップが必要になるためOSとしてはリストを利用したほうが計算オーダーが少なく済む。
スタックとヒープの違いを、使い方とデータ構造から説明します。
スタックは手続きの呼び出しで利用されます。手続きが呼び出されると、呼び出された手続きのローカル変数を格納するためのフレームがスタック上に生成されます。手続きからリターンすると、そのフレームも不要になります。メモリ領域の確保と解放のタイミングは、後から呼び出された手続きのフレームほど先に解放されます。
従って、スタックを実装するデータ構造としては、先入れ後出し(FILO)のデータ構造である「スタック(同じ名前なのでややこしいかもしれませんが)」がスタックを実装するのに利用されます。
これに対して、ヒープに確保されるメモリ領域は、確保と解放にこのような一定の順序がありません。先に確保したメモリ領域が先に解放されることもあります。そのため、メモリ領域を確保した順序に関係なく解放できる必要があります。
従って、ヒープを実装するデータ構造としては、途中の要素をいつでも削除できるデータ構造であるリストなどが利用されます。
質問がズレてきてしまっているのかもしれないので、最初の質問文「ヒープ領域とスタック領域の違いについて教えてください」に答えてみようと思います。
メモリ領域は元々は1つですがそれでは扱い辛いため、任意サイズ・ブロックに切り出し、使用・未使用を管理することで便利になります。この管理自体や切り出されたブロックのことをheapと呼びます。このメモリブロックをどのように使うかは利用者側の自由です。
グローバル変数(この用語自体、言語毎に定義されるもので一般化し辛いところですが)などはheapに内容を格納したりもします。
一方、プログラムは一般に呼び出し、戻りの繰り返しであり、グローバル変数のように常に特定のメモリを参照するわけにはいきません。例えば再起呼び出しなら呼び出し毎にそれぞれ異なるローカル変数が必要なはずです。そのような場合、stack(LIFO: Last In First Out)での管理が適切です。ですので、heapの1ブロックをstackとして用います。(heapをどのように使うかは自由です。)
さてheapは全てのメモリ・最大限格納可能な領域なのに対し、stackはあくまでheapの1ブロックにすぎないという点が問題になってきます。多量のローカル変数が必要とされていてもstackには入りきりません。そこで使われるのが、heapにデータを格納しそのheapのアドレスだけをstackに格納するという手法です。
以上がおおよその一般論です。この前提を踏まえて、各言語及び言語の実装ではどのようにメモリ管理していくのかが決められていきます。例えばC++言語ではnew演算子を使用した場合はheapに格納しアドレスを返す、ローカル変数は全てstackに格納する、もしくはC#言語では参照型(class)はheapに格納し、値型(struct)変数はstackに格納する、といった具合です。
あと1点、heapが双方向リストで管理される、というのもあくまで実装の1つに過ぎません。現実的には単方向リストの方が多いようにも思います。