자바 병렬 프로그래밍 - 15장 단일 연산 변수와 넌블로킹 동기화

단일 연산 변수와 대기 상태에 들어가지 않는 넌블로킹 동기화 기법에 대해서 살펴본다.

 

넌블로킹 알고리즘은 락을 기반으로 하는 방법보다 설계와 구현 모두 훨씬 복잡함.

대신 확장성과 활동성을 엄청나게 높여준다.

 

여러 스레드가 동일한 자료를 놓고 경쟁하는 과정에서 대기 상태에 들어가는 일이 없어서 스케줄링 부하를 대폭 줄여준다.

 

데드락이나 기타 활동성 문제가 발생할 위험도 없다.

 

15.1 락의 단점

 

락 확보 경쟁이 벌어지는 상황에서는 JVM 역시 운영체제 도움을 받는다.

 

스레드가 락을 확보하기 위해 대기하고 있는 상태에서 대기 중인 스레드는 다른 작업을 전혀 못한다.

 

이런 상태에서 락을 확보하고 있는 스레드의 작업이 지연되면 락 확보를 위해 대기하던 모든 스레드의 작업이 전부 지연된다.

 

스레드 실행을 중단했다가 다시 실행하는 방법은 상당한 부하 발생

 

카운터 값 증가와 같은 세밀한 작업은 연산을 동기화하기에 락이 너무 무거운 방법임.

 

 

15.2 병렬 연산을 위한 하드웨어적인 자원

 

베타적인 락 방법은 보수적인 동기화 방법임.

 

일단 값을 변경하고 다른 스레드의 간섭 없이 값이 제대로 변경되는 낙관적인 방법이 있다.

 

충돌 검출 방법을 통해 값을 변경하는 동안 다른 스레드의 간섭이 있었는지 확인하고,

만약 간섭이 있었다면 연산 실패 후 재시도 혹은 재시도를 하지 않는다.

 

“허락을 받기보다는 나중에 용서를 구하는 편이 더 쉽다”

 

멀티프로세서 연산을 염두에 두고 만들어진 프로세서는 공유 변수 동시 접근 상황을 간단히 관리할 수 있도록 특별한 명령어를 제공함.(CAS, LL, SC 등)

 

 

15.2.1 비교 후 치환(Compare And Swap)

 

IA32, Sparc 같은 프로세서에서 채택하고 있는 방법은 비교 후 치환(CAS) 명령을 제공하는 방법이다.

 

만약 여러 스레드가 동시에 CAS 연산을 사용해 한 변수의 값을 변경하려고 하면,

스레드 가운데 하나만 성공적으로 값을 변경하고 나머지 스레드는 모두 실패한다.

 

이와 같은 CAS 연산의 유연성 때문에 락 사용 시 발생할 수 있는 여러 가지 활동성 문제를 미연에 방지할 수 있음.

 

[CAS 연산 예제]

 

package com.may.java.concurrent;

import net.jcip.annotations.GuardedBy;
import net.jcip.annotations.ThreadSafe;

@ThreadSafe
public class SimulatedCAS {
    @GuardedBy("this")
    private int value;
   
    public synchronized int get() {
        return value;
    }
   
    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        int oldValue = value;
       
        if (oldValue == expectedValue) {
            value = newValue;
        }
       
        return oldValue;
    }
   
    public synchronized boolean compareAndSet(int expectedValue, int newValue) {
        return (expectedValue == compareAndSwap(expectedValue, newValue));
    }

}

 

 

15.2.2 넌블로킹 카운터

 

예제 15.2는 CAS 연산을 사용해 대기 상태에 들어가지 않으면서도 스레드 경쟁에 안전한 카운터 클래스이다.

 

[예제 15.2]

 

import net.jcip.annotations.ThreadSafe;

@ThreadSafe
public class CasCounter {
    private SimulatedCAS value;

    public SimulatedCAS getValue() {
        return value;
    }
   
    public int increment() {
        int v;
       
        do {
            v = value.get();
        } while (v != value.compareAndSwap(v, v + 1));
       
        return v + 1;
    }
}

 

 

그냥 보기에는 CAS 기반의 카운터 클래스가 락 기반의 카운터보다 훨씬 성능이 떨어질 것 같지만 그렇지 않다.

 

락 기반의 프로그램을 보면 언어적인 문법은 훨씬 간결하지만, JVM과 운영체제가 락 처리를 위한 작업은 간단하지 않다.

 

 

15.2.3 JVM에서의 CAS 연산 지원

 

자바에서 하드웨어 프로세서의 CAS 연산을 호출하려면 AtomicInteger와 같은 java.util.concurrent.atomic 패키지의 AtomicXxx 클래스를 사용하면 된다.

 

 

15.3 단일 연산 변수 클래스

 

단일 연산 변수는 락보다 훨씬 가벼우면서 세밀한 구조를 가지고 있다.

 

멀티프로세서에서 고성능 병렬 프로그램 작성 시 핵심적 역할을 한다.

 

 

15.3.1 더 나은 volatile 변수로의 단일 연산 클래스

 

volatile 을 사용함으로 얻을 수 있었던 메모리 가시성을 단일 연산 변수 클래스를 사용함으로써도 얻을 수 있음.

 

메모리 가시성과 더불어 동기화에 대한 보장도 받을 수 있음.

 

=> 더 나은 volatile 변수 역할을 할 수 있다.

 

 

import net.jcip.annotations.Immutable;

import java.util.concurrent.atomic.AtomicReference;

public class CasNumberRange {
    @Immutable
    private static class IntPair {
        final int lower; // 불변조건 : lower <= upper
        final int upper;

        public IntPair(int lower, int upper) {
            this.lower = lower;
            this.upper = upper;
        }
    }

    private final AtomicReference<IntPair> values = new AtomicReference<IntPair>(new IntPair(0, 0));

    public int getLower() {
        return values.get().lower;
    }

    public int Upper() {
        return values.get().upper;
    }

    public void setLower(int i) {
        while (true) {
            IntPair oldv = values.get();

            if (i > oldv.upper) {
                throw new IllegalArgumentException("Can't set lower to " + i + " > upper");
            }

            IntPair newv = new IntPair(i, oldv.upper);
            if (values.compareAndSet(oldv, newv)) {
                return;
            }
        }

        // setUpper 메소드도 setLower와 비슷하다.
    }

}

 

 

15.3.2 성능 비교 : 락과 단일 연산 변수

 

- 경쟁이 많은 상황에서는 단일 연산 변수보다 락이 빠르게 처리됨.

 

- 하지만 실제적인 경쟁 상황에서는 단일 연산 변수가 락보다 성능이 좋음.

(단일 연산 변수는 일반적인 경쟁 상황에서 더 효율적으로 처리하게 때문)

 

- 경쟁이 적거나 보통일 경우 : 단일 연산 변수

경쟁 아주 많은 경우 : 락

이렇게 사용하는 것이 좋다!

 

- 하지만 스레드 별로 각자의 값을 사용하게 할 수 있어서 ThreadLocal을 사용한다면 그것이 가장 성능이 좋다.

 

 

15.4 넌블로킹 알고리즘

 

- 넌블로킹 알고리즘 : 특정 스레드에서 작업이 실패하거나 대기 상태에 들어가는 경우에, 다른 어떤 스레드라도 그로 인해 실패하거나 대기 상태에 들어가지 않는 알고리즘.

 

- 락 대신 CAS를 사용해서 구현한 알고리즘을 말한다고 보면 된다.

 

 

[예제 15.6 트라이버 알고리즘으로 대기 상태에 들어가지 않도록 구현한 스택]

 

import java.util.concurrent.atomic.AtomicReference;

public class ConcurrentStack<E> {
    AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();
   
    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;
       
        do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));
    }
   
    public E pop() {
        Node<E> oldHead;
        Node<E> 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<E> {
        public final E item;
        public Node<E> next;
       
        public Node(E item) {
            this.item = item;
        }
    }
}

 

 

 

[예제 15.7 마이클-스콧 넌블로킹 큐 알고리즘 가운데 항목 추가 부분]

 

package com.may.java.concurrent;

import net.jcip.annotations.ThreadSafe;

import java.util.concurrent.atomic.AtomicReference;

@ThreadSafe
public class LindedQueue <E> {
    private static class Node <E> {
        final E item;
        final AtomicReference<Node<E>> next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = new AtomicReference<Node<E>>(next);
        }
    }
   
    private final Node<E> dummy = new Node<E>(null, null);
    private final AtomicReference<Node<E>> head = new AtomicReference<Node<E>>(dummy);
    private final AtomicReference<Node<E>> tail = new AtomicReference<Node<E>>(dummy);
   
    public boolean put(E item) {
        Node<E> newNode = new Node<E>(item, null);
       
        while (true) {
            Node<E> curTail = tail.get();
            Node<E> tailNext = curTail.next.get();
           
            if (curTail == tail.get()) {
                if (tailNext != null) {
                    // 큐는 중간 상태이고, 꼬리 이동
                    tail.compareAndSet(curTail, tailNext);
                } else {
                    // 평온한 상태에서 항목 추가 시도
                    if (curTail.next.compareAndSet(null, newNode)) {
                        // 추가 작업 성공, 꼬리 이동 시도
                        tail.compareAndSet(curTail, newNode);
                        return true;
                    }
                }
            }
        }
    }
   
}

 

 

15.4.3 단일 연산 필드 업데이터

 

15.4.4 ABA 문제

 

CAS 연산 시 발생할 수 있는 문제

현재 A인 상태를 확인하는 변수값이 A->B->A 이렇게 돌아온 경우.

(참조형 변수의 경우 메모리 주소를 의미한다)

메모리 주소는 같지만 실제 다른 값으로 내용이 변경되었을 수 도 있다.

 

일반적인 방법으로는 이런 경우를 확인할 수 없어서, AtomicStampedReference 클래스를 이용하면 된다.

 

AtomicStampedReference는 객체 참조와 버전 번호를 같이 저장한다.