개요
Hazard pointer는 Lock free데이터 구조에서 메모리 관리로 인해서 발생하는 ABA 문제를 해결하기 위한 접근 방식이다. 보통 Garbage collection이 없는 경우에 발생한다.
Compare and swap(CAS)를 사용하는 Lock free데이터 구조는 ABA문제, 즉 작업 시작과 끝에서 누군가 데이터 구조의 Consistency를 망가트리는, 문제를 해결해야 한다. 예를 들어서 스택에서 A -> B -> C로 이어지는 구조가 있다고 하자. 스레드가 C를 팝하고자 하면, Lock free구조에서는 보통 Push를 수행하기 직전, B노드를 체크하고 CAS로 B가 바뀌었는지, 아닌지 체크하면서 POP를 한다. 그러나, 누군가 B의 값은 같지만 포인터는 다른 구조로 만들 수 있는데, 이 경우가 바로 ABA문제가 발생하는 원리이다. (Treiber stack 참고).
Hazard pointer는 각 스레드가 현재 엑세스 중인 포인터를 가지는 Hazard pointer list를 가진다. 이 Hazard pointer list의 pointer들은 다른 스레드에 의해서 수정되거나, Deallocation되지 않도록 보호된다.
Hazard pointer를 대체할 수 있는 다른 방식으로는 Reference counting이 있다. Hazard pointer는 수동으로 작동하는 GC라고 생각하여도 된다.
알고리즘
- 자료구조
- 각 스레드들은 hazard pointer list라고 불리는 하나의 공유 리스트를 공유한다.
- 각 스레드들은 Thread local list로 Retire list를 소유한다.
- 알고리즘
- 어떤 스레드가 사용하고자 하는 포인터가 있으면 (스택에서는 노드), 그 포인터를 Hazard pointer list에 등록하고 사용한다.
- 만약 그 포인터를 다 사용하였으면, 포인터를 Hazard pointer list에서 등록 해제한다.
- 만약 어떤 스레드가 제거해야할 포인터가 있으면, Hazard pointer list에서 검색한다. 만약 있으면 Retire list에 등록하고, 나중에 다시 체크하며, 만약 없으면 안전하게 제거한다.
여기서 중요한 점은, hazard pointer를 위해서 사용되는 List또한 Lock-free여야 한다는 점이다. 그렇다면 이 리스트에서는 ABA문제가 생기지 않을까? 그러나 Hazard pointer를 담을 리스트는 보통, 정적으로 정의된 길이 만큼으로 결정되기 때문에, 동적 할당 및 해제가 필요 없다. 즉 hazard pointer list만 적당한 크기로 만들어 놓으면, 포인터를 효율적으로 관리 할 수 있다.