Pintos Prerequisite: Mutex와 Semaphore, Condition Variable

Credit: https://x.com/RaulJuncoV/status/1847621858763370802

Mutex와 Semaphore, Condition Variable는 동기화/동시성 제어에서 아주 중요한 개념입니다. Mutex와 Semaphore가 마치 교통 체증을 관리하는 경찰관이나 신호등과 같다면, Condition Variable은 신호가 바뀌길 기다리는 차량들의 정지선 같은 존재입니다. Condition Variable은 어떤 조건이 만족될 때까지 스레드가 기다리게 해주는 동기화 도구이기에, 이를 교통 신호에 비유하면, 차들이 신호가 초록불로 바뀌기 전까지 정지선에서 기다리는 상황이랑 비슷하거든요.

---

Mutex (Mutual Exclusion)

Mutex는 한국어로 "상호 배타(배제)"로 번역됩니다. 그 이름 그대로 공유 자원에 대해 오직 하나의 스레드만 접근하도록 허용하는 메커니즘입니다. 마치 화장실 문에 있는 잠금장치와 같습니다.

나락도 lock입니다. Credit: https://blog.naver.com/soj24/223067129317

• 잠금(Lock)과 해제(Unlock): Mutex는 딱 두 가지 상태를 가집니다. '잠금 상태'와 '해제 상태'. 어떤 스레드가 공유 자원에 접근하기 전에 Mutex를 잠그려고 시도합니다. 만약 Mutex가 잠겨 있지 않다면, 그 스레드는 Mutex를 잠그고 공유 자원에 접근할 수 있게 됩니다. 작업을 마치면, 그 스레드는 반드시 Mutex를 해제해야 합니다.
• 소유권(Ownership): 중요한 점은 Mutex를 잠근 스레드만이 그 Mutex를 해제할 수 있다는 것입니다. 다른 스레드는 잠긴 Mutex를 강제로 풀 수 없어요. 마치 화장실 키를 가진 사람만 문을 열 수 있는 것과 같죠.
• 주 사용처: 하나의 스레드만 접근해야 하는 임계 영역(critical section)을 보호하는 데 주로 사용됩니다. 예를 들어, 공유 변수를 업데이트하는 코드 블록이나 파일에 데이터를 쓰는 작업 등이 있습니다.

---

Semaphore

Semaphore는 Mutex보다 좀 더 일반화된 개념입니다 (Semaphore는 Mutex가 될 수 있지만 Mutex는 Semaphore가 될 수 없습니다). 공유 자원에 접근할 수 있는 스레드의 수를 제한하는 데 사용됩니다. 마치 주차장의 빈자리를 세는 전광판과 같은 것입니다.

Credit: https://www.signal-tech.com/products/parking/space_available_and_end_of_aisle

• 카운터(Counter): Semaphore는 카운터를 가지며, 여기에는 0 이상의 정수가 들어갑니다. 현재 접근 가능한 자원의 수를 나타냅니다.
• wait (P 연산)과 signal (V 연산)
  • wait (P 연산): 스레드가 공유 자원에 접근하려고 할 때, Semaphore의 카운터를 1 감소시킵니다. 만약 카운터가 0보다 크면 즉시 자원에 접근할 수 있습니다. 만약 카운터가 0 이하가 되면, 그 스레드는 자원이 available해질 때까지 대기 상태에 들어갑니다. 마치 주차장에 자리가 없으면 기다리는 것과 같습니다.
  • signal (V 연산): 스레드가 공유 자원 사용을 마치면, Semaphore의 카운터를 1 증가시킵니다. 대기 중인 스레드가 있다면, 그 중 하나가 깨어나 자원에 접근할 수 있게 됩니다. 마치 차가 주차장에서 나가면 다른 차가 들어올 수 있게 되는 것과 같습니다.
• 종류
  • Binary Semaphore: 카운터가 0 / 1만 가질 수 있는 Semaphore입니다. 사실상 Mutex와 유사하게 동작합니다. 아래 더 자세하게 서술됩니다.
  • Counting Semaphore: 카운터가 0 이상의 정수 값을 가질 수 있는 Semaphore입니다. 특정 개수의 자원에 대한 접근을 제어하는 데 유용합니다. 예를 들어, 동시에 접속 가능한 데이터베이스 연결 수를 제한하는 데 사용할 수 있습니다.

	Mutex	Semaphore
목적	상호 배제 (하나의 스레드만 접근)	자원 접근 가능한 스레드 수 제한
상태	잠김(Locked) / 해제(Unlocked)	0 이상의 정수 값 (카운터)
소유권	잠근 스레드만 해제 가능	소유권 개념 없음
사용 사례	임계 영역 보호, 단일 자원 접근 제어	제한된 개수의 자원 접근 제어, 스레드 동기화

---

Condition Variable

Credit: https://velog.io/@takealittletime/

Pintos에서는 Condition Variable (이하 컨디션 변수)를 다룹니다. 컨디션 변수란, 스레드들이 특정 조건이 만족될 때까지 기다리거나, 조건이 만족되었음을 알리는 데 사용되는 동기화 도구입니다. 마치 식당에서 음식이 나오기를 기다리는 손님과 음식이 완성되면 손님을 호출하는 직원과 같다고 생각하시면 됩니다.

컨디션 변수 자체는 특정 조건과 연결되어 있습니다. 스레드는 이 조건이 참이 되기를 기다릴 수 있고, 다른 스레드는 이 조건을 참으로 만든 후 기다리는 스레드들에게 알림을 보낼 수 있습니다.

컨디션 변수는 일반적으로 mutex와 함께 사용된다는 점이 중요합니다. Mutex는 공유 변수를 보호하는 역할을 하고, 컨디션 변수은 그 공유 변수의 상태(특정 조건)에 따라 스레드들을 대기시키거나 깨우는 역할을 합니다. 

컨디션 변수가 제공하는 주요 연산은 다음과 같습니다.

• wait(condition, mutex): 이 함수를 호출한 스레드는 mutex를 해제하고, condition이 만족될 때까지 잠시 잠듭니다 (대기 큐에 들어갑니다). 나중에 다른 스레드가 이 조건을 만족시키고 signal 또는 broadcast를 호출하면, 이 스레드는 깨어나 다시 mutex를 획득하려고 시도합니다. wait 함수는 반드시 mutex가 잠긴 상태에서 호출되어야 하며, 깨어난 후에는 다시 mutex를 획득해야 합니다.
• signal(condition): 이 함수를 호출하면, condition을 기다리고 있는 하나의 스레드를 깨웁니다. 어떤 스레드가 깨어날지는 스케줄러에 따라 다릅니다. 깨어난 스레드는 다시 mutex를 획득하려고 경쟁합니다.
• broadcast(condition): 이 함수를 호출하면, condition을 기다리고 있는 모든 스레드를 깨웁니다. 깨어난 모든 스레드는 다시 mutex를 획득하려고 경쟁합니다.

참고로, Pintos의 우선순위 컨디션 변수 관련 테스트(priority-condvar)에서는 semaphore를 확인하는데, 이쪽은 mutex를 안 씁니다. 대신 자체적인 struct lock + struct condition 구현체를 조합한 struct semaphore를 사용합니다.

코드 예시

설명만으로는 잘 안 와닿지요? 아래는 전형적인 생산자-소비자 패턴 예시로. 생산자가 데이터를 만들어두면 소비자가 그걸 가져가는 구조이며, 소비자는 컨디션 변수로 신호가 올 때까지 기다렸다가 데이터가 준비되면 깨어납니다.

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

int buffer = 0;  // 공유 자원
int data_ready = 0;

/* POSIX 스레드 동기화 툴 */
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

void* producer(void* arg) {
    sleep(1);  // 생산이 늦게 일어나는 상황을 시뮬레이션
    pthread_mutex_lock(&mutex);

    buffer = 42;  // 데이터 생성
    data_ready = 1;
    printf("Producer: 데이터 생성 완료!\n");

    pthread_cond_signal(&cond);  // 얘가 컨디션 변수. 소비자에게 신호를 보냄.
    pthread_mutex_unlock(&mutex);
    return NULL;
}

void* consumer(void* arg) {
    pthread_mutex_lock(&mutex);
    while (data_ready == 0) {
        printf("Consumer: 데이터 생성을 기다리는 중...\n");
        pthread_cond_wait(&cond, &mutex);  // 조건이 만족될 때까지 기다림
    }

    printf("Consumer: 데이터 획득! %d\n", buffer);
    pthread_mutex_unlock(&mutex);
    return NULL;
}

void main() {
    pthread_t t1, t2;

    pthread_create(&t1, NULL, consumer, NULL);
    pthread_create(&t2, NULL, producer, NULL);

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

    pthread_mutex_destroy(&mutex);
    pthread_cond_destroy(&cond);
}

여기서 pthread_cond_t cond;가 바로 컨디션 변수입니다. pthread_cond_wait()와 pthread_cond_signal()에서 쓰이고, 스레드 간에 "조건이 만족됐다"는 신호를 주고받는 메커니즘입니다. 한편 int data_ready;는 스레드가 언제까지 기다려야 하는지를 저장하는 flag로 볼 수 있습니다. 

컨디션 변수 자체는 "신호를 주고받는 수단"이지, 조건의 참/거짓을 저장하진 않습니다. 그래서 실제 조건(데이터가 준비됐는지)을 나타낼 flag가 같이 따라오는 것입니다.

---

왜 Mutex와 함께 사용될까요?

컨디션 변수는 공유 변수의 상태(조건)를 기반으로 동작합니다. 이 공유 변수를 여러 스레드가 동시에 접근하면 데이터 불일치 문제가 발생할 수 있습니다. 따라서 컨디션 변수을 사용하기 전에 반드시 Mutex를 획득하여 공유 변수를 보호해야 합니다.

1. 스레드가 특정 조건을 확인하기 전에 Mutex를 잠급니다.
2. 조건이 만족되지 않으면, 스레드는 컨디션 변수의 wait 함수를 호출하면서 Mutex를 해제하고 잠듭니다.
3. 다른 스레드가 조건을 만족시키는 작업을 수행한 후, 컨디션 변수의 signal 또는 broadcast 함수를 호출하여 대기 중인 스레드를 깨웁니다. 이때, 깨어난 스레드는 다시 Mutex를 획득하려고 시도합니다.
4. Mutex를 획득한 스레드는 다시 조건을 확인하고, 만족되면 작업을 진행합니다.

---

Binary Semaphore (이진 세마포어)

이진 세마포어는 세마포어의 특별한 형태로, 카운터가 0 / 1만 되는 세마포어입니다. 이진 세마포어는 Mutex와 매우 유사하게 동작하며, 상호 배제를 구현하는 데 사용될 수 있습니다.

• 초기 값은 보통 1로 설정됩니다.
• wait 연산을 호출하면 카운터가 0이 되고, 다른 스레드는 wait 연산을 통해 접근 불가능하게 됩니다 (잠금 상태와 유사).
• signal 연산을 호출하면 카운터가 1이 되어, 다른 스레드가 다시 wait 연산을 통해 접근 불가능하게 됩니다 (해제 상태와 유사).

---

Mutex vs. Binary Semaphore

둘이 유사하게 동작하지만 세부적으로는 아래와 같이 차이가 있습니다.

	뮤텍스	이진 세마포어
기반 메커니즘	잠금 메커니즘	신호 전달 메커니즘
락 해제	뮤텍스를 획득한 스레드는 임계 구역을 벗어날 때만 뮤텍스를 해제할 수 있습니다.	현재 스레드보다 우선순위가 높은 스레드도 바이너리 세마포어를 해제하고 잠금을 획득할 수 있습니다.
값	뮤텍스 값은 잠금 또는 잠금 해제와 마찬가지로 수정될 수 있습니다.	세마포어 값은 wait() 및 signal() 작업에 따라 변경됩니다.
동시 획득	한 번에 하나의 스레드만 뮤텍스를 획득할 수 있습니다.	여러 개의 스레드가 동시에 이진 세마포어를 획득할 수 있습니다.
소유권	뮤텍스에는 소유권이 있어, 소유자만이 잠금을 해제할 수 있기 때문입니다.	이진 세마포어에는 소유권이 없습니다.
오버헤드	이진 세마포어보다 느린 이유는 잠금을 획득한 스레드만 잠금을 해제해야 하기 때문입니다.	다른 스레드/프로세스가 바이너리 세마포어를 잠금 해제할 수 있기 때문에 뮤텍스보다 빠릅니다.
인스턴스 수	리소스에 대한 단일 인스턴스 접근에는 뮤텍스를 사용하는 것이 더 좋습니다.	리소스에 대한 인스턴스 수가 많은 경우 이진 세마포어를 사용하는 것이 더 좋습니다.
활용 사례	데이터의 일관성을 유지	더 일반적인 동기화 및 스레드간 통신

출처: https://www.geeksforgeeks.org/difference-between-binary-semaphore-and-mutex/

결국 둘은 메커니즘, 사용법, 소유권, 동작 방식이 다 다르다는 것을 알 수 있습니다.

---

추가: 컨디션 변수를 얘기할 때 이진 세마포어가 같이 등장하는 이유

블로그를 찾아보다 보면 컨디션 변수를 설명하면서 이진 세마포어를 같이 이야기하는 경우가 많습니다. 컨디션 변수는 로우레벨 동기화 메커니즘이기에, 때로는 이진 세마포어를 이용하여 컨디션 변수의 기본적인 동작 방식을 설명하거나, 컨디션 변수를 직접 구현하는 방식을 설명하는 데 쓰입니다. 예를 들어, wait 연산은 내부적으로 스레드를 블록시키고, signal 연산은 블록된 스레드를 깨우는 방식으로 구현될 수 있는데, 이때 이진 세마포어가 이러한 메커니즘을 제어하는 데 활용될 수 있습니다.

잊지 말아야 할 것은 컨디션 변수와 이진 세마포어는 결국 다른 목적을 가진 도구라는 점입니다. 이진 세마포어는 주로 상호 배제를 구현하는 데 사용되는 반면, 컨디션 변수는 특정 조건에 따른 스레드간 효율적인 대기 및 알림 메커니즘을 제공합니다.