[OS] Semaphore(세마포어)를 사용하여 concurrency(동시성) 구현하기 - OS 공부 22

안녕하세요 Pingu입니다.

 

지난 글에서는 Concurrency(동시성)에서 Synchronization(동기화)를 구현하기 위한 condition variable(조건 변수)에 대해 알아봤었습니다. 동기화란 스레드 간에 실행 순서를 정해 줄 수 있도록 하는 것으로 유명한 producer/consumer 문제로 적용해서 알아봤었습니다. 이번 글에서는 그 유명한 semaphore에 대해 알아보고 이를 producer/consumer, reader/writer, dining Philosophers(식사하는 철학자 문제)와 같은 유명한 문제들에 적용해보며 실제로 좋은지에 대해 알아보려고 합니다. Semaphore는 간단하게 말하면 지금까지 알아본 Lock, condition variable의 역할을 모두 할 수 있는 자료구조입니다. Semaphore가 Edsger Dijkstra(다익스트라)라는 분이 개발하신 거더라고요. 정말 다익스트라는 컴퓨터 분야를 공부하다 보면 자주 등장하시는 거 같습니다.🧐 이번 글은 제가 참고하고 있는 책인 OSTEP에서는 Chapter 31 - Semaphore 부분입니다!

Semaphores

지금까지 동시성 구현을 위해 알아본 lock, condition variable을 기억하시나요? Lock을 사용해서 여러 스레드가 동시에 접근할 수 있는 자원에 대한 상호 배제를 구현하고 Condition variable을 사용해서 스레드들의 실행 순서를 관리할 수 있었습니다. 근데 이 둘을 하나로 합쳐서 사용할 수 있는 방법을 Dijkstra가 개발했습니다. 이것이 바로 Semaphore(세마포어)입니다. 세마포어만 있으면 lock과 condition variable을 모두 사용할 수 있게 되는 것이죠! 그럼 지금부터 이러한 세마포어를 어떻게 사용할 것인지, 세마포어가 무엇인지에 대해 알아보도록 하겠습니다.

Semaphores: A Definition

그럼 세마포어의 정의부터 알아보도록 하겠습니다. 세마포어는 두 개의 routine(기능, 함수 정도로 해석하면 될 듯합니다)으로 조작할 수 있는 정수 값을 가진 객체입니다. 여기서 두 개의 함수는 sem_wait(), sem_post()입니다. 세마포어가 생성될 때 정의되는 정수 값에 의해 동작이 결정되는데, 세마포어를 생성하는 방법은 아래와 같습니다.

#include <semaphore.h>
sem_t s;
// 세마포어 생성.
// 첫 번째 매개변수는 세마포어 자료구조
// 두 번째 매개변수는 세마포어의 프로세스간 공유 여부(0이면 공유x, 그 외의 값이면 공유)
// 세 번째 매개변수는 세마포어의 값
sem_init(&s, 0, 1);

위와 같이 세마포어를 초기화할 수 있습니다. 초기화 할 때 3개의 매개변수를 갖는데, 첫 번째 매개변수는 세마포어 자료구조입니다. 두 번째 매개변수는 세마포어를 프로세스 간에 공유할 것인지에 대한 여부인데 0이면 공유를 안 하는 것이고 그 외의 값이면 공유를 하는 것입니다. 이번 글에서는 이를 0으로 모두 설정하고 공부할 예정입니다. 이 값이 0이기 때문에 프로세스 내의 스레드끼리만 세마포어를 공유합니다. 마지막 값은 세마포어의 값입니다. 이 값이 0보다 크면 스레드를 실행 가능한 상태이고 음수면 스레드를 sleep상태로 전환해야 합니다. 따라서 이 값을 수정해주는 것이 세마포어를 사용하는 방법인데 이를 수정하는 방법이 아까 언급한 두 개의 함수입니다.

int sem_wait(sem_t *s) {
    // 세마포어의 값을 1 감소한다.
    // 만약 세마포어의 값이 음수라면 스레드를 sleep 상태로 전환한다.
}

int sem_post(sem_t *s) {
    // 세마포어의 값을 1 증가시킨다.
    // 만약 sleep 상태의 스레드가 있다면 한 개만 깨운다.
}

위와 같이 두 개의 함수가 있습니다. wait은 세마포어의 값을 1 감소하고 만약 값이 음수라면 sleep, 양수라면 실행시킵니다. post는 세마포어의 값을 1 증가시키고 sleep 상태의 스레드를 깨웁니다.

 

두 개의 함수를 사용하기 전에 몇 가지를 생각해야 하는데, 첫 번째는 sem_wait()가 실행되면 스레드가 즉시 반환되거나 부모 스레드가 실행을 일시 중단하는 것을 볼 수 있습니다. 여러 스레드가 sem_wait()를 호출할 수 있기 때문에 모든 스레드가 깨어날 때까지 대기해야 합니다.

 

두 번째는 sem_post()는 sem_wait()처럼 특정 조건이 되는 것을 기다리지 않는다는 것입니다. 그냥 실행이 되면 세마포어 값을 하나 증가하고 잠자는 스레드를 하나 깨웁니다.

 

마지막으로 만약 세마포어 값이 음수라면 이 값의 절댓값이 sleep 중인 스레드 수라고 할 수 있습니다. 

 

아직 세마포어의 값에 대한 경쟁 조건은 해결해주지 않았습니다. 글을 진행하면서 lock, condition variable을 활용하여 이를 해결해보도록 하겠습니다.

Binary Semaphores(Locks)

세마포어의 가장 중요한 3가지 함수, init(), wait(), post()를 알았으니 이제 세마포어를 사용할 준비는 됐습니다. 세마포어는 lock, condition variable로 모두 사용 가능하다고 했는데, 먼저 lock으로 사용하는 것을 살펴보도록 하겠습니다.

위와 같이 코드를 만들면 세마포어를 lock으로 사용할 수 있습니다. Critical section(임계 영역)에 접근하기 전에 sem_wait()를 호출하고 임계 영역에서의 작업이 끝나면 sem_post()를 호출합니다. 위의 코드에서 가장 중요한 것은 sem_init()을 할 때 세마포어의 초기값입니다. 위의 코드에서는 X라고 이름을 붙였네요. X의 값은 어떤 값이어야 할까요? X값은 1이면 될 것 같습니다. 그럼 X가 1일 때 코드의 흐름을 살펴보겠습니다.

우선 위와 같이 스레드가 2개인 경우를 상상해보겠습니다. 스레드 0이 먼저 수행되고 sem_wait()를 수행하여 세마포어 값을 1 감소합니다. sem_wait()는 값이 0보다 작을 때만 sleep 상태로 전환되기 때문에 스레드 0은 바로 임계 영역에 접근하게 됩니다. 그런 뒤 임계 영역에서의 작업이 끝나면 sem_post()를 호출하여 세마포어 값을 1로 증가시킵니다. 물론 여기서 만약 sleep 상태의 스레드가 있다면 그 스레드를 깨워주는 작업도 하게 됩니다.

 

여기서 주의 깊게 볼 점은 스레드 0이 sem_wait()을 수행한 바로 뒤의 시점입니다. 이 시점에서 만약 다른 스레드가 sem_wait()를 수행하여 임계 영역에 접근하려고 하면 어떻게 될까요? 

위와 같이 스레드 0이 sem_wait()를 수행한 뒤 바로 스레드 1이 sem_wait()를 수행하면 세마포어의 값은 2번 줄게 되어 -1이 됩니다. 따라서 스레드1의 sem_wait()는 세마포어의 값이 0보다 작기 때문에 스레드1의 현재 상태를 저장하고 sleep 상태로 전환하게 됩니다. 그러다 스레드0이 임계 영역에서의 작업을 끝내고 sem_post()를 수행하면 세마포어의 값을 1 늘리고 sleep 중인 스레드1을 깨웁니다. 그런 뒤 context switch가 되어 스레드1이 실행되면 아까 중단된 시점부터 시작하게 되고 임계영역으로 접근하게 됩니다. 임계영역에서의 작업이 끝나면 sem_post()를 수행하게 되고 세마포어의 값은 초기값과 같은 1로 다시 돌아오게 됩니다.

 

위와 같이 세마포어를 lock과 동일하게 사용할 수 있습니다. 이러한 lock에는 lock을 획득한 상태, lock을 해제한 상태의 2가지만 존재하기 때문에 이를 binary semaphore(이진 세마포어)라고 합니다. 

Semaphores For Ordering

그럼 세마포어를 lock으로 사용해봤으니 이젠 조건 변수의 역할도 할 수 있는지 확인해보겠습니다. 조건변수를 사용한 이유는 스레드 간에 실행 순서 관계를 위해서 였습니다. 기억하시나요? 따라서 세마포어로 스레드의 실행 순서 관계를 제어할 수 있는지 확인해보도록 하겠습니다! 그럼 예를 보며 이를 확인해보도록 하겠습니다.

위의 코드를 실행하면 항상 위와 같이 결과가 나오게 됩니다. 이렇게 나올 수 있는 이유는 세마포어를 사용하여 스레드간에 순서 관계를 만들어줬기 때문인데요, 부모 스레드가 자식 스레드를 만들고 바로 sem_wait()를 수행하여 sleep 상태로 전환합니다. 따라서 자식 스레드가 수행되고 자식 스레드는 sem_post()를 수행하여 sleep 상태의 부모 스레드를 깨웁니다. 즉, 부모 스레드는 자식 스레드가 완료된 뒤에 실행되는 것이죠! 그렇다면 만약 위와 같이 동작하도록 하기 위해서는 세마포어의 초기값이 얼마여야 할까요?

 

위와 같이 순서 관계를 주기 위해서는 세마포어의 초기값을 0으로 설정해주면 됩니다. 그럼 스케줄링 정책에 의해 두 가지 경우가 발생할 수 있는데, 하나는 부모 스레드가 sem_wait() 하기 전에 자식 스레드가 먼저 sem_post()를 수행하는 경우이고, 다른 하나의 경우는 방금 전에 살펴본 과정대로 부모의 sem_wait()가 먼저 수행되고 자식 스레드가 수행되는 경우입니다. 두 가지 경우를 자세히 살펴보며 이해해볼까요?

첫 번째 경우는 부모 스레드의 sem_wait()가 먼저 실행되는 경우입니다. 세마포어 값을 1 감소하면 0보다 작아지므로 부모 스레드는 sleep 상태로 전환되고 자식 스레드가 실행됩니다. 자식 스레드는 sem_post()를 실행하여 세마포어 값을 0으로 증가한 뒤 부모 스레드를 깨웁니다. 그렇게 다시 부모 스레드가 실행되면 그 뒤의 코드를 실행하게 됩니다.

그럼 반대로 자식 스레드의 sem_post()가 먼저 수행되는 경우도 살펴보겠습니다. 이 경우엔 자식 스레드의 sem_post()가 세마포어 값을 1 증가시키고 sleep 중인 스레드를 깨웁니다. 물론 아무도 자고 있지 않기 때문에 그냥 넘어가고 부모 스레드로 context switch 된 뒤 부모 스레드가 sem_wait()를 수행하게 되면 세마포어 값이 1이므로 바로 진행하게 됩니다.

 

이렇게 어떠한 경우로 실행되더라도 동일한 결과를 보여주기 때문에 세마포어를 사용하여 스레드 간에 순서 관계를 제어할 수 있는 것을 알 수 있습니다.

The Producer/Consumer (Bounded Buffer) Problem

지난 글에서 조건 변수를 활용하는 방법을 살펴보며 알아봤던 생산자/소비자 문제를 세마포어로도 잘 되는지 살펴보도록 하겠습니다. 물론 방금까지 알아본 대로 세마포어는 lock, condition variable의 역할을 모두 할 수 있기 때문에 이 문제도 잘 해결할 수 있을 것 같아요!

 

세마포어로 이 문제를 해결하기 위한 방법으로 두 가지를 알아볼 예정인데, 그중 첫 번째 방법은 두 개의 세마포어를 사용하는 방법입니다. 각 세마포어는 full, empty로 정의하며 이 세마포어는 각각 버퍼가 텅 비었는지 가득 채워졌는지를 표시하는 데 사용됩니다.

위와 같이 put(), get() 함수가 정의되어 있고 생산자와 소비자 스레드도 정의되어 있습니다. 생산자 스레드는 put()을 수행 한 뒤 sem_post()로 소비자를 깨우고 소비자 스레드는 get()을 수행 한 뒤 sem_post()로 생산자를 깨웁니다. 만약 empty 세마포어의 초기값을 1로 정한다면 어떻게 될까요?(MAX = 1로 만든다는 것)

 

MAX = 1이면서 생산자 스레드 1개 소비자 스레드 1개인 경우로 생각해보겠습니다. 

위와 같은 과정으로 수행되게 될 텐데요, 먼저 소비자 스레드가 실행된다고 보겠습니다. sem_wait(&full)을 수행하게 되고 full 값을 1 감소시켰더니 0보다 작아져서 sleep 상태가 됩니다. 그런 뒤 생산자 스레드가 실행되고 sem_wait(&empty)를 수행하고 초기값이 1이었기 때문에 감소를 하더라도 0보다 커서 그냥 진행합니다. put()을 수행하게 되고 sem_post(&full)을 수행합니다. 따라서 full 값이 다시 0이 되고 소비자 스레드도 깨우게 됩니다. 소비자 스레드는 아까 잠들기 전 시점부터 다시 수행하므로 get()을 수행하고 sem_post(&empty)를 수행하여 empty값을 1 증가시킵니다. 이와 같은 과정이 계속 반복되게 됩니다.

 

그런데 만약 MAX가 1보다 크다면 어떻게 될까요? 또한 생산자, 소비자 스레드가 1개가 아닌 여러 개라면 어떻게 될까요? 이는 get, put에서 사용하는 변수인 fill, use에서 경쟁상태가 발생하게 됩니다.

예를 들어 이해해보자면 생산자가 생산자 1, 생산자 2로 2개일 때를 생각해보겠습니다. 두 생산자가 put()을 거의 동시에 실행하고 생산자 1이 먼저 실행되어 버퍼에 값을 넣은 뒤 fill 값을 1 증가하기 전에 context switch가 발생하여 생산자 2가 실행됩니다. 이때 fill 값이 증가되지 않았기 때문에 생산자 2도 버퍼의 동일한 위치에 생산한 값을 넣게 되고 이는 생산자의 데이터 손실을 발생시킵니다. 이를 어떻게 해결해야 할까요?

방금과 같은 경쟁 상태가 발생하는 이유는 상호 배제를 고려하지 않았기 때문입니다. 이를 해결하는 방법은 lock을 사용하는 것이죠. 따라서 위와 같이 임계 영역에 접근하기 전에 이진 세마포어로 lock을 추가하면 아까 전의 문제를 해결할 수 있을 것 같은데... 사실은 해결이 되지 않습니다. 위와 같은 코드를 실행하면 어떤 문제가 발생할까요?

 

생산자 스레드 1개 소비자 스레드 1개가 있는 상태에서 위의 코드를 실행한다고 생각해보겠습니다. 

위와 같이 수행되는데 결과적으로 말하면 아까 코드를 수행하면 생산자와 소비자가 모두 sleep 상태가 되며 이를 깨울 스레드가 존재하지 않게 되는 상태가 됩니다. 즉 생산자와 소비자가 서로 깨워주기를 기다리고만 있는 것이죠. 이러한 문제를 dead lock (교착 상태)이라고 하며 dead lock을 해결하기 위해서는 lock의 범위를 줄여주면 됩니다. 

아까 전에 문제가 발생한 코드와 다른 점은 mutex 세마포어의 사용 위치입니다. 위와 같이 코드를 만들면 멀티 스레드 프로그램에서 일반적으로 사용되는 단순한 bounded buffer가 완성됩니다.

Reader-Writer Locks

이번에 살펴볼 문제는 Reader/Writer 문제입니다. Reader는 데이터를 읽고 Writer는 데이터를 수정합니다. Reader는 그저 읽기만 하기 때문에 공유 자원이라고 해도 여러 스레드가 동시에 접근해도 문제가 없습니다. 하지만 Writer는 데이터를 수정하기 때문에 한 시점에는 반드시 하나의 스레드가 접근할 수 있어야 하죠. Writer가 데이터를 수정하는 동안에는 Reader 스레드도 접근할 수 없습니다. 즉 데이터가 수정 중이 아니라면 Reader 스레드는 여러 개 존재해도 괜찮다는 말입니다!

코드는 위와 같이 만들 수 있습니다. 주의 깊게 볼 점은 rwlock_acquire_readlock() 부분과 rwlock_release_readlock() 부분입니다. read lock을 획득하고 해제하는 함수인데 lock을 획득할 때는 reader의 값을 1 증가시키고 만약 reader가 1명이라면, 즉 reader 스레드가 1개라면 write lock도 획득합니다. 모두 읽은 뒤에는 readlock을 해제합니다. 

 

readlock을 해제하는 부분에서는 reader 스레드가 하나도 없을 때 드디어 write lock을 해제하고 writer 스레드를 깨웁니다. 이 말은 reader 스레드가 하나도 없을 때만 writer 스레드가 공유자원에 접근할 수 있다는 말이 되는 것이죠.

 

위와 같이 코드를 작성하게 되면 reader는 여러 명이라도 공유자원에 접근할 수 있습니다. 한 번 실제로 해볼까요? reader 스레드가 2개 있고 writer 스레드는 한 개 있는 상황을 가정해보겠습니다.

음 좀 삐뚤삐뚤하지만.. 이해 바랍니다. ㅠ.ㅠ 위와 같이 진행되게 되는데 결과적으로 reader가 하나라도 존재하면 writer는 sleep 상태로 존재해야 합니다. 언젠가 readers == 0이 만족되어 sem_post(writerlock)을 해줘야 비로소 sleep 상태에서 깨어나게 되죠. 따라서 reader, writer 문제에서 위의 코드는 공평하지는 않습니다. writer가 오랫동안 sleep 상태에 빠지게 되는 상황이 자주 발생하기 때문이죠.

The Dining Philosophers

이번에는 다익스트라가 해결한 가장 유명한 동시성 문제 중 하나인 식사하는 철학자 문제를 알아보도록 하겠습니다. 조금 재밌는 상황이 주어지는데요, 일단 식사하는 철학자 문제에서 철학자들은 둥근 식탁에 앉아있습니다. 철학자들 사이마다 포크가 하나씩 있으며 테이블 중앙에는 파스타가 하나 있습니다. 철학자들은 철학에 대해 생각을 하다가 배가 고파지면 자신의 양쪽에 있는 포크를 들고 파스타를 먹는데, 자신의 양쪽에 있는 포크를 모두 사용해야 파스타를 먹을 수 있다고 합니다. 즉 이를 그림으로 나타내면 아래와 같아집니다.

철학자가 하는 행동의 패턴을 코드로 나타내면 아래와 같아집니다.

여기서 포크는 공유자원이 되며 여기에 접근할 수 있는 철학자는 한 시점에 한 명이 됩니다. 따라서 포크마다 세마포어도 존재해야합니다.

만약 위와 같이 포크를 잡고 내려놓는 함수를 구현했다고 하면 어떨까요? 철학자들은 파스타를 잘 먹을 수 있을까요? 위와 같은 코드로 철학자들이 식사를 하려고 할 때 모든 철학자가 자신의 왼쪽에 있는 포크를 집어 든다면 어떻게 될까요?

그럼 위와 같이 모두가 자신의 왼쪽 포크를 가지고 있는 상태가 되며 오른쪽 포크를 얻으려고 해도 모두 누군가가 가지고 있기 때문에 아무도 파스타를 먹을 수 없는 dead lock(교착 상태)이 됩니다. 이러한 문제를 어떻게 해결해야 할까요?

아주 단순하게 마지막 철학자 보고 왼쪽을 먼저 잡지 말고 오른쪽을 먼저 잡으라고 하면 이 문제는 해결됩니다.

위와 같이 p4는 sleep 상태로 전환되고 p3이 f4를 얻어서 식사를 하고 포크를 내려놓으면 p2도 식사를 하고... 계속해서 철학자들은 식사를 할 수 있게 됩니다. 이렇게 간단하게 해결한 사람이 다익스트라라고 합니다. 

Thread Throttling

세마포어의 다른 사용 사례도 존재하는데, 만약 스레드가 동시에 너무 많이 실행되어 시스템에 문제를 주게 된다면 어떻게 해결할 수 있을까요? 세마포어를 활용하여 적절한 최댓값을 정해서 스레드의 개수가 특정값 이상으로 존재하지 않도록 할 수 있습니다. 스레드가 너무 많아지면 각각의 스레드마다 메모리를 할당해줘야 하고 스레드가 너무 많아지면 실제 존재하는 메모리의 양을 초과할 수 있습니다. 이렇게 되면 이전에 배운 paging, segmentation 기법으로 메모리를 디스크 공간으로 옮겨줘야 하는데 이러한 과정에서 오버헤드가 발생하기 때문에 성능 저하로 이어집니다.

 

이러한 문제를 세마포어를 사용하면 쉽게 해결할 수 있습니다. 세마포어 값을 사용해서 스레드의 최대 수를 정해주고 sem_wait(), sem_post()를 사용하여 스레드 수를 조절하면 이 문제를 해결할 수 있게 됩니다.

Summary

이번 글에서는 동시성 프로그래밍을 구현하기 위한 방법으로 세마포어를 알아봤습니다. 세마포어를 사용하면 지금까지 살펴봤던 lock, condition variable을 한 번에 사용할 수 있었습니다. 또한 생산자, 소비자 문제, reader, writer문제, 식사하는 철학자 문제들을 통해 고질적인 문제인 dead lock에 대해서도 알아봤습니다. 다음 글에서는 동시성을 구현할 때 발생하는 문제인 dead lock(교착 상태)를 해결하는 방법에 대해 집중적으로 살펴보도록 하겠습니다.