- Authors
- Name
- Youngju Kim
- @fjvbn20031
実行時環境 - スタック、ヒープ、ガベージコレクション
コンパイラはコードを生成する際にプログラムが実行時にどのようにメモリを使用するかを知る必要があります。この記事ではメモリ構成、スタック割り当て、ヒープ管理、そしてガベージコレクションを扱います。
1. メモリ構成（Storage Organization）
実行中のプログラムのメモリは一般的に以下のように構成されます。
高いアドレス
+------------------+
| スタック | <- 関数呼び出し情報、局所変数
| | |
| v |
| |
| ^ |
| | |
| ヒープ | <- 動的割り当てデータ
+------------------+
| 静的データ | <- グローバル変数、定数
+------------------+
| コード | <- プログラム命令
+------------------+
低いアドレス
各領域の役割
- コード領域: コンパイルされた機械語命令が格納されます。一般的に読み取り専用です。
- 静的データ領域: グローバル変数と定数が格納されます。プログラム開始時に割り当てられ、終了まで維持されます。
- スタック領域: 関数呼び出し時に活性化レコードがpushされ、戻り時にpopされます。
- ヒープ領域:
malloc、newなどで動的に割り当てられたデータが格納されます。
2. 活性化レコード（Activation Record）
関数が呼び出されるたびに**活性化レコード（activation record）またはスタックフレーム（stack frame）**が生成されます。
活性化レコードの構造
高いアドレス
+---------------------------+
| 実引数（arguments） |
+---------------------------+
| 戻り値 |
+---------------------------+
| 制御リンク（control link） | <- 呼び出し元のフレームポインタ
+---------------------------+
| アクセスリンク | <- 静的スコープのサポート
+---------------------------+
| 保存されたレジスタ |
+---------------------------+
| 局所変数 |
+---------------------------+
| 一時変数 |
+---------------------------+
低いアドレス
各フィールドの役割
- 実引数: 呼び出し元が渡した引数値です。
- 戻り値: 関数の結果を格納する空間です。レジスタを使用する場合もあります。
- 制御リンク（Control Link）: 呼び出し元の活性化レコードを指すポインタです。関数戻り時にスタックを復元するのに使用します。
- アクセスリンク（Access Link）: 非局所変数にアクセスするためのポインタです。
- 保存されたレジスタ: 関数進入時に保存すべきレジスタ値です。
- 局所変数: 関数内で宣言された変数です。
- 一時変数: コンパイラが生成した一時的な値です。
3. 呼び出し順序（Calling Sequence）
関数の呼び出しと戻り時に実行されるコードを呼び出し順序と呼びます。
呼び出し元（Caller）がすること
1. 実引数を評価してスタックにpush
2. 戻りアドレスを保存
3. 被呼び出し側に制御を移動（call命令）
被呼び出し側（Callee）がすること
1. 保存すべきレジスタをスタックにpush
2. 以前のフレームポインタ（FP）を保存（制御リンク）
3. 新しいフレームポインタ（FP）を設定
4. 局所変数用の空間を割り当て（SPを移動）
戻り時に被呼び出し側がすること
1. 戻り値を指定された位置に格納
2. SPをFPに復元
3. 保存されたレジスタを復元
4. 以前のFPを復元
5. 戻りアドレスにジャンプ
呼び出し過程の例
void main() { void foo(int x) {
foo(10); int y = x + 1;
// ... bar(y);
} }
void bar(int a) {
int b = a * 2;
}
スタックの変化:
[1] main呼び出し時 [2] foo(10)呼び出し時 [3] bar(11)呼び出し時
+-------+ +-------+ +-------+
| main | | main | | main |
+-------+ +-------+ +-------+
| foo | | foo |
| x=10 | | x=10 |
| y=11 | | y=11 |
+-------+ +-------+
| bar |
| a=11 |
| b=22 |
+-------+
4. 非局所変数のアクセス
入れ子の関数（nested function）がある言語では、外側の関数の変数にアクセスする必要がある場合があります。
アクセスリンク（Access Link）
アクセスリンクは静的に囲んでいる（enclosing）関数の活性化レコードを指します。
// Pascal風のコード
procedure A;
var x: integer;
procedure B;
var y: integer;
procedure C;
begin
x := y + 1; // Aのxとbのyにアクセス
end;
begin
C;
end;
begin
B;
end;
スタック（呼び出し: A -> B -> C）:
+-------+
| A | <- アクセスリンク: なし（最外側）
| x |
+-------+
| B | <- アクセスリンク: Aのレコードを指す
| y |
+-------+
| C | <- アクセスリンク: Bのレコードを指す
| |
+-------+
Cからxにアクセス: アクセスリンクを2回辿る（C -> B -> A）
Cからyにアクセス: アクセスリンクを1回辿る（C -> B）
アクセスリンクを辿る回数は入れ子の深さの差に等しいです。
ディスプレイ（Display）
ディスプレイはアクセスリンクチェーンを辿る代わりに、各入れ子の深さの現在の活性化レコードへのポインタ配列を維持します。
ディスプレイ配列:
display[1] = Aの活性化レコードポインタ
display[2] = Bの活性化レコードポインタ
display[3] = Cの活性化レコードポインタ
Cからxにアクセス: display[1]で直接アクセス（O(1)）
Cからyにアクセス: display[2]で直接アクセス（O(1)）
ディスプレイの利点は非局所変数のアクセスが常に定数時間であることです。ただし、関数の進入/脱出時にディスプレイ更新のコストがあります。
5. ヒープ管理（Heap Management）
ヒープは動的に割り当てられ、解放されるデータを格納します。
ヒープ割り当てが必要な場合
- オブジェクトのサイズがコンパイル時に不明な場合
- オブジェクトの寿命が関数呼び出しの範囲を超える場合
- データ構造（連結リスト、木など）の動的生成
メモリ割り当て戦略
1. ファーストフィット（First Fit）:
十分な大きさの最初の空きブロックを使用
[使用中][ 空きブロック ][使用中][ 空きブロック ]
^
ここに割り当て
2. ベストフィット（Best Fit）:
要求サイズに最も近い空きブロックを使用
-> 外部断片化の可能性が高い
3. バディシステム（Buddy System）:
2の累乗サイズのブロックで分割/統合
-> 内部断片化の可能性があるが統合が高速
断片化（Fragmentation）
外部断片化（External Fragmentation）:
空き空間の合計は十分だが、連続ブロックが不足
[使用][空き][使用][空き][使用][空き]
^^^ ^^^ ^^^
各100Bだが200B要求は不可
内部断片化（Internal Fragmentation）:
割り当てられたブロック内の未使用空間
要求: 100B、割り当て: 128B -> 28Bの無駄
6. ガベージコレクション（Garbage Collection）の基礎
ガベージコレクション（GC）はもう使用されないメモリを自動的に回収する技法です。
ガベージとは？
**ルート集合（root set）**から到達不可能なオブジェクトをガベージと呼びます。
ルート集合: スタック変数、グローバル変数、レジスタ
[ルート] --> [オブジェクトA] --> [オブジェクトB]
|
v
[オブジェクトC]
[オブジェクトD] --> [オブジェクトE] <- 到達不可 = ガベージ！
7. 参照カウント（Reference Counting）
各オブジェクトに参照カウントを維持し、カウントが0になったら回収します。
a = new Object(); // Objectのrefcount = 1
b = a; // Objectのrefcount = 2
a = null; // Objectのrefcount = 1
b = null; // Objectのrefcount = 0 -> 回収！
参照カウントの長所と短所
長所:
- 即時回収: 参照が0になったらすぐにメモリを返却
- 一時停止なし: GC停止（stop-the-world）なし
- 実装が簡単
短所:
- 循環参照の処理不可:
[A] --> [B]
^ |
+-------+
A.refcount = 1, B.refcount = 1（永遠に0にならない）
- カウント更新のオーバーヘッド: 代入ごとにカウント更新
- キャッシュ効率の低下: 参照更新時のリモートメモリアクセス
8. 追跡ベースのガベージコレクション
マーク・アンド・スイープ（Mark-and-Sweep）
2段階で動作します。
マーク段階（Mark Phase）:
1. ルート集合から開始
2. 到達可能な全オブジェクトに「マーク」を付ける
3. DFSまたはBFSでオブジェクトグラフを走査
スイープ段階（Sweep Phase）:
1. ヒープの全オブジェクトを走査
2. マークされていないオブジェクトを回収
3. マークされたオブジェクトのマークを除去
マーク前:
[A*] -> [B*] -> [C*]
|
v
[D ] -> [E ] [F*]
* = ルートから到達可能
スイープ後:
[A] -> [B] -> [C]
|
v
[空き] -> [空き] [F]
D、Eは回収された
マーク・アンド・スイープの特徴
長所:
- 循環参照も正確に回収
- オーバーヘッドがゴミの量に比例
短所:
- Stop-the-World: GC実行中にプログラムが一時停止
- 断片化: 回収後にメモリが断片化
9. コピーコレクタ（Copying Collector）
ヒープを2つの半空間（semispace）に分けて使用します。
[From空間] [To空間]
+---------+ +---------+
| A B C | コピー --> | A C |
| (空き) D| | (空き) |
+---------+ +---------+
生きているオブジェクトだけをTo空間にコピー
-> 断片化なし、連続メモリ
Cheneyアルゴリズム
BFS方式で生きているオブジェクトをコピーします。
1. To空間の先頭にscanとfreeポインタを設定
2. ルートから参照されるオブジェクトをTo空間にコピー
3. scanポインタが指すオブジェクトの参照を処理:
- 参照するオブジェクトがFromにあればToにコピー
- 参照を新しい位置に更新
4. scanがfreeに追いついたら完了
コピーコレクタの特徴
長所:
- 断片化なし（圧縮効果）
- 割り当てが非常に高速（ポインタ増加のみ）
- 生きているオブジェクトにのみコストが発生
短所:
- メモリの半分しか使用不可
- 生きているオブジェクトが多いとコピーコストが大きい
- ポインタの更新が必要
10. 世代別ガベージコレクション（Generational GC）
世代別GCは「ほとんどのオブジェクトは若くして死ぬ（generational hypothesis）」という観察に基づきます。
世代の区分
+------------------+
| Old世代 | （長く生き残ったオブジェクト）
| (Major GC対象) | <- GC頻度低い
+------------------+
| |
| Young世代 | （新しく生成されたオブジェクト）
| (Minor GC対象) | <- GC頻度高い
| +----+ +------+ |
| |Eden| |Survivor||
| +----+ +------+ |
+------------------+
動作方式
1. 新しいオブジェクトはYoung世代に割り当て
2. Young世代が満杯になるとMinor GCを実行:
- 生きているオブジェクトをSurvivor領域にコピー
- 複数回生き残ったオブジェクトはOld世代に昇格（promotion）
3. Old世代が満杯になるとMajor GCを実行:
- ヒープ全体を対象にGC（コストが大きい）
記憶集合（Remembered Set）
Old世代からYoung世代への参照を追跡する必要があります。
Old世代のオブジェクトAがYoung世代のオブジェクトBを参照する場合:
-> 記憶集合にAを追加
-> Minor GC時に記憶集合のオブジェクトもルートとして扱う
これによりMinor GCがOld世代全体をスキャンしなくて済みます。
実際のGC実装例
Java HotSpot JVM:
Young: Eden + Survivor0 + Survivor1（コピー収集）
Old: Mark-CompactまたはCMS/G1/ZGC
Go:
世代なしの並行（concurrent）マーク・アンド・スイープ
三色マーキング（tri-color marking）使用
Python:
参照カウント + 世代別GC（循環参照処理用）
11. 現代のGCの発展
並行GC（Concurrent GC）
プログラムの実行とGCを同時に行います。
[プログラムスレッド] -------実行-------実行-------実行------->
[GCスレッド] --マーク--|-スイープ--|---------|-マーク--|-->
-> Stop-the-World時間を最小化
増分GC（Incremental GC）
GC作業を小さな単位に分けてプログラムと交互に実行します。
[プログラム] [GC] [プログラム] [GC] [プログラム] [GC] [プログラム]
10ms 2ms 10ms 2ms 10ms 2ms 10ms
-> 長い一時停止の代わりに短い一時停止を複数回
現代のコレクタ
Java G1（Garbage First）:
- ヒープを同一サイズのリージョン（region）に分割
- ガベージが多いリージョンを優先的に収集
- 一時停止目標時間の設定が可能
Java ZGC / Shenandoah:
- 非常に短い一時停止（数ミリ秒以内）
- 大容量ヒープ（数テラバイト）に対応
- 並行圧縮（concurrent compaction）
まとめ
| 概念 | 核心内容 |
|---|---|
| 活性化レコード | 関数呼び出し時に生成されるスタックフレーム |
| 制御リンク | 呼び出し元のフレームを指すポインタ |
| アクセスリンク | 静的スコープの外側の関数を指すポインタ |
| ディスプレイ | 各入れ子の深さの現在の活性化レコードポインタ配列 |
| ヒープ管理 | 動的割り当て/解放、断片化管理 |
| 参照カウント | 参照数を数えて0なら回収、循環参照の問題 |
| マーク・アンド・スイープ | 到達可能なオブジェクトをマークし残りを回収 |
| コピーコレクタ | 生きているオブジェクトだけを新空間にコピー |
| 世代別GC | オブジェクトの寿命で区分して効率的に収集 |
実行時環境の理解は効率的なコードを生成するために不可欠です。このシリーズで扱ったコンパイラの各段階（字句解析、構文解析、意味解析、中間コード生成、実行時環境）は現代のプログラミング言語とツールの基盤となる核心技術です。