ABA 문제

ABA problem

멀티스레드 컴퓨팅에서 ABA 문제는 동기화 중에 발생하는데, 한 위치를 두 번 읽었을 때 두 읽기 모두에 대해 동일한 값을 가지며, "값이 동일하다"를 사용하여 "변화된 것이 없다"고 표시한다.그러나 두 개의 판독 사이에 또 다른 실이 실행되어 가치를 바꾸고, 다른 일을 한 다음 그 가치를 되돌릴 수 있기 때문에 두 번째 실이 그 가정을 위반하는 작용을 했음에도 불구하고 첫 번째 실이 "아무 것도 변하지 않았다"는 생각으로 속일 수 있다.

ABA 문제는 공유 데이터에 액세스하는 여러 스레드(또는 프로세스)가 인터리브할 때 발생한다.다음은 ABA 문제를 야기할 이벤트의 순서다.

  • 프로세스 }은(는) 공유 메모리에서 값 A를 읽는다.
  • }가 선점되어 2{\}} 프로세스 실행이 가능하다.
  • 공유 메모리 값 A를 값 B로 수정하고 선점하기 전에 A로 되돌린다.
  • }가 다시 실행을 시작하여 공유 메모리 값이 변경되지 않은 것을 확인하고 계속된다.

}은는) 실행을 계속할 수 있지만 공유 메모리에서 "숨겨진" 수정으로 인해 동작이 정확하지 않을 가능성도 있다.

잠금 없는 데이터 구조를 구현할 때 ABA 문제의 일반적인 사례가 발생한다.목록에서 항목을 제거하고 삭제한 다음 새 항목을 할당하여 목록에 추가하면 MRU 메모리 할당으로 인해 할당된 개체가 삭제된 개체와 동일한 위치에 있는 것이 일반적이다.따라서 새 항목에 대한 포인터는 이전 항목에 대한 포인터와 같기 때문에 ABA 문제가 발생하는 경우가 많다.

예

잠금 없는 스택을 사용하여 ABA의 소프트웨어 예(C++로 작성됨)를 생각해 보십시오.

/* ABA 문제를 겪고 있는 순진한 잠금 해제 스택.*/ 계급 쌓다 {   찌꺼기::원자성의<오비*> top_ptr;   //   // 상단 객체를 팝업한 후 포인터를 반환한다.   //   오비* 팝() {     하는 동안에 (1) {       오비* ret_ptr = top_ptr;       만일 (!ret_ptr) 돌아오다 무효의;       // 단순화를 위해 이 참조가 안전한지 확인할 수 있다고 가정해 보십시오.       // (즉, 그 사이에 어떤 다른 나사산이 스택을 펑펑 터트리지 않았다는 것).       오비* next_ptr = ret_ptr->다음에;       // 상단 노드가 여전히 재시도된 경우 스택을 변경한 사람이 없다고 가정하십시오.       // (ABA 문제 때문에 그 진술이 항상 진실인 것은 아니다)       // 원자력으로 팽이를 다음으로 교체한다.       만일 (top_ptr.bare_exchange_message(ret_ptr, next_ptr)) {         돌아오다 ret_ptr;       }       // 스택이 변경되었습니다, 다시 시작하십시오.     }   }   //   // obj_ptr로 지정한 개체를 눌러 쌓으십시오.   //   공허하게 하다 밀다(오비* obj_ptr) {     하는 동안에 (1) {       오비* next_ptr = top_ptr;       obj_ptr->다음에 = next_ptr;       // 상단 노드가 여전히 다음인 경우 스택을 변경한 사람이 없다고 가정하십시오.       // (ABA 문제 때문에 그 진술이 항상 진실인 것은 아니다)       // 원자적으로 팽이를 obj로 대체한다.       만일 (top_ptr.bare_exchange_message(next_ptr, obj_ptr)) {         돌아오다;       }       // 스택이 변경되었습니다, 다시 시작하십시오.     }   } };

이 코드는 일반적으로 동시 접속 문제를 방지할 수 있지만, ABA 문제를 겪는다.다음 순서를 고려하십시오.

Stack 초기에는 top → A → B → C가 포함되어 있음

스레드 1이 팝을 실행하기 시작함:

ret = A, next = B;

스레드 1이 중단되는 순간compare_exchange_weak...

{ // 스레드 2 실행 팝:   되받아치다 = A;   다음에 = B;   bare_exchange_message(A, B)  // 성공, 상단 = B   돌아오다 A; } // 이제 스택이 상단 → B → C { // 스레드 2 실행 팝 다시 실행:   되받아치다 = B;   다음에 = C;   bare_exchange_message(B, C)  // 성공, 상단 = C   돌아오다 B; } // 이제 스택이 상단 → C 삭제하다 B; { // 이제 나사산 2가 A를 스택으로 다시 밀어 넣는다.   A->다음에 = C;   bare_exchange_message(C, A)  // 성공, 상단 = A }

이제 스택이 상위 → A → C

스레드 1이 재개되는 경우:

bare_exchange_weak(A, B)

이 명령은 top ==ret(둘 다 a)를 찾으므로 top을 다음(이 B)으로 설정하기 때문에 성공한다.B가 삭제되었으므로 프로그램은 스택의 첫 번째 요소를 살펴보려고 할 때 확보된 메모리에 액세스할 것이다.여기에 표시된 것처럼 C++에서, 자유 메모리에 접근하는 것은 정의되지 않은 행동이다. 이것은 충돌, 데이터 손상 또는 심지어 단지 묵묵히 제대로 작동하는 것처럼 보일 수 있다.이와 같은 ABA 버그는 디버깅하기 어려울 수 있다.

해결책

태그 지정된 상태 참조

일반적인 해결 방법은 고려 중인 수량에 추가 "태그" 또는 "스탬프" 비트를 추가하는 것이다.예를 들어 포인터에서 비교 및 스왑을 사용하는 알고리즘은 포인터 수정에 성공한 횟수를 나타내기 위해 주소의 낮은 비트를 사용할 수 있다.이 때문에 태그 비트가 일치하지 않기 때문에 주소가 같아도 다음 비교-스왑은 실패하게 된다.두 번째 A는 첫 번째 A와 약간 다르게 만들어지기 때문에 이것을 ABAʹ이라고 부르기도 한다.이러한 태그가 지정된 상태 참조는 트랜잭션 메모리에 사용되기도 한다.태그가 지정된 포인터를 구현에 사용할 수 있지만 이중 너비 CAS를 사용할 수 있는 경우 별도의 태그 필드를 사용하는 것이 바람직하다.

"태그" 필드가 감싸면, ABA에 대한 보장은 더 이상 서지 않는다.그러나, 기존 CPU와 60비트 태그를 사용하는 경우 프로그램 수명이 10년으로 제한되는 한(즉, 프로그램을 다시 시작하지 않는 한) 랩 배치는 불가능하다는 것이 관찰되었다. 또한, 실용적인 목적을 위해 일반적으로 40-48비트의 태그만 있으면 아로 래핑에 대한 보장이 충분하다는 주장이 제기되었다.최신 CPU(특히 모든 최신 x64 CPU)가 128비트 CAS 작동을 지원하는 경향이 있으므로, 이는 ABA에 대한 확실한 보증을 허용할 수 있다.[1]

중간 노드

정확하지만 비용이 많이 드는 접근방식은 데이터 요소가 아닌 중간 노드를 사용하여 요소가 삽입되고 제거될 때 불변성을 보장하는 것이다.

이연간행

또 다른 접근방식은 제거된 데이터 요소의 재확보를 연기하는 것이다.매립을 연기하는 한 가지 방법은 자동 가비지 수집기를 특징으로 하는 환경에서 알고리즘을 실행하는 것이다. 그러나 여기서 문제는 GC가 잠금 해제되지 않으면 데이터 구조 자체가 잠금 해제되어도 전체 시스템이 잠금 해제되지 않는다는 것이다.

개간을 연기하는 또 다른 방법은 하나 이상의 위험 포인터를 사용하는 것인데, 이 포인터는 목록에 표시할 수 없는 위치에 대한 포인터다.각 위험 포인터는 진행 중인 변화의 중간 상태를 나타낸다. 포인터의 존재는 추가적인 동기화를 보장한다[Doug Lea].위험 포인터에는 잠금 기능이 없지만, 나사산당 사용 중인 원소의 수가 정해져 있을 때만 추적할 수 있다.

그러나 회수를 연기하는 또 다른 방법은 RCU 읽기-사이드 중요 섹션에 업데이트를 동봉한 다음 제거된 데이터 요소를 해제하기 전에 RCU 유예 기간을 기다리는 것을 포함하는 읽기-복사 업데이트(RCU)를 사용하는 것이다.이러한 방식으로 RCU를 사용하면 현재 실행 중인 모든 작업이 완료될 때까지 제거된 데이터 요소가 다시 나타날 수 없음을 보장한다.RCU는 잠금 기능이 없지만 모든 워크로드에 적합한 것은 아니다.

일부 아키텍처는 "더 많은" 원자 연산을 제공하며, 예를 들어, 이중으로 연결된 목록의 전방 링크와 후방 링크는 모두 원자적으로 업데이트할 수 있다. 이 기능은 아키텍처에 의존하지만, 특히 x86/x64 아키텍처(x86은 64비트 CAS를 허용하며, 모든 현대식 x64 CPU는 128비트 CAS를 허용함)와 IBM의 z에 사용할 수 있다./Architecture(최대 128비트 CAS 허용)

일부 아키텍처는 지정된 위치의 다른 저장소가 없는 경우에만 저장소가 수행되는 로드 링크된 저장 조건부 지침을 제공한다.이는 "저장소 포함 가치"라는 개념과 "저장소가 변경되었다"는 개념을 효과적으로 구분한다.예로는 DEC Alpha, MIPS, PowerPC, RISC-V, ARM(v6 이상) 등이 있다.

참고 항목

참조

  • Dechev, Damian; Pirkelbauer, Peter; Stroustrup, Bjarne (2006). "Lock-free Dynamically Resizable Arrays". CiteSeerX 10.1.1.86.2680. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  • Dechev, Damian; Pirkelbauer, Peter; Stroustrup, Bjarne (2010). "Understanding and Effectively Preventing the ABA Problem in Descriptor-based Lock-free Designs" (PDF).
  1. ^ 'No Bugs' Hare, CAS(Rec)Actor for Non-blocking Multithreaded Primitics, 2017년 과부하 #142, 2017