LockFree Stack은 LockFree Algorithm을 기반으로한 멀티 쓰레드 환경에서 사용할 수 있는 Stack Container 입니다. LockFree Stack은 기본적으로 Push와 Pop 메서드를 가지고 있습니다.
LockFree Queue가 아닌 LockFree Stack을 사용하는 경우
LockFree Stack은 LIFO( Last In First Out )의 Container로서 후인선출 방식의 이점인 캐시 히트율의 이점을 얻으면서 후입선출 방식으로 구현해도 문제가 없을 때 사용합니다.
LockFree Stack Push 구현 방법
Part 3은 신규 노드의 Next를 반드시 지역 변수에 저장한 TOP 노드를 연결해야 합니다. 만약 현재 TOP 노드를 대상으로 연결했다면 현재 TOP 노드는 지역 변수 TOP과 똑같다는 보장이 없기 때문입니다. 만약 Part 4에서 현재 TOP과 지역 변수 TOP이 여전히 다를 경우 CAS에 실패하여 Part 2와 Part 3을 다시 시도하기 때문에 문제가 없지만, Part 4를 시도하기 전에 다른 쓰레드에 의해서 현재 TOP이 다시 지역 변수 TOP과 동일한 TOP으로 수정되었다면 Part 3에서 발생한 전혀 다른 TOP을 가리키는 문제를 감지할 수 없게 됩니다.
LockFree Stack Push에서의 ABA 문제
위 이미지를 보면 LockFree Stack Push에서도 ABA 문제가 발생되며 1번 쓰레드는 이를 인지하지 못하여 신규 노드를 현재 TOP 노드에 연결하여 Push합니다. 하지만, Push에서 ABA 문제가 발생된다 하더라도 Stack이 깨지는 문제가 발생되지 않기 때문에 ABA 문제를 해결하기 위한 조치는 필요하지 않습니다.
LockFree Stack Pop 구현 방법
Pop에서는 주소값만을 비교하는 CAS로는 ABA 문제를 예방할 수 없습니다. 그렇기 때문에 Double CAS와 Count 값을 가지는 Node를 이용해서 주소값과 Count를 동시에 비교하는 작업을 수행해야 합니다.
현재 Top 노드의 Count 값과 현재 Top 노드의 주소값을 지역 변수에 저장할 때 반드시 Count 값을 먼저 저장해야 합니다. 주소값을 저장하고 Count를 저장한다면 주소값을 저장한 다음에 ABA 문제가 발생되더라도 이를 감지할 수 없기 때문입니다.
LockFree Stack Pop에서의 ABA 문제
Pop은 Push와 다르게 ABA 문제가 발생된다면 Stack이 깨지는 문제가 발생됩니다. 1번 쓰레드에서는 현재 TOP인 A 노드의 Next를 B 노드로 알고 있지만, CAS 직전에 다른 쓰레드에 의해서 2번과 같이 A 노드의 Next가 C 노드로 변화되는 순간이 발생될 수 있기 때문입니다. 이를 감지하고 해결하기 위해서는 DCAS를 반드시 사용해야 합니다.
LockFree Algorithm은 멀티 쓰레드 환경에서 동기화 객체를 사용하지 않고 CAS( Compare And Exchange )만을 이용해서 동기화를 하는 알고리즘입니다. LockFree Algorithm을 통해서 LockFree Stack, LockFree Queue Container를 구현할 수 있습니다.
LockFree Algorithm의 장.단점
LockFree Algorithm의 장점
LockFree Algorithm은 CAS를 사용하기에 자신의 퀀텀타임 이내에 성공했다면 동기화 객체를 사용함으로서 발생되는 불필요한 커널 모드로의 전환 및 쓰레드가 블락되는 현상을 예방할 수 있습니다.
LockFree Algorithm의 단점
LockFree Algorithm은 스핀락과 동일할게 성공할 때까지 수행하기 떄문에 퀀텀타임 이내에 성공하지 못했다면 전체적인 쓰레드 처리량이 떨어질 수 있다는 단점이 있습니다.
구현이 어렵고 멀티 쓰레드 환경에서 사용되기 때문에 LockFree Algorithm을 사용한 로직에서 버그가 발생될 경우 디버깅 하기가 매우 어렵습니다.
LockFree Algorithm 구현시 주의사항
Linked List
LockFree Algorithm은 CAS를 이용한 동기화를 하기 때문에 LockFree Stack, LockFree Queue 내부는 배열이 아닌 Linked List로 구현해야 합니다. 배열은 데이터를 넣는 작업과 index를 증가 시켜주는 두 가지 작업을 한 번에 원자적으로 진행할 수 없기 때문입니다.
메모리 재사용( ABA 문제 )
데이터를 넣기 위해서는 node를 할당받아야 하는데 컴퓨터 구조 특성상 node를 반환하고 할당받는 과정에서 언제든지 이전에 사용되었던 node가 반환될 수 있습니다. 이로 인해서 CAS에서 ABA 문제가 발생될 수 있기 때문에 데이터를 추가적으로 동시에 비교하는 작업이 필요합니다.( LockFree Stack, Lockfree Queue의 ABA 문제의 특성은 조금 다르기 때문에 LockFree Stack, Lockfree Queue 포스팅에서 상세히 다루도록 하겠습니다. )
페이지 상태 변화
LockFree Algorithm 특성상 이미 반환된 데이터를 읽어봐야 하는 경우도 발생됩니다. 하지만, 이럴 경우 heap에 의해서 반환된 메모리가 committed reserved 상태로 바뀌었을 경우 읽는것 조차에서도 에러가 발생되기 때문에 heap이 아닌 메모리 프리 리스트와 같은 heap을 대체하여 할당 받고 반환할 수 있는 수단이 필요합니다.
