공유 자원을 안전하게 다루는 동기화 문제와 해법

여러 프로세스나 스레드가 같은 자원에 접근하면, 실행 순서만 달라져도 데이터의 결과가 달라질 수 있다. 세마포어, 뮤텍스, 모니터는 이 충돌을 제어하기 위한 운영체제의 기본 도구다. 생산자-소비자, Readers-Writers, Dining Philosophers 문제는 이 도구들이 어떤 조건을 보장해야 하는지 보여 주는 대표적인 모델이다.

경쟁 조건은 임계 구역에서 시작된다

경쟁 조건(Race Condition)은 여러 프로세스가 공유 데이터를 동시에 다루면서 실행 순서에 따라 결과가 달라지는 상태다. 계좌 잔액을 동시에 갱신하거나, 카운터 변수를 증가시키거나, 하나의 파일에 동시에 쓰는 상황에서 나타날 수 있다.

원인은 비원자적(Non-atomic) 연산, 문맥 교환 시점의 불확실성, 공유 메모리 접근 순서의 미보장에 있다.

임계 구역(Critical Section)은 공유 자원에 접근하는 코드 영역이다. 이 영역은 다음 조건을 충족해야 한다.

• 상호 배제(Mutual Exclusion): 한 번에 하나의 프로세스만 진입
• 진행(Progress): 임계 구역이 비어있으면 진입 가능
• 한정 대기(Bounded Waiting): 무한 대기 방지

⤢✕

세마포어·뮤텍스·모니터가 맡는 역할

세마포어(Semaphore)는 정수형 변수를 이용하는 동기화 도구다. Binary Semaphore는 0 또는 1의 값을 가지며 뮤텍스와 유사하고, Counting Semaphore는 0 이상의 정수로 자원의 개수를 표현한다.

P(S), wait(S), down(S)는 S를 1 감소시키고 S<0이면 대기한다. V(S), signal(S), up(S)는 S를 1 증가시키고 대기 중인 프로세스를 깨운다. 세마포어는 원자적 연산을 보장하며 커널 수준에서 구현되고, Busy waiting 또는 Block/Wakeup 방식으로 동작한다.

뮤텍스(Mutex)는 상호 배제를 위한 이진 락(Binary Lock)이다. 소유권이 있어 락을 획득한 스레드만 해제할 수 있으며, 우선순위 역전 문제가 생길 수 있다.

모니터(Monitor)는 동기화를 추상화한 구조다. 프로그래밍 언어 수준에서 지원되고 조건 변수(Condition Variable)를 제공한다. Java의 synchronized와 C#의 lock이 이에 해당한다.

버퍼의 빈자리와 데이터를 함께 관리하는 생산자-소비자

생산자-소비자 문제(Producer-Consumer Problem)는 생산자가 만든 데이터를 버퍼에 넣고 소비자가 이를 꺼내는 구조를 다룬다. 고정 크기 버퍼를 공유하므로, 버퍼가 가득 찼을 때 생산자가 기다리고 비었을 때 소비자가 기다려야 한다. 버퍼 자체에 접근할 때는 상호 배제도 보장해야 한다.

세마포어를 이용하면 mutex = 1로 버퍼 접근을 보호하고, empty = N으로 빈 슬롯 개수를, full = 0으로 채워진 슬롯 개수를 관리할 수 있다. 여기서 N은 버퍼 크기다.

생산자 측 코드는 다음과 같다.

while (true) {
    item = produce_item();

    wait(empty);        // 빈 슬롯 대기
    wait(mutex);        // 버퍼 락 획득

    insert_item(item);  // 버퍼에 추가

    signal(mutex);      // 버퍼 락 해제
    signal(full);       // 채워진 슬롯 증가
}

소비자는 채워진 슬롯이 있는지 확인한 뒤 버퍼에서 항목을 제거한다.

while (true) {
    wait(full);         // 채워진 슬롯 대기
    wait(mutex);        // 버퍼 락 획득

    item = remove_item(); // 버퍼에서 제거

    signal(mutex);      // 버퍼 락 해제
    signal(empty);      // 빈 슬롯 증가

    consume_item(item);
}

⤢✕

wait(mutex)보다 wait(empty/full)를 먼저 수행해야 한다. 이 순서가 바뀌면 교착 상태가 발생할 수 있다.

메시지 큐에서는 RabbitMQ, Kafka 등을 이용한 이벤트 기반 아키텍처가 이 구조와 맞닿아 있다. 키보드 입력 버퍼나 네트워크 패킷 버퍼 같은 I/O 버퍼링도 같은 관점에서 볼 수 있다.

읽기 병렬성과 쓰기 독점을 조율하는 Readers-Writers

Readers-Writers 문제는 여러 Reader와 Writer가 하나의 공유 데이터베이스에 접근할 때의 규칙을 다룬다. 읽기는 여러 Reader가 동시에 수행할 수 있지만, 쓰기는 Writer의 독점적 접근이 필요하다. Reader와 Writer의 동시 접근도 허용되지 않는다.

Reader가 읽는 동안 Writer는 기다려야 하고, Writer가 쓰는 동안에는 모든 접근을 막아야 한다. 반면 여러 Reader의 동시 읽기는 가능하다.

Reader 우선 정책의 기아 위험

First Readers-Writers 문제는 Reader Preference 정책이다. rw_mutex = 1은 데이터 접근을 제어하고, mutex = 1은 read_count를 보호한다. read_count = 0은 현재 읽기 중인 Reader 수를 나타낸다.

wait(mutex);
read_count++;
if (read_count == 1) {
    wait(rw_mutex);  // 첫 번째 Reader가 락 획득
}
signal(mutex);

/* 읽기 수행 */

wait(mutex);
read_count--;
if (read_count == 0) {
    signal(rw_mutex); // 마지막 Reader가 락 해제
}
signal(mutex);

Writer는 rw_mutex를 획득한 뒤 쓰기를 수행한다.

wait(rw_mutex);

/* 쓰기 수행 */

signal(rw_mutex);

이 정책에서는 Reader가 계속 유입되면 Writer가 무한히 기다리는 Writer 기아(Starvation)가 발생할 수 있다.

Writer 우선과 공정성

Second Readers-Writers 문제는 Writer Preference 정책이다. w_mutex = 1로 write_count를 보호하고, write_count = 0으로 대기 중인 Writer 수를 관리한다. read_try = 1은 Reader 진입을 제어한다.

Writer가 대기 중이면 새 Reader의 진입을 막아 Writer에게 우선권을 준다. 대신 Reader 기아가 발생할 수 있다.

Fair Readers-Writers 문제는 FIFO 순서를 보장해 기아를 막는 방식이다. 타임스탬프 기반 큐, 순서 세마포어, 모니터 기반 구현을 사용할 수 있다.

⤢✕

데이터베이스는 읽기에 공유 락(Shared Lock), 쓰기에 배타 락(Exclusive Lock)을 사용하며 MVCC(Multi-Version Concurrency Control)도 활용한다. 파일 시스템은 여러 프로세스의 파일 읽기를 허용하면서 쓰기는 독점 모드로 처리한다. 캐시 시스템에서는 Write-through, Write-back 정책과 Cache coherence protocol이 관련된다.

순환 대기를 끊어야 하는 Dining Philosophers

Dining Philosophers 문제는 다섯 명의 철학자가 원탁에 앉아 식사하는 상황을 모델로 삼는다. 철학자 사이에는 젓가락 1개씩, 총 5개가 놓여 있고, 식사하려면 양쪽 젓가락 2개가 필요하다. 철학자는 생각하거나 식사한다.

이 구조에서는 교착 상태와 기아 상태가 발생할 수 있어 동시성 제어가 필요하다.

⤢✕

양쪽 젓가락을 항상 같은 순서로 집는 단순 세마포어 구현은 교착 상태를 피하지 못한다.

wait(chopstick[i]);       // 왼쪽 젓가락
wait(chopstick[(i+1)%5]); // 오른쪽 젓가락

/* 식사 */

signal(chopstick[i]);
signal(chopstick[(i+1)%5]);

모든 철학자가 동시에 왼쪽 젓가락을 집으면 누구도 오른쪽 젓가락을 얻지 못한다.

최대 4명만 동시에 테이블에 앉게 제한하는 방법은 room = 4 세마포어를 둔다. 테이블에 들어가기 전 wait(room)을 수행하고, 나갈 때 signal(room)을 수행한다. 구현이 간단하고 교착 상태를 막을 수 있다.

비대칭 접근은 홀수 번호 철학자가 왼쪽부터, 짝수 번호 철학자가 오른쪽부터 집게 하여 순환 대기 조건을 파괴한다.

if (i % 2 == 0) {
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
} else {
    wait(chopstick[(i+1)%5]);
    wait(chopstick[i]);
}

양쪽 젓가락을 동시에 얻을 수 있을 때만 식사하도록 만드는 원자적 획득 방식도 있다.

while (true) {
    wait(mutex);
    if (chopstick[i] == FREE && chopstick[(i+1)%5] == FREE) {
        chopstick[i] = BUSY;
        chopstick[(i+1)%5] = BUSY;
        signal(mutex);
        break;
    }
    signal(mutex);
    sleep(random_time); // 백오프
}

이 방식은 Busy waiting이 발생하고 성능이 저하될 수 있다.

모니터는 철학자의 상태와 조건 변수를 기반으로 자원을 제어한다. 상태는 THINKING, HUNGRY, EATING으로 나뉜다.

monitor DiningPhilosophers {
    state[5];
    condition[5] self;

    pickup(i) {
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            self[i].wait();
    }

    putdown(i) {
        state[i] = THINKING;
        test((i+4)%5);  // 왼쪽 철학자 확인
        test((i+1)%5);  // 오른쪽 철학자 확인
    }

    test(i) {
        if (state[i] == HUNGRY &&
            state[(i+4)%5] != EATING &&
            state[(i+1)%5] != EATING) {
            state[i] = EATING;
            self[i].signal();
        }
    }
}

이 접근은 교착 상태를 막고 기아 상태도 방지할 수 있으며, 동기화 규칙을 깔끔하게 추상화한다.

문제마다 달라지는 제어 대상

문제	핵심 이슈	주요 기법	실무 사례
생산자-소비자	버퍼 관리	Counting 세마포어	메시지 큐
Readers-Writers	접근 우선순위	읽기 락, 쓰기 락	데이터베이스
Dining Philosophers	자원 순환 의존	순서 지정, 모니터	분산 락

락 이후의 동기화 선택지

Lock-Free 알고리즘은 원자적 연산(Atomic operation)을 이용해 락 없이 동기화한다. 교착 상태가 없고, 높은 병렬성과 낮은 지연 시간을 기대할 수 있다. Compare-And-Swap (CAS), Load-Link/Store-Conditional, Memory barriers가 여기에 쓰이는 기법이다.

트랜잭션 메모리(Transactional Memory)는 데이터베이스 트랜잭션 개념을 메모리 동기화에 적용한다. Hardware Transactional Memory (HTM)에는 Intel TSX가 있고, Software Transactional Memory (STM)에는 Clojure와 Haskell이 있다. 조합 가능성(Composability), 교착 상태의 자동 회피, 프로그래밍 편의성이 장점이다.

병렬 시스템에서 안정성과 효율을 함께 확보하려면 공유 자원의 특성과 대기 정책을 먼저 구분해야 한다. 생산자-소비자 문제는 버퍼와 생산·소비 속도 차이를, Readers-Writers 문제는 읽기·쓰기의 우선순위를, Dining Philosophers 문제는 자원의 순환 의존을 드러낸다.