16. Synchronization (3)

 

 

 

 

---

 

Producer Process(생산자 프로세스)는 정보를 생산하고, 그것을 Consumer Process에서는 소비하는 구조이다.

보통 생산자가 버퍼에 정보를 채워놓을 때, 버퍼의 크기가 무한대인 Unbounded Buffer를 이상적으로 생각한다. 버퍼의 크기가 한계가 없으니 생산자는 계속 정보를 넣을 수 있다.

하지만, 현실적으로 이런 것을 구현할 수 없으니 유한 버퍼 Bounded Buffer를 Circular array로 구현해서 Unbounded Buffer 흉내를 낸다.

 

이런 유한 버퍼에서는 

1) 버퍼가 비어있으면 소비자는 waiting 해야하고

2) 버퍼가 꽉 차있으면 생산자는 waiting 해야 한다.

 

Circular array로 구현하기 위해서 우리는 in과 out을 사용할 것이다.

in은 next free position in the buffer를 가리킬 것이고,

out은 first full position in the buffer를 가리킬 것이다.

 

따라서 버퍼가 비어있으면 in == out 이고

버퍼가 꽉 차있으면 ((in + 1) % Buffer_Size) == out 이다.

 

 

보통 하나를 비워놓고 꽉찼다고 한다.

한 개를 못쓰게 되는 것이다.

버퍼는 Buffer_Size-1 까지만 쓸 수 있다.

 

 

 

먼저 다음과 같은 struct를 만든다.

typedef struct {
    int n;
    semaphore mutex = 1;
    semaphore empty = n;
    semaphore full = 0;
}

binary semaphore와 counting semaphore를 구분하는 가장 좋은 방법은 초기값이다.

여기서 binary semaphore 는 mutex / counting semaphore는 empty, full 이다.

 

empty와 full은 버퍼의 총 수 n을 기준으로 조건이 달리는데, 뒤의 코드를 보며 설명하겠습니다.

먼저 producer process 구조입니다.

 

(첫번째 Producer process가 실행됐습니다.)

먼저 프로듀서가 아이템을 만듭니다.

만들어진 아이템은 critical section에서 버퍼로 진입할 것입니다.

 

critical section에 진입하기 위해  wait(empty)와 wait(mutex)를 호출하는데, wait(empty)로 인해 초기값 n은 n-1이 됩니다.

(empty의 초기값 n은 버퍼의 n개 공간이 아이템으로 차있지 않다는 의미입니다.

현재 버퍼에 새로운 아이템을 넣으려고 하니 비어있는 n개의 공간이 n-1 개로 바뀌는 것이라 생각하시면 됩니다.)

 

그 후 mutual exclusion 조건을 만족시키기 위해 binary semaphore의 wait 함수를 사용하고, critical section에 진입합니다.

 

버퍼에 아이템을 채우는 행위가 끝나면 다시 한 번 binary semaphore의 signal 함수를 호출해 critical section 탈출을 알리고,

signal(full)을 호출해 0의 초기값을 full->value++ 를 해줘 1로 만들어 줍니다.

(버퍼의 공간이 하나도 차있지 않았는데 (0) 내가 하나 채웠으니 1이 된 것입니다.)

 

시간이 꽤 흘려 (Consumer의 실행이 한 번도 없다는 가정 하에) Producer가 n+1 번 실행되면

wait(empty)의 조건에 걸려 그 Producer는 block이 됩니다.

n이 -1이 되기 때문입니다.

(버퍼가 꽉 차있으니 새로 만들어진 아이템을 넣을 공간이 없어서 block 됨)

 

 

---

 

 

 

Producer : 새로 넣는 애

while(((in + 1) % BUFFER_SIZE) == out); // 버퍼가 꽉차면 기다린다.

buffer[in] == next_produced; // 그렇지 않으면 buffer[in] 에다가 새로운 값을 넣고

in = (in+1)%BUFFER_SIZE; // in에다가 다음 슬롯을 가리키게 한다.

while(((in + 1) % BUFFER_SIZE) == out); // 버퍼가 꽉차면 기다린다.
buffer[in] == next_produced; // 그렇지 않으면 buffer[in] 에다가 새로운 값을 넣고
in = (in+1)%BUFFER_SIZE; // in에다가 다음 슬롯을 가리키게 한다.

 

Consumer : 쓰는 애

while(in == out) // 버퍼에 아무것도 없으면 기다린다.

next_consumed = buffer[out]; // out이 가리키는 buffer에서 하나를 꺼내 가고

out = (out + 1) % BUFFER_SIZE; // out에다가 다음 슬롯을 가리키게 한다.

while(in == out) // 버퍼에 아무것도 없으면 기다린다.
next_consumed = buffer[out]; // out이 가리키는 buffer에서 하나를 꺼내 가고
out = (out + 1) % BUFFER_SIZE; // out에다가 다음 슬롯을 가리키게 한다.

 

---

여기서도 Synchronization 을 안해주면 문제가 발생할 수 있다.

buffer[in] = data; 에 2개의 쓰레드가 접근하거나

data = buffer[out]; 에 2개의 쓰레드가 접근하거나

 

 

mutex를 써서 Bounded Buffer 를 해결하는 법

값이 뭔지는 한 Producer마다 한번씩만 볼 수 있게 만들어야 한다.

두개의 Producer가 동시에 들어오면 하나만 count에 접근할 수 있게끔 해줘야 한다.

 

 

Semaphore를 써서 Bounded Buffer 를 해결하는 법

 

 

 

 

 

 

 

 

 

 

---

 

배가 고프면 자기 왼쪽에 있는 포크와 오른쪽에 있는 포크를 들고 먹는다.

이 때 동시에 잡는 것이 아니라 하나를 잡고 그 다음 하나를 잡는다.

양손으로 못 잡으면 못 먹는다.

모든 사람이 파스타를 먹으려고 하면 아무도 못 먹게 된다.

 

여러개의 task들이 shared resource가 있는데 shared resource를 잘 공유하지 못하면 멍때리는 상황이 발생한다.

그것을 Deadlock 이라고 한다.

 

 

철학자들이 서로 왼쪽 포크를 잡고 먹으려고 한다.

 

해결법 : 가장 마지막 사람은 오른쪽 포크를 먼저 잡으면 Deadlock이 해결된다.