동기화 이론을 배웠다면, 이제 실제 문제에 어떻게 적용하는지를 살펴볼 차례다. 이 글에서는 운영체제에서 가장 유명한 세 가지 고전 동기화 문제를 다루고, 이어서 POSIX, Windows, Linux, Java 환경에서 동기화를 구현하는 방법을 정리한다.
고전 동기화 문제 (Classical Problems of Synchronization)
Bounded-Buffer 문제
Bounded-Buffer 문제는 생산자(Producer) 와 소비자(Consumer) 가 유한한 크기의 버퍼를 공유하는 상황에서 발생한다.
- 버퍼가 가득 차면, 생산자는 소비자가 항목을 꺼낼 때까지 대기해야 한다
- 생산자에게 필요한 것은 빈 공간(empty slot) 이다
- 빈 슬롯의 개수를 세마포어 empty로 표현한다
- 버퍼가 비어 있으면, 소비자는 생산자가 항목을 넣을 때까지 대기해야 한다
- 소비자에게 필요한 것은 채워진 항목(item) 이다
- 항목의 개수를 세마포어 full로 표현한다
택배 물류센터에 비유하면, 적재 공간이 꽉 찼을 때 새 택배가 들어올 수 없고, 적재 공간이 텅 비었을 때 배송 트럭이 출발할 수 없는 것과 같다.
세마포어를 이용한 해법
세마포어 세 개를 사용한다: full = 0, empty = n, mutex = 1
mutex는 버퍼 접근에 대한 상호 배제(Mutual Exclusion) 를 보장하고, empty와 full은 각각 빈 슬롯과 채워진 슬롯의 수를 추적하여 생산자와 소비자의 동기화를 담당한다.
Readers-Writers 문제
여러 Reader와 Writer가 하나의 공유 데이터에 접근하는 상황이다.
- Reader는 동시에 여러 명이 데이터에 접근할 수 있다 (읽기만 하므로 충돌 없음)
- Writer가 데이터에 접근하는 동안에는 어떤 스레드도 접근할 수 없다
Writer의 행동 규칙:
- 임계 구역에 어떤 스레드라도 있으면, Writer는 대기해야 한다
- Writer는 임계 구역에 아무 스레드도 없을 때만 진입할 수 있다
- 진입 시 다른 모든 스레드의 진입을 차단해야 한다
Reader의 행동 규칙:
- 임계 구역에 Writer가 없으면 자유롭게 진입할 수 있다
- Writer가 있으면 Writer가 떠날 때까지 대기한다
- Reader가 이미 임계 구역에 있으면 다른 Reader도 진입 가능하지만, Writer는 불가하다
- 핵심은 첫 번째 Reader의 조건이 이후 Reader와 다르다는 점이다. 첫 Reader만 Writer 존재 여부를 확인하면 된다.
공유 데이터와 의사 코드
공유 데이터로 세마포어 mutex = 1, wrt = 1, 그리고 정수 readcount = 0 (임계 구역 내 Reader 수)을 사용한다.
Writer:
wait(wrt);
// writing is performed
signal(wrt);Reader:
wait(mutex); // readcount 보호 (상호 배제)
readcount++;
if (readcount == 1) // 첫 번째 Reader만
wait(wrt); // Writer 차단
signal(mutex);
// reading is performed
wait(mutex); // readcount 보호 (상호 배제)
readcount--;
if (readcount == 0) // 마지막 Reader만
signal(wrt); // Writer 허용
signal(mutex);mutex는 readcount 변수에 대한 상호 배제를, wrt는 Writer와 첫 번째/마지막 Reader 간의 동기화를 담당한다.
식사하는 철학자 문제 (Dining Philosophers)
이 문제는 동기화에서 가장 유명한 예제 중 하나다.
문제 정의:
- 원형 테이블에 5명의 철학자가 앉아 있다
- 철학자는 생각(Thinking) 하거나 식사(Eating, 임계 구역) 한다
- 5개의 그릇과 5개의 젓가락(각 철학자 사이에 하나씩)이 있다
- 철학자는 서로 대화하지 않는다
- 식사하려면 자신에게 가장 가까운 두 개의 젓가락을 모두 집어야 한다
- 한 번에 젓가락 하나만 집을 수 있다
- 식사를 마치면 젓가락을 내려놓는다
단순한 해법과 데드락
각 철학자가 왼쪽 젓가락을 먼저 집고 오른쪽 젓가락을 집는 방식은 가능하지만, 데드락(Deadlock) 이 발생할 수 있다.
데드락의 4가지 필요 조건 (네 가지 모두 성립해야 데드락이 발생한다):
- Mutual Exclusion: 하나의 젓가락은 한 철학자만 사용
- Hold and Wait: 젓가락 하나를 잡은 채 다른 젓가락을 대기
- No Preemption: 다른 사람이 강제로 젓가락을 빼앗을 수 없음
- Circular Wait: 모든 철학자가 원형으로 서로의 젓가락을 대기 (가장 쉬운 해결책: 짝수 번 철학자는 왼쪽 먼저, 홀수 번은 오른쪽 먼저 집기)
모니터를 이용한 해법
데이터 구조 (Field):
enum \{ thinking, hungry, eating \} state[5]: 각 철학자의 상태- hungry는 식사를 원하는 상태를 뜻한다
condition self[5]: 각 철학자의 대기 조건 변수 (wait,signal사용)
i번째 철학자의 동작 (Method):
dp.pickup(i); // entry section
Eat // critical section
dp.putdown(i); // exit section
이 해법은 Hold and Wait 조건을 제거하여 데드락이 발생하지 않는다(Deadlock-free). 하지만 특정 철학자가 영원히 식사하지 못하는 기아(Starvation) 가 발생할 수는 있다.
POSIX 동기화
POSIX(Portable Operating System Interface)에서 제공하는 동기화 도구를 살펴본다.
뮤텍스 락 (Mutex Locks)
생성과 초기화pthread 라이브러리를 사용한다.
#include <pthread.h>
pthread_mutex_t mutex; // 전역 선언
pthread_mutex_init(&mutex, NULL); // 첫 lock 전에 호출
// 해제: pthread_mutex_destroy(&mutex);또는 정적 초기화를 사용할 수 있다 (전역 변수일 때 편리하다):
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;pthread_mutex_lock(&mutex); // wait (잠금 획득)
/* critical section */
pthread_mutex_unlock(&mutex); // signal (잠금 해제)Named 세마포어
Named 세마포어는 서로 관련 없는(unrelated) 여러 프로세스가 이름을 통해 동일한 세마포어에 접근할 수 있게 해준다.
생성과 초기화#include <semaphore.h>
sem_t *sem; // 전역 선언 (포인터)
sem = sem_open("SEM", O_CREAT, 0666, 1); // 이름으로 생성/열기
// 해제: sem_close(sem); / sem_unlink("SEM");sem_wait(sem); // 세마포어 획득
/* critical section */
sem_post(sem); // 세마포어 해제Unnamed 세마포어
Unnamed 세마포어는 이름이 없어 관련 프로세스 간에만 공유 가능하다. fork() 이전에 생성하면 부모-자식 프로세스 간 공유된다.
#include <semaphore.h>
sem_t sem; // 전역 선언 (포인터가 아님!)
sem_init(&sem, 0, 1); // 초기화
// 해제: sem_destroy(&sem);Named 세마포어와 달리 포인터가 아닌 변수 자체를 선언한다는 점에 주의한다.
임계 구역 보호sem_wait(&sem); // 세마포어 획득 (&를 붙인다)
/* critical section */
sem_post(&sem); // 세마포어 해제 (&를 붙인다)조건 변수 (Condition Variables)
POSIX에서 조건 변수는 모니터 대신 뮤텍스 락과 결합하여 사용한다.
초기화pthread_mutex_t mutex; // procedure 간 상호 배제 보장
pthread_cond_t cond_var; // 조건 변수
pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&cond_var, NULL);
pthread_cond_wait()은 뮤텍스를 해제하고 조건을 기다리며, pthread_cond_signal()은 대기 중인 스레드를 깨운다.
커널 내 동기화 (Synchronization within the Kernel)
Windows 커널의 동기화
Windows 커널은 멀티스레드 커널이며, 실시간 애플리케이션을 지원한다. 선점적 우선순위 스케줄링(Preemptive Priority Scheduling)을 사용하여 응답 시간을 줄이고, 다중 프로세서도 지원한다.
전역 변수 접근 보호:
- 단일 프로세서 시스템: 인터럽트 마스킹(Mask Interrupt) 으로 보호
- 다중 프로세서 시스템: 스핀락(Spinlock) 사용
- 짧은 코드 구간만 보호하는 데 적합하다
- 커널은 스핀락을 보유한 스레드가 선점되지 않도록 보장한다
디스패처 객체 (Dispatcher Objects)
커널 외부에서의 스레드 동기화를 위해 Windows는 디스패처 객체를 제공한다. 뮤텍스 락, 세마포어, 이벤트, 타이머 등이 있다.
디스패처 객체는 두 가지 상태를 가진다:
- Signaled 상태: 객체가 사용 가능 (mutex = 1, unlock). 스레드가 획득 시 블록되지 않는다.
- Nonsignaled 상태: 객체가 사용 불가 (mutex = 0, lock). 스레드가 획득을 시도하면 블록되며, 상태가 ready에서 waiting으로 바뀌고 해당 객체의 대기 큐에 배치된다.
Critical Section 객체
Windows의 Critical Section 객체는 커널 개입 없이도 획득/해제할 수 있는 사용자 모드 뮤텍스다. 이것은 하이브리드 락(Hybrid Lock) 으로, 스핀락과 블로킹을 결합한다.
- 먼저 스핀락을 사용하여 다른 스레드가 해제하기를 기다린다. 이 단계에서는 커널 객체를 할당하지 않으므로 효율적이다.
- 스핀이 너무 오래 지속되면, 커널 뮤텍스를 할당하고 CPU를 양보(yield)한다.
Linux 커널의 동기화
Linux는 v2.6부터 완전한 선점형(Fully Preemptive) 커널이 되었다.
원자적 정수 (atomic_t)
모든 수학 연산이 중단 없이 수행되어 경쟁 조건(Race Condition) 을 방지한다.
atomic_t counter;
int value;
뮤텍스 락 (커널 내부)
int mutex_init(mutex_t *mp, int type, void *arg);
int mutex_lock(mutex_t *mp); // wait
int mutex_trylock(mutex_t *mp); // 비블로킹 시도
int mutex_unlock(mutex_t *mp); // signal
int mutex_consistent(mutex_t *mp); // 뮤텍스 일관성 복구
int mutex_destroy(mutex_t *mp);스핀락
spin_lock(), spin_unlock() 등을 사용한다. 짧은 시간 동안의 보호에 적합하며, 단일 프로세서 코어에서는 부적절하다 (바쁜 대기만 발생).
커널 선점 제어
preempt_disable()과 preempt_enable()로 커널 선점을 활성화/비활성화할 수 있다. 이 기능은 사용자 모드에서는 사용할 수 없다.
Java에서의 동기화 (Synchronization in Java)
Java 모니터
Java는 synchronized 키워드를 통해 모니터 방식의 동기화를 제공한다.
Entry Set과 Lock:
- Entry Set: 락을 기다리는 스레드들이 대기하는 곳
- 락이 해제되면 JVM이 임의의 스레드를 선택하여 실행한다 (실제로는 FIFO 정책을 따르는 경우가 많다)
Java에서의 Producer-Consumer 구현:
wait()과 notify()
락을 보유한 스레드가 계속 진행할 수 없을 때(예: 버퍼가 가득 찬 상태에서 insert() 호출), wait() 을 호출한다.
wait() 호출 시:
- 해당 객체의 락을 해제한다
- 스레드 상태가 blocked로 설정된다
- 스레드가 해당 객체의 Wait Set에 배치된다
다른 스레드가 notify() 를 호출하면:
- Wait Set에서 임의의 스레드 T를 선택한다
- T를 Wait Set에서 Entry Set으로 이동시킨다
- T의 상태를 blocked에서 runnable로 변경한다
- 락이 해제되면 JVM이 Entry Set에서 임의로 스레드를 선택하여 실행한다
Java 세마포어
Java에서도 세마포어를 사용할 수 있다.
Semaphore sem = new Semaphore(1); // 초기값 1
HGU 전산전자공학부 김인중 교수님의 23-1 운영체제 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.