임계영역과 동기화: 공유 자원 접근을 제어하는 방법

공유 자원 접근이 겹칠 때 생기는 문제

다중 프로세스 환경에서 같은 자원에 동시에 접근하면 데이터 불일치와 경쟁 조건이 발생할 수 있다. 임계영역(Critical Section)은 공유 자원을 다루는 코드 중 한 번에 하나의 프로세스만 실행하도록 보호해야 하는 부분이다.

임계영역 전에는 진입 허가를 얻고, 실행을 마치면 다음 대기자에게 기회를 넘겨야 한다. 공유 자원과 무관한 일반 코드는 이 보호 범위 밖에서 실행한다.

// Critical Section 기본 패턴
do {
    // Entry Section
    acquire_lock();

    // Critical Section
    // 공유 자원 접근 코드
    shared_resource++;

    // Exit Section
    release_lock();

    // Remainder Section
    // 일반 코드 실행

} while (TRUE);

공유 변수 count를 두 프로세스가 동시에 읽고 증가시킨 뒤 기록하면, 증가 연산은 두 번 수행됐어도 최종 값은 1이 될 수 있다.

⤢✕

안전한 임계영역이 갖춰야 할 조건

상호배제(Mutual Exclusion)는 어떤 프로세스가 임계영역을 실행하는 동안 다른 프로세스가 들어오지 못하게 한다. 이 조건이 깨지면 공유 자원의 일관성이 무너지고 경쟁 조건이 생긴다. Lock, Semaphore, Monitor는 이를 구현하는 대표적인 수단이다.

진행(Progress)은 임계영역이 비어 있을 때 진입하려는 프로세스가 불필요하게 기다리지 않도록 하는 조건이다. 나머지 영역을 실행 중인 프로세스는 진입 결정에 영향을 주지 않아야 하며, 위반하면 Livelock이나 불필요한 지연이 발생할 수 있다.

한정 대기(Bounded Waiting)는 임계영역 진입을 요청한 뒤 허가를 받을 때까지의 대기에 한계가 있음을 뜻한다. FIFO 큐나 우선순위 고려가 여기에 사용되며, 보장하지 못하면 특정 프로세스가 무한히 기다리는 기아 상태(Starvation)가 생길 수 있다.

이 조건들 외에도 모든 프로세스에 공평한 기회를 주는 Fairness, 동기화 오버헤드를 줄이는 Performance, 프로세스 수가 늘어도 유지되는 Scalability, 여러 플랫폼에서의 Portability를 함께 고려한다.

소프트웨어만으로 진입 순서를 조정하는 방식

Peterson's Algorithm은 2-프로세스 환경에서 진입 의사와 차례를 이용한다. 특수 하드웨어 명령어 없이 상호배제, 진행, 한정 대기를 만족하지만, n-프로세스로의 확장이 복잡하고 현대 CPU에서는 메모리 배리어가 필요하다.

// 2-프로세스용 Peterson's Algorithm
int turn;  // 누구 차례인지
bool flag[2] = {false, false};  // 진입 의사

// Process i (i = 0 or 1)
void process_i() {
    int j = 1 - i;  // 다른 프로세스

    while (true) {
        flag[i] = true;      // 진입 의사 표시
        turn = j;             // 상대방에게 양보

        // 상대방이 원하고 상대방 차례면 대기
        while (flag[j] && turn == j);

        // Critical Section
        critical_section();

        flag[i] = false;     // 진입 의사 철회

        // Remainder Section
        remainder_section();
    }
}

Dekker's Algorithm은 1960년대 Dijkstra가 발표한 최초의 Critical Section Problem 소프트웨어 해법이다. Peterson보다 로직이 복잡하지만 같은 조건을 만족하며, 현대에는 Peterson 방식이 더 선호된다.

Bakery Algorithm은 Lamport가 제안한 n-프로세스용 알고리즘이다. 은행 번호표처럼 순서를 관리해 FIFO와 한정 대기 조건을 명확히 만족하지만, 프로세스 수에 비례하는 비교 연산이 필요하다.

원자 연산으로 만드는 동기화 기반

하드웨어 원자 명령어는 읽기와 변경을 분리되지 않게 처리한다.

명령어	동작	특징
Test-and-Set	값 읽고 1로 설정	가장 간단, 널리 지원됨
Compare-and-Swap	예상값 일치 시 변경	Lock-free 구현 가능
Fetch-and-Add	원자적으로 증가 후 이전값 반환	카운터 구현 최적
Exchange	두 변수 값 원자적 교환	스핀락 구현에 유용

Test-and-Set은 Lock 상태를 원자적으로 확인하고 설정해 상호배제를 구현한다. 다만 Busy Waiting으로 CPU를 낭비할 수 있고, 기본 구현은 한정 대기를 보장하지 않아 Starvation이 가능하다. 낮은 우선순위 프로세스가 Lock을 보유할 때는 우선순위 역전도 문제가 된다.

// 하드웨어가 제공하는 원자적 명령어
bool test_and_set(bool *target) {
    bool old_value = *target;
    *target = true;
    return old_value;
}

// 이를 이용한 상호배제
bool lock = false;

void process() {
    while (true) {
        // Entry Section
        while (test_and_set(&lock));  // Busy waiting

        // Critical Section
        critical_section();

        // Exit Section
        lock = false;

        // Remainder Section
        remainder_section();
    }
}

Compare-and-Swap(CAS)은 현재 값이 예상값과 같을 때만 새 값으로 바꾼다. 블로킹 없는 자료구조를 만들 수 있고 다양한 동기화 패턴에 적용할 수 있지만, ABA 문제는 Load-Link/Store-Conditional로 해결할 수 있다.

bool compare_and_swap(int *value, int expected, int new_value) {
    if (*value == expected) {
        *value = new_value;
        return true;
    }
    return false;
}

// Lock-free 카운터 예시
void atomic_increment(int *counter) {
    int old_value, new_value;
    do {
        old_value = *counter;
        new_value = old_value + 1;
    } while (!compare_and_swap(counter, old_value, new_value));
}

언어와 운영체제가 제공하는 동기화 도구

Semaphore는 정수 값을 이용해 여러 자원을 관리한다. P(wait)와 V(signal) 연산은 원자적으로 값을 감소·증가시키며, Binary Semaphore는 0 또는 1을 사용해 Mutex와 유사하게 동작한다. Counting Semaphore는 제한된 자원 풀을 다룰 때 사용한다.

Mutex는 Lock을 획득한 쓰레드만 해제할 수 있다는 소유권 개념을 갖는다. 동일 쓰레드가 여러 번 획득할 수 있는 Recursive Mutex, 우선순위 역전을 다루는 우선순위 상속, Futex(Fast Userspace Mutex) 같은 최적화 버전도 있다.

Monitor는 Java synchronized, C# lock처럼 언어 수준에서 제공되는 동기화 구조다. 메서드 진입 시 자동으로 Lock을 적용하고, 조건 변수(Condition Variable)로 특정 조건을 기다리거나 통지한다. 동기화 코드를 구조화해 프로그래밍 오류를 줄이는 데 적합하다.

커널부터 웹 서버까지의 선택 기준

운영체제 커널은 임계영역의 길이와 실행 맥락에 따라 도구를 나눈다.

⤢✕

Linux Kernel에서는 짧은 임계영역과 인터럽트 컨텍스트에 Spinlock을, 긴 임계영역과 프로세스 컨텍스트에 Mutex를 사용한다. 읽기가 대부분인 경우에는 RCU(Read-Copy-Update), 읽기를 우선하고 쓰기 시 시퀀스 번호를 증가시키는 경우에는 Seqlock이 쓰인다.

데이터베이스에서는 Row-level Locking으로 행 단위 상호배제를 적용하거나 Table-level Locking으로 테이블 전체를 잠근다. Optimistic Concurrency는 버전 번호로 충돌을 감지하고, MVCC는 읽기는 Lock 없이 처리하면서 쓰기만 직렬화한다.

웹 서버에서는 Semaphore로 Connection Pool의 최대 연결 수를 제한하고, Mutex로 세션 객체를 보호할 수 있다. 로그 파일에는 파일 잠금 또는 버퍼링을 적용하며, 캐시 갱신처럼 읽기가 많은 구간에는 Read-Write Lock으로 읽기 동시성을 높인다.

경합 비용을 줄이는 설계

대기 중 CPU를 양보하는 Blocking Synchronization은 Busy Waiting을 피하는 방식이다. 짧은 시간은 Spin하고 길어지면 Sleep하는 Hybrid Approach, JVM의 Biased Locking을 활용하는 Adaptive Spinning, NUMA-aware 스핀락인 MCS Lock도 선택지다.

Fine-grained Locking은 임계영역 자체를 작게 유지하고, 큰 자료구조를 여러 Lock으로 나누는 접근이다. Hash table의 버킷별 Lock처럼 Lock Striping을 적용할 수 있으며, ConcurrentHashMap의 Segment Lock이 예시다.

CAS 기반 Lock-free Queue, Stack, List는 높은 동시성을 제공하고 Deadlock이 없다는 장점이 있다. 대신 구현이 복잡하며 ABA 문제를 고려해야 한다.

Read-Write Lock은 여러 읽기 작업의 동시 접근을 허용하지만, 쓰기 작업이 시작되면 모든 접근을 막는다. 읽기가 많은 워크로드에 맞으며 Upgradable Read Lock과 Sequence Lock 같은 변형도 있다.