고전적 동기화 문제
동기화 도구의 올바른 사용법을 이해하기 위해, 운영체제 분야에서 전통적으로 다루는 세 가지 고전적 문제를 살펴본다.
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보다 유연한 잠금 메커니즘이다.
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는 뮤텍스, 세마포어, 조건 변수 등 다양한 동기화 도구를 제공한다. 트랜잭셔널 메모리나 함수형 프로그래밍 같은 대안적 접근법도 동시성 문제를 해결하는 방법으로 주목받고 있다.
현재 단락 (1/322)
동기화 도구의 올바른 사용법을 이해하기 위해, 운영체제 분야에서 전통적으로 다루는 세 가지 고전적 문제를 살펴본다.