[Java] Java에서의 Lock-Free (Atomic, Volatile)

Lock Free 기법이란?

Lock을 사용하지 않고 동시성 문제 해결하는 기법 중 하나를 의미합니다. Lock은 대부분의 동시성 문제를 쉽고 안전하게 해결할 수 있는 효과적인 방법이지만, 여러 단점을 가지고 있습니다.

Lock의 단점

1. 데드락 (Deadlock)
2. 우선순위 역전 (Priority Inversion) : 우선순위가 낮은 스레드가 락을 가진 상태에서 CPU 사용이 우선순위에 의해 스왑되면, 해당 락이 필요한 우선순위 높은 스레드가 종료되지 않는 한 무한정 대기하게 되는 문제가 발생
3. 성능 오버헤드 (Performance Overhead) :스레드가 락을 얻기 위해 ‘블록’ 상태로 변경되고ㅡ 이 과정에서 불필요한 컨텍스트 스위치가 발생

 

동시성 문제의 근본적인 해결법은?

예를 들어, 크리티컬 섹션인 count에 대해 + 1 연산을 여러 쓰레드가 동시에 진행한다고 가정해보자.

count++은 Atomic이지 않기 때문에 count에 대한 데이터 정합성을 보장하지 못한다.

 

[ x86 아키텍처에서의 count ]

; count 변수의 값을 eax 레지스터로 복사 (원본 값 저장)
mov eax, dword ptr [count]

; count 변수의 값을 1 증가시킴
inc dword ptr [count]

따라서 근본적으로 Lock Free 동시성 문제를 해결하기 위해선 Atomic한 명령어를 사용하여 한다는 것을 알 수 있다.

 

Java에서의 Lock Free

[ volatile 키워드 ]

크리티컬 섹션을 volatile로 선언하면, long/double을 포함한 모든 타입 변수의 읽기/쓰기 연산이 원자적으로 처리된다.

Volatile에 대해선 추후 글을 작성하겠다.

 

[ java.util.concurrent.atomic ]

AtomicInteger, AtomicLong, AtomicReference 등 다양한 Atomic 클래스를 제공한다. 이 클래스들의 메서드(예: incrementAndGet(), compareAndSet())는 내부적으로 CPU가 보장하는 저수준 Atomic 연산을 사용한다.

 

AtomicInteger

java.util.concurrent.atomic에서 가장 흔하게 사용되는 원자 클래스이다.

이를 이용하여 Fake 레포지토리를 구현하기도 한다. 이 또한, 추후 글을 포스팅하겠다.

메서드는 아래와 같이 사용이 가능하다.

 

동작	증가 메서드	Getter + 증가 메서드
1 증가	incrementAndGet()	getAndIncrement()
1 감소	decrementAndGet()	getAndDecrement()
지정된 값(delta) 더하기	addAndGet(delta)	getAndAdd(delta)

 

AtomicReference

AtomicInteger와 다르게 모든 객체를 원자 형식으로 만들어 사용할 수 있다.

그러나 해당 객체의 메서드를 원자적으로 실행시키는 것이 아니라 아래 원자 메서드를 지원하는 것에 불과하다는 것을 명심하자.

반환 메서드 설명

반환	메서드	설명
V	get()	현재 참조하고 있는 객체(값)를 가져옵니다. volatile 읽기와 동일한 메모리 효과를 가집니다.
void	set(V newValue)	참조 값을 newValue로 설정합니다. volatile 쓰기와 동일한 메모리 효과를 가집니다.
void	lazySet(V newValue)	참조 값을 newValue로 설정하지만, 일반 set보다 약한 순서 보장을 가집니다. 후속 메모리 연산과의 순서가 재조정될 수 있습니다.
boolean	compareAndSet(V expect, V update)	현재 값이 expect와 동일하면(== 비교), 새로운 값 update로 원자적으로 교체합니다. 성공 시 true, 실패 시 false를 반환합니다.
boolean	weakCompareAndSet(V expect, V update)	compareAndSet과 유사하지만, 드물게 값이 동일해도 실패할 수 있습니다 (spurious failure). 일반적으로 반복문 안에서 사용됩니다.

 

Atomic 컬렉션의 단점

syncronized 키워드나 Lock보다 훨씬 간단하게 사용할 수 있다는 장점이 있지만, 어디까지나 단일 메서드(incrementAndGet() 등)에 대해서만 원자성을 보장한다는 단점이 존재한다.

따라서, 여러 메서드들에 대해서 원자성을 보장받기 위해선 락이나 Syncronized 키워드를 사용하는 것이 적합해보인다.

 

Lock-Free로 Stack 구현해보기

다양한 예시들 중 가장 유명한 Lock-Free Stack을 Java로 구현해보자.

먼저 Stack을 구현하기 위해 Linked List 형태의 노드를 만들어주었다.

private static class StackNode<T> {
    public T value;
    public StackNode<T> next;

    public StackNode(T value) {
        this.value = value;
        this.next = next;
    }
}

그리고, Stack의 Top을 AtomicReference를 통해 원자값으로 만들었다.

 

 

[ 초기 세팅 ]

만약 push나 pop을 수행할 경우, head와 counter를 갱신한 후 StckNode의 next 값을 적절하게 조정하면 된다.

public static class LockFreeStack<T> {
        private AtomicReference<StackNode<T>> head = new AtomicReference<>();
        private AtomicInteger counter = new AtomicInteger(0);

        public void push(T value) {
            StackNode<T> newHeadNode = new StackNode<>(value);

            while (true) {
                StackNode<T> currentHeadNode = head.get();
                newHeadNode.next = currentHeadNode;
                if (head.compareAndSet(currentHeadNode, newHeadNode)) {
                    break;
                } else {
                    LockSupport.parkNanos(1);
                }
            }
            counter.incrementAndGet();
        }

        public T pop() {
            StackNode<T> currentHeadNode = head.get();
            StackNode<T> newHeadNode;

            while (currentHeadNode != null) {
                newHeadNode = currentHeadNode.next;
                if (head.compareAndSet(currentHeadNode, newHeadNode)) {
                    break;
                } else {
                    LockSupport.parkNanos(1);
                    currentHeadNode = head.get();
                }
            }
            counter.incrementAndGet();
            return currentHeadNode != null ? currentHeadNode.value : null;
        }

        public int getCounter() {
            return counter.get();
        }
    }

 

push()

새로운 노드인 newHeadNode를 임계 영역인 head의 값을 newHeadNode로 변경한다. 그 이후, newHeadNode의 next를 기존 head 값으로 대체한다.

여기서 중요한 것이 set한 head(newHeadNode)와 get한 head(currentHeadNode)가 같을 때까지 무한 루프를 돌게 된다. 그 이유는 set한 결과가 다른 스레드에 의해 무시되었는지 확인하기 위해서이다.

pop()

push와 마찬가지로 currentHeadNode의 next를 newHeadNode로 가져와 head로 설정한다.  똑같이 무한루프를 통해 값이 정확히 변경되도록 한다.