[OSTEP 병행성(concurrency)]세마포어(semaphore)

📝서론 

다양한 범주의 병행성 문제 해결을 위해서는 락과 조건 변수가 모두 필요하다.

이번 장에서는 세마포어라는 동기화 기법을 알아보자 

핵심 질문: 세마포어를 어떻게 사용하는가
락과 컨디션 변수 대신에 세마포어를 사용하는 방법은 무엇인가?
세마포어의 정의는 무엇인가?
이진 세마포어는 무엇인가?
락과 컨디션 변수를 사용하여 세마포어를 만드는 것이 가능한가?
그 반대로 세마포어를 사용하여 락과 조건 변수를 만드는 것이 가능한가?

 

📝세마포어 : 정의

세마포어는 정수 값을 갖는 객체로서 두 개의 루틴으로 조작할 수 있다. 

POSIX 표준에서 이 두개의 루틴은 sem_wait()과 sem_post()이다. 세마포어는 초기값에 의해 동작이 결정되기에 사용전에 제일 먼저 값을 초기화해야한다.

 

 #include<semaphore.h>
 sem_ts;
 sem_init(&s, 0, 1);

 

이 코드에서 세마포어 s를 선언 후, 3번째 인자로 1을 전다랗여 세마포어 값을 초기화한다.

sem_init()의 두 번째 인자는 모든 예제에서 0이며 이 값은 같은 프로세스 내의 쓰레드 간에 세마포어를 공유한다는 것이다.

 

초기화된 후에는sem_wait(),또는sem_post()라는 함수를 호출하여 세마포어 를 다룰 수 있다.이 두 함수의 동작은 아래에서 확인이 가능하다.

 

 int sem_wait(sem_t*s){
 	decrement the value of semaphore s by one;
 	wait if value of semaphore s is negative;
 }
 
 int sem_post(sem_t*s){
 	increment the value of semaphore s by one;
 	if there are one or more threads waiting, wake one;
 }

 

 

• sem_init(sem_t *sem, int pshared, unsigned int value);
  • sem : 세마포어 객체
  • pshared = 0 → 같은 프로세스 내의 스레드끼리 공유
  • value : 초기값 (예: 1이면 mutex처럼 작동)
• int sem_wait(sem_t *sem);
  • 세마포어 값을 1 감소
  • 값이 0 이하이면 대기(blocking)
  • 스레드가 깨워질 때까지 잠듦 (스핀락이 아님)
• int sem_post(sem_t *sem);
  • 세마포어 값을 1 증가
  • 대기 중인 스레드가 있다면 하나를 깨움

 

 

항목	설명
원자성	sem_wait()과 sem_post()는 커널 수준에서 원자적으로 실행되며, 경합 상태 없이 실행됩니다.
임계 영역 보호	세마포어는 임계 영역에서 한 번에 하나의 스레드만 접근하도록 보장합니다.
초기값이 1이면	이진 세마포어로써 뮤텍스와 유사한 동작을 합니다.
대기 큐	sem_wait()은 대기 중인 스레드들을 큐에 넣고 재움(sleep) 상태로 전환합니다.

 

📝이진 세마포어(락)

이제 세마포어를 사용해보자 우리는 처음으로 세마포어를 적용할 곳은 "락"이다.

 

 

이진 세마포어는 값이 0 또는 1만 가지는 세마포어이다.
락처럼 임계 영역에 대한 상호 배제를 보장하는 용도이다. 

📌 핵심 동작 원리

• sem_init(&m, 0, 1); ← 초기값을 1로 설정
• sem_wait(&m);
  → 세마포어 값을 1 감소 (1 → 0)
  → 값이 0이면 진행, 음수면 대기
• sem_post(&m);
  → 세마포어 값을 1 증가 (0 → 1)
  → 대기 중인 스레드가 있다면 하나를 깨움

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

sem_t m;  // 이진 세마포어

void* thread_func(void* arg) {
    sem_wait(&m);  // 락 획득
    printf("Thread %ld: critical section start\n", (long)arg);
    sleep(1);  // 임계 영역 작업
    printf("Thread %ld: critical section end\n", (long)arg);
    sem_post(&m);  // 락 해제
    return NULL;
}

int main() {
    pthread_t t1, t2;

    sem_init(&m, 0, 1);  // 초기값 1 → 락 사용 가능

    pthread_create(&t1, NULL, thread_func, (void*)1);
    pthread_create(&t2, NULL, thread_func, (void*)2);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    sem_destroy(&m);
    return 0;
}

 

📝컨디션 변수로서의 세마포어

어떤 조건이 참이 되기를 기다리기 위해 현재 쓰레드를 멈출 때에도 세마포어는 유용하게 사용될 수 있다.

대기중인 쓰레드가 프로그램에서의 어떤 조건이 만족되기를 대기 하며 세마포어를 컨디션 변수처럼 사용이 가능하다.

 

🔧 목적

• 어떤 조건이 만족될 때까지 대기하고, 조건이 충족되면 깨우는 동기화 패턴
• 즉, 세마포어를 컨디션 변수처럼 사용

💡 핵심 구현 방식

• sem_t s를 초기값 0으로 초기화
• 자식 쓰레드는 작업 후 sem_post(&s) 호출 (→ 세마포어 값 증가, 시그널 역할)
• 부모 쓰레드는 sem_wait(&s) 호출 (→ 세마포어 값이 0이면 대기)

📝생산자/소비자 문제

다음 문제는 유한 버퍼 문제이다. 

이 문제를 해결하기 위한 첫 번째 시도는 empty와 full 이라는 두 개의 세마포어를 사용하는 것이다.

즉 쓰레드는 해당 변수들을 사용하여 버퍼 공간이 비었는지 채워졌는지 확인한다. 

sem_t empty;
sem_t full;

void *producer(void *arg) {
	int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&empty);
		put(i);
		sem_post(&full);
	}
}

void *consumer(void *arg) {
	int i, tmp = 0;
	while (tmp != -1) {
		sem_wait(&full);
		tmp = get();
		sem_post(&empty);
		printf("%d\n", tmp);
	}
}

 

하지만 역시 문제가 발생한다. 두 개의 생산자가 있는데 두 쓰레드가 동시에 put()을 호출한다고 해보면 

처음에 실행한 생산자의 버퍼를 두 번째 생산자가 새로운 값으로 대체해버린다.

그렇기에 상호 배제가 필요하다. 

 

sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg) {
	int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&mutex);
		sem_wait(&empty);
		put(i);
		sem_post(&full);
		sem_post(&mutex);
	}
}

void *consumer(void *arg) {
	int i, tmp = 0;
	while (tmp != -1) {
		sem_wait(&mutex);
		sem_wait(&full);
		tmp = get();
		sem_post(&empty);
		sem_post(&mutex);
		printf("%d\n", tmp);
	}
}

 

위의 코드처럼 상호 배제를 넣어서 만들면 된다. 

그런데 아직도 동작하지 않는다. 그 이유는 교착 상태가 발생하기 때문이다. 

1. 생산자, 소비자 쓰레드가 각 하나씩 있다고 가정해보자.
2. 소비자가 먼저 실행되었다.
3. mutex를 획득하고, full 변수에 대해 sem_wait()를 호출한다.
   1. 아직 데이터가 없기 때문에 소비자는 대기하고, CPU를 양보한다.
   2. 여전히 소비자가 락을 획득하고 있는 중이다.
4. 생산자가 실행된다.
5. 먼저 mutex 세마포어에 대해서 sem_wait()를 호출한다.
   1. 이미 락을 소비자가 가지고 있기 때문에 생산자도 대기하게 된다.

 

해법

 

위의 락 문제를 해결하기 위해 락의 범위를 줄여야한다. mutext 락의 범위를 아래 코드와 같이 안쪽으로 줄여버리면 된다. 

이렇게하면 mutex 락이 딱 임계 영역 내에서만 걸리기 때문에 교착 상태를 방지할 수 있다. 

sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg) {
	int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&empty);
		sem_wait(&mutex);
		put(i);
		sem_post(&mutex);
		sem_post(&full);
	}
}

void *consumer(void *arg) {
	int i, tmp = 0;
	while (tmp != -1) {
		sem_wait(&full);
		sem_wait(&mutex);
		tmp = get();
		sem_post(&mutex);
		sem_post(&empty);
		printf("%d\n", tmp);
	}
}

 

 

📝Reader-Writer 락

또 하나의 고전적인 문제가 있다. 좀 더 융통성 있는 락 기법이 필요하다. 다양한 자료 구조를 접근하는 데 여러 종류의 락 기법이 필요하다. 리스트에 삽입하고 간단한 검색을 하는 것과 같은 병행연산이 여러 개 있다고 가정해보자

• 삽입 연산은 리스트의 상태를 변경
• 검색은 자료 구조를 단순히 읽는다.

삽입 연산이 없다고 보장된다면 다수의 검색 작은 동시에 할 수 있다. 

이것을 구현한 것이 Reader-Writer 락이다. 

 

📝식사하는 철학자 문제 

Dijkstra(디익스트라)가 제시한 병행 프로그래밍의 고전적인 문제로, 자원 공유와 교착 상태(deadlock) 문제를 재미있고 직관적으로 설명하기 위해 만들어졌습니다.
실제 활용보다는 교육용, 면접용 문제로 자주 등장합니다.

 

🍴 문제 상황

• 철학자 5명이 원형 식탁에 앉아 있음.
• 철학자 사이에는 총 5개의 포크가 있음 (하나의 포크는 두 철학자 사이에 공유됨).
• 철학자들은 생각(think)과 식사(eat)를 반복함.
• 식사하려면 양쪽 포크 두 개를 모두 들어야 함.

 

즉 이 포크를 잡기 위한 경쟁, 그에 따른 동기화 문제를 다룬다. 

아래는 철학자의 동작을 나타낸 기본 의사 코드이다.

while (1) {
	think();
	getforks();
	eat();
	putforks();
}

 

주요 쟁점은 getforks()와 putfork()를 사용하되 교착 상태의 발생을 방지하며, 기아 상태 또한 발생하면 안되며 병행성이 높아야한다. 

🎯 문제의 핵심

• getforks()와 putforks()의 구현이 핵심
• 다음의 3가지 조건을 만족해야 함:
  1. 교착 상태(Deadlock) 발생 방지
  2. 기아 상태(Starvation) 발생 방지
  3. 높은 병행성 확보 (가능한 많은 철학자가 동시에 식사 가능)

 

✅ 첫 번째 해결책: 포크 위치 계산 함수

 

int left(int p) { return p; } 
int right(int p) { return (p + 1) % 5; }

• 철학자 p가 자신의 왼쪽 포크를 사용하려면 left(p)
• 오른쪽 포크는 right(p)
• % 5를 사용하는 이유는 마지막 철학자(p=4)의 오른쪽 포크가 포크 0이기 때문

 

✅ 두 번째 해결책: 세마포어를 이용한 단순 구현

각 포크마다 1개의 세마포어를 설정합니다:

void getforks() {
	sem_wait(forks[left(p)]);
	sem_wait(forks[right(p)]);
}

void putforks() {
	sem_post(forks[left(p)]);
	sem_post(forks[right(p)]);
}

 

 

• 식사 전: 왼쪽 → 오른쪽 포크 순서로 락 획득
• 식사 후: 왼쪽 → 오른쪽 포크 순서로 락 해제

1. 문제점 ❌
   → 철학자 전원이 왼쪽 포크를 먼저 들면, 서로가 서로의 오른쪽 포크를 기다리며 영원히 대기하게 됨 → 교착 상태 발생

 

✅ 세 번째 해결책: 교착 상태 방지 

위의 코드들이 교착 상태가 발생한다는 것은 인지했을 것이다. 

교착 상태가 발생하는 조건은 4가지이다.

1. 상호 배제(Mutual Exclusion): 자원을 한 번에 하나의 프로세스만 사용
2. 점유와 대기(Hold and Wait): 자원을 점유한 상태에서 다른 자원을 기다림
3. 비선점(No Preemption): 점유한 자원을 강제로 빼앗을 수 없음
4. 환형 대기(Circular Wait): 프로세스들이 서로 자원을 기다리는 사이클 형성

•  

각자 모두 자신의 왼쪽 포크를, 다른 철학자가 오른쪽 포크를 들기 전에 잡기에

모든 철학자가 오른쪽 포크를 기다린다 그렇기에

void getforks() {
	if (p == 4) {
		sem_wait(forks[right(p)]);
		sem_wait(forks[left(p)]);
	} else {
		sem_wait(forks[left(p)]);
		sem_wait(forks[right(p)]);
	}
}

마지막 철학자가 오른쪽 포크를 먼저 잡게한다면 어떨까?

교착 상태 발생의 원칙 중 환형 대기를 깨트리기에 교착 상태가 발생하지 않게 됩니다. 

 

📝요약

✅ 정의

• 정수 값을 갖는 동기화 객체로, 두 함수로 조작:
  • sem_wait(sem_t *s): 값 감소, 0 이하이면 대기
  • sem_post(sem_t *s): 값 증가, 대기 중이면 하나 깨움
• 초기화 함수: sem_init(&s, 0, 초기값)
  (pshared = 0이면 스레드 간 공유)

---

🔑 세마포어 사용 목적

• 병행성 문제 해결
• 락 대체 (이진 세마포어) 또는 조건 변수 대체로 활용

---

🔸 이진 세마포어 (Binary Semaphore)

• 초기값: 1 → 뮤텍스처럼 동작
• sem_wait()으로 잠금, sem_post()로 해제
  (임계 영역 보호에 적합)

---

🔸 컨디션 변수처럼 사용

• 세마포어 초기값 0 → 조건 충족까지 대기
• 예:
  • 부모: sem_wait(&s) 대기
  • 자식: sem_post(&s) 조건 충족 후 신호

---

🍞 생산자/소비자 문제

❌ 초기 시도

• empty, full 세마포어만 사용 → 동시 put/get 시 충돌 가능

✅ 개선

• mutex 이진 세마포어로 상호 배제 추가
• 주의: 락 범위를 잘못 지정하면 교착 상태 발생

💡 최종 해법

sem_wait(&empty);
sem_wait(&mutex); // 임계 영역 진입
put(i);
sem_post(&mutex);
sem_post(&full);

→ 락의 범위를 임계 영역 안으로 한정하여 교착 방지

---

이렇게보면 세마포어는 동기화 변수를 구현한 것이다. 세마포어의 중요한 역할은 동기화 변수를 구현한 구조이면서 원자적 연산과 자원 카운팅 기능이 겹한된 멀티 목적 동기화 도구입니다.