タグ→クリア

タグクリアは主流のトラッキング収集アルゴリズムの一種であり、参照カウントに比べてトラッキング収集は間接的な方法であり、プログラムとの結合性が低く、簡単に言えば、プログラムは必要なときにメモリを申請するだけで、使用時にリファレンスカウントメカニズムのようにリアルタイムでメンテナンスする必要はありません.一定の条件(一般的にはメモリ領域が一定のしきい値に達することが申請されている)まで、プロセスは実行を一時停止し、ゴミ収集器でゴミを回収し、実行を継続する.もちろん収集後もメモリが不足している場合は、エラーを報告する.多くの言語の主流の実装ではjava、C#などの追跡式の収集が使用されている
 
追跡式収集はごみの概念定義に厳格に従い,ルートセットからすべての達成可能なオブジェクトセットを見つけ,コレクションから達成可能セットを減算し,残りはごみである.タグ-パージアルゴリズムは、次の3つのステップに分けられます.
 
1すべてのオブジェクトを非マーク状態に初期化
 
2ルートセットからすべての到達可能オブジェクトをマーク
 
3すべてのオブジェクトを巡回し、マークされていない場合は解放
 
後で見ますが、実際には2ステップで、初期化は3ステップ目で処理されます.
 
各オブジェクトにはタグビットが必要です.このメモリは多くありません.bitビットでいいので、言語のオブジェクト構造設計と組み合わせて、一般的にこのようなビットを見つけることができます.例えば、オブジェクトヘッダは、オブジェクトのタイプ(C++のような虚表ポインタ)をintで表し、プログラムのタイプの数がintの最大値(32ビットのint、この範囲が超えている場合は、私に拝礼してください)を超えないと仮定すると、シンボルビットはこのタグに使用できます.
 
すべての新規出願の対象は、マークされていない状態であり、上記の第3のステップは、次のようにすることができる.
 

for obj in all_obj 
{ 
    if (obj.marked()) 
    { 
        obj.unmark(); 
    } 
    else 
    { 
        free(obj); 
    } 
} 

すべてのオブジェクトを巡回するときに、マークされている場合はマークされていない状態に変更し、マークされていない場合は解放します.これにより,ゴミ回収が開始されるたびに,すべてのオブジェクトがマークされていない状態であることが保証され,上記の第1ステップの初期化が省ける.
 
そこで、コアな問題は、ルートセットからすべてのオブジェクトをどのようにマークするかです.一見難しくありません.例えば、DFSを採用することができます.
 

void mark() 
{ 
    this.mk = true; //     bool   
    for obj in this.obj_list 
    { 
        if (obj.unmark()) 
        { 
            //           ，                
            obj.mark(); 
        } 
    } 
} 
for obj in root_set 
{ 
    obj.mark(); 
} 

あるいはBFSを採用する
 

todo_list = root_set 
while (todo_list.size() > 0) 
{ 
    new_todo_list = new list; 
    for obj in todo_list 
    { 
        if (obj.unmarked()) 
        { 
            obj.mark(); //   mark           
            for item in obj.obj_list 
            { 
                if (item.unmarked()) 
                { 
                    new_todo_list.add(item); 
                } 
            } 
        } 
    } 
    todo_list = new_todo_list; 
} 

どちらの方法も可能ですが、ゴミ収集では、タグが必要なオブジェクトが多い場合、消費空間が大きい可能性があり、DFSはスタック空間を消費し、BFSは反復するたびにリストの空間を消費するという共通の問題があります.一般的な問題であれば、メモリ消費は当然であるが、追跡式収集では、ゴミ収集器のトリガ条件は、一般的にスタック空間が消費されて差が少ない場合であり、この場合、対象数に関連する線形空間がゴミ収集を行う必要がある場合、ゴミ回収トリガのスタック空間閾値を低減せざるを得ない.さらにごみの回収を激化させる頻度
 
そのため、最良の方法は定数空間内でマーキングプロセスを実現することであるが、残念なことに、このようなアルゴリズムは遅いか、複雑である(複雑なアルゴリズム自体も速くない).しかし、実際の使用では、全文追跡収集の実現は比較的少なく、いくつかの新しいメカニズムはこの問題を緩和することができる.
 
追跡式収集の長所と短所は引用カウントと比較して、大部分がちょうど逆で、引用カウントの長所は、ちょうど追跡式収集の欠点であり、例えば、対象の生存周期の制御性がもっと悪く、収集過程が運転を一時停止するため、リアルタイム性が悪く、局所性が悪いなどである.逆に、引用カウントの多くの欠点は、プログラムコードとの結合性が低く、メンテナンスが便利で、プログラムの実行期間に余分な消費がなく、空間の浪費が少なく、すべてのゴミが回収され、全体の効率が高いなど、追跡式収集の点である.
 
具体的にはタグ-クリア、プロシージャから表示されます.このアルゴリズムの実行時間はメモリ内のオブジェクト数に比例しており(メモリ解放が定数時間であると仮定する)、オブジェクトが多いと時間がかかる可能性があり、実際の状況を考慮すると、ほとんどのプログラムはゴミ回収が必要な場合、集合が少ないことが多く、統計によると、80%~98%のオブジェクトは構築後すぐに(約数百万件の命令)は破棄されるため、マークアップフェーズの時間は相対的に少なく、クリアフェーズに多くの時間がかかるため、リアルタイム性を高めるために、マークアップが完了した後、クリアフェーズは複数回に分けて行うことができる.ゴミ収集をトリガーするのは一般的に空きスペースが不足している場合であり、このとき空きメモリの一部をクリアすればよいからだプログラムを続行させる
 
これにより、クリーンアップ開始からクリーンアップ完了までの間、プログラムがnewして新しいオブジェクトが出てきますが、新しいオブジェクトの状態がunmarkedである場合は、使用中のオブジェクトを誤ってクリーンアップする可能性がありますが、この間ゴミになったオブジェクトはすぐに回収されません.これは関係ありません.次のマークの時に正常に片付けることができます