マーク＆スイープ（まーくあんどすういぷ）

概要

マーク＆スイープは、動的に割り当てられたメモリ領域のうち、どの領域がまだ使用されているかを特定し、不要な領域を解放するためのアルゴリズムです。プログラムの実行中に自動的に行われるため、プログラマが手動でメモリを管理する必要がありません。

動作原理

1. マークフェーズ: プログラムのルートオブジェクト（グローバル変数、スタック上の変数など）から開始し、到達可能なすべてのオブジェクトを再帰的に探索します。到達可能なオブジェクトには「マーク」が付けられます。
2. スイープフェーズ: ヒープ全体を走査し、「マーク」が付けられていないオブジェクトを「ガベージ」と判断し、メモリを解放します。

歴史

マーク＆スイープは、1960年代にLispプログラミング言語のために開発されました。初期のガベージコレクションアルゴリズムとして広く採用され、その基本的な考え方は現代の多くのガベージコレクションシステムにも引き継がれています。

利点

• 実装が比較的容易
• メモリリークを防止

欠点

• 停止時間（ガベージコレクションの実行時間）が長くなる可能性がある
• メモリの断片化が発生しやすい

派生アルゴリズム

マーク＆スイープを改良した様々なアルゴリズムが存在します。例えば、コピーコレクション、世代別ガベージコレクションなどがあります。