1 歴史と背景
1.1 手動メモリ管理の課題
初期のプログラミング言語（C、C++など）では、プログラマがmallocやfreeを用いて手動でメモリを確保・解放する必要があった。この方式は柔軟性が高い一方、解放忘れによるメモリリークや、解放済み領域へのアクセス（ダングリングポインタ）などの深刻なバグを引き起こしやすく、大規模ソフトウェアの開発において大きな負担となった。
1.2 Lispにおける初期のGC実装
ガベージコレクションの概念は、1959年にジョン・マッカーシーが開発したLisp言語にさかのぼる。Lispは記号処理と動的メモリ割り当てを多用するため、手動管理が非現実的であった。マッカーシーはマーク・アンド・スイープ方式のGCを考案し、その後、1960年代に多くのLisp処理系に改良が加えられた。
1.3 現代言語への普及
1990年代以降、JavaやC#などの言語がGCを標準搭載し、広く普及した。これにより、メモリ管理の自動化が主流となり、プログラマはビジネスロジックに集中できるようになった。現在では、Go、Python、Ruby、JavaScriptなど、ほとんどの高水準言語が何らかのGC機構を持つ。
2 基本原理と用語
2.1 到達可能性（Reachability）
GCの基本は、プログラムから直接または間接的に参照されているオブジェクトを「到達可能」とみなし、そうでないオブジェクトを「ゴミ」と判断することである。到達可能なオブジェクトは生存していると見なされ、解放されない。
2.2 ルートセット（Root Set）
到達可能性の起点となるのがルートセットである。これは、スタック上のローカル変数、静的変数、レジスタなど、プログラムが直接保持する参照を指す。GCはルートからたどって全ての到達可能オブジェクトを特定する。
2.3 コレクタとミューテータ
GCを実行する部分を「コレクタ（collector）」、ユーザープログラム（アプリケーションコード）を「ミューテータ（mutator）」と呼ぶ。ミューテータはオブジェクトの生成や参照の変更を行い、コレクタはそれらに影響されずにゴミを回収する。
3 主要アルゴリズム
3.1 参照カウント（Reference Counting）
各オブジェクトに参照の数を保持し、カウントが0になった時点で即座に解放する方式。シンプルでリアルタイム性が高いが、後述する循環参照の問題に対処できない。
3.1.1 循環参照問題
互いに参照し合うオブジェクト群（循環参照）がある場合、外部からの参照がなくなってもカウントが0にならず、メモリリークが発生する。この問題を解決するため、多くの言語では補助としてマーク・アンド・スイープを併用するか、弱参照（weak reference）を導入する。
3.2 マーク・アンド・スイープ（Mark-and-Sweep）
2フェーズからなる古典的アルゴリズム。まず「マークフェーズ」でルートから到達可能な全オブジェクトにマークを付け、次に「スイープフェーズ」で未マークのオブジェクトを解放する。循環参照にも対応できるが、プログラム全体を停止（ストップ・ザ・ワールド）する必要があり、断片化が発生しやすい。
3.3 コピーGC（Copying GC / Cheney's Algorithm）
ヒープを2分割し、片方の領域（From領域）にある生存オブジェクトをもう片方（To領域）にコピーする。コピー後にFrom領域全体を一括解放するため、断片化が解消される。ただし、生存オブジェクトが多いとコピーコストが高くなり、使用可能メモリが半分になる欠点がある。
3.4 世代別GC（Generational GC）
多くのオブジェクトが短期間に消滅するという経験則（弱い世代仮説）に基づき、ヒープを世代に分割する。新生オブジェクトを集めるマイナーGCと、長期間生存したオブジェクトを対象とするメジャーGCを組み合わせ、効率を高める。
3.4.1 若い世代（Young Generation）と古い世代（Old Generation）
若い世代は新しいオブジェクトが割り当てられ、頻繁にGCが実行される。一定回数のコレクションを生き延びたオブジェクトは古い世代に昇格（プロモート）される。古い世代のGCは低頻度で行われる。
4 最適化と応用技術
4.1 並行GC（Concurrent GC）
ミューテータの実行と並行してGCを行う方式。アプリケーションの停止時間を短縮するが、実装が複雑で、オブジェクト参照の一貫性を保つための同期処理が必要となる。
4.1.1 三色マーキング（Tri-color Marking）
並行GCで用いられるマーキング手法。オブジェクトを白（未探索）、灰（探索済みだが参照先未処理）、黒（処理完了）の3色で管理する。これにより、ミューテータによる参照変更を考慮しながら安全にGCを進められる。
4.2 インクリメンタルGC（Incremental GC）
GC処理を小さな単位に分割し、ミューテータの実行と交互に行う方式。ストップ・ザ・ワールド時間を細かく分散させ、応答性を改善する。三色マーキングと組み合わせて実装されることが多い。
4.3 リアルタイムGC（Real-time GC）
ハードリアルタイムシステム向けに設計されたGC。最悪ケースの停止時間を保証するため、インクリメンタルや並行アルゴリズムを厳密に分析して実装される。ただし、スループットが低下するトレードオフがある。
5 課題とトレードオフ
5.1 ストップ・ザ・ワールド（Stop-the-World）問題
多くのGCアルゴリズムでは、全ミューテータを一時停止してからGCを実行する。この停止時間が長くなると、インタラクティブなアプリケーションやリアルタイム処理に悪影響を及ぼす。並行GCやインクリメンタルGCはこの問題を軽減する。
5.2 フラグメンテーション（Fragmentation）
マーク・アンド・スイープなどでは、解放されたメモリ領域が断片化し、大きな連続領域を確保できなくなることがある。コピーGCやコンパクション（圧縮）機能がこれを防ぐ。
5.3 パフォーマンスとスループットのバランス
GCの頻度やアルゴリズムの選択は、アプリケーションの特性に依存する。低停止時間を重視するとスループットが下がり、高スループットを追求すると停止時間が伸びる。チューニングは常にトレードオフを伴う。
6 実装例と応用分野
6.1 JavaのHotSpot VM
OracleのHotSpot VMは世代別GCを採用し、複数のコレクタ（Serial、Parallel、G1、ZGCなど）を提供する。G1は低停止時間・高スループットを両立するよう設計され、ZGCは極めて短い停止時間（サブミリ秒）を実現する。
6.2 .NETのCLR
.NETの共通言語ランタイム（CLR）も世代別GCを採用し、ワーカースレッドとバックグラウンドGCを組み合わせて停止時間を短縮する。サーバーGCとワークステーションGCの2モードがあり、用途に応じて選択可能である。
6.3 JavaScriptエンジン（V8, SpiderMonkey）
ブラウザ向けJavaScriptエンジンでは、インタラクティブ性を重視したGCが実装されている。Google V8は世代別とインクリメンタルGCを組み合わせ、SpiderMonkeyは並行マーキングを採用する。どちらも短い停止時間を目指している。
6.4 ゲームエンジンにおけるGC回避戦略
Unity（C#）やUnreal Engine（C++）など、リアルタイム性が重要なゲームエンジンでは、GCによる予測不能な停止を避けるため、オブジェクトプールや手動メモリ管理を併用する。また、GCが発生するタイミングを制御するAPI（例：System.GC.Collectの明示的呼び出し）も利用される。