[자료 구조/알고리즘] 논블로킹 자료 구조와 CAS

스레드 안전성과 동기화

프로그래밍에서 데이터 타입이나 메서드가 스레드 안전(thread safe)하다는 것은 멀티 스레드 프로그램에서 서로 다른 스레드가 동일한 데이터 타입이나 메서드에 접근하여 이를 사용하더라도 의도대로 올바르게 동작하는 것을 말한다.

동시성(concurrent) 연산이 수행되는 경우 이벤트(코드 실행)의 상대적 발생 순서 및 시점에 따라 연산 결과가 달라지고 연산의 정확성이 떨어지게 되는데 이러한 문제를 발생시키는 상태를 경쟁 조건(race condition)(또는 경합 조건)이라고 한다. 경쟁 조건의 원인이 되는 코드 영역을 임계 영역(critical section)이라고 한다. 멀티 스레드 환경에서 여러 스레드가 동일한 가변 변수를 공유하는 경우, 스레드가 수행하는 작업을 서로 조율하는 과정이 없다면 프로그램의 정확성은 저수준의 연산 수행 시점에 따라 달라질 수 있으며 이는 스레드 안전하지 않다.

동시적으로 수행되는 여러 스레드의 작업들을 서로 조율하기 위해서는 동기화(synchronization)라는 과정이 필요하다. 동기화는 서로 다른 스레드가 공유 리소스(shared resource)에 접근하는 순서를 지정하거나, 접근을 막는 등의 방법을 사용하여 여러 스레드가 공유 리소스에 동시에 접근하지 못하도록 방지함으로써 스레드 안전한 데이터 타입을 구현하는데 사용된다. 임계 영역은 공유 리소스를 변경하는 코드 영역이며, 동기화는 서로 다른 스레드가 동시에 임계 영역을 실행하는 것을 제어한다. 동기화는 소프트웨어적으로 구현하거나, 하드웨어적으로 구현할 수 있으며 하드웨어적인 방법은 소프트웨어적인 방법보다 성능이 좋고 효율적이다.

멀티 스레드 환경에서 스레드 안전한 코드를 구현하기 위해 다음과 같은 방법을 사용할 수 있다.

1. 가변 데이터가 스레드 간 공유되지 않도록 한다.
2. 스레드 간 공유하여 사용할 데이터는 불변성을 갖도록 만든다.
3. 공유 가변 데이터는 스레드 안전한 데이터 타입에 저장한다. API 또는 라이브러리가 제공하는 스레드 안전한 데이터 타입을 사용한다.
4. 동기화를 통해 한번에 하나의 스레드만 접근할 수 있는 데이터 타입을 정의한다.

스레드 안전한 데이터 타입은 그것을 사용하는 호출자가 별다른 전제조건 없이 사용할 수 있다. 반면 스레드 안전하지 않은 데이터 타입의 경우 여러 스레드가 공유하여 사용하게 되면 올바른 동작이 보장되지 않으므로 사용 시점에 경쟁 조건에 의해 연산 또는 메서드 호출이 방해 받지 않도록 제한이 필요하다.

로컬 변수는 항상 특정 스레드에 한정되어 있으므로 스레드 간 공유될 경우가 존재하지 않는다. 따라서 로컬 변수는 가변이거나 불변에 관계 없이 스레드 안전하다. 반면 정적 변수(클래스의 정적 필드)는 특정 스레드에 한정되지 않으며 공유될 수 있다. 따라서 가변 정적 변수는 스레드 안전하지 않으며 불변 정적 변수는 스레드 안전하다.

스레드 안전한 데이터 타입을 사용하는 것은 스레드 안전하지 않은 데이터 타입을 사용하는 것보다 더 많은 시스템 리소스를 필요로 한다. 스레드 안전성으로 인해 성능 저하가 유발되므로 연산의 정확성과 성능을 기준으로 적절한 사용 여부를 판단해야 한다.

싱글톤 패턴(singleton pattern)을 구현한 객체는 그 자체로 스레드 안전하지는 않다. 싱글톤 패턴에서 싱글톤 인스턴스는 하나만 생성되는 것이 목적이지만 스레드 경쟁 조건에 따라 여러 개의 인스턴스가 생성될 수도 있다. 이러한 문제를 해결하기 위해 스레드 안전하게 싱글턴 인스턴스를 생성하는 코드 구현이 반드시 필요하다.

락

멀티 스레드 환경에서 여러 스레드가 동시에 같은 자료 구조(공유 리소스)에 접근할 경우 데이터 경합 조건으로 인한 비일관성(inconsistency) 문제가 발생할 수 있다. 이러한 문제를 막기 위해서는 적절한 동기화가 필요하다.

락은 소프트웨어적인 동기화 기법 중 하나로, 자료 구조에 대한 접근을 제어한다. 락을 사용하여 한 번에 하나의 스레드만 해당 자료 구조에 접근하도록 제한함으로써 데이터의 일관성(consistency)을 유지할 수 있으며 이러한 방식으로 사용 가능한 자료 구조는 스레드 안전하다.

락을 사용하여 동기화를 수행하는 경우 스레드는 자료 구조에 대한 락을 획득(acquire)하고 해제(release)한다. 락을 획득한 스레드는 스레드 안전하게 자료 구조를 읽거나 변경할 수 있으며 다른 스레드는 락이 해제될 때까지 대기해야 한다. 락은 올바르게 사용하지 않으면 데드락(deadlock)(또는 교착상태), 리브락(livelock)과 같은 문제가 발생할 수 있으므로 주의해야 한다. 락을 제외한 다른 동기화 기법들도 문제를 발생시킬 수 있다.

하나의 스레드가 락을 획득하면 해제하기 전까지 다른 스레드는 락을 획득할 수 없다. 이때 락을 획득한 스레드가 중단되면 다른 스레드는 영원히 기다리게 된다. 락 획득을 기다리는 스레드를 블로킹(blocking)되었다고 한다. 락에 의한 스레드 블로킹으로 인해 데드락 문제가 발생 가능하다.

데드락이란 두 개(또는 그 이상)의 스레드가 영원히 블로킹되어 서로를 기다리는 상황을 말한다. 스레드 A와 스레드 B가 각각 자료 구조 A, 자료 구조 B에 대해 락을 획득하고 있는 상태에서 스레드 A가 자료 구조 B, 스레드 B가 자료 구조 A에 대한 락을 획득하려고 기다리는 경우, 두 스레드 중 하나가 락을 해제하기 전까지 두 스레드가 영원히 블로킹되는 데드락이 발생하게 된다. 데드락이 발생하면 두 스레드는 블로킹되어 진행 상태가 아닌 대기 상태에 있으며 작업을 수행하지 못한다.

리브락이란 두 개(또는 그 이상)의 스레드가 서로의 상태에 의존하는 경우 발생 가능하다. 스레드는 서로 반응하여 상태를 지속적으로 변경하지만 작업을 진행하지 못한다. 스레드 A와 스레드 B가 자료 구조를 공유하려고 할 때, 스레드 A는 스레드 B가 활성 상태인지 확인하고 활성 상태일 때 자료 구조를 스레드 B에게 넘긴다. 스레드 A는 스레드 B가 비활성 상태일 때 작업을 진행한다. 반대로 스레드 B는 스레드 A가 활성 상태인지 확인하고 활성 상태일 때 공유 자료 구조를 스레드 A에게 넘긴다. 스레드 B는 스레드 A가 비활성 상태일 때 작업을 진행한다. 그러나 두 스레드 모두 활성 상태이므로 서로에게 공유 자료 구조를 무기한으로 계속 넘겨주며 이로 인해 각 스레드는 작업을 진행하지 못한다. 리브락의 경우 데드락과 달리 스레드가 블로킹되지는 않으며 각각의 스레드는 진행 상태에 있지만 작업이 완료할 수 없는 상태가 반복된다.

동시 자료 구조

여러 스레드가 하나의 자료 구조에 동시적으로 접근하는 경우 해당 자료 구조를 동시 자료 구조(concurrent data structure)^링크라고 한다. 스레드가 블로킹되는지의 여부에 따라 동시 자료 구조는 다음과 같이 두 가지로 구분할 수 있다.

• 블로킹(blocking) 자료 구조
• 논블로킹(non-blocking) 자료 구조

하나의 스레드가 작업 도중 중단되더라도 다른 스레드의 작업에 영향을 주지 않는 경우 해당 알고리즘을 논블로킹 알고리즘(non-blocking algorithm)이라고 한다. 논블로킹 알고리즘은 블로킹 알고리즘의 여러 문제를 해결하지만 구현 복잡도와 리소스 오버헤드가 높으므로 주의해야 한다.

스레드가 자료 구조에 접근 가능하여 어떤 연산을 수행하는 것을 작업이라고 했을 때 스레드가 제약 없이 동시 자료 구조에 얼마나 접근 가능한지가 스레드의 작업 진행(progress) 정도를 결정한다. 스레드가 어떠한 이유에서든 동시 자료 구조에 접근할 수 없다면 해당 스레드는 작업을 진행할 수 없다. 한 스레드가 동시 자료 구조를 오랫동안 점유하게 되면(이러한 스레드를 탐욕적(greedy) 스레드라고 한다) 다른 스레드는 접근할 수 없으며 이러한 상황을 기아 상태(starvation)라고 한다. 데드락과 리브락은 기아 상태의 원인이 된다.

논블로킹 알고리즘은 스레드의 작업 진행 보장 정도에 따라 세 가지 수준으로 구분할 수 있다.

1. 방해-자유 (obstruction-free): 스레드 작업 진행 정도가 가장 약한 상태이다. 스레드의 작업 진행을 방해하는 다른 모든 스레드가 중단된 상태에서 스레드는 단독으로 실행되어 작업을 완료한다. 시스템 전체의 처리량이 보장되며 기아 상태가 발생하지 않는다. 모든 락-자유 알고리즘은 방해-자유 알고리즘이다.
2. 락-자유 (lock-free): 스레드 작업 진행 정도가 중간 정도인 상태이다. 스레드는 기아 상태가 될 수 있지만 시스템 전체의 처리량을 보장한다. 한 스레드가 중단된 경우 나머지 스레드가 작업을 계속 진행할 수 있도록 보장한다. 데드락이 발생할 수 있는 경우 락-자유 알고리즘이 아니다. 모든 대기-자유 알고리즘은 락-자유 알고리즘이다.
3. 대기-자유 (wait-free): 스레드 작업 진행 정도가 가장 강한 상태이다. 락이 없으며 모든 스레드가 작업을 진행하는 것이 보장된다.

CAS

앞서 말한 락은 스레드를 블로킹하는 동기화 기법이다. 락을 사용하지 않고 스레드 논블로킹 방식으로 동기화를 수행하려면 다른 방법이 필요하다. CAS(compare-and-swap)는 동시성 프로그래밍에서 락으로 인한 스레드 블로킹의 문제를 하드웨어적으로 해결하는 기법 중 하나로서, 락-자유 알고리즘을 구현한다. CAS를 사용한 연산은 원자적(atomic)이므로 멀티 스레드 환경에서 공유 리소스에 대한 동시 접근을 스레드 안전하게 처리할 수 있도록 하여 데이터의 일관성을 보장한다. CAS를 사용하는 동기화는 락을 사용하지 않으므로 데드락(deadlock)과 같은 문제를 일으키지 않는다.

CAS 연산 과정은 다음과 같다. 하나의 스레드가 공유 가변 변수를 변경하기 전의 값을 예상 값(expected value), 스레드가 가변 변수를 변경한 후의 값을 새로운 값(new value)이라고 할 때, CAS 연산은 메모리에 저장된 값(변수의 값)을 예상 값과 비교하고 값이 같으면 메모리의 값을 새로운 값으로 변경하며 이 경우 연산은 성공한 것으로 간주한다. 값이 다르면 메모리의 값을 변경하지 않으며 이 경우 연산은 실패한 것으로 간주한다. 이 과정은 원자적으로 수행된다.

• 공유 가변의 값이 예상 값과 동일한가? -> 기존의 값을 새로운 값으로 변경한 후 참을 반환 (연산 성공)
• 공유 가변의 값이 예상 값과 다른가? -> 기존의 값을 유지하고 거짓을 반환 (연산 실패)

두 스레드가 공유 가변 변수를 변경하는 상황에서 CAS 연산으로 동기화를 수행하는 예는 다음과 같다. 메서드에 공유 가변 변수를 변경하는 임계 영역이 존재하는 경우, 하나의 스레드가 공유 가변 변수를 변경하는 동안 다른 스레드도 공유 가변 변수를 동시에 변경할 수 있다. 하나의 스레드가 임계 영역을 실행하기 전에 공유 가변 변수를 변경하기 전의 값인 예상 값을 로컬 변수에 저장한다. 임계 영역을 실행할 때 예상 값을 현재 공유 가변 변수의 값과 비교한 후 동일하면(다른 스레드에 의한 변경이 없으면) 변경하려는 값인 새로운 값으로 공유 가변 변수의 값을 변경한다(연산 성공). 임계 영역을 실행할 때 예상 값이 현재 공유 가변 변수의 값과 다르다면(다른 스레드에 의한 변경이 있으면) 변경하지 않으며 로컬 변수를 현재 공유 가변 변수의 최신 값으로 변경한다(연산 실패). CAS 연산이 실패한 경우 스레드는 반복적으로 연산을 성공할 때까지 시도한다.

CAS를 사용하면 스레드를 블로킹하지 않고도 스레드 안전하게 공유 리소스의 값을 변경할 수 있다. CAS를 사용하는 예로는 자바 언어가 제공하는 java.util.concurrent.atomic 패키지의 Atomic으로 시작하는 클래스의 compareAndSet() 메서드, 스레드 안전한 처리를 위한 자료 구조인 CurrentHashMap이 있다.

참고

• https://web.mit.edu/6.005/www/fa16/classes/20-thread-safety/
• https://www.baeldung.com/lock-free-programming
• https://web.mit.edu/6.005/www/fa15/classes/23-locks/
• https://docs.oracle.com/javase/tutorial/essential/concurrency/index.html
• https://www.baeldung.com/cs/deadlock-livelock-starvation
• https://www.cs.cornell.edu/courses/cs4414/2023sp/Slides/17-Deadlocks.pdf
• Java 9 Concurrency Cookbook - Second Edition (Javier Fernández González)