[Kotlin] 동시성 문제와 해결방법

소프트웨어를 개발하는 데 있어서, 성능을 높이기 위해 가장 흔하게 사용할 수 있는 방법은 병렬로 실행하는 것 입니다. 병렬 실행은 하드웨어의 특성을 이용하여 성능을 높이는 가장 좋은 방법이지만, 병렬로 여러 프로세스나 스레드에서 같은 데이터를 접근하여 읽고 쓰는 과정이 수행될 때, 데이터에 대한 일관성과 안정성을 지키지 못하는 문제가 발생하게 됩니다. (다른말로 무결성 을 위배한다고 말합니다.)

멀티 스레드나 멀티 프로세스 환경에서 데이터에 대한 무결성을 지키는 것은 매우 중요합니다. 이것은 소프트웨어를 사용하는 사용자에게 데이터에 대한 신뢰성을 보장하지 못하여 사용자 경험이 떨어지는 문제를 초래할 수 있기 때문입니다.

운영체제, 데이터베이스의 트랜잭션 등 의 CS 교과목에서 저는 이미 이와 관련한 내용들을 충분히 학습했었습니다. 하지만, Java 기반의 Kotlin 언어로 구현하는 안드로이드 앱에서 이를 실질적으로 해결하는 방법들에 대해서는 미숙했었습니다.

이번 포스팅에서는 멀티스레드나 멀티 코어 환경에서 구체적으로 어떤 문제들이 발생하며, 어떻게 발생할 수 있고, Java 기반의 Kotlin 언어로 이를 어떻게 해결할 수 있는지 의 방법들에 대해 정리해보고자 합니다.

Race Condition

동시에 여러 스레드나 프로세스가 동일한 데이터에 접근하여 읽기 만 수행할 경우 문제가 발생하지는 않습니다. 데이터의 변화가 없는 상태에서 읽었기 때문에 동일한 데이터의 결과를 얻었을 것입니다. 이렇게 특정 작업을 수행했을 때 예측되는 결과가 나오는 경우 일관성 또는 안정성 을 보장하고 “데이터가 무결하다”는 의미로 무결성 을 만족한다고 합니다.

하지만, 읽기 와 쓰기 를 동시에 수행하는 경우는 말이 달라집니다. 누가 먼저 데이터를 읽고, 쓰기를 수행했느냐 에 따라 그 결과가 달라지게 됩니다. 이렇게 결과를 예측할 수 없는(일관성을 보장할 수 없는) 경우를 Race Condition 이라고 부릅니다.

Race Condition 은 “경쟁 상태” 라는 뜻입니다. 두개 이상의 스레드나 프로세스가 서로 공유 자원에 접근하기 위해 경쟁하여 누가 먼저 수행되었느냐에 따라 그 결과가 항상 달라지고 일관성을 보장할 수 없는 문제를 통칭합니다. 보통 이러한 경우 병렬 실행되는 스레드나 프로세스들의 접근을 제한하여 순차적으로 실행하도록 만들어 해결합니다. 이것을 상호 배제 라고 말합니다. 상호 배제에 대해서는 뒤에서 더 설명하기로 하고, 지금은 “순차적으로 접근하게 만든다” 라고 이해하시면 될 것 같습니다.

이 방법은 궁극적으로 특정 작업을 실행하는 스레드나 프로세스들에 대해 그 결과를 예측 가능하게 만들어 주지만, 병렬 실행의 목적이었던 성능 개선의 이점을 잃어버리게 됩니다. 따라서 모든 작업들을 순차적 실행으로 만드는 상호 배제를 만족시키는 것은 모든 상황에서 만족할 수는 없으며, Blocking 없이 동기화 할 수 있는 방법들도 뒤에서 정리해보겠습니다.

상호 배제(Mutual Exclusion)

보통 동시성에 대한 문제를 해결하는 방법으로 상호 배제 원리를 기반으로 사용합니다. 상호 배제는 공유 자원에 대해 lock 과 unlock 을 통해, 접근 가능한 스레드를 제한함으로써 동시성에 대한 문제를 해결하는 방법을 말합니다. 이는 멀티 스레드나 멀티 코어 환경에서 동시 접근을 제한하고, 순차적으로 접근하도록 만들어 동시성에 대한 무결성을 보장하는 원리입니다. 이때, 공유 자원에 대한 영역을 임계 영역 이라고 부릅니다.

lock 은 스레드가 임계 영역에 접근하여 더 이상 다른 스레드가 접근하지 못하도록 점유하기 위한 방법이며, unlock 은 임계 영역을 점유했던 스레드가 자신의 작업을 모두 마치고 공유 자원에 대한 점유를 해제하여 다른 스레드가 접근 가능하도록 만드는 방법 입니다.

상호 배제를 하면 동시성에 대한 문제를 해결할 수 있습니다. 하지만, 상호 배제를 이용하게 되면 특정 상황에서 추가적인 문제가 발생할 수 있습니다.

Dead Lock

만약, A 스레드가 A1 임계 영역을 점유하고 있고, B 스레드가 B1 임계 영역을 점유하고 있다고 가정해 봅시다. 이 때, A 스레드가 B1 임계 영역에 접근하기 위해 B가 unlock 하기를 기다리고 있고, B 스레드는 A1 임계 영역에 접근하기 위해 A 가 unlock 하기를 서로 기다리고 있는 상황이라면, 서로 영원히 서로의 자원을 내놓기를 기다려 Blocking 되어 버리는 상황이 발생할 수 있습니다. 이런 상황을 교착 상태(DeadLock) 라고 부릅니다.

보통 Dead Lock 이 발생할 조건들을 만족하지 않게 구현하거나, 발생할 경우 이를 파악하고 해결하는 방법을 이용합니다. 이에 대한 구체적 예시나 조건들은 여기를 참고하시면 되겠습니다.

이외에도 자원을 점유하고 있는 스레드나 프로세스가 영원히 점유하여 다른 스레드나 프로세스가 점유할 기회를 잃어버리는 기아상태(Starvation) 와 같은 문제도 발생할 수 있습니다.

상호 배제는 영어로 Mutual Exclusion 이라고 부르며, 이를 줄여 흔히 알고 있는 Mutex 라고 부릅니다. Mutex 는 임계영역에 대한 lock 과 unlock 을 통해 동시 접근을 막는 추상적 개념 입니다. 이를 실질적으로 소프트웨어로 구현하는 방법들에는 데커 알고리즘, 피터슨 알고리즘이 있었습니다. 하지만 이들에는 Busy waiting 과 같은 문제들이 있었습니다. 이런 문제들을 해결하여 가장 잘 알려진 것이 세마포어 알고리즘 입니다.

세마포어

기존의 알고리즘에서는 임계 영역에 접근한 스레드가 있어 현재 스레드가 접근할 수 있는지 없는지를 무한 반복문을 돌면서 확인했었습니다. 이 방법은 지속적 폴링을 실행하면서 CPU 자원을 낭비하게 되는 원인을 초래했습니다. 그래서 임계 영역에 접근하기 위해 대기하는 스레드들을 반복문으로 busy waiting 하지 않게 하고, Set 에 넣어 대기시켜 놓았다가 임계 영역에서 작업을 마치고 나오는 스레드가 대기 중인 스레드를 깨워주도록 만든 방법이 세마포어 알고리즘 입니다.

세마포어는 정수 타입의 조건 변수 S 를 가지며 P() 와 V() 연산을 통해 Mutex 를 구현합니다.

• P() 연산: S 의 값이 0 보다 큰지 확인하고, 0 보다 크다면 1감소 시킨 후 임계 영역에 진입한다. 그렇지 않다면, 대기Set 에 들어가 대기한다.
• V() 연산: 임계 영역에 진입했던 스레드가 나오면서, S 의 값을 1 증가시킨다. 이때, 대기Set 에 존재하는 스레드가 있으면 깨워줘 대기중인 스레드가 임계영역에 진입할 수 있도록 동기화 해준다.
• S: S는 임계 영역에 진입 가능한 스레드의 수를 세는 카운팅 변수 이다. 이 조건 상수를 통해 모든 스레드들이 협력할 수 있어 Busy waiting 을 하지 않아도 된다.

세마포어에는 2가지 종류로, 카운팅 변수를 2로 제한한 이진 세마포어 와 3 이상인 카운팅 세마포어 로 나뉩니다. 이진 세마포어의 경우 Mutex 로 치환될 수 있으며, 구체적 구현 방법이 적용된 사례가 됩니다.

Mutex 를 구현하는 방법들은 병렬 실행 이 아닌 순차 실행 으로 만들어 멀티 스레드나 프로세스의 이점을 잃게 만듭니다. 병렬 실행을 유지하면서 즉, Lock 과 Unlock 을 수행하지 않으면서 “동기화를 만족할 수 있는 방법은 없을까?” 하고 고안된 방법이 락-프리(Lock-Free) 알고리즘 입니다.

Lock-Free 알고리즘

Lock 을 하지 않고 병렬 실행을 유지하면서 동기화를 할 수 있는 대표적인 방법으로 CAS(Compare And Set) 가 있습니다. CAS 알고리즘은 원본 데이터를 캐싱하여 캐싱한 데이터의 복사본에 쓰기 연산을 수행하고, 복사본을 원본데이터에 적용할 때, 캐싱한 데이터와 원본 데이터를 비교하여 다른 경우 쓰기를 취소하고 재시도하는 알고리즘 입니다.

이를 실제로 구현하여 제공된 것이 Java 의 Atomic 입니다.

Atomic

Atomic 은 Int, Double, Long 과 같은 특정 타입들에 대해 Lock-Free 알고리즘 중 하나인 CAS 를 이용하여 Non-Blocking 동기화를 지원해주는 클래스 입니다. 구체적 예시로 AtomicInteger 를 살펴보겠습니다.

public class AtomicInteger extends Number implements java.io.Serializable {

  private volatile int value;
  public final int get() {  
      return value;  
  }
  public final void set(int newValue) {  
     value = newValue;  
  }

  private static final VarHandle VALUE;  
  static {  
      try {  
          MethodHandles.Lookup l = MethodHandles.lookup();  
          VALUE = l.findVarHandle(AtomicInteger.class, "value", int.class);  
      } catch (ReflectiveOperationException e) {  
          throw new ExceptionInInitializerError(e);  
      }  
  }

  public final boolean compareAndSet(int expectedValue, int newValue) {  
    return VALUE.compareAndSet(this, expectedValue, newValue);  
  }
}

AtomicInteger 클래스에 존재하는 VarHandle 타입의 Value는 내부에 Volatile 키워드가 붙은 value 의 값에 원자적으로 접근하기 위한 멤버변수 입니다. 이는 compareAndSet() 함수와 같이 동기화가 필요한 메소드에서 호출되는데, 1.value 를 가져와서 2. value 를 newValue 로 업데이트하는 두 단계 사이에 다른 스레드가 접근하여 쓰기 연산을 수행할 수 없도록 원자적으로 실행하기 위해 필요한 Delegate 입니다.

하지만 JVM 구현상 메인 메모리에서 값을 읽은 후 CPU-캐시에 저장하여 좀 더 빠르게 데이터를 읽어 오기 위한 매커니즘을 사용하기 때문에 실제로 스레드가 값을 저장하면 CPU-캐시에 저장되고, 이값이 메인 메모리에 저장되기 까지 시간이 걸리게 되면서 다른 스레드가 그 값을 읽었을 때 기대되는 값이 아닐 수 있는 가시성 문제가 발생할 수 있습니다.

따라서 value 라는 실제 값이 존재하는 변수에 Volatile 키워드가 작성되어 있습니다. Volatile 키워드는 CPU-캐시에서 값을 읽지 않고, 항상 메인 메모리로부터 값을 읽도록 만드는 키워드 입니다. 물론, Volatile 을 남용하게 되면 메인메모리에서 항상 데이터를 읽는 것은 CPU-캐시를 이용하는 것보다 느리므로 성능 문제가 발생할 수 있습니다. 결론적으로 Atomic 클래스는 Volatile 을 통해 JVM 구현상의 가시성 문제를 해결하면서, 여러 스레드가 동시에 AtomicInteger 로 접근하면서 발생할 수 있는 동시성 문제를 VarHandle 로 Delegate 하여 동기화 함으로써 해결합니다.

CAS 는 병렬 실행을 유지하면서 즉, 성능을 높이면서 동기화를 해줄 수 있는 좋은 방법이지만, 모든 알고리즘과 디자인 패턴들이 그러하듯, 특정 상황에서는 문제가 발생할 수 있습니다. 이에 대한 대표적 문제가 ABA 문제 입니다.

ABA 문제는 3개의 스레드가 동작하는 상황에서 같은 Stack의 데이터를 POP 연산할 때 발생합니다.

첫번째 스레드가 A 를 POP 하기 위해 current 로, B 를 next 로 설정한 상태에서, 중간에 두번째 스레드가 끼어들어 A와 B를 POP 합니다. 이후 세번째 스레드가 A 를 PUSH 하면, 첫번째 스레드 입장에서는 정상적으로 POP 하려는 A가 존재하므로 문제가 없어 작업을 실행합니다. 하지만 next 로 설정되어 있지만 지금은 존재하지 않는 B 를 current 로 변경하고 있는 문제가 발생하게 됩니다. 이 상황은 궁극적으로 Stack 에 존재하는 요소들의 주소값이 동등한지 비교한 후, 동등한 경우 실행해버리기 때문에(CAS) 발생하게 됩니다.

또 이것을 해결하기 위해 주소값 뿐만아니라 POP 대상에 대해서도 저장하는 Double-CAS 를 이용하기도 합니다. 물론 이는 근본적 문제를 해결하기 보다는 특정 사례를 해결하는 방법이기도 합니다. 2개의 요소가 아닌 3개, 4개, N개의 요소가 영향을 준다고 생각해 봅시다. 또 이러한 사례가 발생할 수 있다는 것 이므로, 내가 개발하려는 상황에서 발생하지 않는다면 베스트로 선택될 수 있습니다.

결국 궁극적으로 항상 그러하듯, 모든 문제를 해결할 수 있는 베스트 알고리즘이나 디자인패턴과 아키텍처는 없습니다. 주어진 상황에 맞추어 해결할 수 있는 최적의 방법이 존재할 수 있다는 점을 항상 염두 해 두어야 합니다.

이러한 방법들을 토대로 Java 에서는 어떻게 동시성에 대한 문제를 해결할 수 있는 방법들을 제공하고 있는지, 또 Java 기반의 Kotlin 은 이를 어떻게 활용하고 있는지에 대해서 정리해보겠습니다.