세마포어(Semaphore) & 뮤텍스(Mutex)

공유 자원에 여러 실행 흐름이 동시에 접근하면 데이터가 깨질 수 있다. 이를 막기 위해 임계 구역을 보호하는 동기화 도구가 필요하다.

임계 구역(Critical Section)

여러 실행 흐름이 공유 데이터를 접근하는 코드 구간

이 구간에서는 상호 배제(mutual exclusion)가 필요할 수 있다.

세마포어(Semaphore)

세마포어는 사용 가능한 자원 개수를 나타내는 동기화 도구다.

• 이진 세마포어(binary semaphore): 값이 0 또는 1인 경우가 많다.
• 카운팅 세마포어(counting semaphore): 여러 개의 동일 자원을 관리할 수 있다.

전통적으로 연산 이름은 다음과 같다.

• P, wait, down: 자원을 얻으려 시도
• V, signal, up: 자원을 반납하고 대기자를 깨움

중요한 점은 이 연산이 원자적(atomic) 이어야 한다는 것이다. 단순한 while (S == 0) 식 코드는 경쟁 상태가 생길 수 있어서 실제 블로킹 세마포어 구현으로는 부정확하다.

개념적으로는 다음처럼 생각하면 된다.

wait(S):
    원자적으로 S를 감소시키고
    사용할 수 있는 자원이 없으면 현재 실행 흐름을 block

signal(S):
    원자적으로 S를 증가시키고
    대기 중인 실행 흐름이 있으면 하나를 깨움

즉, 세마포어는 "한 번에 하나만 들어가라"는 용도뿐 아니라 "동시에 최대 N개까지 들어가라"는 식의 자원 개수 제한에도 적합하다.

뮤텍스(Mutex)

뮤텍스는 상호 배제용 락이다.

• lock: 임계 구역 진입 시도
• unlock: 임계 구역 사용 종료

핵심 특징은 소유권(ownership) 이다.

• lock을 획득한 실행 흐름만 unlock할 수 있다.
• 목적은 "딱 한 명만 임계 구역에 들어가게 하는 것"이다.

스핀락(Spinlock)

스핀락은 임계 구역에 진입할 수 없을 때, 스레드가 잠들지 않고(context switch 없이) 락을 획득할 때까지 무한 루프를 돌며 대기하는 동기화 기법이다.

• Busy Waiting: 락이 반환될 때까지 CPU를 계속 점유하면서 상태를 확인한다.
• 장점: 락을 기다리는 시간이 매우 짧은 경우, 스레드를 블로킹(Blocking)하고 깨우는 문맥 교환(Context Switching) 오버헤드를 피할 수 있어 뮤텍스보다 성능이 우수하다.
• 단점: 락 대기 시간이 길어지면 CPU 자원을 낭비하게 된다. (특히 단일 코어 환경에서는 의미가 없다)

언제 사용하는가?

• 임계 구역의 실행 시간이 매우 짧을 때
• 운영체제 커널 수준의 인터럽트 처리 루틴(Interrupt Handler)처럼 문맥 교환이 불가능하거나 허용되지 않는 곳
• 멀티 코어 환경 (단일 코어에서는 다른 스레드가 락을 해제할 기회를 주어야 하므로 스핀락이 부적합하다)

세마포어와 뮤텍스 차이

• 세마포어는 자원 개수를 표현할 수 있다.
• 뮤텍스는 소유권이 있는 상호 배제 락이다.
• 이진 세마포어와 뮤텍스는 비슷해 보이지만, unlock 주체 제약과 사용 목적이 다르다.

현대 시스템에서의 구현

실제 운영체제와 런타임은 데커/피터슨 알고리즘 같은 순수 소프트웨어 기법보다는 다음을 사용한다.

• CPU의 atomic instruction(CAS, test-and-set, LL/SC 등)
• 커널의 mutex, semaphore, spinlock
• 사용자 공간의 futex 기반 pthread_mutex

또한 락 종류도 상황에 따라 다르다.

• mutex: 잠들 수 있는(sleeping) 락, 비교적 긴 임계 구역에 적합
• spinlock: 짧은 임계 구역과 인터럽트 컨텍스트에 적합
• semaphore: 자원 개수 제한이나 producer-consumer 같은 문제에 적합

고전 알고리즘은 왜 배우나요?

데커(Dekker), 피터슨(Peterson), 제과점(Bakery) 알고리즘은 락이 왜 필요한지, 상호 배제와 진행 조건을 어떻게 만족시키는지 설명하는 데 유용하다.

다만 현대 멀티코어 환경에서는 메모리 모델과 성능 문제 때문에 이런 알고리즘을 실전에서 그대로 구현해 쓰지 않는다. 면접에서는 개념 이해용 역사적 알고리즘이라고 설명하면 정확하다.