- Authors
- Name
- Youngju Kim
- @fjvbn20031
배경: 경쟁 조건
여러 프로세스(또는 스레드)가 공유 데이터에 동시에 접근하면, 실행 순서에 따라 결과가 달라질 수 있다. 이를 **경쟁 조건(Race Condition)**이라 한다.
// 경쟁 조건 예시: 두 스레드가 공유 변수 count를 증가
// count의 초기값이 5일 때
// 스레드 A: count++
// 내부적으로:
// register_A = count (register_A = 5)
// register_A = register_A + 1 (register_A = 6)
// count = register_A (count = 6)
// 스레드 B: count++
// 내부적으로:
// register_B = count (register_B = 5)
// register_B = register_B + 1 (register_B = 6)
// count = register_B (count = 6)
// 교차 실행 시나리오:
// T0: A가 register_A = count (register_A = 5)
// T1: A가 register_A = register_A + 1 (register_A = 6)
// T2: B가 register_B = count (register_B = 5) <-- 아직 5!
// T3: B가 register_B = register_B + 1 (register_B = 6)
// T4: A가 count = register_A (count = 6)
// T5: B가 count = register_B (count = 6)
// 결과: count = 6 (기대값 7이 아님!)
임계 영역 문제 (Critical Section Problem)
임계 영역(Critical Section)은 공유 데이터에 접근하는 코드 영역이다.
[프로세스 구조]
do {
[진입 영역(Entry Section)]
-- 임계 영역에 들어가기 위한 허가 요청 --
[임계 영역(Critical Section)]
-- 공유 데이터 접근 --
[퇴출 영역(Exit Section)]
-- 임계 영역 사용 완료 알림 --
[나머지 영역(Remainder Section)]
} while (true);
임계 영역 문제의 해결 조건 세 가지는 다음과 같다.
- 상호 배제(Mutual Exclusion): 한 프로세스가 임계 영역을 실행 중이면, 다른 프로세스는 들어갈 수 없음
- 진행(Progress): 임계 영역에 아무도 없을 때, 들어가려는 프로세스 중 하나가 선택되어야 함. 결정이 무한히 지연되면 안 됨
- 한정 대기(Bounded Waiting): 프로세스가 임계 영역 진입을 요청한 후, 다른 프로세스가 임계 영역에 들어가는 횟수에 한계가 있어야 함
피터슨 해법 (Peterson's Solution)
두 프로세스 간의 임계 영역 문제를 소프트웨어로 해결하는 고전적 알고리즘이다.
// 피터슨 해법 (두 프로세스 i, j)
int turn; // 누구 차례인지
bool flag[2]; // 임계 영역 진입 의사
// 프로세스 i의 코드
void process_i() {
while (true) {
flag[i] = true; // 나(i)는 들어가고 싶다
turn = j; // 상대방(j)에게 양보
while (flag[j] && turn == j)
; // 상대가 원하고, 상대 차례면 대기
// 임계 영역
// ... 공유 데이터 접근 ...
flag[i] = false; // 나는 다 썼다
// 나머지 영역
}
}
피터슨 해법은 세 가지 조건(상호 배제, 진행, 한정 대기)을 모두 만족한다. 하지만 현대 컴퓨터 아키텍처에서는 컴파일러나 프로세서의 명령어 재배치(reordering) 때문에 올바르게 동작하지 않을 수 있다.
하드웨어 동기화 지원
메모리 배리어 (Memory Barrier)
메모리 배리어(또는 메모리 펜스)는 프로세서에게 배리어 전후의 메모리 접근 순서를 보장하도록 지시한다.
// 메모리 배리어 사용 예시
// 스레드 1
while (!flag)
memory_barrier(); // flag 읽기가 이 시점 이전으로 재배치되지 않음
print(x);
// 스레드 2
x = 100;
memory_barrier(); // x 쓰기가 flag 쓰기 이전에 완료됨을 보장
flag = true;
CAS (Compare-And-Swap)
CAS는 원자적(atomic) 하드웨어 명령어로, 동기화의 기본 빌딩 블록이다.
// CAS의 논리 (실제로는 하나의 원자적 명령어)
bool compare_and_swap(int *value, int expected, int new_value) {
if (*value == expected) {
*value = new_value;
return true;
}
return false;
}
// CAS를 이용한 원자적 증가
void atomic_increment(int *counter) {
int old_val;
do {
old_val = *counter;
} while (!compare_and_swap(counter, old_val, old_val + 1));
// 성공할 때까지 재시도
}
// CAS를 이용한 상호 배제
int lock = 0;
void acquire() {
while (!compare_and_swap(&lock, 0, 1))
; // lock이 0(사용 가능)이면 1(사용 중)로 변경
}
void release() {
lock = 0;
}
원자적 변수 (Atomic Variables)
CAS 같은 하드웨어 명령어를 기반으로, 기본 데이터 타입에 대한 원자적 연산을 제공한다.
// C11 원자적 변수
#include <stdatomic.h>
atomic_int counter = 0;
void increment() {
atomic_fetch_add(&counter, 1); // 원자적 증가
}
// Java의 원자적 변수
// import java.util.concurrent.atomic.AtomicInteger;
// AtomicInteger counter = new AtomicInteger(0);
// counter.incrementAndGet(); // 원자적 증가
원자적 변수는 단일 변수에 대한 경쟁 조건은 해결하지만, 복잡한 임계 영역 문제의 일반적 해결책은 되지 못한다.
뮤텍스 락 (Mutex Lock)
뮤텍스는 가장 단순한 동기화 도구로, 임계 영역을 보호하는 잠금 장치다.
// 뮤텍스 사용 패턴
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void critical_section() {
pthread_mutex_lock(&mutex); // 잠금 획득 (acquire)
// 임계 영역
// 공유 데이터 접근
pthread_mutex_unlock(&mutex); // 잠금 해제 (release)
}
[뮤텍스 동작]
스레드 A 스레드 B
| |
|-- lock() 성공 ---- |
| (임계 영역 진입) |-- lock() 시도
| 공유 데이터 접근 | (대기/블로킹)
| | ...
|-- unlock() ------- |
| ----->|-- lock() 성공
| | (임계 영역 진입)
| | 공유 데이터 접근
| |-- unlock()
스핀락(Spinlock): lock을 얻을 때까지 반복 확인하며 대기(바쁜 대기, busy waiting). 멀티코어에서 짧은 임계 영역에 적합하다. 컨텍스트 스위치 오버헤드를 피할 수 있기 때문이다.
// 스핀락 구현 (CAS 기반)
typedef struct {
atomic_flag flag;
} spinlock_t;
void spin_lock(spinlock_t *lock) {
while (atomic_flag_test_and_set(&lock->flag))
; // 잠금될 때까지 반복 (바쁜 대기)
}
void spin_unlock(spinlock_t *lock) {
atomic_flag_clear(&lock->flag);
}
세마포어 (Semaphore)
세마포어는 뮤텍스보다 일반적인 동기화 도구다. 정수 변수로 wait()와 signal() 연산만 허용한다.
// 세마포어의 기본 연산 (원자적)
wait(S) { // P 연산 또는 acquire
while (S <= 0)
; // 대기
S--;
}
signal(S) { // V 연산 또는 release
S++;
}
세마포어의 종류
- 카운팅 세마포어: 값의 범위에 제한 없음. 가용 자원의 개수를 추적
- 이진 세마포어: 0 또는 1만 가능. 뮤텍스와 유사
// 카운팅 세마포어 사용 예: 최대 5개 동시 접속
#include <semaphore.h>
sem_t connection_pool;
void init() {
sem_init(&connection_pool, 0, 5); // 초기값 5
}
void handle_request() {
sem_wait(&connection_pool); // 연결 획득 (남은 수 감소)
// 데이터베이스 작업 수행
// ...
sem_post(&connection_pool); // 연결 반환 (남은 수 증가)
}
세마포어를 이용한 순서 제어
// S1이 S2보다 먼저 실행되도록 보장
sem_t sync_sem;
sem_init(&sync_sem, 0, 0); // 초기값 0
// 프로세스 1
void process1() {
S1; // 먼저 실행할 문장
sem_post(&sync_sem); // signal
}
// 프로세스 2
void process2() {
sem_wait(&sync_sem); // wait (S1 완료까지 대기)
S2; // S1 이후에 실행
}
바쁜 대기 없는 세마포어
실제 구현에서는 바쁜 대기 대신 대기 큐를 사용한다.
typedef struct {
int value;
struct list_head waiting_list; // 대기 프로세스 목록
} semaphore;
void wait(semaphore *S) {
S->value--;
if (S->value < 0) {
// 현재 프로세스를 대기 목록에 추가
add_to_list(&S->waiting_list, current_process);
block(); // 프로세스를 대기 상태로 전환
}
}
void signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
// 대기 목록에서 프로세스 하나를 깨움
process *P = remove_from_list(&S->waiting_list);
wakeup(P); // P를 준비 상태로 전환
}
}
모니터 (Monitor)
세마포어는 강력하지만 사용하기 어렵고 오류가 발생하기 쉽다. 모니터는 프로그래밍 언어 수준에서 동기화를 지원하는 고수준 구조체다.
[모니터 구조]
+------------------------------------+
| monitor |
| |
| 공유 데이터 |
| +-----------+ |
| | 변수들 | |
| +-----------+ |
| |
| 조건 변수 |
| condition x, y; |
| |
| procedure P1() { ... } |
| procedure P2() { ... } |
| procedure P3() { ... } |
| |
| 초기화 코드 |
| |
+------------------------------------+
^ ^ ^
| | |
스레드1 스레드2 스레드3
(한 번에 하나만 모니터 내부 실행)
조건 변수 (Condition Variable)
모니터 내에서 특정 조건이 만족될 때까지 대기하기 위해 사용한다.
x.wait(): 호출한 프로세스를 조건 x의 대기 큐에 넣고 모니터를 해제x.signal(): 조건 x의 대기 큐에서 하나의 프로세스를 깨움
// Java에서 모니터 패턴 (synchronized 키워드)
public class BoundedBuffer {
private final Object[] buffer;
private int count = 0;
private int in = 0;
private int out = 0;
public BoundedBuffer(int size) {
buffer = new Object[size];
}
// synchronized: 한 번에 하나의 스레드만 실행
public synchronized void produce(Object item)
throws InterruptedException {
while (count == buffer.length) {
wait(); // 버퍼가 가득 차면 대기
}
buffer[in] = item;
in = (in + 1) % buffer.length;
count++;
notifyAll(); // 대기 중인 소비자 깨움
}
public synchronized Object consume()
throws InterruptedException {
while (count == 0) {
wait(); // 버퍼가 비어있으면 대기
}
Object item = buffer[out];
out = (out + 1) % buffer.length;
count--;
notifyAll(); // 대기 중인 생산자 깨움
return item;
}
}
// Pthreads 조건 변수 사용
#include <pthread.h>
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int ready = 0;
// 대기하는 스레드
void *waiter(void *arg) {
pthread_mutex_lock(&mutex);
while (!ready) {
// 조건이 만족될 때까지 대기
// mutex를 해제하고 대기, 깨어나면 다시 획득
pthread_cond_wait(&cond, &mutex);
}
printf("조건 충족! 진행합니다.\n");
pthread_mutex_unlock(&mutex);
return NULL;
}
// 신호를 보내는 스레드
void *signaler(void *arg) {
pthread_mutex_lock(&mutex);
ready = 1;
pthread_cond_signal(&cond); // 대기 중인 스레드 깨움
pthread_mutex_unlock(&mutex);
return NULL;
}
활성 문제 (Liveness Problems)
동기화 도구를 부적절하게 사용하면 프로세스가 영원히 진행하지 못하는 상황이 발생할 수 있다.
교착 상태 (Deadlock)
두 개 이상의 프로세스가 서로 상대방이 보유한 자원을 기다리며 영원히 대기하는 상태다.
[교착 상태 예시]
스레드 A 스레드 B
lock(mutex1); lock(mutex2);
// mutex1 보유 // mutex2 보유
lock(mutex2); lock(mutex1);
// mutex2 대기! // mutex1 대기!
// 서로 상대방의 자원을 기다리며 교착
해결: 자원 획득 순서를 항상 동일하게 유지
스레드 A 스레드 B
lock(mutex1); lock(mutex1); // 같은 순서로 획득
lock(mutex2); lock(mutex2);
기아 (Starvation)
프로세스가 필요한 자원을 영원히 얻지 못하는 상태다. 예를 들어, 우선순위가 낮은 프로세스가 높은 우선순위 프로세스에 의해 계속 밀리는 경우다.
우선순위 역전 (Priority Inversion)
높은 우선순위 프로세스가 낮은 우선순위 프로세스가 보유한 자원을 기다리게 되는 상황이다.
[우선순위 역전 시나리오]
우선순위: H > M > L
1. L이 자원 R을 획득하고 실행 중
2. H가 도착, R을 요청 -> L이 보유 중이므로 대기
3. M이 도착, L을 선점 -> M이 실행
4. H는 L이 R을 반납해야 하는데, L은 M에 의해 선점됨
5. 결과: M이 H보다 먼저 실행! (우선순위 역전)
해결: 우선순위 상속 프로토콜
L이 R을 보유한 동안 H의 우선순위를 상속받음
-> L이 M에 의해 선점되지 않음 -> L이 R을 빨리 반납
화성 탐사선 패스파인더에서 우선순위 역전 버그가 실제로 발생한 사례가 유명하다. 우선순위 상속 프로토콜을 활성화하여 해결했다.
정리
프로세스 동기화는 공유 자원에 대한 경쟁 조건을 해결하기 위해 필수적이다. 하드웨어 수준의 CAS와 원자적 변수부터, 뮤텍스와 세마포어, 그리고 고수준의 모니터까지 다양한 도구가 존재한다. 이러한 도구를 올바르게 사용하지 않으면 교착 상태, 기아, 우선순위 역전 같은 활성 문제가 발생할 수 있다.