경쟁상태와 동기화 매커니즘의 활용

멀티 스레드, 멀티 프로세스, 스케일 아웃한 서버들 등 동시성의 활용은 성능을 향상시키고 자원을 효율적으로 사용하는 데 필수적이다. 그러나 동시성은 몇 문제를 동반하는데 시스템의 예측 가능성, 안정성을 저해하기에 이를 해결하기 위한 방법들을 잘 알고 활용하는 것이 중요하다.

 

이번 포스트에서 경쟁상태부터 동기화 매커니즘을 살펴보며 실제 어플리케이션에서는 어떻게 활용되는지 정리해 보았다. 문제의 시작인 경쟁상태부터 살펴보자.

 

 

 

경쟁상태

경쟁상태(Race Condition)는 스레드나 프로세스가 공유 자원에 동시에 접근하며 발생하는 문제이다. 공유 자원을 사용하며 다수가 동시에 접근할 수 있는 영역을 임계 영역(Critical Section)이라고 부르며, 이 임계 영역에 접근하는 순서에 따라 결과가 달라질 수 있다.

 

예를 들어, 아래와 같이 decreaseCount 메서드가 있다. 해당 메서드는 count라는 공유자원을 사용하며 다수의 쓰레드가 동시에 접근가능한 영역이다. 100개의 스레드가 이 영역에 동시에 접근했을때 예상되는 count를 수정한다면 모두 수행 후 count의 값은 무엇일까?

 

var count = 100;

// 임계 영역
fun decreaseCount() {
    sleep(20)
    var now = count
    now = now - 1
    count = now
}

fun main() {
    val threads = mutableListOf<Thread>()

    // 100개의 스레드 생성
    repeat(100) {
        val t = thread(start = false) { decreaseCount() }
        threads.add(t)
    }

    // 모든 스레드 시작 & 종료될 때까지 대기
    threads.forEach { it.start() }
    threads.forEach { it.join() }

    // 모든 스레드 실행 후 count 결과
    println(count)
}

 

위 상황에서 각 스레드들은 decreaseCount 라는 임계영역에 접근한다. 해당 임계영역에서는

1. count를 읽고
2. 수정한 뒤
3. 수정한 값을 다시 count에 저장한다.

 

이 과정은 Read-Modify-Write 주기라고도 부르며, 경쟁상태가 발생하는 가장 흔한 케이스이다. 경쟁상태가 발생하는 상황은 다음과 같다.

1. A 스레드가 1,2번을 수행한 뒤 3번 실행하여 count 값을 99로 바꾸기 전
2. B 스레드가 1번을 수행하면 바뀌기 전의 count 값(100)을 읽음
3. A 스레드가 3번을 실행하여 count를 99로 바꿈
4. B 스레드도 2,3번을 실행함. 마찬가지로 count가 99로 바뀜

 

decreaseCount 두 번 실행 되었기에 98의 결과값을 예상했지만 동시접근으로 인해 count의 결과값이 99가 되었다. 마찬가지로 100개의 스레드가 동시에 과정을 수행하면, 모두 실행 후 count 값은 우리가 예상하지 못한 숫자 일 것이다.

 

만약 실제 프로덕트에서 선착순으로 쿠폰 100개를 발급한다고 생각해보자. 위와 같은 상황이 벌어진다면 비즈니스에 매우 치명적일 것이다. 따라서, 이러한 경쟁상태를 해결하기 위한 동기화 매커니즘을 알고 활용할 수 있어야 한다.

 

 

 

OS에서의 동기화 매커니즘

멀티 스레드로 동작하는 어플리케이션 내 공유자원을 사용하는 코드영역에 여러 스레드가 동시에 접근하는 경우, 다수의 서버가 데이터베이스의 같은 레코드에 쿼리하는 경우 등 어플리케이션 개발에서도 경쟁상태는 흔히 발생할 수 있다. 이러한 상황을 현명하게 헤쳐나가기 위해서는 동기화 매커니즘을 제대로 이해할 필요가 있다.

 

 

 

경쟁상태 해결조건

운영체제(OS) 학습 시 경쟁상태를 해결하기 위한 조건(혹은 동기화 조건)으로 아래 3가지를 모두 만족해야한다고 이야기한다.

1. 상호배제(Mutual Exclusion) : 하나의 자원에 하나의 프로세스만 접근 가능해야한다.
2. 진행(Progress) : 임계구역에 진입한 프로세스가 없다면 어떤 프로세스든 진입할 수 있어야 한다.
3. 유한대기(Bounded Waiting) : 임계구역에 진입하기 위해 기다리는 프로세스들은 결국 진입할 수 있어야 한다.

 

위 조건들은 '화장실(임계구역)을 사용할려면 한 명(프로세스)씩 이용하세요'와 같은 의미처럼 보여 간단해 보이지만 다수의 임계영역에 대한 접근을 처리하는 복잡한 상황에서 위 조건을 모두 충족시키기 어렵다.

 

 

 

대표적인 동기화 방법

동기화 매커니즘을 구현하는 방식은 잠금을 사용하지 않는 Lock-Free(or 원자적 연산), 잠금을 사용하는 Lock 방식으로 나눌 수 있다. 두 방식별 대표적으로 다음과 같은 것들이 있다.

 

원자적 연산(Lock Free)

• 소프트웨어적으로 상호배제 구현 : Dekker's 알고리즘, Peterson's 알고리즘
• 하드웨어 지원을 통한 상호배제 : Compare And Set(CAS), Test And Set(TAS)

 

Lock을 이용한 동기화

• Busy Waiting 방식 : Spin Lock
• Block & WakeUp 방식 : Metex, Semaphore

 

 

 

원자적 연산을 통한 동기화

원자적 연산이란 연속된 연산들이 중간에 중단되지 않고 단일 연산으로 수행되는 것을 보장하는 방법이다. 멀티 스레드나 멀티 프로세스 환경에서 임계영역 내 연산 중간에 컨텍스트 스위칭으로 인해 다른 스레드가 CPU를 점유하고 임계영역에 접근하여 경쟁상태가 발생한다. 하지만 원자적 연산은 임계영역의 연산들을 하나의 연산처럼 수행시켜 경쟁상태를 해결하는 것이다. 

 

원자적 연산의 구현은 소프트웨어적으로 해결하는 방법과 하드웨어의 도움을 받는 방법이 있다. 소프트웨어적인 방식은 여러 한계점이 있어 잘 쓰이지는 않고 현대의 원자적 연산은 대부분 하드웨어의 도움을 받아 처리한다. 먼저 두 방식을 모두 알아보자.

 

Peterson's 알고리즘

임계영역에 하나의 프로세스만 진입할 수 있도록, 즉 상호배제를 충족시킬 수 있도록 소프트웨어적으로 해결하는 방법에는 Dekker's와 Peterson's 알고리즘이 있다. 두 알고리즘 모두 매커니즘이 비슷하므로 Peterson's 알고리즘을 소개한다.(Peterson은 Dekker를 보완한 알고리즘)

 

val flags = BooleanArray(2) { false }
var turn: Int = 0

fun peterson() {
    while (true) {
        flags[0] = true // 1. 0번 프로세스가 임계영역에 접근함.
        turn = 1; // 2. 접근전에 1번 프로세스에게 턴을 넘김
        // 3. 1번 프로세스가 사용중 && 1번 턴인지 확인
        while (flags[1] && turn == 1) continue 
        
        /* Critical Section */
        
        // 4. 실행 후 임계영역 접근 = false
        flags[0] = false
    }
}

 

1. 임계영역에 접근하기 전, 접근 프로세스가 임계영역에 접근한다는 의미의 flag를 true로 설정
2. 0번 턴이지만 turn 값을 상대 프로세스에게 넘겨줌
3. 1번 프로세스도 접근중이면서 상대 turn 일 경우에는 대기
   1. flags[1] == false 가 되면 상대가 임계영역에 사용이 끝났음을 의미
   2. turn == 0 이 되면 상대가 임계영역 접근 준비중이라는 의미
4. 임계영역에 사용이 끝나면 본인의 flag를 false로 바꿔 상대가 접근할 수 있도록 함

 

Peterson's 알고리즘은 flag와 turn 조건 변수를 이용해 상해배제를 구현한 것이다. 상대 프로세스가 임계영역 사용이 끝나면 대기 후 진입할 수 있어, 진행, 유한대기의 조건도 충족한다.

 

하지만 코드에서 보는 것과 같이 프로세스 2개의 동시접근에서만 동작할 수 있으며, 대기하는 과정에서도 while이 동작하며 CPU의 자원을 계속해서 사용한다.

 

Compare-And-Set

Compare-And-Set(CAS) 연산은 하드웨어적으로 원자성을 보장받는 방식이다. 이전에 읽은 값과 현재 값을 비교 후 같을 경우 새로운 값으로 수정하는 연산이다. 같은지 확인 & 수정, 두 작업을 하나의 연산으로 수행하는 것이다. 현대의 CPU 명령어, 하드웨어는 CAS 연산을 직접 지원하기 때문에 널리 쓰인다.

 

하드웨어의 지원으로 Peterson's 알고리즘처럼 복잡한 코드를 직접 작성하지 않아도 된다. 하지만 '비교 후 수정' 이라는 간단한 연산만지원한다. 현실적으로 단순히 비교 후 수정만하는 임계영역은 거의 없을 것이다. 따라서 복잡한 연산을 수행하기 위해서 잠금을 활용해 동기화를 하는 경우가 많다.

 

 

 

Lock을 이용한 동기화

경쟁상태를 해결하는 또 다른 방식은 잠금(Lock)을 이용한 방식이다. 임계영역에 접근 전 Lock 획득을 시도하고 Lock을 획득한 스레드만 임계영역에 접근함으로써 상호배제를 구현한다. 임계영역 실행 후에는 Lock을 반납하여 다른 스레드들이 Lock을 획득할 수 있다.

 

접근 전 후로 Lock을 획득/반납 할 수만 있다면 임계영역에서 복잡한 로직도 처리가능하다는 장점이 있다. 하지만 Lock을 획득하기 위한 추가적인 오버헤드와 다수의 Lock을 동시에 사용할 경우 데드락의 위험이 존재한다. Lock에 대해 설명하면서 천천히 알아가보자.

 

Lock을 활용한 동기화의 경우 다음과 같은 순서로 실행된다. 여기서 1번 Lock 획득시도와 3번 Lock 반납의 방식에 따라 다른 이름으로 불린다.

1. Lock 획득 시도
2. Lock 획득 및 임계영역 실행
3. Lock 반납

 

Spin Lock

Spin Lock은 Lock을 획득하지 못한 스레드들이 계속해서 Lock 획득을 시도하는 방식이다. 이때 Lock을 획득하기 위해 CAS 연산을 사용한다.

 

class SpinLock {
    fun lock() {
        while (true)
            if (compareAndSet(oldValue = false, newValue = true))
                return
    }

    fun unlock() = compareAndSet(oldValue = true, newValue = false)
}

fun criticalSection() {
    spinLock.lock()
    /* Critical Section */
    spinLock.unlock()
}

 

lock 메서드를 보면 while문으로 Lock획득을 지속적으로 시도한다. CAS연산을 이용해 Lock이 사용중이지 않다면(oldValue = false) Lock을 사용중(newValue = true)로 바꾼다. CAS 연산이 원하는대로 실행된다면 true를 받아 return, 아니라면(Lock이 이미 true일 경우) false를 받아 while을 지속 실행하면서 Lock을 획득할 때가지 시도한다.

 

Spin Lock의 지속적인 획득시도는 CPU 자원을 계속 사용한다.(이런 상황을 일컬어 busy waiting 이라고 부른다) 만약 동시접근하는 스레드가 많다면 큰 낭비일 것이다. 따라서, Spin Lock 사용은 CPU 코어가 많거나 동시 접근하는 스레드가 적을 경우 적합하다.

 

Mutex

Spin Lock이 busy waiting으로 Lock을 획득한다면, Mutex는 Block & Wakeup 방식으로 Lock을 획득한다. Lock 획득을 시도하고 획득하지 못할 경우 스레드는 Block 상태로 전환된다. 이후 Lock이 반납되었을때 Block 상태에서 깨어나 작업을 수행한다.

 

class Mutex {
    fun lock() {
        // 스레드 블로킹
        while (!tryLock()) LockSupport.park()
    }

    fun tryLock(): Boolean = compareAndSet(oldValue = false, newValue = true)

    fun unlock() {
        compareAndSet(oldValue = true, newValue = false)
        // 스레드 깨우기 - 전부 or 특정 하나
        LockSupport.unpark(Thread)
    }
}

 

위 lock() 메서드 시도 시 실패한다면 스레드를 Block한다. 이후 다른 쓰레드에서 Lock을 반납할때 Block 중인 쓰레드를 깨운다. 이때 공정성(fairness) 정책에 따라 먼저 Lock을 요청한 쓰레드를 깨울지(큐로 관리), 모든 쓰레드를 깨울지 달라진다.

 

Mutex는 CPU 자원을 절약할 수 있다는 장점이 크다. 하지만 쓰레드를 블로킹하고 깨우는 과정에서 발생하는 추가적인 Context Switching 비용과 Lock 반납이 제대로 이뤄지지 못한 경우 데드락이 발생할 수도 있다.

 

Semaphore

Semaphore는 Mutex의 Lock 미반납으로 일어날 수 있는 데드락을 방지하기 위한 하나의 솔루션이다. Mutex의 경우 임계영역에 접근할 수 있는 스레드는 Lock을 소유한 1개이지만 Semaphore는 임계영역에 N개의 프로세스의 접근을 허용한다. 이를 위해 Lock 정보가 아닌 임계영역에 접근한 스레드 수를 유지한다.

 

N개의 스레드가 접근할 수 있으므로 공유자원 수정 작업에는 원자성을 보장하는게 중요하다. Semaphore는 접근 가능한 수를 1개로 두었을때 Binary Semaphore(이진 세마포어)라고 부르며, 2개 이상일 경우 Counting Semaphore라고 부른다. 이진 세마포어의 경우 Mutex와 거의 동작이 거의 비슷하다.(Semaphore도 Block & Wakeup 방식이다.)

 

Semaphore는 임계영역에 in/out 시 유지중인 '접근한 스레드 수'를 올리고 내린다. 따라서, 이 수에 대한 연산에 원자성을 보장해야한다.

 

 

 

어플리케이션에서의 동기화

동기화 매커니즘들이 어플리케이션에서 어떤 모양으로 쓰이는지 필자가 알고 있는 한해서 정리해보았다.

 

 

Java 에서의 동기화 활용

Java 언어 수준에서 여러 동기화 매커니즘을 지원한다. 대부분 구현체를 제공해주기 때문에 어플리케이션 프로그래머들은 이를 활용한다. 각 구현체들이 어떤 매커니즘을 활용하는지 알아보자.

 

Java의 Atomic 클래스

Java의 Atomic 클래스들은 원자적 연산인 CAS 연산을 활용해 구현되어 있다. 멀티 스레드로 동작하는 Java 생태계에서 여러 객체가 하나의 변수에 접근하여 읽기-수정-쓰기 연산 시 경쟁상태가 발생할 수 있다. Java에서는 멀티 스레드에서 단일 값 연산에 대한 원자성을 보장하기 위해 AtomicInteger와 같은 클래스를 지원한다. 다음은 AtomicInteger가 CAS를 활용해 값을 더하는 코드이다.

 

public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);
    } while (!weakCompareAndSetInt(o, offset, v, v + delta));
    return v;
}

 

 

getIntVolatile을 이용해 메모리에서 현재값을 읽은 뒤 CAS로 현재값에 delta를 더한 값을 저장한다. 만약 그 사이 현재값이 변경되었다면 다시 값을 읽어 재시도한다.

 

Java의 synchronized 블록

synchronized 블록은 Monitor라는 동기화 매커니즘을 활용한다. Monitor는 위 동기화 매커니즘에서 설명한 개념은 아니지만 객체를 활용한 Lock 방식이다. Java의 각 객체는 내장된 락(intinsic Lock)을 가지고 있다. synchronized 사용하면 해당 객체의 lock을 획득하게 되고 다른 스레드에서 해당 객체의 synchronized 블록에 접근하지 못하게 한다. synchronized 블록은 JVM이 lock, unlock 을 처리해준다.

 

class Crticial {
    public static synchronized void globalCriticalSection() {
        /* Critical Section */
    }

    public synchronized void criticalSection() {
        /* Critical Section */
    }
}

 

Java의 ReentrantLock

Java의 ReentrantLock은 Mutex를 구현한 구현체이다. 위에서 설명한 것과 비슷한 매커니즘으로 동작하며, 추가적으로 Lock 획득을 시도한 순서대로 Lock 획득할 수 있는 공정성을 설정할수 있다. 기본값은 false(Non-Fair)이다.

 

Java의 Semaphore

Java의 Semaphore는 위에서 설명한 Semaphore와 같다. 마찬가지로 공정성을 설정할 수 있다.

 

 

 

DB 에서의 동기화 활용

여러 서버, 여러 트랜잭션을 통해 데이터베이스를 이용할때도 동시성 문제가 발생할 수 있다. 어플리케이션 프로그래머들은 이에 대한 책임을 가지고 경쟁상태를 해결해야한다. 어떤 방식으로 해결할 수 있는지 어떤 매커니즘을 활용하는지 알아보자.

 

Optimisitic Lock, Pessimistic Lock

노드 내 자원뿐만 아니라 리모트 자원에 동시접근해 경쟁상태가 발생할 수도 있다. 다수의 서버 어플리케이션이 동일한 원격 데이터베이스에 접근하는 것이 그런 경우이다. 이런 경우에도 어플리케이션은 Lock을 활용할 수 있다.

 

Pessimistic Lock(비관적 락)은 데이터베이스의 Lock을 활용하는 방식이다. 요청하는 어플리케이션 측이 아닌 RDMBS에서 Lock을 처리한다.

 

Optimisitic Lock(낙관적 락)은 어플리케이션에서 동기화를 수행하는 방식이다. 정확하게는 Lock를 사용하는 것이 아닌 버저닝(Versioning)을 사용하는데 데이터를 새로 수정할때마다 해당 데이터의 버전을 올리는 방식이다. 데이터 쓰기 전 데이터를 읽을때 버전과 데이트 쓰기 시에 버전이 맞지 않으면 쓰기는 실패한다. 버전이 맞지 않는다는 것은 그 사이에 다른 커넥션에서 이미 쓰기를 수행했다는 의미이다. 실패 시에는 어플리케이션에서 재시도를 처리한다.

 

Redis로 Lock 요청하기

Redis로 Lock을 사용하는 경우 특정 이름으로 Lock 획득을 시도할 수 있다.(Redis 뿐만 아니라 MySQL의 네임드락도 있다) 이때 위에서 이야기한 Spin Lock으로 Lock을 획득할때까지 요청을 지속적으로 보낸다. 요청에 비해 획득률이 낮다면 무의미한 부하가 클 수 있으므로 조심해야한다.

 

Redis에서는 Pub/Sub 이벤트 구조로 획득 요청을 보내고 Lock이 반납된 경우에 Redis 측에서 어플리케이션으로 알림을 보내도록 수 있다. 이 방식은 요청 측에서 지속적인 재요청을 하지 않고 기다린다는 점에서 Mutex의 Block & Wakeup 매커니즘과 개념적으로 유사하다고 볼 수 있다.

 

Redis의 Lua Script

Redis는 어플리케이션 수준에서 원자적 연산을 지원한다. Lua Script를 활용해 요청하는 연산을 원자적으로 실행시켜준다. 덕분에 여러 조건연산과 함께 쓰기 연산을 원자적으로 실행할 수 있다. 물론 무차별적으로 사용시 성능 저하가 생길 수도 있다.