[운영체제] 07. 동기화 문제: 생산자-소비자, 철학자 식사

고전적 동기화 문제

동기화 도구의 올바른 사용법을 이해하기 위해, 운영체제 분야에서 전통적으로 다루는 세 가지 고전적 문제를 살펴본다.

1. 유한 버퍼 문제 (Bounded-Buffer Problem)

생산자는 데이터를 만들어 버퍼에 넣고, 소비자는 버퍼에서 데이터를 꺼내 사용한다. 버퍼의 크기가 유한하므로, 버퍼가 가득 차면 생산자는 대기하고, 비어 있으면 소비자가 대기해야 한다.

[유한 버퍼 구조]

생산자 -->  [  |  |  |  |  ]  --> 소비자
            0  1  2  3  4
            ^           ^
           out          in

세마포어:
  mutex = 1      (버퍼 접근 상호 배제)
  empty = N      (빈 슬롯 수, 초기값 = 버퍼 크기)
  full  = 0      (채워진 슬롯 수, 초기값 = 0)

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>

#define BUFFER_SIZE 5

int buffer[BUFFER_SIZE];
int in = 0, out = 0;

sem_t empty;    // 빈 슬롯 수
sem_t full;     // 채워진 슬롯 수
pthread_mutex_t mutex;

void *producer(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < 10; i++) {
        int item = rand() % 100;

        sem_wait(&empty);           // 빈 슬롯이 있을 때까지 대기
        pthread_mutex_lock(&mutex); // 버퍼 접근 잠금

        // 임계 영역: 버퍼에 아이템 추가
        buffer[in] = item;
        printf("생산자 %d: buffer[%d] = %d 생산\n", id, in, item);
        in = (in + 1) % BUFFER_SIZE;

        pthread_mutex_unlock(&mutex);
        sem_post(&full);            // 채워진 슬롯 수 증가

        usleep(rand() % 500000);
    }
    return NULL;
}

void *consumer(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < 10; i++) {
        sem_wait(&full);            // 채워진 슬롯이 있을 때까지 대기
        pthread_mutex_lock(&mutex); // 버퍼 접근 잠금

        // 임계 영역: 버퍼에서 아이템 꺼냄
        int item = buffer[out];
        printf("소비자 %d: buffer[%d] = %d 소비\n", id, out, item);
        out = (out + 1) % BUFFER_SIZE;

        pthread_mutex_unlock(&mutex);
        sem_post(&empty);           // 빈 슬롯 수 증가

        usleep(rand() % 800000);
    }
    return NULL;
}

int main() {
    pthread_mutex_init(&mutex, NULL);
    sem_init(&empty, 0, BUFFER_SIZE);
    sem_init(&full, 0, 0);

    pthread_t prod[2], cons[2];
    int ids[] = {0, 1};

    for (int i = 0; i < 2; i++) {
        pthread_create(&prod[i], NULL, producer, &ids[i]);
        pthread_create(&cons[i], NULL, consumer, &ids[i]);
    }

    for (int i = 0; i < 2; i++) {
        pthread_join(prod[i], NULL);
        pthread_join(cons[i], NULL);
    }

    pthread_mutex_destroy(&mutex);
    sem_destroy(&empty);
    sem_destroy(&full);
    return 0;
}

2. 읽기-쓰기 문제 (Readers-Writers Problem)

데이터베이스를 여러 프로세스가 공유할 때, 읽기만 하는 프로세스(reader)는 동시에 접근해도 안전하지만, 쓰기 프로세스(writer)는 배타적 접근이 필요하다.

[읽기-쓰기 규칙]

Reader + Reader = 허용 (동시 읽기 가능)
Reader + Writer = 불허 (충돌)
Writer + Writer = 불허 (충돌)

첫 번째 변형: 읽기 우선

독자가 있으면 작가가 대기한다. 독자가 계속 들어오면 작가가 기아 상태에 빠질 수 있다.

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t rw_mutex = PTHREAD_MUTEX_INITIALIZER;
int read_count = 0;
int shared_data = 0;

void *reader(void *arg) {
    int id = *(int *)arg;

    pthread_mutex_lock(&mutex);
    read_count++;
    if (read_count == 1) {
        // 첫 번째 독자가 작가를 차단
        pthread_mutex_lock(&rw_mutex);
    }
    pthread_mutex_unlock(&mutex);

    // 임계 영역: 읽기
    printf("독자 %d: 데이터 읽음 = %d (현재 독자 수: %d)\n",
           id, shared_data, read_count);

    pthread_mutex_lock(&mutex);
    read_count--;
    if (read_count == 0) {
        // 마지막 독자가 작가 차단 해제
        pthread_mutex_unlock(&rw_mutex);
    }
    pthread_mutex_unlock(&mutex);

    return NULL;
}

void *writer(void *arg) {
    int id = *(int *)arg;

    pthread_mutex_lock(&rw_mutex);  // 배타적 접근

    // 임계 영역: 쓰기
    shared_data++;
    printf("작가 %d: 데이터 갱신 = %d\n", id, shared_data);

    pthread_mutex_unlock(&rw_mutex);

    return NULL;
}

두 번째 변형: 쓰기 우선

작가가 준비되면 새로운 독자는 들어갈 수 없다. 기존 독자가 모두 나간 후 작가가 실행된다.

3. 식사하는 철학자 문제 (Dining Philosophers Problem)

다섯 명의 철학자가 원형 테이블에 앉아 있다. 각 철학자 사이에 젓가락이 하나씩 있으며, 식사하려면 양쪽 젓가락 두 개가 필요하다.

[식사하는 철학자]

        P0
    C4      C0
  P4          P1
    C3      C1
        P3
      C2
        P2

P: 철학자 (Philosopher)
C: 젓가락 (Chopstick)

철학자 i는 젓가락 i와 젓가락 (i+1)%5를 사용

세마포어를 이용한 간단한 해법 (교착 위험)

// 주의: 이 해법은 교착 상태가 발생할 수 있다!
sem_t chopstick[5];

void *philosopher(void *arg) {
    int id = *(int *)arg;

    while (1) {
        printf("철학자 %d: 생각 중\n", id);
        usleep(rand() % 1000000);

        // 양쪽 젓가락 집기
        sem_wait(&chopstick[id]);           // 왼쪽
        sem_wait(&chopstick[(id + 1) % 5]); // 오른쪽

        printf("철학자 %d: 식사 중\n", id);
        usleep(rand() % 1000000);

        // 젓가락 내려놓기
        sem_post(&chopstick[id]);
        sem_post(&chopstick[(id + 1) % 5]);
    }
}

// 교착 상태: 5명 모두 동시에 왼쪽 젓가락을 들면
// 아무도 오른쪽 젓가락을 얻지 못함!

교착 상태를 방지하는 해법들

// 해법 1: 비대칭 - 짝수 철학자는 왼쪽 먼저, 홀수는 오른쪽 먼저
void *philosopher_asymmetric(void *arg) {
    int id = *(int *)arg;

    while (1) {
        printf("철학자 %d: 생각 중\n", id);

        if (id % 2 == 0) {
            sem_wait(&chopstick[id]);
            sem_wait(&chopstick[(id + 1) % 5]);
        } else {
            sem_wait(&chopstick[(id + 1) % 5]);
            sem_wait(&chopstick[id]);
        }

        printf("철학자 %d: 식사 중\n", id);
        usleep(rand() % 1000000);

        sem_post(&chopstick[id]);
        sem_post(&chopstick[(id + 1) % 5]);
    }
}

모니터를 이용한 해법

// 모니터 기반 해법 (Pthreads 조건 변수 사용)
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

#define N 5
#define THINKING 0
#define HUNGRY   1
#define EATING   2

int state[N];
pthread_mutex_t monitor_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t self[N];

// 왼쪽, 오른쪽 이웃 인덱스
#define LEFT(i)  ((i + N - 1) % N)
#define RIGHT(i) ((i + 1) % N)

void test(int i) {
    // 내가 배고프고, 양쪽 이웃이 식사 중이 아니면 먹을 수 있음
    if (state[i] == HUNGRY &&
        state[LEFT(i)] != EATING &&
        state[RIGHT(i)] != EATING) {
        state[i] = EATING;
        pthread_cond_signal(&self[i]);
    }
}

void pickup(int i) {
    pthread_mutex_lock(&monitor_mutex);

    state[i] = HUNGRY;
    printf("철학자 %d: 배고픔\n", i);
    test(i);  // 바로 먹을 수 있는지 확인

    while (state[i] != EATING) {
        pthread_cond_wait(&self[i], &monitor_mutex);
    }

    printf("철학자 %d: 식사 시작\n", i);
    pthread_mutex_unlock(&monitor_mutex);
}

void putdown(int i) {
    pthread_mutex_lock(&monitor_mutex);

    state[i] = THINKING;
    printf("철학자 %d: 식사 완료, 생각 시작\n", i);

    // 이웃들이 먹을 수 있는지 확인
    test(LEFT(i));
    test(RIGHT(i));

    pthread_mutex_unlock(&monitor_mutex);
}

void *philosopher(void *arg) {
    int id = *(int *)arg;
    while (1) {
        usleep(rand() % 1000000);  // 생각
        pickup(id);                 // 젓가락 집기
        usleep(rand() % 1000000);  // 식사
        putdown(id);                // 젓가락 내려놓기
    }
}

POSIX 동기화

POSIX 뮤텍스

#include <pthread.h>

pthread_mutex_t lock;

// 정적 초기화
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

// 동적 초기화
pthread_mutex_init(&lock, NULL);

// 사용
pthread_mutex_lock(&lock);
// 임계 영역
pthread_mutex_unlock(&lock);

// 비블로킹 시도
if (pthread_mutex_trylock(&lock) == 0) {
    // 잠금 획득 성공
    pthread_mutex_unlock(&lock);
} else {
    // 다른 스레드가 보유 중
}

// 정리
pthread_mutex_destroy(&lock);

POSIX 세마포어

POSIX는 이름 있는(named) 세마포어와 이름 없는(unnamed) 세마포어를 제공한다.

#include <semaphore.h>

// 이름 없는 세마포어 (스레드 간)
sem_t sem;
sem_init(&sem, 0, 1);  // 0: 스레드 간, 초기값 1
sem_wait(&sem);
sem_post(&sem);
sem_destroy(&sem);

// 이름 있는 세마포어 (프로세스 간)
sem_t *sem = sem_open("/my_sem", O_CREAT, 0644, 1);
sem_wait(sem);
sem_post(sem);
sem_close(sem);
sem_unlink("/my_sem");

POSIX 조건 변수

#include <pthread.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int data_ready = 0;

// 생산자
void *producer(void *arg) {
    pthread_mutex_lock(&mutex);

    // 데이터 생성
    data_ready = 1;
    printf("생산자: 데이터 준비 완료\n");

    pthread_cond_signal(&cond);    // 대기 중인 소비자 깨움
    pthread_mutex_unlock(&mutex);
    return NULL;
}

// 소비자
void *consumer(void *arg) {
    pthread_mutex_lock(&mutex);

    while (!data_ready) {
        // 조건이 만족될 때까지 대기
        // wait 중에는 mutex가 자동으로 해제됨
        pthread_cond_wait(&cond, &mutex);
    }

    printf("소비자: 데이터 소비\n");
    data_ready = 0;

    pthread_mutex_unlock(&mutex);
    return NULL;
}

Java 동기화

synchronized 키워드

public class Counter {
    private int count = 0;

    // 메서드 수준 동기화
    public synchronized void increment() {
        count++;
    }

    public synchronized int getCount() {
        return count;
    }

    // 블록 수준 동기화
    public void incrementBlock() {
        synchronized (this) {
            count++;
        }
    }
}

ReentrantLock

synchronized보다 유연한 잠금 메커니즘이다.

import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.Condition;

public class BoundedBufferLock {
    private final Object[] buffer;
    private int count = 0, in = 0, out = 0;

    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();

    public BoundedBufferLock(int size) {
        buffer = new Object[size];
    }

    public void produce(Object item) throws InterruptedException {
        lock.lock();
        try {
            while (count == buffer.length) {
                notFull.await();    // 버퍼 빌 때까지 대기
            }
            buffer[in] = item;
            in = (in + 1) % buffer.length;
            count++;
            notEmpty.signal();      // 소비자 깨움
        } finally {
            lock.unlock();
        }
    }

    public Object consume() throws InterruptedException {
        lock.lock();
        try {
            while (count == 0) {
                notEmpty.await();   // 데이터 올 때까지 대기
            }
            Object item = buffer[out];
            out = (out + 1) % buffer.length;
            count--;
            notFull.signal();       // 생산자 깨움
            return item;
        } finally {
            lock.unlock();
        }
    }
}

대안적 접근법

트랜잭셔널 메모리 (Transactional Memory)

데이터베이스의 트랜잭션 개념을 메모리 접근에 적용한다.

// 개념적 코드 (실제 문법은 구현에 따라 다름)
atomic {
    // 이 블록 안의 모든 메모리 연산은 원자적으로 실행
    // 충돌 발생 시 자동으로 재시도
    account1.balance -= amount;
    account2.balance += amount;
}

함수형 프로그래밍

불변(immutable) 데이터 구조를 사용하면 공유 상태가 변경되지 않으므로 동기화가 불필요하다. Erlang, Scala, Haskell 등의 함수형 언어가 이 접근법을 활용한다.

정리

유한 버퍼, 읽기-쓰기, 식사하는 철학자 문제는 동기화의 핵심 과제를 보여주는 고전적 예제다. POSIX와 Java는 뮤텍스, 세마포어, 조건 변수 등 다양한 동기화 도구를 제공한다. 트랜잭셔널 메모리나 함수형 프로그래밍 같은 대안적 접근법도 동시성 문제를 해결하는 방법으로 주목받고 있다.