Garbage Collection Chapter 2 30 April, 2004 Tatsuya Shirai 発表の流れ • GCの目的 • アルゴリズム – Mark-Sweep – Copying – Reference Counting • アルゴリズムの選択 メモリの管理 • メモリ割り当て – static allocation – stack allocation – heap allocation • メモリの管理 – 割り当てと解放 →バグの温床 メモリリーク root str l_ptr r_ptr A B C D GCの要件 • リークしたメモリを回収する • ユーザプログラムの邪魔をしない アルゴリズム • Mark-Sweep • Copying • Reference Counting Mark-Sweep • ポインタをたどって到達可能nodeを調べる • 到達可能でないnodeを解放する Mark-Sweep • 初期化 – 作業なし • 割り当て – mark_bitを付けて割り当てる – メモリが足りなくなったらGC開始 • 解放 解放 • • • • • ユーザプログラムを停止 rootの探索 到達可能なnodeに印をつける (Mark) markされていないnodeを解放 (Sweep) ユーザプログラムを再開 node node position mark_bit left_ptr right_ptr Mark １ root １ A １ F １ E 0 B 0 C 1 D １ G Code １ mark(N) = if mark_bit(N) == unmarked mark_bit(N) = marked for M in Children(N) mark(M) １A １F １E 0B 0C 1D １G Code １ Sweep() = N = Heap_bottom １A While N < Heap_top if mark_bit(N) == unmarked free(N) １E 0B else mark_bit(N) = marked N = N+size(N) 0C 1D １F １G 性質 • 長所 – 全ての到達不可能なnodeを解放する – 割り当て時のオーバーヘッドが少ない • 短所 – sweepの時にheapを全て調べる – ユーザプログラムを完全に停止させる →リアルタイム処理で致命的になる恐れ Copying • heapを2つに分ける • 片方が足りなくなっ たら到達可能node のみをもう一方に Copyする half_of_heap+1 top_of_space Fromspace free bottom_of_space Tospace Copying • 初期化 – メモリを2つ(Tospace, Fromspace)に分ける • 割り当て – forward_ptrを付けてTospaceに割り当てる – Tospaceが足りなくなったらGC開始 • 解放 – TospaceとFromspaceを入れ替える (flip) – 到達可能nodeをTospaceにCopyする flip top Fromspace half+1 top free bottom Tospace half+1 Tospace free bottom Fromspace node node position forward_ptr left_ptr right_ptr Copy A’ A B’ B E C’ C A’ B’ C’ D’ D’ D Fromspace Tospace Code copy(P) = if atomic(P) or P==nill //ポインタではない return P if not forwarded(P) //まだCopyしていない n = size(P) P’ = free free = free+n temp = P[0] forwarding_address(P) = P’ //Copy先を示す P’[0] = copy(temp) for i=1 to n-1 //nodeの要素をCopy P’[i] = copy(P[i]) return forwarding_address(P) 性質 • 長所 – – – – 全ての到達不可能なnodeを解放する 割り当て時のオーバーヘッドが少ない 到達可能なnodeのみを調べる メモリの整理 • 短所 – メモリの半分しか割り当てられない – ユーザプログラムを完全に停止させる Reference Counting • 各nodeへの参照の数をカウントする • 参照の数が0になったら解放 Reference Counting • 初期化 – 作業なし • ポインタ参照 – 参照時にカウンタを1増やす – 参照削除時にカウンタを1減らす node node position reference_count left_ptr right_ptr Non-cyclic data structure １ root １ A １ F 01 B 10 C 2 21 D E １ G Code free(T) = next(T) = free_list free_list = T １ １A delete (T) = RC(T) = RC(T)-1 0B if RC(T) == 0 for U in Children(T) delete(U) free(T) 0C １F 2E 1D １G Cyclic data structure 1 root 1 A 21 B 1 C 性質 • 長所 – オーバーヘッドが分散する – 到達不可能なnodeをすぐに解放する • 短所 – ポインタ操作ごとにオーバーヘッドがかかる – Cyclic data structureを解放できない アルゴリズムの選択 • オーバーヘッド – メモリ – 時間
© Copyright 2024 ExpyDoc
