[Java Concurrency] 단일 연산 변수와 넌블로킹 동기화

[Java Concurrency] 단일 연산 변수와 넌블로킹 동기화

-
병렬 알고리즘과 관련한 최근의 연구 결과를 보면 대부분이 넌블로킹 알고리즘,
즉 여러 스레드가 동작하는 환경에서 데이터의 안정성을 보장하는 방법으로 락을 사용하는 대신
저수준의 하드웨어에서 제공하는 비교 후 교환(compare-and-swap) 등의 명령을 사용하는 알고리즘을 다루고 있다.


-
넌블로킹 알고리즘은 운영체제나 JVM 에서 프로세스나 스레드를 스케줄링 하거나
가비지 컬렉션 작업, 그리고 락이나 기타 병렬 자료 구조를 구현하는 부분에서 굉장히 많이 사용하고 있다.


-
넌블로킹 알고리즘은 락을 기반으로 하는 방법보다
설계와 구현 모두 훨씬 복잡하며,
대신 확장성과 활동성을 엄청나게 높여준다.


-
넌블로킹 알고리즘은 훨씬 세밀한 수준에서 동작하며,
여러 스레드가 동일한 자료를 놓고 경쟁하는 과정에서 대기 상태에 들어가는 일이 없기 때문에
스케줄링 부하를 대폭 줄여준다.
더군다나 데드락이나 기타 활동성 문제가 발생할 위험도 없다.


-
자바 5.0부터는 AtomicInteger 나 AtomicReference 등의 단일 연산 변수(atomic variable) 를 사용해
넌블로킹 알고리즘을 효율적으로 구현할 수 있게 됐다.


-
단일 연산 변수는 본격적인 넌블로킹 알고리즘을 구현하는 일이 아니라 해도 '더 나은 volatile 변수' 의 역할만으로 사용할 수도 있다.
단일 연산 변수는 volatile 변수와 동일한 메모리 유형을 갖고 있으며
이에 덧붙여 단일 연산으로 값을 변경할 수 있는 기능을 갖고 있다.

15.1. 락의 단점

-
최근 사용하는 JVM 은 스레드 간의 경쟁이 없는 상태에서 락을 확보하는 부분을 최적화하는 기능을 갖고 있으며
락을 해제하는 부분도 굉장히 효율적이다.
하지만 락 확보 경쟁이 벌어지는 상황에서는 JVM 역시 운영체제의 도움을 받는다.


-
스레드의 실행을 중단했다가 계속해서 실행하는 작업은 상당한 부하를 발생시키며
일반적으로 적지 않은 시간 동안 작업이 중단되게 된다.
락을 기반으로 세말한 작업을 주로 하도록 구현돼 있는 클래스는
락에 대한 경쟁이 심해질수록 실제로 필요한 작업을 처리하는 시간 대비 동기화 작업에 필요한 시간의 비율이 상당한 수치로 높아질 가능성이 있다.


-
volatile 변수는 락과 비교해 봤을 때 컨텍스트 스위칭이나 스레드 스케줄링과 아무런 연관이 없기 때문에
락보다 훨씬 가벼운 동기화 방법이라고 볼 수 있다.
반면 volatile 변수는 락과 비교할 때 가시성 측면에서는 비슷한 수준을 보장하긴 하지만,
복합 연산을 하나의 단일 연산으로 처리할 수 있게 해주는 기능은 전혀 갖고 있지 않다.
따라서 하나의 변수가 다른 변수와 관련된 상태로 사용해야 하거나,
하나의 변수라도 해당 변수의 새로운 값이 이전 값과 관련이 있다면
volatile 변수를 사용할 수 없다.


-
락을 확보하고 지연되는 스레드의 우선 순위가 떨어지고 대기 상태에 있는 스레드의 우선 순위가 높다면
프로그램의 성능에 심각한 영향을 미칠 수 있으며,
이런 현상을 우선 순위 역전(priority inversion) 이라고 부른다.
즉 대기 중인 스레드의 우선 순위가 높음에도 불구하고
락이 해제될 때까지 대기해야 하며,
결과적으로 락을 확보하고 있는 스레드의 우선 순위보다 더 낮은 우선순위를 가진 것처럼 동작한다.

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

-
배타적인 락 방법은 보수적인 동기화 기법이다.
즉 가장 최악의 상황을 가정하고 완전하게 확실한 조치를 취하기 전에는 더 이상 진행하지 않는 방법을 택하고 있는데,
바로 락을 확보하고 나면 다른 스레드가 절대 간섭하지 못하는 구조이다.


-
멀티프로세서 연산을 염두에 두고 만들어진 프로세서는 공유된 변수를 놓고 동시에 여러 작업을 해야 하는 상황을 간단하게 관리할 수 있도록 특별한 명령어를 제공한다.
초기의 프로세서는 확인하고 값 설정(test-and-set), 값을 읽어와서 증가(fetch-and-increment), 치환(swap) 등의 단일 연산을 하드웨어적으로 제공했으며, 이런 연산을 기반으로 더 복잡한 병렬 클래스를 쉽게 만드는 데 도움이 되는 뮤텍스(mutex)를 충분히 구현할 수 있었다.
최근에는 거의 모든 프로세서에서 읽고-변경하고-쓰는 단일 연산을 하드웨어적으로 제공하고 있다.



* 15.2.1. 비교 후 치환

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


-
CAS 연산은 일단 성공적으로 치환할 수 있을 것이라고 희망하는 상태에서 연산을 실행해보고,
값을 마지막으로 확인한 이후에 다른 스레드가 해당하는 값을 변경했다면 그런 사실이 있는지를 확인이나 하자는 의미이다.


-
만약 여러 스레드가 동시에 CAS 연산을 사용해 한 변수의 값을 변경하려고 한다면,
스레드 가운데 하나만 성공적으로 값을 변경할 것이고,
다른 나머지 스레드는 모두 실패한다.
대신 값을 변경하지 못했다고 해서 락을 확보하는 것처럼 대기 상태에 들어가는 대신,
이번에는 값을 변경하지 못했지만 다시 시도할 수 있다고 통보를 받는 셈이다.
CAS 연산에 실패한 스레드도 대기 상태에 들어가지 않기 때문에
스레드마다 CAS 연산을 다시 시도할 것인지,
아니면 다른 방법을 취할 것인지,
아니면 아예 아무 조치도 취하지 않을 것인지를 결정할 수 있다.
이와 같은 CAS 연산의 유연성 때문에 락을 사용하면서 발생할 수밖에 없었던 여러가지 활동성 문제를 미연에 방지할 수 있다.



* 15.2.2. 넌블로킹 카운터

-
실제 사용한 예를 보면 많지 않은 양의 경쟁이있는 상황에서도 CAS 기반의 클래스가 락 기반의 클래스보다 성능이 훨씬 좋고,
경쟁이 없는 경우에도 락 기반의 방법보다 나은 경우가 있다.


-
경쟁이 적거나 어느 정도의 경쟁이 발생할 때까지는
CAS 연산은 대부분 성공하는 경우가 많기 때문에 하드웨어에서 분기 지점과 흐름을 예측해
코드에 들어 있는 while 반복문을 포함한 복잡한 논리적인 작업 흐름 구조에서 발생할 수 있는 부하를 최소화 할 수 있다.


-
CAS 연산의 가장 큰 단점은 호출하는 프로그램에서 직접 스레드 경쟁 조건에대한 처리(재시도하거나 나중에 처리하거나 무시해 버린다)를 해야 한다는 점이 있는데, 반면 락을 사용하면 락을 사용할 수 있을 때까지 대기 상태에 들어가도록 하면서 스레드 경쟁 문제를 알아서 처리해준다는 차이점이 있다.


-
CAS 연산의 성능은 프로세서마다 크게 차이가 난다.
CAS 연산의 성능은 프로세서의 구조나 심지어는 같은 프로세서의 서로 다른 버전 간에도 너무나 다양한 차이를 보이고 있다.


-
대략 정리하자면 스레드 간의 경쟁이 없는 상태에서 락을 가장 빠른 경로로 확보하고 해제하는 데 드는 자원은
CAS 연산을 사용할 때보다 약 2배 정도 된다고 보면 무리가 없다.



* 15.2.3. JVM 에서의 CAS 연산 지원

-
자바 5.0부터는 int, long 그리고 모든 객체의 참조를 대상으로 CAS 연산이 가능하도록 기능이 추가됐고,
JVM 은 CAS 연산을 호출받았을 때 해당하는 하드웨어에 적당한 가장 효과적인 방법으로 처리하도록 돼 있다.


-
저수준의 CAS 연산은 단일 연산 변수 클래스,
즉 AtomicInteger 와 같이 java.util.concurrent.atomic 패키지의
AtomicXxx 클래스를 통해 제공한다.
java.util.concurrent 패키지의 클래스 대부분을 구현할 때 이와 같은 AtomicXxx 클래스가 직간접적으로 사용됐다.

15.3. 단일 연산 변수 클래스

-
단일 연산 변수(atomic variable) 는 락보다 훨씬 가벼우면서 세밀한 구조를 갖고 있으며, 멀티프로세서 시스템에서 고성능의 병렬 프로그램을 작성하고자 할 때 핵심적인 역할을 한다.
단일 연산 변수를 사용하면 스레드가 경쟁하는 범위를 하나의 변수로 좁혀주는 효과가 있으며,
이 정도의 범위는 프로그램에서 할 수 있는 가장 세밀한 범위이다.


-
경쟁이 없는 상태에서 단일 연산 변수의 값을 변경하는 실행 경로는 락을 확보하는 가장 빠른 코드 실행 경로보다 느릴 수 없으며, 대부분 단일 연산 변수 쪽이 더 빠르게 실행된다.
느리게 실행되는 경우를 비교해보면,
락을 사용해 구현된 부분과 같이 대기 상태에 들어가거나
스레드 스케줄링과 관련된 문제가 발생하지 않기 때문에 단일 연산 변수를 사용하는 쪽이 명백하게 더 빠르게 실행된다.


-
락 대신 단일 연산 변수 기반의 알고리즘으로 구현된 프로그램은 내부의 스레드가 지연되는 현상이 거의 없으며,
스레드 간의 경쟁이 발생한다 해도 훨씬 쉽게 경쟁 상황을 헤쳐나갈 수 있다.


-
단일 연산 변수 클래스는 volatile 변수에서 읽고-변경하고-쓰는 것과 같은 조건부 단일 연산을 지원하도록 일반화한 구조이다.
AtomicInteger 클래스는 int 값을 나타내며,
일반적인 volatile 변수로 사용할 때 변수의 값을 읽거나 쓰는 연산과 동일한 기능을 하는 get 메소드와 set 메소드를 제공한다.
또한 단일 연산으로 실행되는 compareAndSet 메소드도 제공하며,
그 외의 편의 사항인 단일 연산으로 값을 더하거나, 증가시키거나, 감소시키는 등의 메소드도 제공한다.


-
동기화를 위한 하드웨어의 기능을 직접적으로 활용할 수 있기 때문에
경쟁이 발생하는 상황에서 훨씬 높은 확장성을 제공한다.


-
가장 많이 사용하는 형태는 바로 일반 변수의 형태를 그대로 갖고 있는 AtomicInteger, AtomicLong, AtomicBoolean, AtomicReference 클래스이다.
네 가지 모두 CAS 연산을 제공하며, ( 제공되지 않는 형태의 변수를 단일 연산 변수로 사용하려면, short 나 byte 의 경우에는 int 로 강제 형변환해서 읽거나 쓰면 되고, 정수가 아닌 숫자를 사용하려는 경우에는 Float.floatToIntBits 메소드나 Double.doubleToLongBits 메소드를 사용하면 된다.)


-
단일 연산 배열 변수 클래스(Integer형, Long형, Reference 형이 준비돼 있다.)는
배열의 각 항목을 단일 연산으로 업데이트할 수 있도록 구성돼 있는 배열 클래스이다.
단일 연산 배열 클래스는 배열의 각 항목에 대해 volatile 변수와 같은 구조의 접근방법을 제공한다.


-
단일 연산 변수는 Number 클래스를 상속받고 있다.


-
단일 연산 클래스는 hashCode 메소드나 equals 메소드를 재정의하고 있지는 않으며, 모든 인스턴스가 서로 다르다.
내부 값을 변경할 수 있는 모든 클래스가 그렇지만, 해시 값을 기반으로 하는 컬렉션 클래스에 키 값으로 사용하기에는 적절하지 않다는 점을 잊지 말자.



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

-
AtomicReference 클래스를 적용하면,
경쟁 조건이 발생하지 않게 하면서 범위를 표현하는 값 두 개를 한꺼번에 변경할 수 있다.



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

-
상태 변수를 공유하지 않고 동작하는 방법이 있다면 최대한 공유하지 않는 쪽이 낫다.
스레드 간의 경쟁을 최대한 적절하게 처리하면 확장성을 어느 정도 향상시킬 수 있다.
하지만 최종적으로 확장성을 가장 높일 수 있는 방법은 스레드 간의 경쟁이 발생하지 않도록 미연에 방지하는 방법이라는 점!

15.4. 넌블로킹 알고리즘

-
락 기반으로 동작하는 알고리즘은 항상 다양한 종류의 가용성 문제에 직면할 위험이 있다.


-
특정 스레드에서 작업이 실패하거나 또는 대기 상태에 들어가는 경우에,
다른 어떤 스레드라도 그로 인해 실패하거나 대기 상태에 들어가지 않는 알고리즘을 대기 상태에 들어가지 않는 알고리즘,
즉 넌블로킹(non-blocking) 알고리즘이라고 한다.
또한 각 작업 단계마다 일부 스레드는 항상 작업을 진행할 수 있는 경우 락 프리(lock-free) 알고리즘이라고 한다.
스레드 간의 작업 조율을 위해 CAS 연산을 독점적으로 사용하는 알고리즘을 올바로 구현한 경우에는 대기 상태에 들어가지 않는 특성과 락 프리 특성을 함께 가지게 된다.


-
넌블로킹 알고리즘은 데드락이나 우선 순위 역전등의 문제점이 발생하지 않는다.
(물론 지속적으로 재시도만 하고 있을 가능성도 있기 떄문에 라이브락 등의 문제점이 발생할 가능성도 있기는 하다.)



* 15.4.1. 넌 블로킹 스택

-
대기 상태에 들어가지 않도록 구현한 알고리즘은 락 기반으로 구현한 알고리즘에 비해 상당히 복잡한 경우가 많다.
넌블로킹 알고리즘을 구성할 때 가장 핵심이 되는 부분은 바로 데이터의 일관성을 유지하면서
단일 연산 변경 작업의 범위를 단 하나의 변수로 제한하는 부분이다.


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


-
대기 상태에 들어가지 않는 알고리즘은 락과 같이 compareAndSet 연산을 통해 단일 연산 특성과 가시성을 보장하기 때문에 스레드 안전성을 보장한다.



* 15.4.2. 넌블로킹 연결 리스트

-
넌블로킹 알고리즘을 작성할 때 핵심은 바로 단일 연산의 범위를 단 하나의 변수로 제한하는 부분이다.


-
데이터 구조가 여러 단계의 변경 작업을 거치는 과정을 포함해 언제라도 일관적인 상태를 유지하도록 해야 한다.


-
스레드 A가 값을 변경하는 와중에 스레드 B가 데이터 구조를 사용하고자 접근하는 경우에 스레드 A가 처리중인 작업을 마쳐야 한다는 사실을 알 수 있는 충분한 정보를 데이터 구조에 넣어두는 방법이 있다.



* 15.4.3. 단일 연산 필드 업데이터

-
리플렉션(reflection) 기반의 AtomicReferenceFieldUpdater 클래스가 있다.
이 녀석은 Integer, Long, Reference 에 해당하는 버전이 준비돼 있는데,
현재 사용 중인 volatile 변수에 대한 리플렉션 기반의 "뷰"를 나타내며,
따라서 일반 volatiel 변수에 대해 CAS 연산을 사용할 수 있도록 해준다.


-
이런 단일 연산 필드 업데이터 클래스에는 생성 메소드가 없으며,
인스턴스를 생성하려면 생성 메소드를 호출하는 대신 newUpdater 라는 팩토리 메소드에 해당하는 클래스와 필드, 즉 변수의 이름을 넘겨서 생성할 수 있다.
필드 업데이터 클래스는 특정 인스턴스와 연결돼있지 않으며,
한 번만 생성하면 지정한 클래스의 모든 인스턴스에 들어 있는 지정 변수의 값을 변경할 때 항상 사용된다.


-
업데이터 클래스에서 보장하는 연산의 단일성은 일반적인 단일 연산 변수보다 약하다.
다시 말해 업데이터 클래스에 지정한 클래스의 지정 변수가 업데이터 클래스를 통하지 않고 직접 변경되는 경우가 있다면
연산의 단일성을 보장할 수 없다.
따라서 필드 업데이터 클래스로 지정한 변수에 대해 연산의 단일성을 보장하려면
모든 스레드에서 해당 변수의 값을 변경할 때 항상 compareAndSet 메소드나 기타 산술 연산 메소드를 사용해야만 한다.


-
약간 돌아가는듯한 이 단일 연산 필드 업데이터 방법을 사용하는 이유는 전적으로 성능을 높이기 위함이다.
큐의 연결 노드와 같이 자주 생성하면서 오래 사용하지 않은 클래스가 필요한 경우에는 AtomicReference 라는 클래스의 인스턴스 역시 매번 생성하고 없애는 부하가 생기게 된다
따라서 이런 경우에는 Node 인스턴스를 매번 생성할 때마다 AtomicReference 의 인스턴스를 함께 생성해야 할 필요성을 없앨 수 있으므로 추가작업에 대한 부하를 크게 줄여준다.



* 15.4.4. ABA 문제

-
ABA 문제는 노드를 재사용하는 알고리즘에서 비교 후 치환(compare-and-swap)연산을 고지식하게 사용하다보면 발생할 수 있는 이상 현상을 말한다.
CAS 연산은 "V변수의 값이 여전히 A인지?"를 확인하고 만약 그렇다면 값을 B 로 변경하는 작업을 진행한다.
대부분의 경우에는 이정도의 확인만으로 충분하다.
간혹 "V변수의 값이 내가 마지막으로 A값이라고 확인한 이후에 변경된 적이 있는지?" 라는 질문의 답을 알아야 할 경우도 있다.
일부 알고리즘을 사용하다 보면 V변수의 값이 A에서 B로 변경되었다가 다시 A로변경된 경우 역시 변경 사항이있었다는 것으로 인식하고 그에 해당하는 재시도 절차를 밟아야 할 필요가 있기도 하다.


-
ABA 문제는 연결 노드 객체에 대한 메모리 관리 부분을 직접 처리하는 알고리즘을 사용할 때 많이 발생한다.
연결 리스트의 머리 변수가 이전에 확인했던 그 객체를 참조하고 있다는 사실만으로는 해당 리스트의 내용이 변경되지 않았다고 확신할 수 없다.

굉장히 쉬운 해결 방법은, 참조 값 하나만 변경하는 것이 아니라 참조와 버전 번호의 두 가지 값을 한꺼번에 변경하는 방법이다.
버전 번호를 관리하면 값이 A에서 B로 변경됐다가 다시 A로 변경된 경우라고 해도 버전 번호를 보고 변경된 상태라는 점을 알 수 있다.

AtomicStampedReference( or AtomicMarkableReference ) 클래스는 객체에 대한 참조와 숫자 값을 함께 변경하며,
버전 번호를 사용해 ABA 문제가 발생하지 않는 참조의 역할을 한다.
AtomicMarkableReference 클래스 역시 이와 유사하게 객체에 대한 참조와 불린 값을 함께 변경하며, 일부 알고리즘에서 노드 객체를 그대로 놓아두지만 삭제된 상태임을 표시하는 기능으로 활용하기도 한다.

Summary

-
대기 상태에 들어가지 않는 넌블로킹 알고리즘은 락 대신 비교 후 치환(compare-and-swap)과 같은 저수준의 명령을 활용해 스레드 안전성을 유지하는 알고리즘이다.
이런 저수준의 기능은 특별하게 만들어진 단일 연산 클래스를 통해 사용할 수 있으며,
단일 연산 클래스는 "더 나은 volatile 변수"로써 정수형 변수나 객체에 대한 참조 등을 대상으로 단일 연산 기능을 제공하기도 한다.

넌블로킹 알고리즘을 설계하고 구현하기는 훨씬 어렵지만, 특정 조건에서는 훨씬 나은 확장성을 제공하기도 하고,
가용성 문제를 발생시키지 않는다는 장점이 있다.

JVM 이나 플랫폼 자체의 라이브러리에서 대기 상태에 들어가지 않는 알고리즘을 적절히 활용하는 범위가 넓어지면서
JVM 의 버전이 올라갈 때마다 병렬 프로그램의 성능이 계속해서 나아지고 있다.

이전글 : [Java Concurrency] 동기화 클래스 구현

다음글 : [Java Concurrency] 자바 메모리 모델

ABA, aba 문제, atomic package, atomic variable, AtomicBoolean, atomicinteger, atomiclong, atomicmarkablereference, atomicreference, atomicreferencefieldupdater, atomicstampedreference, byte, CAS, cas 연산 성능, cas 연산의 가장 큰 단점, compare and swap, compareAndSet, concurrent, Double, doubletolongbits, equals, fetch and increment, float, floattointbits, GC, hashcode, IA32, iNT, integer, java concurrency, jvm, jvm 에서 cas 연산 지원, lock free, long, mutex, newUpdater, number, priority inversion, Reference, Reflection, Short, SPARC, swap, test and set, volatile, [Java Concurrency] 단일 연산 변수와 넌블로킹 동기화, 가비지 컬렉션 작업, 가시성, 가용성, 감소, 경쟁 상황, 구조, 구현, 나중 처리, 넌 블로킹 스택, 넌 블로킹 알고리즘, 넌블로킹 동기화, 넌블로킹 알고리즘, 넌블로킹 연결 리스트, 넌블로킹 카운터, 단일 ㅇㄴ산 변수, 단일 연산, 단일 연산 변수, 단일 연산 변수 클래스, 단일 연산 필드 업데이터, 단일성, 대기, 더 나은 volatile 변수, 데드락, 동기화, 동기화 비용, 동작, 라이브락, 락, 락 기반, 락 프리 알고리즘, 락 확보, 락 확보 경쟁, 락과 단일 연산 변수, 락보다 가벼운 동기화 방법, 락의 단점, 리플렉션, 명령어, 무시, 뮤덱트, 배타적인 락, 변수 이름, 병렬 알고리즘, 병렬 연산을 위한 하드웨어적인 지원, 병렬 자료 구조, 보수적인 동기화 기법, 복잡, 복합 연산, 비교 후 치환, 상태 변수, 생성, 설계, 성능, 성능 비교, 숫자, 스레드 경쟁 조건 처리, 스레드 실행, 스케줄링, 연결 노드, 연산 범위, 우선 순위 역전, 운영체제, 인스턴스, 일관성, 일반 volatile 변수, 재시도, 저수준 cas 연상, 적절하지 않다, 정수, 증가, 참조, 참조 숫자, 최적화, 컨텍스트 스위칭, 컬렉션 클래스, 클래스, 팩토리 메소드, 프로세서, 하나의 변수, 하드웨어 단일연산, 확보, 확장성, 활동성