4. 락프리 스택 기본 구현체의 문제 1 (ABA 문제 확인, 수정)

---

ABA 문제

 

이전 포스팅에서 ABA 문제가 발생 가능한 시나리오와 ABA문제로 인하여 스택의 상태가 실제로 꼬이는 문제를 확인하였다. ABA문제는 잘 알려진 문제 이기 때문에 wiki 뿐만 아니라 다양한 블로그와 홈페이지에서 다루고 있으며 해결책 또한 한두 가지가 아니다.

 

ABA problem - Wikipedia

 

모든 방법을 실제 구현하지는 않을 것이며 위키에서 제안한 보편적인 방법을 사용할 것이다.

winAPI 방식의 코드에서는 스탬프 비트를 이용할 것이며, c++ 표준 방식의 코드에서는 스마트 포인터의 참조카운트 방식을 이용해 ABA 문제를 해결하고자 한다.

 

---

winAPI : 스탬프 비트 체크 방법

 

32bit 윈도우 시스템의 유저 영역 메모리 크기는 2GB가 기본값이며, 64bit 윈도우 8.1 이상 시스템의 유저영역 메모리 크기는 128TB가 기본이다.

 

Memory Limits for Windows and Windows Server Releases - Win32 apps

 

즉 64bit의 주소 공간 중 유저가 직접 사용하지 않는 (= 운영체제에 의해 사용되는) 비트가 존재한다.

앞쪽 1바이트 하고 1비트가 사용되지 않는다.

 

이 부분을 스탬프로 사용하거나. CAS의 대상이 되는 변수의 크기를 2배로 늘린 (128bit) double CAS를 이용해 64비트의 스탬프를 이용하는 방법이 존재한다.

내장 함수 _InterlockedCompareExchange128

 

다음 포스팅에서 interlocked 연산 방식과 atomic 방식 두 가지의 성능을 비교할 예정이기 때문에 여기에서는 앞쪽 1바이트가량을 사용하는 방식을 사용하겠다. 왜냐하면 interlocked 방식이 참조 카운트 방식보다 빠르고, CAS가 double-CAS보다 빠르기 때문에 비교를 효과적으로 하기 위함이다.

 

스탬프를 이용하는 방식을 간단히 표현하면 다음과 같다.

 

 

 

 

 

 

 

 

 

 

 

 

이러한 동작을 위해 다음과 같은 매크로 또는 메소드를 구현하여 nodePtr, pushNo, key를 변환한다.

#define		MAKE_KEY(nodePtr, pushNo)		(pushNo << 48) | (unsigned long long int)nodePtr
#define		MAKE_NODEPTR(key)				(node<T>*)(0x0000FFFFFFFFFFFF & key)

 

주의할 점으로는 key 값을 주소값으로 그대로 형변환하면 유저가 커널 영역 메모리에 접근 시도하는 형태가 되므로 운영체제가 메모리 보호를 위해 에러를 발생시킨다. 그러므로 CAS 연산은 key 값으로, 메모리의 새로운 할당과 해제는 ptr 형태로 사용해야 함을 주의하자.

 

---

winAPI : 스탬프 비트 수정 및 테스트 결과

 

code

GitHub - YoungWoo93/lockFreeStack-Queue-sample: 블로그 포스팅 내용과 연계

 

 

테스트 결과 1

첫번째 value가 0이므로 value가 엑셀 시트상 인덱스보다 1 작으면 딱 맞는 것 이다

lockFreeStack_test_3.xlsx

0.16MB

 

 

테스트 결과 2

 

 

테스트 결과 2의 경우 testCount를 1000만, 스레드를 4개, pushPopSize를 1만으로 세팅했을 때 발생했다. 만약 발생하지 않는다면 수치를 더 크게 하면 발생 확률이 올라간다.

 

다음 포스팅에서 테스트 2의 이유를 추론해 보고, 해결방법을 찾을 것이다. 이 과정에서 참조 카운트를 이용한 방식과 interlocked를 이용한 방식의 성능을 비교하고 interlocked 방식이 더 빠른 이유를 생각해 볼 것이다.

 

---

c++ stendard : 참조 카운터 이용

 

참조 카운터를 이용하는 방법은 임의의 노드를 바라보는 스레드의 개수를 이용하여 아무도 해당 노드를 참조하지 않을 때 delete를 하는 방식이다. 누군가 참조를 하고 있다면 delete 되지 않기 때문에 바라보던 노드의 주소가 재사용되어 ABA 문제가 발생할 여지를 두지 않는다. 주의할 점은 노드의 삽입시점에서 stack이 삽입된 노드를 참조하는 값을 1 두어야 하고 POP에 성공한 스레드가 있다면 해당 스레드의 참조 제거와 함께 stack이 참조하고 있던 카운터도 한 개 더 제거해 주어야 한다는 것이다.

 

참조 카운터를 이용하는 방법을 간단히 나타내면 아래와 같다.

 

 

 

 

 

 

 

 

---

c++ stendard : 참조 카운터 이용 수정 및 테스트 결과

 

code

GitHub - YoungWoo93/lockFreeStack-Queue-sample: 블로그 포스팅 내용과 연계

 

테스트 결과 1

스탬프를 이용한 CAS와 동일하다.

 

테스트 결과 2

testCount를 1000만, 스레드를 4개, pushPopSize를 1만으로 세팅해도 문제없이 동작한다.

 

---

 

이번 포스팅 결과를 보면 스탬프 방식보다 참조 카운트를 이용하는 방법이 더 나은 결과로 보인다. 하지만 다음 포스팅에서는 winAPI 버전에서 테스트 2 에러가 발생하는 이유를 찾고 두 가지 방식의 성능을 비교할 것이다. 원인 분석과 성능 비교를 한 결과 개인적으로 스탬프 방식을 더 선호하게 되었다.