[Lecture 9] 멀티쓰레딩 III - Semaphores / 세마포어

#식사하는 철학자 문제 / Dining philosophers problem

위의 사진처럼, 5명의 철학자가 같이 식사를 하려고 모였다고 가정하자. 식탁에는 맛있는 스파게티가 올라와 있고, 각 스파게티 접시 사이에 포크가 하나 씩 있다. 하지만 이 모임에 있는 철학자들은 단순히 음식을 먹지 못한다. 이 철학자들이 음식을 먹기 위해선 다음과 같은 규칙을 따라야 한다.

1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 만약 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아가 반복한다.

굉장히 단순한 규칙같지만, 다음 규칙에는 치명적인 단점이 존재한다. 만약 모든 철학자들이 생각이 겹쳐 동시에 왼쪽 포크를 집으면 어떻게 될까? 이런 상황이 발생한다면, 모든 철학자들은 자신이 집은 포크 반대쪽을 기다려하지만, 모든 철학자들은 똑같은 상태에 있기 때문에 2번 상태에 영원히 머물러야 한다. 즉, 영원히 끝나지 않는 "교착 상태"에 빠진다.

 

이 문제는 네덜란드의 컴퓨터 과학자 에츠허르 데이크스트라 (Edsger W. Dijkstra)가 고안한 문제로 운영체제의 교착 상태, 즉 "deadlock"을 설명 할때 등장하곤 한다. 컴퓨터에서 프로세스는 자원을 할당 받아 일을 하기 때문에 이 문제에서 포크는 CPU와 메모리 같은 컴퓨터 자원이고, 스파게티는 처리해야 할 작업이다.

 

이 문제를 해결하기 위해선 여러가지 방법이 있다. 만약 한 철학자가 포크를 잡는다면, 반대쪽 포크를 잡을 때까지 행동권을 넘길 수 없게 하는 것이다. 현실 세계에서는 CPU의 인터럽트를 무시하는 방식으로 구현할 수 있다. 하지만 이는 커널 레벨에서만 가능하다.

 

단, 멀티쓰레드 환경이라면 사용자 레벨에서 구현할 수 있는 방식이 있다. 사용자가 Semaphore나 우리가 지난 포스트에서 알아봤던 Mutex lock등을 이용해 Critical Section(공유 자원에 Write를 수행하는 경우 등)에서 자신이 만든 다른 쓰레드가 CPU를 잡지 못하게 만들어 쓰레드간의 교착 상태를 방지할 수 있다. 이것이 오늘 우리가 배울 semaphore / 세마포어의 원리이다. 

 

# 쓰레드 협조 / Coordinating Threads

쓰레드들 사이의 협조는 주로 이벤트의 발생에 따라 여러 쓰레드가 서로 조정해야 할 필요가 있을 때 발생한다. 예를 들어, 쓰레드 A가 쓰레드 B가 필요로 하는 값을 계산했는지 여부와 같은 상황이다. 이러한 조정 작업을 '순서 지정', '우선 순위 설정', 또는 '스케줄링 제약'이라고 부르기도 하며, 이는 'X가 실행된 후에 Y를 실행해야 한다'와 같은 상황을 의미한다. 중요한 점은, 협조하는 쓰레드들이 종종 상태를 공유한다 할지라도, 이 상태에 접근하는 것을 조정하는 것은 별개의 문제이며, 때때로 '상호 배제'가 해결책이 될 수 있다.

쓰레드들 사이의 협조 시 고려해야 할 핵심 포인트는 다음과 같다:

정확성: 쓰레드 B는 쓰레드 A가 값을 계산한 이벤트를 놓쳐서는 안 된다.
효율성: 리소스의 낭비 없이(예: 끊임없이 상태를 체크하는 바쁜 대기를 피하면서), 불필요한 지연 없이 이를 달성해야 한다.
이러한 문제를 해결하는 데에는 '세마포어'가 핵심 도구로 사용된다.

# 세마포어

세마포어는 카운터 S를 내포하고 두 가지 기본 연산, P(S)와 V(S),를 제공하는 추상 데이터 타입(ADT)이다. 세마포어는 다양한 클래식 동기화 문제를 해결하는 데 유용하게 사용된다.

바이너리 세마포어: 이는 뮤텍스 락(mutex lock)과 굉장히 유사한 개념으로, 0과 1, 두 가지 값만을 사용한다. 초기값은 1로 설정되며, 여러 프로세스가 임계 구역(critical section) 문제를 해결하고 '상호 배제(mutual exclusion)'를 보장하는 데 사용된다.

카운팅 세마포어: 이는 오늘 우리가 집중해서 살펴볼 세마포어이다. 카운팅 세마포어는 값의 제한이 없으며, 여러 인스턴스를 가진 리소스에 대한 접근을 조정하는 데 사용된다. P(S) 연산은 'down' 혹은 'wait'로 불리며, 카운터 값이 0보다 클 경우에는 감소시킨다. 그렇지 않다면, 카운터 값이 0보다 커질 때까지 대기한 뒤 감소시킨다. V(S) 연산은 'up', 'signal', 혹은 'post'로 불리며, 카운터 값을 증가시키고 필요한 경우 P(S)에 의해 차단된 모든 스레드를 해제한다. 보통 프로그래머는 초기값 Vi를 선택한다.

# 세마포어 불변성

U와 D가 각각 완료된 'up'과 'down' 연산의 수일 때, 항상 Vi + |U| - |D| ≥ 0의 관계가 성립해야 한다. 이는 세마포어의 기본 원칙 중 하나이다.

#Counting Semaphore 구현

struct Semaphore {
 
    int value;
 
    // q contains all Process Control Blocks(PCBs)
    // corresponding to processes got blocked
    // while performing down operation.
    Queue<process> q;
 
} P(Semaphore s)
{
    s.value = s.value - 1;
    if (s.value < 0) {
 
        // add process to queue
        // here p is a process which is currently executing
        q.push(p);
        block();
    }
    else
        return;
}
 
V(Semaphore s)
{
    s.value = s.value + 1;
    if (s.value <= 0) {
 
        // remove process p from queue
        Process p = q.pop();
        wakeup(p);
    }
    else
        return;
}

 

 

1. 위에도 언급했듯이 P 작업은 wait, sleep 또는 down operation이라고도 하며, V 작업은 signal, wake-up, up operation 또는 포스트라고도 한다. 세마포어는 이 두가지 wait와 signal로만 접근 가능하다.

 

2. 프로세스가 wait() 계산을 실행하고 만약 세마포어 값이 양수가 아니면 프로세스는 반드시 대기 또는 일시중지 해야한다.

 

3. 이때 대기하는 프로세스는 다른 프로세스가 signal()연산을 시작하면 다시 시작되어야한다.

 두 작업 모두 atomic이고 세마포어는 항상 1로 초기화된다. 여기서 atomic은 읽기, 수정 및 업데이트가 사전 추출 없이 동시에 발생하는 변수를 의미한다. 즉, 읽기, 수정 및 업데이트 사이에 변수를 변경할 수 있는 다른 작업이 수행되지 않는다.

 프로세스 동기화를 구현하기 위해 중요한 섹션이 두 작업으로 둘러싸여 있다. 프로세스 P의 중요한 부분은 P와 V 작업 사이에 있다. 아래 예제를 보자.

Process P

//어떤 코드
P(s)
//임계 구역 critical section (한 번에 하나의 프로세스/스레드만 실행 가능하도록 만든 영역)
V(s)
//나머지 구역 remainder section

 

#Producer and Consumer 예제

Producer

int coin_flip;
sem_t coin_flip_done; // semaphore for thread 1 to signal coin flip
// requires sem_init(&coin_flip_done, 0, 0) to give initial value 0
static void * thread1(void *_)
{
	coin_flip = rand() % 2;
	sem_post(&coin_flip_done); // raise semaphore, increment, 'up'
    
	printf("Thread 1: flipped coin %d\n", coin_flip);
}

Consumer

static void * thread2(void *_)
{
	// wait until semaphore is raised, then decrement, 'down'
	sem_wait(&coin_flip_done);
	printf("Thread 2: flipped coin %d\n", coin_flip);
}

• 스레드가 sem_wait()과 sem_post() 호출에 도착하는 상대적 순서에 상관없이 코드가 작동한다.
• 초기 값을 N으로 설정하여 최대 N개 리소스의 획득/해제를 나타내도록 일반화할 수 있다
• 그러나 상호 배제 (mutual exclusion)를 위해 세마포어를 사용하는 것은 권장되지 않으며, 대신 mutex(예: pthread mutex_t)를 사용해야 한다

#상호 배제를 위한 세마포어 사용

sem_t S;
sem_init(&S, 0, /*initial value=*/ 1);

void lock_acquire()
{ 	// try to decrement, wait if 0
	sem_wait (S);
}
void lock_release()
{ // increment (wake up waiters if any)
	sem_post(S);
}

세마포어가 무엇에 사용되는지 어떻게 알 수 있을까? 초기 값을 확인하면 된다. 초기값이 1이면 세마포어는 뮤텍스를 나타내고, 0인 경우 세마포어는 ordering에 사용된다