세마포어로 설계하는 프로세스 동기화와 자원 제어

Dijkstra가 1965년 제안한 세마포어는 공유 자원에 접근하는 프로세스의 순서를 제어하는 추상 자료형이다. 정수 값 하나와 원자적으로 실행되는 P, V 연산만으로 임계 영역 보호부터 제한된 자원 관리까지 다룬다.

P와 V가 바꾸는 세마포어 상태

세마포어는 값과 대기 프로세스 큐를 함께 관리한다. P 연산은 값을 감소시키고, 값이 0보다 작아지면 호출한 프로세스를 대기시킨다. V 연산은 값을 증가시키며, 대기 중인 프로세스가 있으면 하나를 깨운다. 이 두 연산이 중단 없이 수행되어야 동기화가 성립한다.

typedef struct {
    int value;           // 세마포어 값
    Queue waiting_list;  // 대기 프로세스 큐
} Semaphore;

// P 연산 (wait, acquire)
void P(Semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // 현재 프로세스를 waiting_list에 추가
        add_to_queue(S->waiting_list, current_process);
        block();  // 프로세스를 대기 상태로 전환
    }
}

// V 연산 (signal, release)
void V(Semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // waiting_list에서 프로세스 하나를 꺼냄
        Process *P = remove_from_queue(S->waiting_list);
        wakeup(P);  // 프로세스를 준비 상태로 전환
    }
}

세마포어는 값의 의미에 따라 이진 세마포어와 카운팅 세마포어로 구분한다.

⤢✕

이진 세마포어로 임계 영역을 잠그는 방식

이진 세마포어의 값은 0 또는 1이다. 잠김과 열림을 표현할 수 있어 상호배제에 쓰이며, Mutex와 기능적으로 유사하지만 소유권 개념은 없다. 일반적으로 초기값은 1이다.

Semaphore mutex;
init_semaphore(&mutex, 1);  // 초기값 1

void process() {
    while (true) {
        P(&mutex);  // Entry Section

        // Critical Section
        shared_resource++;

        V(&mutex);  // Exit Section

        // Remainder Section
        other_work();
    }
}

P1이 먼저 세마포어를 획득하면 P2는 해제될 때까지 대기한다. V 연산 이후 P2가 임계 영역에 진입하는 흐름은 다음과 같다.

시간	P1 동작	P2 동작	mutex 값
T1	P(&mutex) 성공	-	0
T2	Critical Section	P(&mutex) 블록	0 (P2 대기)
T3	V(&mutex)	-	1
T4	-	P(&mutex) 성공	0
T5	-	Critical Section	0
T6	-	V(&mutex)	1

제한된 자원 수를 카운팅 세마포어에 담는다

카운팅 세마포어는 0 이상의 정수를 값으로 사용하며, 초기값은 사용 가능한 자원 수다. 값이 0 이상이면 사용 가능한 자원 수를, 0보다 작으면 대기 중인 프로세스 수를 나타낸다. 동일한 자원이 제한된 수만큼 있을 때 적합하다.

// 프린터 5대를 관리하는 세마포어
Semaphore printers;
init_semaphore(&printers, 5);  // 5대 사용 가능

void print_job() {
    P(&printers);  // 프린터 획득

    // 프린터 사용
    use_printer();

    V(&printers);  // 프린터 반환
}

프린터 5대를 관리하는 경우 초기 value는 5다. 3개 프로세스가 P()를 호출하면 2가 되고, 이어서 3개 프로세스가 더 호출하면 -1이 되어 1개 프로세스가 대기한다. 이후 1개 프로세스가 V()를 호출하면 값은 0이 되고 대기 프로세스가 깨어난다.

생산자-소비자 문제에서는 빈 슬롯, 채워진 슬롯, 버퍼 접근을 각각 다른 세마포어로 제어한다.

#define BUFFER_SIZE 10

Semaphore empty;   // 빈 슬롯 개수
Semaphore full;    // 채워진 슬롯 개수
Semaphore mutex;   // 버퍼 접근 상호배제

init_semaphore(&empty, BUFFER_SIZE);  // 10개 빈 슬롯
init_semaphore(&full, 0);              // 0개 채워진 슬롯
init_semaphore(&mutex, 1);             // 상호배제

void producer() {
    while (true) {
        produce_item();

        P(&empty);   // 빈 슬롯 확보
        P(&mutex);   // 버퍼 잠금

        add_to_buffer();

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

void consumer() {
    while (true) {
        P(&full);    // 채워진 슬롯 확보
        P(&mutex);   // 버퍼 잠금

        remove_from_buffer();

        V(&mutex);   // 버퍼 해제
        V(&empty);   // 빈 슬롯 증가

        consume_item();
    }
}

실행 순서와 접근 권한을 맞추는 패턴

세마포어는 상호배제 외에도 프로세스 간 실행 순서를 보장하는 데 쓸 수 있다. 초기값이 0인 sync는 Process 1이 statement_A()를 마친 뒤 신호를 보내기 전까지 Process 2를 대기시킨다.

Semaphore sync;
init_semaphore(&sync, 0);  // 초기값 0

// Process 1
void process1() {
    statement_A();
    V(&sync);  // Process 2에게 신호
}

// Process 2
void process2() {
    P(&sync);  // Process 1 대기
    statement_B();  // statement_A 후에 실행 보장
}

Readers-Writers 패턴에서는 첫 번째 reader가 writer를 차단하고, 마지막 reader가 writer의 접근을 다시 허용한다.

int read_count = 0;
Semaphore mutex;      // read_count 보호
Semaphore write_sem;  // 쓰기 상호배제

init_semaphore(&mutex, 1);
init_semaphore(&write_sem, 1);

void reader() {
    P(&mutex);
    read_count++;
    if (read_count == 1)
        P(&write_sem);  // 첫 reader가 writer 차단
    V(&mutex);

    // 읽기 수행
    read_data();

    P(&mutex);
    read_count--;
    if (read_count == 0)
        V(&write_sem);  // 마지막 reader가 writer 허용
    V(&mutex);
}

void writer() {
    P(&write_sem);

    // 쓰기 수행
    write_data();

    V(&write_sem);
}

Barrier는 모든 프로세스가 첫 단계에 도착한 다음에야 다음 단계로 진행하게 한다.

#define N 5  // 프로세스 수

int count = 0;
Semaphore mutex;
Semaphore barrier;

init_semaphore(&mutex, 1);
init_semaphore(&barrier, 0);

void process_barrier() {
    // Phase 1 작업
    phase1_work();

    // 모든 프로세스가 도착할 때까지 대기
    P(&mutex);
    count++;
    if (count == N) {
        V(&barrier);  // 첫 프로세스 깨움
    }
    V(&mutex);

    P(&barrier);
    V(&barrier);  // 다음 프로세스 깨움 (연쇄)

    // Phase 2 작업 (모든 프로세스 동기화 후)
    phase2_work();
}

스핀 대기와 블로킹 구현의 차이

Busy-waiting 구현은 세마포어 값이 변할 때까지 CPU를 계속 사용한다. 원자적 연산을 가정하며, 실제 구현에는 하드웨어 지원이 필요하다. CPU 낭비와 우선순위 역전 가능성이 단점이다.

// 원자적 연산 가정 (실제로는 하드웨어 지원 필요)
void P_busy(Semaphore *S) {
    while (S->value <= 0);  // Busy waiting
    S->value--;
}

void V_busy(Semaphore *S) {
    S->value++;
}

Blocking 구현은 대기 프로세스를 큐에 넣고 문맥 교환을 발생시킨다. CPU를 효율적으로 사용할 수 있고 대기 시간을 예측할 수 있지만, 커널 작업과 대기 큐 관리가 필요하다.

void P_blocking(Semaphore *S) {
    disable_interrupts();

    S->value--;
    if (S->value < 0) {
        enqueue(S->waiting_list, current_process);
        block(current_process);  // 문맥 교환 발생
    }

    enable_interrupts();
}

void V_blocking(Semaphore *S) {
    disable_interrupts();

    S->value++;
    if (S->value <= 0) {
        Process *P = dequeue(S->waiting_list);
        wakeup(P);
    }

    enable_interrupts();
}

Test-and-Set 같은 하드웨어 원자 연산은 세마포어 상태를 갱신하는 구간을 보호하는 데 사용할 수 있다.

// Test-and-Set을 이용한 구현
bool lock = false;

void P_hardware(Semaphore *S) {
    while (test_and_set(&lock));  // Acquire spinlock

    S->value--;
    if (S->value < 0) {
        // 대기 큐 추가 및 블록
    }

    lock = false;  // Release spinlock
}

획득 순서가 무너지면 생기는 문제

서로 다른 순서로 세마포어를 획득하면 교착상태가 발생할 수 있다. P1이 S1을 보유한 상태에서 S2를 기다리고, P2가 S2를 보유한 상태에서 S1을 기다리는 경우가 대표적이다.

Semaphore S1, S2;
init_semaphore(&S1, 1);
init_semaphore(&S2, 1);

// Process P1
void process1() {
    P(&S1);
    P(&S2);  // Deadlock if P2 holds S2
    // Critical Section
    V(&S2);
    V(&S1);
}

// Process P2
void process2() {
    P(&S2);
    P(&S1);  // Deadlock if P1 holds S1
    // Critical Section
    V(&S1);
    V(&S2);
}

모든 프로세스가 S1 → S2 순서로 자원을 획득하도록 정하면 이 문제를 피할 수 있다. Timeout 설정과 Deadlock 탐지 및 복구도 대응 방법이다.

P와 V의 호출 순서 또는 호출 횟수가 어긋나도 보호 범위가 무너진다.

// 잘못된 코드
V(&mutex);  // Critical Section 보호 안됨
critical_section();
P(&mutex);

// V 누락 - Deadlock
P(&mutex);
critical_section();
// V(&mutex) 누락!

// 상호배제 위반
P(&mutex);
critical_section();
V(&mutex);
V(&mutex);  // 잘못된 중복 호출

운영체제가 제공하는 세마포어 인터페이스

POSIX 환경에서는 sem_init()으로 세마포어를 초기화하고, sem_wait()와 sem_post()를 각각 P, V 연산으로 사용한다.

#include <semaphore.h>

sem_t sem;

// 초기화
sem_init(&sem, 0, 1);  // pshared=0 (쓰레드 간), value=1

// P 연산
sem_wait(&sem);

// Critical Section
shared_data++;

// V 연산
sem_post(&sem);

// 제거
sem_destroy(&sem);

sem_trywait()는 비블로킹 P 연산을, sem_timedwait()는 타임아웃 설정을 제공한다. Named semaphore는 sem_open()을 통해 프로세스 간에 공유할 수 있다.

System V 세마포어는 세마포어 배열과 프로세스 종료 시 자동 복구하는 Undo 기능을 지원하며, 프로세스 간 공유에 사용한다.

#include <sys/sem.h>

int semid = semget(IPC_PRIVATE, 1, 0666 | IPC_CREAT);

// P 연산
struct sembuf p_op = {0, -1, 0};
semop(semid, &p_op, 1);

// V 연산
struct sembuf v_op = {0, 1, 0};
semop(semid, &v_op, 1);

// 제거
semctl(semid, 0, IPC_RMID);

Windows에서는 CreateSemaphore()로 핸들을 만들고 WaitForSingleObject()와 ReleaseSemaphore()로 접근을 제어한다.

#include <windows.h>

HANDLE hSemaphore = CreateSemaphore(
    NULL,   // 보안 속성
    1,      // 초기값
    1,      // 최대값
    NULL    // 이름
);

// P 연산
WaitForSingleObject(hSemaphore, INFINITE);

// Critical Section
shared_data++;

// V 연산
ReleaseSemaphore(hSemaphore, 1, NULL);

CloseHandle(hSemaphore);

비용을 고려해 대기 방식을 고른다

세마포어의 비용에는 커널 모드 전환에 따른 시스템 콜 비용, 블로킹 시의 컨텍스트 스위칭, 프로세스 전환으로 인한 캐시 무효화, 대기 큐 관리 오버헤드가 포함된다.

임계 영역이 짧으면 Spinlock 사용을 고려할 수 있다. 큰 타임 슬라이스로 문맥 교환 빈도를 줄이고, Futex(Fast Userspace Mutex)로 커널 개입을 최소화하는 방법도 있다. Readers-Writers 패턴에서는 읽기 우선 전략을 선택할 수 있다.