위험 포인터
Hazard pointer | 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다.(2014년 1월)(이를 과 시기 |
멀티스레드 컴퓨팅 환경에서 위험 포인터는 잠금 없는 데이터 구조에서 노드의 동적 메모리 관리에 의해 발생하는 문제를 해결하기 위한 하나의 접근방식이다.이러한 문제는 일반적으로 자동 쓰레기 수거가 없는 환경에서만 발생한다.[1]
비교 및 스왑 원시 데이터를 사용하는 잠금 없는 데이터 구조는 ABA 문제를 다루어야 한다.예를 들어, 내접적으로 연결된 목록으로 대표되는 잠금 없는 스택에서 하나의 스레드가 스택의 전면에서 항목을 튀기려고 시도하고 있을 수 있다(A → B → C).두 번째 시작 값 "B"를 기억한 다음compare_and_swap(target=&head, newvalue=B, expected=A). 불행히도 이 작업 중간에 또 다른 실이 두 번 펑크를 낸 다음 다시 A를 위로 밀어 스택(A → C)을 만들었을지도 모른다.비교스왑은 '머리'와 'B'를 맞바꾸는데 성공하고, 그 결과 스택에 쓰레기(자유된 원소 'B'를 가리키는 포인터)가 들어 있는 것이다.
또한, 양식의 코드를 포함하는 잠금 없는 알고리즘
노드.* currentNode = 이->머리; // "this->head"로부터의 하중이 원자라고 가정한다. 노드.* nextNode = currentNode->다음에; // 이 부하도 원자성이라고 가정함 쓰레기 자동 수거가 없는 상황에서 또 다른 큰 문제에 시달리고 있다.이 두 선 사이에 다른 스레드가 다음을 가리키는 노드에 튀어나올 가능성이 있다.this->head할당을 해제하면 메모리 액세스가currentNode두 번째 줄에는 할당되지 않은 메모리(사실상 완전히 다른 목적으로 다른 스레드에 의해 이미 사용되고 있을 수 있음)를 읽는다.
위험 포인터는 이러한 두 가지 문제를 모두 해결하는 데 사용될 수 있다.위험 지점 시스템에서 각 스레드는 스레드가 현재 액세스하고 있는 노드를 나타내는 위험 지점의 목록을 보관한다. (많은 시스템에서 이 "목록"은 아마도[1][2] 한 두 개의 요소만으로 제한될 수 있다.위험 포인터 목록의 노드는 다른 스레드에 의해 수정되거나 할당 해제되지 않아야 한다.
각 판독기 스레드는 "위험 포인터"라고 불리는 단일 작성기/다중 판독기 공유 포인터를 소유하고 있다.판독기 스레드가 위험 포인터에 지도 주소를 할당하면 기본적으로 다른 스레드(작성자)에 공지한다. "나는 이 지도를 읽고 있다.원하면 교체할 수 있지만 내용물은 바꾸지 말고 확실히 보관한다.
delete손을 떼고."— Andrei Alexandrescu and Maged Michael, Lock-Free Data Structures with Hazard Pointers[2]
스레드가 노드를 제거하고자 할 때, 노드는 "나중에 해제할 노드" 목록에 표시되지만, 다른 스레드의 위험 목록에 포인터가 포함될 때까지 노드의 메모리를 실제로 할당 해제하지 않는다.이 수동 가비지 수집은 전용 쓰레기 수집 쓰레드에 의해 수행될 수 있다(모든 쓰레드에 의해 "나중에 해방될 목록"이 공유되는 경우) 또는 "해방될 목록"을 "팝"과 같은 작업의 일부로서 각 작업자 쓰레드에 의해 수행될 수 있다(이 경우 각 작업자 쓰레드는 "해방될 것"을 책임질 수 있다).리스트를 작성하다
2002년 IBM의 메이지 마이클이 유해 포인터 기법에 대한 미국 특허를 출원했으나 2010년 출원을 포기했다.[3]
참고 항목
참조
- ^ a b c 앤서니 윌리엄스.C++ 액션에서의 동시성: 실제 다중 스레딩.매닝:피난처 섬, 2012.특히 7.2장 "잠금 없는 데이터 구조 예"를 참조하십시오.
- ^ a b Andrei Alexandrescu and Maged Michael (2004). "Lock-Free Data Structures with Hazard Pointers". Dr. Dobb's. (C++ 지향 기사)
- ^ 미국 응용 프로그램 20040107227 매이지 M.Michael, "안전한 메모리 회수를 통해 동적 잠금 없는 데이터 구조를 효율적으로 구현하기 위한 방법"2002년 12월 3일 접수.
- Maged Michael (2004). "Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects" (PDF). IEEE Transactions on Parallel and Distributed Systems. 15 (8): 491–504. CiteSeerX 10.1.1.130.8984. doi:10.1109/TPDS.2004.8. Archived from the original (PDF) on 2017-11-04.
