About

저자: 앨런 B. 다우니 (Allen B. Downey)
버전 2.2.1
The Little Book of Semaphores 다운로드 링크

• 책에서 필요한 부분을 정리. 추가 코드는 GPT에게 예제를 요청했다.
• 소개: 동기화 개념과 고전적 문제(생산자-소비자, 독자-작가 등)를 퍼즐 형식으로 풀어내는 실습 중심 교재다.(실제 저자가 대학에서 운영체제 수업자료로 활용함)
  Python 기반의 의사코드와 실제 실행 가능한 예제, 다양한 패턴을 통해 세마포어 활용법을 익히도록 구성된 무료 오픈 라이선스 책.

2장: 세마포어

세마포어는 유명한 괴짜 컴퓨터 과학자(!)인 Edsger Dijkstra가 발명했다. WOW

2.1 정의 (Definition)

일반적인 정수와 비슷하지만, 정수와 다음과 같은 차이점이 있다.
1) 세마포어를 생성할 때는 어떤 정수든 초기값으로 설정할 수 있지만, 이후에는 증가, 감소만 가능하다.

• 현재 값이 몇인지 읽어오는 연산은 없다.
• sem_wait()= 값 감소/sem_post()= 값 증가 연산만 허용
• 안전한 추상화를 위함(값은 내부적으로 관리, 접근은 wait, post로 하게)

2) 어떤 스레드가 세마포어를 감소시키고 그 결과가 음수가 되면, 그 스레드는 (스스로) 차단(block)이 되며 다른 스레드가 세마포어를 증가시킬 때까지 실행을 멈춘다.
3) 스레드가 세마포어를 증가시킬 때, 대기 중인 스레드가 있다면 그 중 하나가 unlock되어 실행을 재개한다.

참고) block = 운영체제의 스케줄러에게 해당 스레드는 현재 실행 불가능하다고 알리는 것이다. 차단된 스레드는 특정 조건을 만족해 해제되기 전까지 실행되지 않는다.

4) 세마포어의 값

• 양수: 그 수만큼의 스레드가 wait()를 해도 차단되지 않고 실행할 수 있음
• 0: 누군가 wait()하면 차단됨
• 음수: 현재 차단된 스레드 수를 나타냄(단, 확인 불가)

2.3 왜 세마포어인가?(why semaphores?)

세마포어의 장점

• 의도적인 제약 조건을 부여함으로써, 프로그래머의 실수를 줄인다.(제약이 많은 만큼 안전)

  • P(wait/down): 자원을 얻기 위해 시도, 값 감소. 값이 음수가 되면 대기
  • V(signal/up): 자원을 돌려주거나 다른 스레드 깨우기, 값 증가

• 구조가 깔끔하다

• 대부분의 시스템에서 효율적으로 구현 가능하며, 이식성과 성능이 좋다.

3장: 기본 동기화 패턴

3.4 상호 배제(Mutex)

puzzle

두 스레드가 동일한 변수 x에 접근한다고 가정해보겠습니다.
스레드 A는 x = x + 1,
스레드 B는 x = x + 2를 실행합니다.
이 코드는 어떤 결과를 초래할까요?
그리고 어떻게 해야 이 문제를 해결할 수 있을까요?

about

• 동시 업데이트(concurrent update)의 또 다른 예시

A가 먼저 실행: x = 1 + 1 = 2, 그 후 B가 실행: x = 2 + 2 = 4
B가 먼저 실행: x = 1 + 2 = 3, 그 후 A가 실행: x = 3 + 1 = 4

어떤 경우든  x = 4

• 두 스레드가 동시에 실행된 경우 x = 2, 3, 4 모두 될 수 있다.

코드로 보기

1) 문제 상황(경쟁 조건 발생)

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

int x = 0; // 공유 변수

void* threadA(void* arg) 
{
    // 스레드 A: x = x + 1
    int tmp = x;      // x 읽기
    usleep(10);
    tmp = tmp + 1;    // 연산
    x = tmp;          // 쓰기
    return NULL;
}

void* threadB(void* arg) 
{
    // 스레드 B: x = x + 2
    int tmp = x;      // x 읽기
    usleep(10);
    tmp = tmp + 2;    // 연산
    x = tmp;          // 쓰기
    return NULL;
}

int main() 
{
    pthread_t t1, t2;

    x = 1; // 초기값
    pthread_create(&t1, NULL, threadA, NULL);
    pthread_create(&t2, NULL, threadB, NULL);

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

    printf("최종 결과: x = %d\n", x);
    return 0;
}

• 이 코드의 정말 신기한 점:
  usleep(10)을 걸기 전까지는 x = 4로 나왔는데, 저렇게 바꾼 순간부터 x = 2, 3, 4로 바뀌었다.

• 의미

  • 알맞은 결과가 나와도 코드가 안전한 상태가 아니다. 경쟁 조건은 "가능성"이지 반드시 즉시 드러나는 게 아니다.
  • 단순한 테스트 몇 번 만으로는 버그가 드러나지 않고, 부하가 걸리거나 타이밍이 달라지는 상황에 갑자기 터질 수도 있다.

• usleep으로 인해 달라진게 무엇일까?

  • 임계 구역 안에서 오래 머물게 한 것이다.(일부러 지연)
  • usleep으로 스레드 a 다음으로 스레드 b가 실행되서 x의 값을 변경한 것이다.
  • 아주 짧지만 문맥 전환이 될 기회가 생김
  • usleep은 인위적으로 타이밍을 흔들어 경쟁 조건을 드러내는 실험 장치다.

2) solution

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

int x = 0;        // 공유 변수
sem_t mutex;      // 세마포어 선언

void* threadA(void* arg) 
{
    sem_wait(&mutex);    // 진입 (lock)
    int tmp = x;
    tmp = tmp + 1;
    x = tmp;
    sem_post(&mutex);    // 해제 (unlock)
    return NULL;
}

void* threadB(void* arg) 
{
    sem_wait(&mutex);    // 진입 (lock)
    int tmp = x;
    tmp = tmp + 2;
    x = tmp;
    sem_post(&mutex);    // 해제 (unlock)
    return NULL;
}

int main() 
{
    pthread_t t1, t2;

    x = 1; // 초기값

    // 세마포어 초기화: 초기값 1 → 한 번에 하나의 스레드만 접근 가능
    sem_init(&mutex, 0, 1);

    pthread_create(&t1, NULL, threadA, NULL);
    pthread_create(&t2, NULL, threadB, NULL);

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

    printf("최종 결과: x = %d\n", x);

    // 세마포어 제거
    sem_destroy(&mutex);

    return 0;
}

☕ 문맥 교환(context switching)

1) 문맥: CPU가 현재 실행 중인 작업에 대한 모든 상태

• 레지스터 상태(PC, SP, general-purpose register 값들)
• 메모리 매핑 정보(페이지 테이블, 주소 공간)
• 스케줄링 정보(우선 순위, CPU 점유 시간)
• 스레드/프로세스 별 커널 관리 정보

2) 프로세스 문맥 전환 vs 스레드 문맥 전환

• 프로세스 간 전환

  • 주소 공간이 다름 -> 페이지 테이블 교체 필요
  • 그래서 오버헤드가 크다

• 스레드 간 전환(같은 프로세스)

  • 주소 공간 공유 -> 페이지 테이블 교체 불필요
  • 스레드마다 다른 것: 레지스터 값, 스택 포인터, 프로그램 카운터 등 CPU 실행 상태
  • 오버헤드가 상대적으로 적다

3.5 Multiplex

멀티플렉스: 동시 접근 개수를 제한하는 세마포어 패턴

puzzle

엘리베이터가 한 번에 최대 3명만 탈 수 있다고 가정해봅시다.
엘리베이터를 이용하려는 사람들을 스레드로 표현한다면,
동시에 3명까지만 입장 가능하게끔 코드를 작성해보세요.

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

#define NUM_TREADS 5

sem_t elevator;
void *person(void *arg)
{
    int id = *((int *)arg);
    free(arg);
    printf("사람 %d: 엘리베이터 타기 대기 중...\n", id);
    sem_wait(&elevator); // 엘리베이터 타기
    printf("사람 %d: 엘리베이터 탑승!\n", id);
    sleep(1); // 엘리베이터 타고 이동 중
    printf("사람 %d: 엘리베이터에서 내림!(나는 정상적으로 내려요)\n", id);
    sem_post(&elevator);
    return NULL;
}

int main()
{
    pthread_t threads[NUM_TREADS];
    sem_init(&elevator, 0, 2); // 엘리베이터 정원 2명
    for (int i = 0; i < NUM_TREADS; i++)
    {
        int *id = malloc(sizeof(int));
        *id = i + 1;
        pthread_create(&threads[i], NULL, person, id);
        usleep(200000);
    }
    for (int i = 0; i < NUM_TREADS; i++)
    {
        pthread_join(threads[i], NULL);
    }
    sem_destroy(&elevator);
    return 0;
}

3.5.1 multiplex solution

1) solution: 동시 접근은 허용하되, 제한된 수만 허용하고자 할 때 사용되는 일반적인 동기화 패턴

• 초기값이 최대 허용 수(n)인 세마포어를 생성한다
• 각 스레드는 접근 전 wait()를 호출하고, 작업 후 signal()를 호출합니다

2) 일반화

• semaphore(n)은 동시에 최대 n개만 허용되는 상황에서 매우 유용하다
• mutex(semaphore(1))은 멀티플렉스의 특수한 형태다 = mutex

3) 주의사항

• multiplex를 사용하는 경우에도 공유 자원에 대한 정확한 wait/signal() 쌍을 보장해야 한다. wait()를 호출하고 signal()을 하지 않으면 자원이 영구 잠금 상태에 빠질 수 있다.
  (= 자원이 사실상 반납되지 않아서 시스템 입장에서는 자원이 부족하다고 착각하게 됨. deadlock, 자원 영구 잠금 상태라고도 부름)

3.8 큐 (Queue)

지금까지 살펴본 동기화 패턴은 대부분 비공정한 방식이다. 예를 들어, 세마포어를 사용할 경우, 어떤 스레드가 wait()에 도달하면 언제 실행 재개될지는 보장되지 않는다. 결국, 어떤 스레드는 계속 기다리게 되는 문제가 발생할 수 있다.(이를 기아 starvation이라고 한다.)

이런 문제를 방지하기 위해, 스레드가 도착한 순서대로 처리하는 큐(queue)를 만들 수 있다.

puzzle4

여러 스레드가 어떤 자원(resource)에 접근하려고 대기할 때
도착한 순서대로 접근할 수 있도록 하려면 어떻게 해야 할까요?

3.8.1 해법 1 (N개의 세마포어와 공유 큐(명시적 큐))

• 대기 과정
  • 각 스레드는 enqueue()를 통해서 자신의 세마포어를 큐에 넣는다.
  • 첫 번째 스레드는 바로 실행 시작, 나머지 스레드는 my_turn.wait()에서 자신의 차례가 올 때까지 대기
• 자원 사용 후
  • 스레드가 자원을 사용하고 나면 자신을 큐에서 제거함
  • 큐가 비어 있지 않다면 바로 뒤 대기 중인 세마포어(queue[front])를 조회하여 signal()을 보낸다. 다음 스레드가 깨어나 실행을 시작한다
• 보장 특성
  • FIFO 순서 보장, 스레드들이 도착한 순서대로 자원 접근
  • 그래서 모든 스레드가 공평하게 기회를 얻게 됨

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

#define NUM_THREADS 5
#define MAX_QUEUE 100

sem_t *queue[MAX_QUEUE];
int front = 0; 
int rear = 0;

sem_t mutex;

void enqueue(sem_t *sem)
{
    queue[rear] = sem;
    rear = (rear + 1) % MAX_QUEUE;
}

sem_t *dequeue()
{
    if (front == rear)
        return NULL;
    sem_t *sem = queue[front];
    front = (front + 1 ) % MAX_QUEUE;
    return sem;
}

void use_resource(int id)
{
    printf("스레드 %d: 자원 사용 시작\n", id);
    // sleep(1);
    // 0~0.5초 랜덤 대기
    usleep((rand() % 500000));
    printf("스레드 %d: 자원 사용 종료\n", id);
}

void *thread_func(void *arg)
{
    int id = *((int *)arg);
    free(arg);

    sem_t my_turn;
    sem_init(&my_turn, 0, 0);

    // 큐에 등록
    sem_wait(&mutex);
    int is_first = (front == rear); // 내가 첫번째?
    enqueue(&my_turn);
    sem_post(&mutex);

    // 첫 번째가 아니라면 차례를 기다림
    if (!is_first)
        sem_wait(&my_turn);
    // 자원 사용
    use_resource(id);
    // 다음 스레드에게 신호
    sem_wait(&mutex);
    sem_t *next = NULL;
    dequeue(); // 나 제거
    if (front != rear)
        next = queue[front]; // 여기가 중요, 큐가 비어있지 않다면 그냥 조회
    if (next)
        sem_post(next);
    // else
    // {
    //     front = rear = 0; // 큐 비우기
    // }
    sem_post(&mutex);
    sem_destroy(&my_turn);
    return NULL;
}

int main()
{
    pthread_t threads[NUM_THREADS];
    sem_init(&mutex, 0, 1);

    for (int i = 0; i < NUM_THREADS; i++)
    {
        int *id = malloc(sizeof(int));
        *id = i + 1;
        pthread_create(&threads[i], NULL, thread_func, id);
        usleep(100000); // 0.1초 간격으로 생성
    }

    for (int i = 0; i < NUM_THREADS; i++)
        pthread_join(threads[i], NULL);
    sem_destroy(&mutex);
    return 0;
}

3.8.1 해법 2 (표 뽑기 시스템으로 구현하기(조건변수+뮤텍스))

• 각 스레드는 queue에 자기 표를 등록하고 조건 변수에서 기다린다
• 자원이 비면 가장 먼저 들어온 표를 가진 스레드가 조건 변수 신호를 받고 자원에 접근한다.
• 표 번호가 큐 역할을 대신하는 것이다.

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

#define THREADS 5

typedef struct s_ticket_lock
{
	pthread_mutex_t	lock;
	pthread_cond_t	cond;
	int				next_ticket;
	int				now_serving;
}	t_ticket_lock;

void	ticket_lock(t_ticket_lock *tl, int *my_ticket)
{
	pthread_mutex_lock(&tl->lock);
	*my_ticket = tl->next_ticket++;
	while (tl->now_serving != *my_ticket)
		pthread_cond_wait(&tl->cond, &tl->lock);
	pthread_mutex_unlock(&tl->lock);
}

void	ticket_unlock(t_ticket_lock *tl)
{
	pthread_mutex_lock(&tl->lock);
	tl->now_serving++;
	pthread_cond_broadcast(&tl->cond);
	pthread_mutex_unlock(&tl->lock);
}

void	*worker(void *arg)
{
	t_ticket_lock	*tl;
	int				my_ticket;

	tl = (t_ticket_lock *)arg;
	ticket_lock(tl, &my_ticket);
	printf("Thread got resource (ticket %d)\n", my_ticket);
	usleep(100000); // 자원 사용 (0.1초)
	ticket_unlock(tl);
	return (NULL);
}

int	main(void)
{
	pthread_t		t[THREADS];
	t_ticket_lock	tl;
	int				i;

	pthread_mutex_init(&tl.lock, NULL);
	pthread_cond_init(&tl.cond, NULL);
	tl.next_ticket = 0;
	tl.now_serving = 0;
	for (i = 0; i < THREADS; i++)
		pthread_create(&t[i], NULL, worker, &tl);
	for (i = 0; i < THREADS; i++)
		pthread_join(t[i], NULL);
	pthread_mutex_destroy(&tl.lock);
	pthread_cond_destroy(&tl.cond);
	return (0);
}

• 티켓락
  스핀락의 한 종류로 각 스레드에 표(ticket)을 발급하고 now_serving과 비교하여 자신의 차례가 될 때까지 busy wait(스핀)으로 기다리는 방식이다. 일반 스핀락과는 달리 FIFO순서를 보장하여(fairness) 기아(starvation)을 방지한다. 구현할 때 next_ticket과 now_serving은 원자적 연산으로 다뤄야 하며, 잘못된 구현에서는 data race 위험이 있다. cpu를 계속 소모하는 busy wait방식이기 때문에 사용자 레벨보다는 커널이나 저수준 환경에서 주로 쓰인다.

최종) GPT야 두 개를 비교해 줘... 집에 가고 싶다...

과제 중 만난 엄청 좋은 책

https://pages.cs.wisc.edu/~remzi/OSTEP/Korean/

• 한국어 번역본이 무료다!!
• 이 책에서도 [The Little Book of Semaphores]를 다음과 같이 안내한다.
  - 세마포어에 대한 좋은 (그리고 공ḽ!) 책이다. 이런 류를 좋아한다면 재미있는 문제들이 많이 있다.
• 어려운 내용임에도 책에 위트가 곳곳에 있어서 술술 읽힌다. 왜 이제야 알았을까!

번외. 파이썬 전역 인터프리터 락(GIL)

• 알고 보니 곳곳에 숨어 있는 것이 신기하다.
• 파이썬 알고리즘 인터뷰에서