コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

ガベージコレクション

出典: フリー百科事典『ウィキペディア（Wikipedia）』
（Dangling pointerから転送）

ガベージコレクション[注釈 1]（英: garbage collection、GC）とは、コンピュータプログラムが動的に確保したメモリ領域のうち、不要になった領域を自動的に解放する機能である。1959年ごろ、LISPにおける問題を解決するためジョン・マッカーシーによって発明された[1][2]。

メモリの断片化を解消する機能はコンパクション（英: memory compaction）と呼ばれ、実現方法によってはガベージコレクションと共にコンパクションも行う仕組みになっている。そのためコンパクションを含めてガベージコレクションと呼ぶ場合もあるが、厳密には区別される。

また、ガベージコレクションを行う主体はガベージコレクタ（英: garbage collector）と呼ばれる。ガベージコレクタはタスクやスレッドとして実装される場合が多い。

「ガベージコレクション」を直訳すれば「ゴミ集め」「ごみ拾い」となる。JISでは「廃品回収」[3]や「ゴミ集め」[4]などという直訳が割り当てられている規格もあるが、一般的な意味での「ゴミ集め」と紛らわしく、プログラミングの分野ではかえって意味が通じなくなるため、ごく一部の学会誌や論文など[5]を除き、実際に使われることはほとんどなく、外来語として各種カナ表記やGCという略記が使われることが一般的である[6]。

動作

[編集]

従来のメモリ管理では、プログラマがプログラムの実行中においてメモリが必要となる期間を考え、必要となった時点でメモリを確保するコードを記述し、不要となった時点で解放するコードを記述していた。

ガベージコレクションを使用する場合、メモリを確保するコードはプログラマが明示的に記述するが、メモリの解放については明示的に記述する必要がなく、ガベージコレクタが不要と判断した時に、自動的にメモリを解放する。確保したメモリが不要かどうかは、プログラムが今後そのメモリにアクセスするかどうかで決まり、スタックや変数テーブルなどから参照をたどってメモリに到達可能かどうかによって判断される。

ガベージコレクションの機能は、初めからプログラミング言語の言語機能や言語処理系あるいはフレームワークに組み込まれている場合や、外部ライブラリなどによって提供される場合がある。

特徴

[編集]

ガベージコレクションはプログラマが明示的にメモリの解放を行う必要が無いため、以下に示すメモリ管理に関連する陥りやすいバグを回避することができる。

メモリリークの回避
ガベージコレクションは、オブジェクト（データを格納したメモリ領域）とそれを指し示すポインタを管理するため、オブジェクトは存在しているがそれを指すポインタが無い状態を回避することができる。
オブジェクトの二重解放の回避
いったん解放したオブジェクトをさらに解放することを防ぐ。
無効なポインタの回避
例えば、メモリを動的に割り当てるサブルーチン（C言語のmalloc関数やPascalのNew手続きなど）で確保したメモリ領域を指すポインタだったが、メモリを解放するサブルーチン（C言語のfree関数やPascalのDispose手続きなど）に渡し解放した直後のポインタや、サブルーチン内の自動変数（非静的なローカル変数）のアドレスを指すポインタだったが、戻り値などによって誤ってサブルーチンの呼び出し元に返却されてしまったポインタ、などが該当する。これらのポインタにはあるアドレスが代入されているが、そのアドレスには有効なオブジェクトがすでに存在せず、ポインタは無効なメモリアドレスを指している。このような無効なポインタをダングリング・ポインタ (dangling pointer) といい、ガベージコレクションはこの問題を回避する。

ただしガベージコレクションにおいても、今後使用することのないオブジェクトへのポインタをいつまでも保持しているようなコードでは、いつまでもオブジェクトが解放されず、メモリ不足を起こしてしまう。これは論理的な設計の問題であり、ガベージコレクションを持つ処理系においてもこの種のメモリリークは発生する。

メモリ管理に関するバグを回避する以外に、プログラミングスタイルの選択肢を広げる効果も持つ。型変換などのために一時的なオブジェクトを生成する、マルチスレッドを利用したプログラムでスレッド間でオブジェクトを共有して使用する、といった処理はメモリ確保・解放の処理の記述が煩雑となることが多い。しかし、ガベージコレクションを持つ言語処理系においては煩雑な記述を省略することができ、これらの処理をより自然に記述することができる。

多くの実装では、入れ違いにより誤って到達可能なメモリが不可能と判断されないように、ガベージコレクトが開始されると他の処理を止め、本処理が中断される（Stop-the-world ガベージコレクタ）。CPUを長時間（数百ミリ秒から数十秒）占有することもある。ガベージコレクションの動作タイミングの予測やCPUの占有時間の事前予測などが困難なことから、デッドラインが決められているリアルタイムシステムに使用することは難しい。リアルタイム性を改善したGCとして、インクリメンタルGCやコンカレントGCがある。

実装

[編集]

ガベージコレクションは、Javaのように言語仕様および言語処理系（ランタイム）に標準的に組み込まれたものを透過的に利用する形態がほとんどである。しかし、C言語やC++のように言語仕様および言語処理系には存在していなくとも、Boehm GC（英語版）あるいは各種スマートポインタのようなライブラリとして実装されたものを利用することもできる。

ガベージコレクションは、プログラム本来の動作とは別に時間のかかる処理である。そこで、ガベージコレクションには本来のプログラムの動作に対して影響が少ないことが求められる。

一般に、デスクトップアプリケーションでは、応答時間を短くするため、ガベージコレクションによるプログラムの停止時間を最小にすることが要求される。また、サーバアプリケーションでは、応答時間よりもスループットを求められることが多く、ガベージコレクションにもスループット性能が高いものが求められる。さらに、機器組み込みアプリケーションでは、機器に搭載されるCPUの能力の低さやメモリ容量の小ささから、リソース消費が小さいものが求められる。また、リアルタイムシステムでは、プログラム動作時間のばらつきを最小にしたいという要求もある。

これらの要求をすべて満たすようなアルゴリズムは存在しないため、さまざまな手法が提案されている。代表的なガベージコレクションアルゴリズムには、以下のものがある。

参照カウント
オブジェクトを参照するポインタの数を数え、参照するポインタの数がゼロになったら解放する方法。循環参照の問題がある。解放が集中したときに、単純な実装だと停止時間が長くなる。
マーク・アンド・スイープ
オブジェクトから別のオブジェクトへの参照をたどり、到達できないオブジェクトを破棄する方法。
コピーGC
通常使用するメモリ領域と同じ容量のメモリ領域をもうひとつ用意し、ガベージコレクションの際に有効なオブジェクトのみをもう一方のメモリ領域にコピーする方法。メモリ領域をデータ保持に必要な容量の2倍消費すること、コピーの際にオブジェクトのアドレスが変更されることなどの欠点があるが、ガベージコレクションとコンパクションが同時に行える利点がある。

これらのアルゴリズムは複合して使用することもあり、世代別ガベージコレクションではコピーGCとマーク・アンド・スイープの両方のアルゴリズムを使用している。

また、アプリケーション動作への影響の観点から、アプリケーション動作をすべて止めるストップ・ザ・ワールド方式と、アプリケーション動作と並行して動作するコンカレント方式に分類することができる[7]。

言語による利用可能性

[編集]

一般論として、高レベルな言語ほどガベージコレクションを言語の標準機能として備えていることが多い。言語に組み込まれていない場合でも、C言語/C++向けのBoehm GC（英語版）やスマートポインタのように、非標準または標準のライブラリとして実装されていることもある。ただしライブラリベースのアプローチは、オブジェクトの生成と破棄のメカニズムを変更する必要があるなど、欠点もある。

MLやHaskell、APLなどの関数型言語の多くはガベージコレクションが組み込まれている。特に、関数型言語の先駆けとなったLISPは最初にガベージコレクションを取り入れた言語でもある。

LuaやRubyなどといった動的言語も、ガベージコレクションを備えていることが多い（ただしPerl 5やPHP 5.2以前には参照カウント方式のものしかない）。Smalltalk、Java、ECMAScript（JavaScript）のようなオブジェクト指向言語には、たいていガベージコレクションが組み込まれている。C#やVisual Basic .NETなどの.NET言語は.NET Framework/.NET Compact Framework/Mono/.NET Coreといった実行環境下において、実装形態に差はあれどいずれもガベージコレクションを利用可能である。特筆すべき例外はC++とDelphiで、それらはデストラクタがその代わりとなっている。

RustはGCを持たないが、所有権に基づいてメモリを管理する[8]。RustではC++のようにデストラクタを定義することもでき、また参照カウントベースのスマートポインタを標準的に利用することもできる。

古典的なBASICインタープリタ（N88-BASIC、F-BASICなど）においてもガベージコレクションが備えられており、文字列の連結操作の結果使われなくなった領域を再度BASICが使えるようにする処理が行われた。その処理の間、BASICがフリーズしたかのようになることから、ガベージコレクションが発生しないようにする方法として、文字列の連結を極力行わず、最大文字数が格納できる領域を持った文字列変数に対して MID$、LEFT$、RIGHT$ 関数を使用することで代用することが推奨されていた。

Objective-Cには参照カウントベースのオブジェクト寿命管理機能が組み込まれており、元々ガベージコレクションはなかったが、AppleのObjective-C 2.0では、Mac OS X 10.5以降に限り[9]保守的な世代別GCベースのランタイムコレクタが使用可能である。ただしiOSではこのGCを利用できない。なお、macOSに関しても、NSGarbageCollectorはOS X 10.8から廃止予定扱いとなり、SDK 10.10を最後に廃止されており[10]、またOS X 10.11を最後に[11]このGCは搭載されなくなり、macOS 10.12で廃止された。2015年5月以降、Mac App Storeで新規登録／更新されるアプリはGCを使えなくなっている[12]。代替として、自動参照カウント (Automatic Reference Counting; ARC) によるメモリ管理が推奨されている。SwiftもARCを採用している。一方で、GNUstepはBoehm GCを使用している。

Pythonは主に参照カウント方式のガベージコレクションを用いているが、補助的に（伝統的なマーク＆スイープとは逆順の探索アルゴリズムによる）世代別GCを併用している[13][14]。

C++/CLIでは、gcnewで生成したCLIオブジェクトは.NET Frameworkのガベージコレクションにより管理される。

C++/CX（英語版）では、ref newで生成したWindowsランタイムオブジェクトはCOMベースの参照カウントにより管理される。

ライブラリ

[編集]

スマートポインタ

[編集]

なお、C言語で参照カウント方式のガベージコレクションを利用する場合、通常煩雑なコーディングを必要とするが、C++では以下のようなRAIIを活用したスマートポインタ（英語版）を利用することで緩和できる。

分散ガベージコレクション

[編集]

分散コンピューティング環境では、あるホスト内のオブジェクトだけではなく、リモートホスト上に存在するオブジェクトとメッセージのやり取りが行われることがある。このような環境においてローカルなガベージコレクションと同様、不要なオブジェクトを破棄する手法が分散ガベージコレクションである。リモートホストからの参照状態の検出、通信が切れた場合の処理などローカルホストのガベージコレクションとは異なる課題を解決する必要がある。

世代別ガベージコレクション

[編集]
→「世代別ガベージコレクション」も参照

従来のGCは、対象となるメモリ領域がいっぱいになった時に一気にGCを行なうものであり、この方法では、メモリ領域のサイズが大きくなるに従い、GC時間が長くなっていく欠点がある。この問題に対処するために世代別ガベージコレクションが考案された。 世代別GCでは新領域と古い領域にメモリ領域が分けられ、新規に作成されたオブジェクトは、新領域に配置され、新領域がいっぱいになった時点で、新領域内部だけのGCが走る。このGCはメモリ全体に対するGCに比べると当然のことながら低負荷・高速になる。新領域に対するGCを一定回数生き残ったオブジェクトは、古領域に移動し、古領域がいっぱいになった時に、初めて全てのメモリ領域を対象とするFULL GCが行われる。

SSDにおけるガベージコレクション

[編集]
→詳細は「ライトアンプリフィケーション § SSDにおけるガベージコレクション(GC)」を参照

脚注

[編集]
[脚注の使い方]

注釈

[編集]
  1. ^ 英単語 garbage のカナ表記には「ガベージ」や「ガーベージ」のほかに、原音に近い「ガーベッジ」や「ガーベジ」などもあるが、本項では出典を除き、「ガベージ」に統一する。

出典

[編集]
  1. ^ Recursive functions of symbolic expressions and their computation by machine, Part I
  2. ^ RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I) (12-May-1998)
  3. ^ JISX3002 2011.
  4. ^ JISX3015 2008.
  5. ^ 田浦健次朗、米澤明憲「分散記憶並列計算機における局所ごみ集めのスケジュール方式について」『情報処理学会論文誌』第41巻第5号、情報処理学会、2000年5月、1490-1499頁、CRID 1050282812861984640、ISSN 1882-7764。 
  6. ^ 金子雅志, 入江道生, 四七秀貴「Java-ASにおけるガベージコレクション対策に関する一考察」『電子情報通信学会技術研究報告』第109巻第448号、電子情報通信学会、2010年3月、321-324頁、CRID 1520009408010420864、ISSN 09135685。 
    松井祥悟, 田中良夫, 前田敦司, 中西正和「相補型ガーベジコレクタ」『情報処理学会論文誌』第36巻第8号、情報処理学会、1995年8月、1874-1884頁、CRID 1050001337887661056、hdl:2241/00136890、ISSN 1882-7764。 
    平岡慶子, 小寺信治, 寺島元章「三世代ガーベッジコレクションの圧縮方式による実装について」『情報処理学会論文誌プログラミング（PRO）』第44巻SIG02(PRO16)、情報処理学会、2003年2月、36-36頁、CRID 1050564287843999360、ISSN 1882-7802。 
    五百蔵重典, 西尾孝典, 野木兼六「世代管理を保守的に行う世代別GCアルゴリズムの提案およびRuby への実装と評価」『情報処理学会論文誌プログラミング（PRO）』第48巻SIG10(PRO33)、情報処理学会、2007年6月、199-199頁、CRID 1050564287843923968、ISSN 1882-7802。 
    井手上慶, 里見優樹, 津邑公暁「GC実行時のポインタ判別コストを削減するハードウェア支援手法の検討」『電子情報通信学会技術研究報告』第113巻第169号、電子情報通信学会、2013年8月、19-24頁、CRID 1520853833160204800、ISSN 09135685。 
  7. ^ “古典的Javaガベージコレクションを理解する”. 2020年9月15日閲覧。
  8. ^ メモリー管理を安全に、次代のシステムプログラミング言語「Rust」の魅力とは | 日経クロステック（xTECH）
  9. ^ “メモリ管理を理解する（後編） (2/2)：Cocoaの素、Objective-Cを知ろう（8） - ＠IT”. 2019年2月14日閲覧。
  10. ^ “NSGarbageCollector - Foundation | Apple Developer Documentation” (英語). 2019年2月14日閲覧。
  11. ^ “Xcode Release Notes | Xcode 8.3” (英語). 2019年2月14日閲覧。
  12. ^ “Apple Warns Developers Garbage Collection is Dead, Move to ARC – The Mac Observer” (英語). 2019年2月14日閲覧。
  13. ^ “29.11. gc — ガベージコレクタインターフェース — Python 3.6.5 ドキュメント”. 2019年2月10日閲覧。
  14. ^ “Garbage Collection for Python” (英語). 2019年2月10日閲覧。

参考文献

[編集]

関連項目

[編集]
「https://ja-two.iwiki.icu/w/index.php?title=ガベージコレクション&oldid=98794944」から取得