マーク&スイープ
英語表記: Mark and Sweep
概要
マーク&スイープ（Mark and Sweep）は、現代のプログラミング環境における「メモリ管理と運用」を支える重要な技術の一つ、ガーベジコレクション（GC）の代表的なアルゴリズムです。これは、プログラムが実行中に動的に確保したメモリ領域のうち、もはや利用されていない（到達不可能となった）領域を自動的に特定し、再利用できるように解放する仕組みを指します。プログラマが手動でメモリを解放する手間を省き、メモリリークの発生を防ぐことを目的としています。この方式は、GCのアルゴリズムの中でも最も古典的かつ基礎的な手法として広く知られています。
詳細解説
マーク&スイープは、私たちが日々利用するアプリケーションの安定稼働を支える「メモリ管理と運用」の自動化を実現する、非常に重要な役割を担っています。特に、JavaやC#、Pythonなどの実行環境（仮想マシンやインタプリタ）において、ヒープメモリを効率的に管理するために採用されています。
目的と階層構造における位置づけ
このアルゴリズムの究極の目的は、プログラマに「メモリの解放」という煩雑でエラーの多い作業から解放し、開発効率を高めることです。
階層構造で考えると、マーク&スイープは「メモリ階層（キャッシュ, DRAM, NVRAM）」の中で最も容量の大きいDRAM（主記憶）上の「ヒープ領域」の管理に深く関わります。このDRAM上での「メモリ管理と運用」を自動で行うための具体的な手段が「ガーベジコレクション」であり、マーク&スイープはその中核をなす動作原理なのです。
動作原理：二段階のプロセス
マーク&スイープは、その名の通り「マーク（印付け）」と「スイープ（掃き出し）」という二つのフェーズから構成されています。
1. マークフェーズ (Mark Phase)
このフェーズでは、プログラムが現在「生きている」オブジェクト、すなわち将来的に参照される可能性があるオブジェクトを特定します。特定作業は、プログラムが確実に参照している場所（これを「ルートセット」と呼びます。具体的には、スタック上の変数やグローバル変数などです）から開始されます。
ルートセットからスタートし、そこから参照されているオブジェクトを辿り、さらにそのオブジェクトが参照しているオブジェクトへと芋づる式に調査を進めていきます。到達できたオブジェクトには「使用中」であることを示すマークをつけます。このプロセスを通じて、たとえヒープ上に存在していても、ルートセットから辿り着けないオブジェクトは、もはやプログラムにとって不要である、と判断されるわけです。
2. スイープフェーズ (Sweep Phase)
マークフェーズが完了すると、次にスイープフェーズが開始されます。このフェーズでは、ヒープメモリ全体をスキャンし、マークがついていないオブジェクトの領域を特定します。
マークがついていない領域は「ガーベジ（ゴミ）」とみなされ、そのメモリ領域が解放されます。解放された領域は、以降、新しいオブジェクトを格納するために再利用可能な「フリーリスト」に追加されます。これが「掃き出し（スイープ）」と呼ばれる所以です。
克服すべき課題：ストップ・ザ・ワールド (STW)
マーク&スイープの古典的な実装には、避けられない課題が存在します。それは「ストップ・ザ・ワールド（Stop The World: STW）」と呼ばれる現象です。
マーク処理中やスイープ処理中に、もしプログラムがオブジェクトの参照関係を変更してしまうと、GCの判断が狂い、必要なオブジェクトを誤って解放したり、不要なオブジェクトを見逃したりする可能性があります。これを防ぐため、GCが動作している間、一時的にアプリケーションの実行を完全に停止させる必要があります。
このSTWの時間が長くなると、ユーザーはアプリケーションの一時的なフリーズを感じてしまい、応答性（レスポンス）が低下します。そのため、現代のGC技術（例：世代別GC、コンカレントGCなど）では、このSTW時間をいかに短縮するかが、メモリ管理技術の大きな課題となっているのです。
具体例・活用シーン
マーク&スイープは、目に見えないところで私たちのデジタルライフを支えてくれている、縁の下の力持ちのような存在です。
図書館の蔵書整理というメタファー
初心者の方には、マーク&スイープを図書館の蔵書整理に例えると非常に分かりやすいかと思います。
設定:
* 図書館全体（メモリ）: 図書館の全書架と収蔵スペース。
* 個々の本（オブジェクト）: メモリ上に確保されたデータやプログラムの塊。
* 貸出リスト（ルートセット）: 現在、利用者が借りている本や、図書館員が「重要資料」として必ず保管すると決めている本のリスト。
マークフェーズ:
図書館員（GC）が、まず貸出リストにある本を確認します。そして、それらの本に関連する資料や、現在書架にあり、参照リストに載っている本（将来誰かが借りる可能性がある本）に、一時的に「チェック済み」の付箋（マーク）を貼っていきます。この作業によって、「今、誰かに必要とされている本」が明確になります。
スイープフェーズ:
図書館員は、付箋（マーク）が貼られていない本、つまり誰にも借りられず、参照リストからも外れ、書架の隅で埃をかぶっている本を「不要なゴミ」と判断します。これらの本を一掃し、廃棄処分します。この廃棄によって空いたスペースは、新しく購入する本のためのスペースとして再利用されます。
このように、マーク&スイープは、利用者の存在（ルートセット）を基準に、必要なものだけを残し、不要なものを効率的に除去することで、貴重なスペース（メモリ）を常に有効活用しているのです。
活用シーン
- Java仮想マシン (JVM): 多くのJVMのGCアルゴリズムの基盤となっています。特に初期のGCや、世代別GCにおけるOld領域の回収などでこの原理が活用されています。
- JavaScript実行環境: WebブラウザやNode.jsなどのJavaScript実行環境（V8エンジンなど）でも、メモリ管理はこのマーク&スイープをベースに改良された技術が使われています。
この技術のおかげで、私たちはメモリ解放のコードを書く必要がなく、純粋にアプリケーションのロジック開発に集中できるのですから、本当にありがたいことですね。
資格試験向けチェックポイント
IT資格試験、特に基本情報技術者試験や応用情報技術者試験では、「メモリ管理と運用」の自動化技術であるガーベジコレクションに関する理解度が問われます。マーク&スイープはGCの基本中の基本なので、以下の点をしっかり押さえておきましょう。
- マーク&スイープの目的: メモリリークの防止と、プログラマのメモリ解放作業の負担軽減を目的としていることを確認してください。これは「メモリ管理の自動化」という文脈で非常に重要です。
- 二つのフェーズの役割: 「マーク」が到達可能なオブジェクトの特定（生きているものの識別）を行うこと、「スイープ」がマークされていないオブジェクトの領域解放（ゴミの除去）を行うこと、この役割分担を正確に把握してください。
- ルートセットの理解: どこから参照の探索が始まるのか（スタック、グローバル変数など）を理解することが、到達可能性の判断基準となります。
- STW（ストップ・ザ・ワールド）の概念: マーク&スイープの課題として、処理中にアプリケーションの実行が一時停止するSTWが発生し、これがシステムの応答性に影響を与えるという点を覚えておきましょう。特に、STWを避けるための現代的なGC技術（コンカレントGCなど）との対比で問われることがあります。
- 対比される手法: 参照カウント方式（オブジェクトへの参照数を数える方式）との違いもよく問われます。マーク&スイープは循環参照（お互いを参照し合っているが、ルートからは到達できないオブジェクト群）を正しく回収できるという利点がある点を押さえておくと得点源になります。
関連用語
- 情報不足
このセクションでは、マーク&スイープの理解を深めるために不可欠な関連用語として、本来ならば「ガーベジコレクション（GC）」そのもの、そして「ヒープ領域」「ストップ・ザ・ワールド（STW）」「コンパクション（メモリ断片化解消の手法）」などを挙げるべきです。
特に、マーク&スイープはメモリを解放するだけで、解放後のメモリが不連続な空き領域（断片化）となってしまうという問題があります。この断片化を解消するために、回収後にオブジェクトを詰め直す「コンパクション」というプロセスが必要になるため、セットで理解することが非常に重要です。
しかし、指定された要件に従い、関連用語の情報が不足していることを明記いたします。
