Semaphore Bounded Buffer Problem

put과 get 동작 방식

지금부터 말하는 Bounded Buffer는 Circular Queue가 된다.

그림으로 그려보면 아래와 같다.

Circular Queue 그림

 

item이 들어있는 개수와 매칭 되는 semaphore는 full, 현재 넣을 수 있는 빈칸 수에 대한 semaphore가 empty 이다.

따라서 put 은 빈칸이 있어야 할 수 있도록 해야하며, get은 item이 들어 있어야 꺼내올 수 있도록 작성되어야한다.

추가로 empty는 넣을 수 있는 빈칸 수를 의미 하기 때문에 초기값을 buffer의 최대 크기인 MAX 값을 주고

full은 item이 들어있는 개수를 의미하기 때문에 초기값을 0으로 준다. 다시 말하지만 초기값 설정은 중요하다.

 

Condition Variable에서는 count 변수를 가지고 이를 확인했다. 상태를 저장할 수 있는 자체적인 변수를 가지고 있지 않기 때문에 별도로 존재한다. 하지만 Semaphore는 내부에 value를 자체적으로 갖는다.

따라서 이 변수가 count를 대신 할 수 있기 때문에 굳이 count 변수를 별도로 다루지 않는다.

 

get 할 때는 use 포인터가 가리키는 곳에서 가져올 수 있도록 하고 use 포인터를 그 다음으로 이동.

fill 할 때는 buffer의 그 자리에 value를 넣고 fill을 그 다음 자리로 이동시켜준다.

 

producer를 호출하면 producer는 빈 자리가 있는지 확인해야하기 때문에 empty를 sem_wait를 통해 꺼내온다.

이 때 만약 꺼내지면 빈 자리가 있다는 것이기 때문에 put()을 하고 꺼내지지 않을 경우 negative number로 내려가서

waiting을 하게 될 것이다. (waiting이 깨어나면 빈 자리를 얻은 것)

put을 했다면 item이 증가했다는 의미이기도 하기 때문에 sem_post에 full을 넘겨주고 호출한다.

full은 item 개수와 매칭 되기 때문에 sem_post를 통해 증가시켜줘야한다. 이 때 item은 consumer에서 기다린다.

마찬가지로 consumer를 보면 sem_wait를 할 때 full을 확인하는데, item이 존재하는지 확인하는 것이다.

여기서도 마찬가지로 못가져올 경우 sleep을 통해 기다려야한다.

그렇게 item을 get을 통해 꺼내게 되면 빈자리가 생긴다.

따라서 sem_post에 empty를 넘겨줘서 빈 자리를 증가시킨다. 이 때 빈 자리는 producer가 기다리고 있다.

 

헷갈리기 때문에 정리를 하자면 자기가 원하는 조건인가를 확인하는 것이 sem_wait 이고

서로 자기가 바꾼 정보를 알려주는 것이 sem_post이다.

또한 sem_wait는 무조건 감소, sem_post는 증가 하는 함수이다.

Problem

put과 get은 critical section으로 만들어야 한다. producer가 2개가 있을 때 이들은 경쟁적으로 put을 호출할 것이다.

그 때 fill의 값이 가져다가 사용하고 변경을 하는데, 이 과정이 atomic 하지 않는다면 race condition이 발생한다.

(get의 use도 마찬가지이다.)

이를 해소하기 위해서 Lock & Unlock 을 사용하여 use와 fill 을 사용하는 get, put 함수에서 LD, ADD, ST를 하는 부분이

critical section이 되도록 하여 해당 코드가 하는 일이 상호 배제(mutual exclusive) 되도록 만들어야한다.

이를 동기화 라고 한다.

따라서 producer와 consumer에서 sem_wait를 호출하기 전에 lock을 걸고 sem_post가 끝난 후에 lock을 풀어줘야한다.

Solution (Incorrectly)

Mutual Exclusion을 추가하는 방식

기존 producer와 consumer의 sem_wait 앞에 lock, sem_post 뒤에 unlock을 걸어서 Mutual Exclusive 하게 만든다.

 

하지만 이렇게 할 경우 Deadlock 이 발생할 수 있다.

예를 들어서 item이 없는 상태에서 consumer Thread에서 consumer를 호출하면 full이 0 -> -1로 되면서

Sleep 상태에 들어가는데, 이 상태에서 Thread가 producer Thread로 Switching이 되고

producer를 호출하려고 할 때 문제가 발생한다.

producer에서는 lock을 얻으려고 할텐데 앞에서 consumer가 lock을 얻었기 때문에 producer는 waiting 상태가 된다.

따라서 Sleep 상태로 들어 가게 되고 결국 둘 다 Sleep 상태가 된다.

즉 consumer는 full을 기다리는데, 이는 producer가 깨워주어야 하고 producer는 lock을 기다리는 상태이기 때문에

consumer가 unlock을 해주어야하지만, unlock을 하기 위해서는 sem_post(&full)을 producer를 통해서 받아야하는 문제

때문에 서로 cross가 되어서 계속 빙글빙글 돌기만 하고 아무도 서로의 Sleep을 깨우지 못하는 상황이 되는 것이다.

바로 이런 현상을 Deadlock이라고 한다.

 

Deadlock의 발생 원인은 critical section 안에서 lock을 가지고 Sleep을 했기 때문이다.

이 Sleep을 깨우려면 producer가 critical section으로 진입을 해야하는데 진입 하기 위해서는 lock이 필요하다.

consumer가 lock을 쥐고 Sleep을 했기 때문에 방법이 없다.

Solution(Correctly)

 

sem_wait와 sem_post를 critical section 밖으로 내보낸다. 즉 mutex lock과 unlock을 최소화 한다.

이는 Semaphore의 특징으로 인해 critical section에서 Sleep 하는 경우를 없게 만들 수 밖에 없기 때문이다.

이렇게 하면 Producer & Consumer 문제를 Semaphore로 해결할 때 Deadlock을 회피 할 수 있다.

critical section에서 Sleep하는 것을 도저히 방지 할 수 없다면 Condition Variable을 사용해야한다.

Condition Variable의 경우 critical section 안에서도 편하게 Sleep이 가능하기 때문이다.

참고

Condition Variable의 경우 Sleep 하기 전에 lock을 풀어주고 Sleep 했다가 다시 Ready 상태로 돌아갈 때 lock을 얻는다.

따라서 이 경우는 critical section으로 진입해도 문제가 발생하지 않는다.