[OS/OSTEP] 31.threads-semaphore, 세마포어, 세마포어로 락 구현, 컨디션 변수로서의 세마포어, 생산자/소비자 문제, Dining Philosopher, 제마포어

[OS/OSTEP] 30.threads-condition variable, 쓰레드 컨디션 변수, 컨디션 변수 두개, 쓰레드 동기화 문제, 생

 

[OS/OSTEP] 30.threads-semaphore

# 시작하며

 저번시간에는 컨디션 변수에 대해서 공부했었다. 쓰레드가 동시에 실행됨에 따라서 어떠한 조건을 기다려야 했다. 동기화과정이 필요했는데 이럴때 컨디션 변수를 사용했었다. 컨디션 변수를 사용하여 기다려야하는 상황에서는 wait시켜서 잠시 대기하도록 했다. 이렇게 되기하는 쓰레드들을 큐에 담아서 나중에 signal을 보내 깨울때 순서대로 깨워 READY상태로 만들었다. 생산자/소비자 문제에서는 컨디션 변수를 하나만 사용할때, 잘못 사용한다면 모든 쓰레드가 잠드는 상황에 빠질 수 있었다. 이러한 상황을 방지하기 위해 empty와 fill과 같이 두개의 컨디션 변수를 만들어, 생산자는 empty에 소비자는 fill에 대기시키며 서로가 서로를 깨워주면서 모두가 잠드는 상황을 방지했다. 하나의 큐를 사용하고 broadcast를 사용하여 signal대신하여 컨디션 변수에 있는 모든 쓰레드를 깨움으로써 조건을 한번 더 검사하여 처리하는 방향으로 설계했다. 이번 세마포어 시간에서는 이전까지 구현했던 락과 컨디션 변수들을 세마포어로 구현해보도록 할 것이다.

 

# 세마포어(semaphore)

 다양한 범주의 병행성 문제 해결을 위해서는 락과 조건 변수가 모두 필요하다. 다익스트라(Dijkstra)라는 사람은 세마포어라는 동기화 기법을 개발해냈다. 세마포어는 락과 컨디션 변수로 모두 사용 할 수 있다. 락과 컨디션 변수를 대신하여 세마포어를 어떻게 사용하는지 이진 세마포어는 무엇인지 살펴보도록 하자

 

# 정의

세마포어는 정수 값을 갖는 객체로서 두 개의 루틴으로 조작 할 수 있다. sem_wiat()와 sem_post()이 있으며, 초기값으로 설정해준 값에 의하여 동작이 결정된다. 그렇기 때문에 세번째 인자로 적절한 값을 초기값을 초기화 해야한다. sem_wait()와 sem_post()는 어떤 동작을 수행하는지 살펴보자.

 sem_wait()가 호출되면 해당 세마포어의 정수값을 -1을 한다. 그리고나서 그 값이 음수이면 즉 0보다 작은 경우에 wait하여 sleep에 빠지고, 그렇지 않은경우에는 그냥 return한다. 일단 실행되면 무조건 적으로 세마포어의 값을 -1하게 된다.

 sem_post()는 그와 반대로 세마포어의 정수값을 +1한다. 그리고 한개 이상의 쓰레드가 wait중이라면 그 쓰레드를 깨워준다.

세마포어가 음수라면 그 값은 현재 대기 중인 쓰레드의 개수와 같다는 것을 알아 두면 좋을 듯 하다. 또한 wait와post는 원자적으로 수행된다고 가정한다. 이 루틴들은 다수의 쓰레들에 의해 동시에 호출되는 것을 가정으로한다. 그렇기 때문에 늘 임게영역은 적절히 보호해야한다. 일단은 세마포어의 기능에 주목하고, 뒷부분에서 임계영역을 보호하는 방법을 적용할 것이다.

 

# 이진 세마포어 락 ( binary semaphore lock )

 세마포어를 활용해서 락을 구현할 수 있었다고 했다. 락의 구현사항은, 락을 획득하지 못한 경우에는 락을 획득하는 시점까지 대기하다가 락을 획득할 수 있는 경우에 락을 획득하고 임계영역을 수행하면 된다. 세마포어도 wait를 활용한다면 락 획득 가능 시점까지 대기할 수 있다.

 세마포어의 초기값 설정은 중요하기 때문에 이 경우 초기값을 어떤것으로 설정해야 할까? 맨 처음 나는 0으로 설정해야 한다고 생각했지만, 그럴 경우 sem_wait 즉 lock이라는 구절이 실행되자 말자 무조건적으로 세마포어값이 -1이 되어 sleep상태가 될 것이다. 그렇기 때문에 초기값을 1로 주고, wait가 가장 먼저 실행되면 세마포어값은 0이 되어 임계영역을 정상적으로 실행되고, 이때 다른 쓰레드에서 락을 요청(sem_wait)을 하게되면 세마포어 값이 -1이 되어 요청한 쓰레드는 락을 기다리는 상태가 될 수 있을 것이다. 그렇기 때문에 초기값은 1로 설정하는 것이 알맞다.

 

두개의 쓰레드가 아닌 여러개의 쓰레드가 서로 락을 얻으려는 상황을 생각해보면 아래와 같을 것이다.

병렬로 실행 될 수 있다는 가정하에, 초기의 T1쓰레드가 락을 얻었다면 T2,T3,T4는 세마포어가 하나씩 감소할 것이다. 위에서 이야기 했듯이 세마포어가 음수일때 그 값(절대값)은 대기하는 쓰레드의 갯수가 된다고 했다. 여튼 post하여 큐에 있는 쓰레드를 하나씩 깨우게 되면서 순차적으로 세마포어값이 증가하면서 모든 쓰레드가 정상적으로 락을 얻고 반납까지 끝냈다면 다시 초기값 1로 돌아오게 될 것이다.

 

# 컨디션 변수로서의 세마포어 - 상태변수

어떤 조건이 참이 되기를 기다리기 위해 컨디션 변수를 사용했다. 이번에는 세마포어를 사용해서 컨디션 변수를 구현해보자. 익숙한 부모-자식간 쓰레드가 실행되는 상황을 가정해보자.

 부모쓰레드는 자식쓰레드가 완료 됐는지를 확인하고 기다릴 수 있어야한다. 이때 초기값은 어떤것을 넣어야 할까? 정답부터 말하자면 락을 구현할때와는 다르게 0이 되어야한다. 이전에는 count와 같은 상태변수를 활용하여 부모쓰레드의 wait구문보다 먼저 실행이 완료된 상황을 점검하여 sleep상태에 빠지지 않아야 됐다. 여기서는 초기값 1이 이러한 count의 상태 변수의 역할을 한다. 자식쓰레드가 완료되기 전에 부모쓰레드의 wait가 실행되는 경우에는 무조건적으로 sleep상태에 빠져서 기다려야 한다. 이 경우에는 0 -> -1로 세마포어 값이 변화하여 조건을 만족한다. 반대의 경우 자식이 부모의 wait가 호출되기 전에 완료된 경우라면 부모쓰레드는 sleep상태가 되면 안된다. 자식이 실행될때 sem_post를 호출함에따라 세마포어값이 0 -> 1로 증가하게 되고, 그후 부모쓰레드의 wait가 실행되어 1 -> 0으로 바뀌게 된다. 세마포어 값이 음수가 아니기 때문에 sleep이 되지 않는다. 이 역시 조건을 만족 시켰다.

 

# 생산자 / 소비자 ( 유한 버퍼 ) 문제

 컨디션 변수를 다루면서 producer / consumer 상황을 구현해야 했고 그 과정에서 몇가지 문제점들이 생기기도 했다. broadcast나 두개의 컨디션변수를 만들어 이러한 상황을 관리했다. 세마포어를 이용할때는 어떻게할 수 있을까? 일단 공통적으로 사용되는 put과 get의 코드를 알아보자.

 

## 첫번째 시도, 그러나 상호배제 문제 발생

 두개의 컨디션변수를 사용했던거와 같이, empty와 full이라는 두개의 세마포어를 사용한다.

 각각의 세마포어 값에 따라 현재 버퍼의 상태를 확인할 수 있기 때문에 알맞게 동작할 것이다. 또한 empty와 full처럼 두개의 큐로 관리되기 때문에 모두가 잠들어버린 경우도 존재하지 않을 것이다. 

 그렇지만 100% 완벽한 구현은 아니다. 왜냐하면 여러 생산자 소비자 쓰레드가 존재하고 버퍼가 단일 값이 아닌 10과 같이 여러개를 저장할 수 있는 크기를 가지는 경우에는 인터럽트에 의해서 경쟁조건이 발생 할 수있다. 예를 들어 두개의 생산자 Pa와 Pb가 실행된다고 가정해보자. 세마포어 empty의 초기값은 10이 될 것이다. empty가 음수가 되지 않는한 여러 쓰레드가 sleep없이 실행 될 수 있다. Pa와 Pb가 7번(// P1)라인을 수행하여 empty가 8로 변화 했다. 이제 8번라인의 put()이 실행 되면서 put()함수가 호출 될 것이다. 현재 int fill의 값은 0이고 //f2라인을 수행하기 직전 Pb로 인터럽트가 걸려 Pb또한 똑같은 루틴을 싱해하여 //f1라인까지 실행을 맞췃다. 각 쓰레드(Pa,Pb)의 레지스터에는 fill변수에 대한 동일한 값 0 을 지니고 있고, Pb의 f2가 정상적으로 실행되어 fill값은 1로 바뀌고 다시 Pa로 인터럽트가 걸려 마저 실행된다. Pa 역시 fill에 1의 값을 저장시킨다. 전형적인 경쟁조건의 발생이다. 원래대로라면 fill은 2가 되어야 했지만 한개의 값이 씹혀 버렸다! 우리는 이 경우를 락을 이용해서 해결했다. 똑같은 방법으로 이제 해결해보자.

 

## 락 구현 - 상호배제 추가

 우리는 경쟁조건을 해결하기 위해서는 락을 추가했듯이, 세마포어로 구현한 락을 각각의 구문에 추가시킨다. 그러나 위 구문은 잘못 된 경우다. 컨디션 변수의 의해서 wait(sleep)되는 경우에는 소유한 락을 반드시 반환해야 했다. 그렇지 않으면 데드락현상이 발생한다. 즉 락을 가진채로 쓰레드가 잠들어 버렸는데, 쓰레드를 깨우기 위해서는 락이 필요하다, 근데 락을 얻을 수 없으니 깨우지 못하는 상황이 발생 하는 것이다. 

 

## 올바른 구현 - 락의 범위를 축소

 락의 범위를 축소 시켰다. 이제 쓰레드가 잠드는 상황이 오더라도 해당 쓰레드는 락을 가지고 있지 않다. 경쟁조건의 문제또한 put과 get에서 발생했기때문에 알맞게 보호됐다.

 

# Reader-Writer 락

 읽기를 수행하는 쓰레드와 쓰기를 수행하는 쓰레드가 존재할 수 있을 것이다. 읽는 것은 여러 쓰레드가 동시에 실행해도 문제가 없을 것이지만, 쓰는 작업은 단편적인 하나의 시점을 잘라봤을때 한개만 쓰고 있어야한다. 그렇지 않으면 상호배제의 규칙에 어긋나게 된다. 읽기든 쓰기든 작업이 들어올때와 작업이 나갈때 각각의 큐에서 관리해야한다. 또한 각각의 작업이 끝나는 시점의 정의가 중요하다. 아무 생각 없이 짜게 된다면 특정 쓰레드는 starvation현상이 일어날 것이다. 학교에서 수업을 들으며 나온 예제를 살펴보도록 하자. 이 예제의 최종본에서는 WaitngWriter에서 대기중인 Writer쓰레드가 없으면 Reader는 무한정으로 동시에 실행하다가, WaitingWriter에 Writer쓰레드가 한개 이상 존재하는 시점에서 들어오는 Reader는 WaitingReader로 보내고, Sleep시킨다. 그리고 실행중인 Reader쓰레드가 모두 끝이 나면 Writer를 스케줄링 했다.

 reader에 대한 세마포어 큐를 따로 만들지 않아도 되는 이유는 reader는 몇개가 동시에 읽히든 관계 없기 때문에다. 그러나 writer는 동시에 한개만 읽힐 수 있어야 하기 때문에 초기화를 1을 사용해야 한다.

 

지금 보니 아래 예제는 세마포어로 구현된 것이 아니라 일반적인 컨디션 변수를 이용한것 같다.. 그래도 참고하면 좋을 듯 싶다!

## starvation 발생

 

## 스케줄링 정책을 정해줌

 

# Dining Philosopher - 식사하는 철학자 문제

 철학자 4명이 존재한다. 철학자가 밥을 먹으려면 왼쪽에 있는 포크와 오른쪽에 있는 포크를 가져야 한다. 그리고 먹고 포크를 다시 왼쪽에 있는 포크를 내려놓고 오른쪽에 있는 포크를 내려놓는다. 

 위 루틴과 같이 실행한다면, 어떤 문제가 발생하는지 생각해보자. 내가 그림에서 그림거와 같이 각각의 철학자들은 왼쪽 포크를 먼저 들게 된다. 4명의 철학자가 자신의 왼쪽에 있는 포크를 가졌다면 먹기 위해서 오른쪽 포크를 가져야하는데, 오른쪽 포크를 내려놓기 위해서는 밥을 먹어야 한다. 그런데 포크가 없으니 밥을 먹지 못한다. 서로가 눈치만 보면서 오른쪽 포크를 가지기 위해서 기다리고만 있는 것이다.

 

## 해답 - 의존성 제거

 마지막 철학자가 포크를 가지는 순서가 반대가 된다면, f4 즉 P3은 양쪽 포크를 가지게 될 것이고 먹고 반납하게 되면 P2도 오른쪽 포크를 가지고 밥을 먹고 반납 .. 이 순서가 반복되며 의존성이 제거 될 것이다.

 

# 제마포어

락과 컨디션 변수를 사용하여 세마포어를 구축해보자

 

# 마치며

헷갈리면서도 알거 같고 문제풀면 또 모를거 같고.. 그래도 블로그에 글 쓰려면 최소 1회 정독 후, 글 쓰면서 읽으면서 쓰게 되니까 못해도 2번은 읽게 되니까 어찌저찌 이해는 잘 된다. 근데 시간이 너무 오래걸린다 ㅠㅠ