なぜ「スタック」と「ヒープ」の2つのデータ構造しか持たないのですか？

Question

なぜ「スタック」と「ヒープ」の2つのデータ構造しか持たないのですか？ int型の値はスタックに格納され、同様に参照型の値はヒープに格納されます。

他のデータ構造を使用できないのはなぜですか？これらのスタックとヒープを2つだけ使用する特別な理由はありますか？

ありがとうございます。

Answer 1

スタックはデータ構造です。ヒープはデータ構造ではありません。ヒープにスタックを作成することができます。

実際、あなたがそれらを記述しているように、それらはMEMORY ALLOCATIONスキームです。プログラミング言語のユーザーは第3のメカニズム：静的割り当て。

プログラミング言語の背後にいれば、ヒープはちょうどメモリです。スタックは単なるメモリです。スタックをスタックにする唯一のことは、メモリが最後に最後に割り当てられることです。どのメモリもスタックにすることができます。

手直しのようですね。

実行可能ライブラリファイルと共有ライブラリファイルは、実際にはローダーに何をすべきかを指示するプログラムです。プログラムを実行すると、実行可能ファイルはローダーにメモリのページを割り当てるように指示します。このメモリは、通常、読み出し専用（静的データ）、読み出し/書き込み（初期化されたプログラムデータ）、読み出し/書き込み要求ゼロ（スタティックデータはゼロに初期化され、スタックとして。EXEは、このブロックの（に近い）先頭に登録スタックポインタを置くローダーに指示します。

注プログラムが起動何のヒープがないこと。

をプログラムが開始されると、メモリ通常はプログラム内に1つしか存在しませんが、複数のメモリマネージャを持つことは可能です。これらのメモリマネージャはヒープになるメモリの読み書きページを割り当てます。

アプリケーションがメモリマネージャを使用してメモリブロックを割り当て、それをプログラムスタックにすることはまったく可能です（まれですが、さまざまなアルゴリズムのアプリケーションスタックを割り当てるのが一般的です）。

スタックは一般的なデータ構造です。 プログラムスタックは、スタックポインタレジスタによって管理されるスタックです。 スタック自体は単なる読み出し/書き込みメモリのブロックです。

ヒープは、メモリマネージャによって制御される単なるブロックまたは読み書き可能なメモリです。メモリマネージャは確実にヒープ上にデータ構造を課すが、その構造はアプリケーションには見えない。すべてのアプリケーションは、アドレス空間にページが追加されたことを認識します。

動的メモリ割り当てには2つのレベルがあります。

1. オペレーションシステムからページ割り当てメモリマネージャから
2. ブロック割り当て。

メモリマネージャは＃2のサービスコールにコールする必要があります。一般に、メモリマネージャから割り当てられたメモリは、「動的」であるとみなされます。

ただし、アプリケーションに読み込まれたページは動的でもかまいません。プログラムローダーがアプリケーションの初期状態を設定している間、アプリケーションはページを割り振って解放することによってページレイアウトを変更できます。ほとんどのシステムでは、アプリケーションはアプリケーションローダによって作成されたページを解放することもできます（しかし、クラッシュを引き起こす可能性があります）。

集計： 1.アプリケーションは、読み取り専用、読み取り/書き込み（初期化済みまたは要求ゼロ）、および読み取り/実行用のメモリーページを持つことができます。 2.任意のページをプログラムスタックにすることができます（ただし、読み書きする方が良い）。 3. 1つ以上のメモリマネージャは、読み書き可能なページを割り当ててヒープに使用することができます。

Answer 2

メモリ割り当てのコンテキストでの「スタック」と「ヒープ」はデータ構造ではありません。スタックレイアウトは、スタック/ヒープ（それぞれ）で実装することも、実装することもできないメモリレイアウトスキームです。

これら2つのメモリレイアウトスキームの存在は、メモリの2種類の必要性に由来する：機能のみの寿命の持続時間のために存在する

1. メモリ、そのような関数パラメータ、ローカル変数として、および戻り値。
2. 無期限に存在し、関数が終了しても保持されるメモリ。

のは2例を考えてみましょう：

スタティックメモリ割り当て

まず、我々は唯一のパラメータと入力を取り、出力として、いくつかの値を返し、ローカルを使用していない機能を扱っていた場合を想像変数。関数の開始前に何らかの方法でパラメータを格納し、関数が存在すると戻り値を格納するメモリが必要です。このためのデータ構造の自然な選択はスタックです。新しい関数が呼び出されるたびに、新しいスタックフレームがスタックに配置され（ランタイムスタックと呼ばれます）、パラメータがプッシュされます。関数が存在するときはいつでも、そのスタックフレームはスタックからポップされ、その戻り値はその呼び出し側が読むことができるようにプッシュされます。

このスキームを拡張して、ローカル変数をサポートすることができます。定義によって、「ローカル」である変数は、関数の存続期間中のみ存在します。このため、関数は非常にうまく収まるので、関数のスタックフレームにそれらのためのスペースを割り当てることができます。

このスタックは、連続した配列やリンクされたリストなど、さまざまな方法で実装できますが、最終的にスタックとして機能し、上部にプッシュ/ポップする機能しかありません。この制約は、関数と関数呼び出しの仕組みの性質のために受け入れられます。 - 呼び出し元のすべての関数が完了する前に関数を終了することはできません。結果として、積み重ねの最上部にない位置でスタックフレームを削除する必要はありません。 - 現在実行中の関数だけが新しい関数呼び出しを行うことができます。その結果、スタックの上部以外の位置にスタックフレームを追加する必要はありません。

動的なメモリ割り当て

に第二に、我々はそれを定義した関数の寿命にバインドされていないいくつかの無期限のために存在することができるように必要なメモリを持っています。これは、過多の方法で行うことができます。分割されて何らかの形で割り当てられた連続した配列（最終的にRAMがどのように動作するか）、リンクされたリストまたはツリー構造になる可能性があります。 A heapは一種の木ですが、これは偶然です。ヒープという用語は、動的メモリ割り当てに関係しているため、混乱したものの集合である「束」や「積み重ね」という意味です。メモリの寿命のための第三の選択肢はありませんので

サードケース

は、存在しません。彼らは関数の存続期間に拘束されているか、そうでないかのどちらかです。第3のメモリ割り当て方式は、最初の2つのケースでカバーされていない第3の要件がある場合にのみ存在します。