Menu
Article concurrency

Garbage Collection

MaxLevSnail

• 3 min read

Garbage collection이 왜 문제?

concurrent한 데이터 구조는 당연히 여러 쓰레드가 접근하고 있습니다.
그래서 당연히 이 모두가 사용을 마쳤을 때 free를 해주어야 하겠죠?
근데 그 타이밍 잡기가 어렵습니다. 그래서 나온 게 Hazard Pointer와 Epoch-based Reclamination입니다.

Hazard Pointer

가장 단순한 방식입니다. 포인터 사용하기 전 protect해 주고, 다 쓰면 unprotect해 줍니다. 그리고 collect를 통해 모두 unprotect가 되었을 때 회수해 주는 것이지요.

해저드 포인터의 단점

  • 느립니다.

왜냐? 해저드 포인터 내부 protected된 목록에 저장해서 protect하고, 거기서 빼서 unprotect가 진행되는데, 이 두 과정의 순서가 재배열되면 안됩니다.

(T1-1) Add b to the hazard list       | (T2-1) Unlink b and `retire(b)`
       (`Shield::try_protect()`)      |
(T1-2) Check if b is still reachable  | (T2-2) Check if b is in the hazard list
       if so, deref b                 |        if not, free b
(T1-3) Remove b from the hazard list  |
       (`Shield::drop()`)             |

더 구체적으로 말하면, SeqCst Fence가 필요해져서 그렇습니다. 여기서 단순히 Release & Acquire로 오더링을 지정해주면, T1-1이 T2-2보다 나중에, 그리고 동시에 T2-1이 T1-2보다 나중에 실행될 수 있는 것이죠. 그래서 이 두 지점 사이에 fence를 넣어서 컴파일러 최적화를 방지해야 합니다.

  • chained retirement를 지원하지 않습니다.

노드 0 - 노드 1 - 노드 2

가 있을 때 쓰레드 1이 노드 0을 protect했다 합시다. 그리고 쓰레드 2가 노드 0 노드 1을 모두 retire해 버렸다 하면, 노드 0은 protect되어있으니 살아있지만, 노드 1은 free되었을 겁니다. 그리고 쓰레드1이 노드1을 protect한다면 위험한 상황이 발생하게 되는 것이죠.

Epoch Based Reclaimation

Epoch를 바탕으로 전체 데이터 구조를 보호하는 방식입니다. 앞에 소개한 해저드 포인터와는 다르게 여러 노드를 접근하더라도 한번만 fence를 사용하면 되고, 여러 노드를 한번에 비울 수도 있습니다.

원리는 다음과 같습니다.

  1. 데이터 구조에 접근할 때 set_active()해 줍니다. 그리고 사용을 마치면 set_quiscent()해 줍니다. 즉, 전체 데이터를 보호하는 해저드 포인터처럼요.

  2. 여기서 Epoch가 등장합니다. 매 set_active()에서는 현재 active한 최대 Epoch + 1값을 Epoch로 갖게 됩니다. 즉 자신의 epoch + 2를 가지는 구간은 자신과 겹치는 일이 하나도 없겠죠?

  3. 혹시 e+1의 작업이 e 부분을 사용할 수도 있으니 e+3의 epoch를 받게 될 때 안전하게 free시켜줄 수 있게 됩니다.

단점

Epoch Based Reclaimation에서는 한 epoch가 계속 사용중이면 이웃한 다른 epoch에서 retire된 메모리를 회수할 수 없다는 단점이 있습니다.

PEBR

교수님 랩에서 나온 논문으로, EBR과 같게 진행되지만, eject를 통해 epoch를 계속 전진시켜줍니다. 그래서 한 epoch가 계속 잡아먹는 일이 없지요. 대신 free 전에 해저드 포인터의 기능을 사용해 진짜 free가 가능한 노드인지 확인하는 작업이 들어가게 됩니다.

Share