http://junhoahn.kr/noriwiki/index.php?action=history&feed=atom&title=The_Pauseless_GC_Algorithm 2026-05-19T17:33:49Z 이 문서의 편집 역사 MediaWiki 1.43.0 http://junhoahn.kr/noriwiki/index.php?title=The_Pauseless_GC_Algorithm&diff=1716&oldid=prev 2024-12-06T13:35:40Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ko"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 이전 판</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2024년 12월 6일 (금) 13:35 판</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">1번째 줄:</td> <td colspan="2" class="diff-lineno">1번째 줄:</td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[분류: <del style="font-weight: bold; text-decoration: none;">시스템 논문</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[분류: <ins style="font-weight: bold; text-decoration: none;">USENIX VEE</ins>]]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  Usenix VEE 2005</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  Usenix VEE 2005</div></td></tr> </table>

Ahn9807 http://junhoahn.kr/noriwiki/index.php?title=The_Pauseless_GC_Algorithm&diff=1561&oldid=prev 2024-10-21T02:23:25Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ko"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 이전 판</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2024년 10월 21일 (월) 02:23 판</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">1번째 줄:</td> <td colspan="2" class="diff-lineno">1번째 줄:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[분류: 시스템 논문]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[분류: 시스템 논문]]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>  Usenix VEE <del style="font-weight: bold; text-decoration: none;">2025</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>  Usenix VEE <ins style="font-weight: bold; text-decoration: none;">2005</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  Cliff Click, Gil Tene, Michael Wolf</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  Cliff Click, Gil Tene, Michael Wolf</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> </table>

Ahn9807 http://junhoahn.kr/noriwiki/index.php?title=The_Pauseless_GC_Algorithm&diff=1560&oldid=prev 2024-10-20T13:38:03Z

<p>새 문서: <a href="/noriwiki/index.php?title=%EB%B6%84%EB%A5%98:%EC%8B%9C%EC%8A%A4%ED%85%9C_%EB%85%BC%EB%AC%B8" title="분류:시스템 논문">분류: 시스템 논문</a> Usenix VEE 2025 Cliff Click, Gil Tene, Michael Wolf == 개요 == 인터럽트를 User-level에 효율적으로 전달할 수 있고, Read-barrier를 하드웨어적으로 구현할 수 있는 특수 CPU를 사용하여서, Garbage collection의 고질적인 문제인 Stop-the-world시간을 최소한 (이론상 0)으로 만들 수 있는 GC를 설계함 == Motivation == 기존 시스템에서 GC의 Stop-the-world는 Real-time시스템이나 Late...</p> <p><b>새 문서</b></p><div>[[분류: 시스템 논문]]<br /> <br /> Usenix VEE 2025<br /> Cliff Click, Gil Tene, Michael Wolf<br /> <br /> == 개요 ==<br /> 인터럽트를 User-level에 효율적으로 전달할 수 있고, Read-barrier를 하드웨어적으로 구현할 수 있는 특수 CPU를 사용하여서, Garbage collection의 고질적인 문제인 Stop-the-world시간을 최소한 (이론상 0)으로 만들 수 있는 GC를 설계함<br /> <br /> == Motivation ==<br /> 기존 시스템에서 GC의 Stop-the-world는 Real-time시스템이나 Latency sensitive한 시스템에서 예측할 수 없는 Latency peak을 가져온다. 이를 줄이기 위한 많은 연구가 수행중이지만, 완전히 없앨 수 있는 방식은 연구된바 없었다.<br /> <br /> == Design ==<br /> === Hardware modification ===<br /> * Not-marked-through (NMT)라는 VA상의 하드웨어의 8byte비트를 재사용하여서, mark coloring을 가능하게 하였다. 즉 이 VA가 마크되었는지, 아니면 마크되지 않았는지를 판단하기 위한 bit로 저 bit의 값이 per-thread mark value와 같으면 page fault가 나지 않지만, 만약 다르면 GC-fault를 발생시켜 User-level에 구현된 인터럽트 핸들러로 바로 Invoke시켜준다.<br /> <br /> === Garbage collection 방식 ===<br /> 전통적인 Garbage collection은 Mark phase, Relocate phase, 그리고 Remap phase로 구성된다. <br /> * Mark Phase: Marking은 Heap memory를 흝으며, Live memory와 Dead object를 체크한다.<br /> * Relocate Phase: Marking결과 페이지의 대부분이 Dead object이면, 이 Compaction을 위해서, 이 페이지를 메모리의 새로운 영역으로 옮긴다.<br /> * Remap Phase: 메모림가 Relocate되면, Relocate되기 전의 VA가 stale, 즉 새로운 곳으로 옮겨같지만, 아직 옮겨지지 않은 상태로 놓이는데, 이를 옮겨진 포인터로 다시 엎어써주는 단계가 필요하다.<br /> <br /> 이 각각의 단계는 Synchronization이 매우 중요하다. 그렇다면 어떻게 Stop-the-world없이 Main Application thread가 Concurrency bug를 일으키는 것을 막을 것인가?<br /> <br /> === Concurrency Handling ===<br /> * Mark Phase: Mark Phase시작전에, NMT비트를 새롭게 설정한다. Marking이 계속 진행되면, Marking된 포인터의 NMT값은 그 값으로 업데이트 된다. 아직 Mark가 되지 않은 VA와 같은 경우에는, 하드웨어가 Read가 일어나는 순간 User-level GC-handler로 넘긴다. 이 User-level GC Handler는 포인터에 대한 Marking을 수행하고, 만약 Remap이 필요한 Pointer를 가지고 있으면, Remap을 수행한다.<br /> * Relocate Phase: 아직 Relocate되지 않은 영역에 대한 접근이 read barrier가 확인후, 있으면 GC-trap이 발생하고, User-level handler가 Relocating을 수행한다.<br /> * Remap Phase: Pauseless GC에서는 Remap과 Mark를 동시에 수행하기 때문에, 최초의 Mark phase이외에는 Remap은 Mark와 함께 진행된다.<br /> <br /> === 그래서 Stop-the-world가 정말로 없나요? ===<br /> 이론적으로는 Stop-the-world를 완전히 없앨 수 있지만, Initialization같은 단계에서 쉽게 구현하기 위해서 약간의 Stop-the-world가 발생한다.<br /> <br /> === Conclusion ===<br /> 특수 하드웨어를 사용해야 한다는 단점이 있지만, 후대의 ZGC나 C4 GC에 영향을 미친 중요한 논문이다.</div>

Ahn9807