코딩하는 오징어

Lock Free 알고리즘(Non-Blocking 알고리즘) 본문

CS/알고리즘

Lock Free 알고리즘(Non-Blocking 알고리즘)

코딩하는 오징어 2020. 4. 21. 23:58
반응형

 병렬 알고리즘과 관련해서 최근의 연구 결과를 보면 대부분이 Non-Blocking 알고리즘, 즉 여러 스레드가 동작하는 환경에서 데이터의 안정성을 보장하는 방법으로 락을 사용하는 대신 저수준의 하드웨어에서 제공하는 compare-and-swap 혹은 compare-and-set (이후 CAS연산이라고 하겠다.)등의 명령을 사용하는 알고리즘을 다루고 있다. Non-Blocking 알고리즘은 운영체제나 JVM에서 프로세스나 스레드를 스케줄링 하거나 가비지 컬렉션 작업, 그리고 락이나 기타 병렬 자료 구조를 구현하는 부분에서 많이 사용되고 있다.

 

다음과 같은 순서로 글을 써내려가겠다.

 

  • 락 기반 알고리즘의 단점
  • 병렬 연산을 위한 하드웨어 지원
  • JVM에서의 CAS 연산 지원
  • Non-Blocking 알고리즘

락 기반 알고리즘의 단점

 공유된 자원에 대하여 여러 스레드에서 읽고 쓰기를 해야 한다면 개발자들은 보통 Mutex나 Semaphore를 이용하여 Lock을 걸고 Lock을 획득한 스레드를 제외한 다른 스레드들은 해당 자원에 접근하지 못하도록 구현할 것이다. JVM은 기본적으로 Monitor라는 개념이 사용되며 이는 Mutex와 동일한 역할을 한다. 고성능이 필요로 하지않는 상황에서는 굉장히 편한 방법이지만 고성능을 요구하는 어플리케이션에서 Lock기반으로 임계 영역을 관리한다면 요구사항을 충족 시키지 못할 것이다. Lock을 확보하지 못한 스레드는 실행되지 못하고 Lock을 획득한 스레드가 Lock을 Release할 때까지 대기 상태에 머물러야 하며 조건이 충족 될때 다시 실행시켜야한다. Lock을 획득하더라도 실제 CPU를 할당 받기전에 이미 CPU를 사용하고 있는 다른 스레드가 CPU할당량을 모두 사용하고 CPU 스케줄을 넘겨줄 때까지 대기해야한다. Lock에 대한 경쟁이 심해질수록 실제로 필요한 작업을 처리하는 시간 대비 동기화 작업에 필요한 시간의 비율이 높아지면서 성능이 떨어지게된다. 극단적인 경우에는 Lock을 획득한 스레드가 스케줄 대상에서 우선 순위가 낮아져 Lock을 Release하는 시간이 늦어진다면 공유 자원을 사용하기 위해 기다리는 다른 스레드들도 모두 대기 상태에 머무르게 되는 상황이 발생할 수 있다.

병렬 연산을 위한 하드웨어 지원

 세밀하고 단순한 작업을 처리하는 경우에는 일반적으로 훨씬 효율적으로 동작할 수 있는 낙관적인 방법이 있다. 일단 값을 변경하고 다른 스레드의 간섭 없이 값이 제대로 변경되는 방법이다. 이 방법에는 충돌 검출 방법을 사용해 값을 변경하는 동안 다른 스레드에서 간섭이 있었는지를 확인할 수 있으며, 만약 간섭이 있었다면 해당 연산이 실패하게 되고 이후에 재시도하거나 아예 재시도조차 하지 않기도 한다. 초기의 프로세서는 확인하고 값 설정(test-and-set), 값을 읽어와서 증가(fetch-and-increment), 치환(swap)등의 단일 연산을 하드웨어적으로 제공했으며, 이런 연산을 기반으로 더 복잡한 병렬 클래스를 쉽게 만드는 데 도움이 되는 Mutex를 구현할 수 있었다. 최근에는 거의 모든 프로세서에서 읽고 -> 변경하고 -> 쓰는 단일 연산(CAS연산)을 하드웨어에서 제공하고 있다. (compare-and-swap, load-linked/store-conditional등의 연산이 있다.) 운영체제와 JVM은 모두 이와 같은 연산을 사용해 락과 여러 가지 병렬 자료 구조를 작성했지만, JAVA 5.0 이전에는 해당 기능을 직접 사용할 수는 없었다.

 CAS(compare-and-swap)연산에 대해서 자세히 알아보자. CAS연산에는 3개의 인자를 넘겨주게된다. 작업할 대상 메모리의 위치(V), 예상하는 기존 값(A), 새로 설정할 값(B). CAS연산은 V위치에 있는 값이 A와 같은 경우에 B로 변경하는 단일 연산이다. 만약 이전 값이 A와 다르다면 아무런 동작도 하지 않는다. 그리고 값을 B로 변경했건 못했건 간에 어떤 경우라도 현재 V의 값을 리턴한다.(compare-and-set이라는 약간 다른 연산의 경우 리턴되는 값은 설정 연산이 성공했는지의 여부라는 점을 참고하자) 만약 여러 스레드가 동시에 CAS연산을 사용해 한 변수의 값을 변경하려고 한다면, 스레드 가운데 하나만 성공적으로 값을 변경할 것이고, 다른 스레드들은 모두 실패한다. 대신 값을 변경하지 못했다고 해서 Lock을 확보하는 것처럼 대기 상태에 들어가는 대신, 값을 변경하지 못했지만 다시 시도할 수 있다고 알림을 받는 셈이다. CAS연산에 실패한 스레드도 대기상태에 들어가지 않기 때문에 스레드마다 CAS연산을 다시 시도할 것인지, 아니면 다른 방법을 취할 것인지, 아니면 아예 아무 조치도 취하지 않을 것인지를 결정할 수 있다. CAS를 활용하는 일반적인 방법은 먼저 V에 들어 있는 A를 읽어내고, A값을 바탕으로 새로운 값 B를 만들어 낸 후 CAS연산을 사용해 V에 들어 있는 A 값을 B값으로 변경하도록 시도한다. 다른 스레드에서 그 사이에 V의 값을 A가 아닌 다른 값으로 변경하지 않은 한 CAS연산이 성공하게 된다. 이처럼 CAS 연산을 사용하면 다른 스레드와 간섭이 발생했는지를 확인할 수 있기 때문에 Lock을 사용하지 않으면서도 읽고-변경하고-쓰는 연산을 단일 연산으로 구현해야 한다는 문제를 간단하게 해결 할 수 있다.

JVM에서의 CAS 연산 지원

 JAVA 5.0 이전에는 native 코드를 작성하지 않는 한 불가능한 일이었다. JAVA 5.0 이후 부터는 int, long 그리고 모든 객체의 참조를 대상으로 CAS 연산이 가능하도록 기능이 추가되었으며, JVM은 CAS 연산을 호출받았을 때 해당하는 하드웨어에 적당한 가장 효과적인 방법으로 처리하도록 되어있다. CAS 연산을 직접 지원하는 플랫폼(운영체제)의 경우 JAVA 프로그램을 실행할 때 CAS 연산 호출 부분을 직접 해당하는 기계어 코드로 변환해 실행한다. 하드웨어에서 CAS 연산을 지원하지 않는 최악의 경우에는 JVM자체적으로 스핀 락을 사용해 CAS연산을 구현한다. 이와 같은 저수준의 CAS연산은 단일 연산 변수 클래스, 즉 AtomicInteger와 같이 java.util.concurrent.atomic 패키지의 AtomicXxx클래스를 통해 제공한다. java.util.concurrent 패키지의 클래스 대부분을 구현할 때 이와 같은 AtomicXxx클래스가 직간접적으로 사용됐다.

public class AtomicTest {

    public static void main(String... args) {
        AtomicInteger atomic = new AtomicInteger(0);
        int value = 0;
        int update = 1;
        
        while(!atomic.compareAndSet(value, update)) {
            ; // TO DO SOMETHING
        }
        
        System.out.println(atomic.get());
    }
}

Non-Blocking 알고리즘

 Lock기반으로 동작하는 알고리즘은 항상 다양한 종류의 가용성 문제에 직면할 위험이 있다. Lock을 현재 확보하고 있는 스레드가 I/O작업 때문에 대기 중이라거나, 메모리 페이징 때문에 대기 중이라거나, 기타 어떤 원인 때문에라도 대기 상태에 들어간다면 다른 모든 스레드(Lock을 획득하기 위해 대기하고 있는)가 전부 대기 상태에 들어갈 가능성이 있다. 특정 스레드에서 작업이 실패하거나 또는 대기 상태에 들어가는 경우에, 다른 어떤 스레드라도 그로인해 실패하거나 대기 상태에 들어가지 않는 알고리즘을 Non-Blocking 알고리즘이라고 한다. 또한 각 작업 단계마다 일부 스레드는 항상 작업을 진행할 수 있는 경우 Lock-Free 알고리즘이라고 한다. 스레드 간의 작업조율을 위해 CAS 연산을 독점적으로 사용하는 알고리즘을 올바로 구현한 경우에는 대기 상태에 들어가지 않는 특성과 Lock-Free 특성을 함께 가지게 된다. 여러 스레드가 경쟁하지 않는 상황이라면 CAS 연산은 항상 성공하고, 여러 스레드가 경쟁을 한다고 해도 최소한 하나의 스레드는 반드시 성공하기 때문에 성공한 스레드는 작업을 진행할 수 있다. Non-Blocking 알고리즘은 Dead-Lock이나 우선 순위 역전(priority-inversion)등의 문제점이 발생하지 않는다.(지속적으로 재시도만 하고 있을 가능성도 있기 때문에 라이브락 등의 문제점이 발생할 가능성이 있기는 하다.) Non-Blocking 알고리즘이 적용된 Non-Blocking Stack을 예로 살펴보자. Non-Blocking 알고리즘이 적용된 자료구조를 Lock-Free 자료구조라고 한다.

Non-Blocking Stack

public class NonBlockingStack<T> {

    final AtomicReference<Node<T>> top = new AtomicReference<Node<T>>();
    
    public void push(T item) {
    	Node<T> newHead = new Node<T>(item);
        Node<T> oldHead;
        
        do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));
    }
    
    public T pop() {
    	Node<T> oldHead;
        Node<T> newHead;
        
        do {
            oldHead = top.get();
            if (oldHead == null) {
            	return null;
            }
            
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));
        
        return oldHead.item;
    }
    
    private static class Node<T> {
    	public final T item;
        public Node<T> next;
        
        public Node(T item) {
            this.item = item;
        }
    }
}

 위의 코드는 Non-Blocking Stack의 구현 코드이다. CAS연산을 시작하기 전에 알고 있던 top 항목이 CAS 연산을 시작한 이후에도 동일한 값이었다면 CAS 연산이 성공한다. 반대로 다른 스레드에서 그 사이에 top 항목을 변경했다면 CAS 연산이 실패하며, 현재의 top항목을 기준으로 다시 새로운 Node 인스턴스를 top으로 설정하기 위해 CAS 연산을 재시도한다. CAS 연산이 성공하거나 실패하는 어떤 경우라 해도 스택은 항상 안정적인 상태를 유지한다.

 

참고 서적

 

  • JAVA CONCURRENCY IN PRACTICE
  • 프로그래머가 몰랐던 멀티코어 CPU이야기
반응형
Comments