私のコンピュータの1つで、最新のアップデートを含む64ビットArch Linuxを実行しています。私は現在コンピュータサイエンスを専攻しており、昨日の接続リストを使用して動的スタックを実装するテストを行いました。私は私のコンピュータでスタックがどのように構築されているのか理解したいのですが、私のArch Linuxコンピュータで "stack.c"というコメントが見つかりません。スタックプログラミングはどこにありますか?スタックがどのようにメモリを生成するかを理解していますが、実際にコードを見て自分で試してみたいです。
答え1
「スタック」という言葉が多すぎる。いくつかの可能な説明は次のとおりです。
- 「スタック」は抽象的な埋め込み要素へのLIFO(後入れ先出し)アクセスを提供する一連のデータ構造。
- 持つ達成する「スタック」抽象化。クラスで開発された接続リストベースのスタックは、そのような実装の1つです。これが唯一の悟りではありません。たとえば、配列を使用してスタックを構築することもできます。
- ランタイムアクティベーションスタック(プログラム内のスレッドの実行中に関数の呼び出しと戻りを管理するために使用されるスタック)は、「スタック」抽象化の別の実装です。これは配列ベースのスタックのように動作します。
(3)によると、プログラムで実行されている各スレッドにメモリ「ブロック」が割り当てられています。関数がこれらのスレッドから呼び出されて返されると、スレッドに関連付けられたスタックから「スタックフレーム」(スタックのランタイムアクティベーション「要素」)をプッシュしてポップします。スタックフレームに含まれる内容の詳細は、ハードウェアアーキテクチャによって異なります。通常、スタックフレームには以下が含まれます。
- 発信者の返信アドレス
- 関数のパラメータの一部または全部(ハードウェアアーキテクチャ、パラメータ数、およびサイズによって異なります)
- 関数内で定義されたローカル変数です。
- 関数が使用するが関数が返される前に値を復元する必要があるレジスタの状態。
引数の数、関数内のローカル変数の数とサイズ、保存する必要があるレジスタが関数ごとに異なるため、スタックフレームには一定のサイズはありません。
stack.c
アクティベーションレコードスタックを管理するコードは、関数ごとにプログラム機能を構築するコンパイラによって生成されるため、確認する必要はありません。コンパイラは、関数呼び出しをトリガするコマンドを生成します。コンパイラは、プログラム命令を生成するときに次のことを知っています。
- 関数呼び出しをトリガーするために使用されるハードウェア命令とその命令がスタックに与える影響(たとえば、自動的に戻りアドレスを保存するのか、スタックの「上部」を追跡するレジスタを調整するのか)
- 呼び出しのパラメータがスタックに保存されると、これらのパラメータはスタックの「一番上」になります。
- 関数内のローカル変数のサイズとスタックの「上」を基準としたこれらの変数の位置(コンパイラはそれを使用してスタックの「上」を追跡するレジスタを調整します)。
- 関数で使用されるレジスタと保存/復元が必要な時期
- 関数呼び出しで戻りをトリガーするために使用されるハードウェア命令と、この命令がスタックに与える影響。
コンパイラは、ハードウェアアーキテクチャに対してよく確立されたルールセット(呼び出しルール)に従うため、異なるコンパイラによって構築されたさまざまな部分で構成されるプログラムを相互運用できます。
ランタイムアクティベーションスタック(3)は「スタック」抽象化(1)の実装ですが、レコードのプッシュ/ポップの概念以外はリンクベースの実装とほとんど似ていません。
答え2
前述のように、スタックは汎用データ型であり、特定の汎用オペレーティングシステムには複数のスタック実装があります。単一のスタックはありません。これスタック、システムレベルのプログラマ以外のハードウェア呼び出しスタックは、おそらくそうです。おそらく。
OpenSSLにはstack.h
、このライブラリはスタックデータ構造を実装します。たぶんこれがあなたが見つけたものかもしれません。C++には標準コンテナもあります。std::stack
。 (このファイルはstack
私のLinuxでは別名と呼ばれることがありますstl_stack.h
。ヘッダファイルもライブラリを使用するエントリをコンパイルするためにのみ必要です。