Synchronization 관련 문제

Bounded-Buffer Problem(Producer-Consumer Problem)

버퍼의 크기가 유한하며 producer와 consumer가 여러 개인 환경이다. producer는 공유 버퍼에 데이터를 만들어서 집어넣는 역할을 한다. 위 그림에서 주황색 원이 데이터가 들어있는 버퍼를 의미하며 비어있는 원이 비어있는 버퍼를 의미한다.

이런 상황에서 synchronization 과 관련된 어떤 문제가 발생할 수 있을까?

먼저, 여러 생산자가 동시에 도착하여 비어있는 버퍼를 동시에 확인하여 동시에 데이터를 만들어 집어넣게 되면 문제가 발생한다. 이런 문제를 방지하기 위해 생산자가 비어있는 버퍼를 확인하고 집어넣는 작업을 그냥 하는 것이 아니라 공유 버퍼에 lock을 걸어 다른 프로세스들의 접근을 막아야 한다. 데이터를 집어넣는 작업이 끝나면 unlock을 한다. 소비자도 마찬가지로 여러 소비자가 동시에 데이터를 꺼내가려 하면 문제가 발생한다. 소비자가 공유버퍼에 lock을 건 다음에 데이터를 꺼내가야 한다.

두번째 문제는 자원의 개수가 또다른 세마포어가 되는데, bounded buffer와 관련된 문제이다. 버퍼의 공간이 유한하기 때문에 버퍼 N개를 가득 채우고 나면 생산자가 도착하더라도 데이터를 넣을 수 없다. 소비자가 데이터를 꺼내가서 사용해야지만 생산자가 데이터를 집어넣을 수 있다. 생산자 입장에서는 비어있는 버퍼의 개수가 카운팅해야 하는 자원이다. 소비자 입장에서는 내용이 들어있는 버퍼가 카운팅해야 하는 자원이다.

Readers-Writers Problem

공유데이터(DB)에 프로세스가 할 수 있는 연산의 종류에 read와 write 가 있다. readers-writers problem에서는 write는 동시에 하면 안 되지만 read작업은 여러 프로세스가 동시에 할 수 있다
즉 누군가가 Read하고 있는 경우에는 lock을 걸지 않고 같이 읽을 수 있도록 허용할 수 있도록 하는 것이 readers-writers problem이다.
writer가 db에 접근 허가를 얻지 못한 상태에서는 모든 대기 중인 reader들이 다 db에 접근할 수 있도록 해준다. writer는 대기 중인 reader가 하나도 없을 때 db 접근이 허용된다. writer가 db에 접근하여 write 중인 경우 reader들의 접근이 금지된다. writer가 db에서 빠져나가야만 reader의 접근이 허용된다.

이 문제는 아래와 같은 코드로 해결한다.
만약 read할 때 lock을 이용하여 하나의 프로세스만이 read하도록 하면 비효율적이다. 하지만 Read할 때도 write하지 못하게 하기 위해 lock이 필요하다. 그래서 만약 내가 아무도 읽지 않는 상황에서 읽으러 들어온다면 (readcount==1) db에 Lock을 건다. 만약 readcount가 1보다 큰 경우 누가 이미 읽고 있는 경우라면 lock을 걸지 않는다.
그런데 Readcount도 공유변수이기 때문에 그냥 증가시키게 되면 readcount가 원치 않는 결과대로 증가될 수 있다. 그래서 mutex를 사용하여 readcount에 대해 lock을 걸어야 한다. 빠져나갈 때는 mutex로 unlock하며, readcount가 0이 되면 마지막으로 읽고 빠져나가는 프로세스임을 의미하기 때문에 V(db)를 하여 db에 걸었던 lock을 풀어준다.

이때 reader가 lock을 이미 걸어놓은 상태에서는 writer가 도착해도 reader들이 계속 많이 도착한다면 이 writer들은 reader들을 계속해서 기다려야 한다. 이런 상황에서 writer가 지나치게 오래 기다린다면 starvation이 발생할 수 있다. 이런 문제는 큐에 우선순위를 줘 writer가 너무 오래 기다린 상황에서 지나치게 늦게 reader가 들어온다면 writer가 먼저 들어가는 식으로 구현하여 해결할 수 있다.

• mutex : readcount 변수에 대해 lock을 거는 세마포어
• db : 공유 db에 lock을 거는 세마포어

Dining-Philosophers Problem

철학자들은 eat, think의 행동을 할 수 있다. 철학자들이 배가 고파져 eat하는 타이밍은 모두 다르다. 밥을 먹기 위해선 왼쪽 젓가락과 오른쪽 젓가락을 차례대로 잡아야 한다. 옆의 철학자가 젓가락을 잡고 있다면 젓가락을 놓을 때까지 기다린다.
위 코드는 deadlock에 빠질 가능성이 있다. deadlock이란 더 이상 아무것도 진행되지 않고 멈춰있는 상황을 말한다. 만약 모두가 동시에 왼쪽 젓가락을 잡으면 오른쪽 젓가락은 아무도 잡을 수 없기 때문에 아무도 밥을 먹지 못하는 deadlock이 발생한다.

해결방안

• 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
• 젓가락을 두 개 모두 집을 수 있는 상황에서만 젓가락을 집을 수 있게 한다.
  
• 비대칭
  짝수 철학자는 왼쪽 젓가락을 먼저 잡도록 하고 홀수 철학자는 오른쪽 젓가락을 먼저 잡도록 하는 방법이다. 하나의 젓가락이 더 우선순위가 높아 그 젓가락을 잡기 전까진 나머지 젓가락을 잡지 못하기 때문에 문제를 해결할 수 있다.

  추후에 모니터를 사용한 코드를 배우는데 그것이 더 적합하다.

Monitor

세마포어는 P, V연산을 통해 비교적 프로그래밍을 쉽게 만들었지만, 그럼에도 문제가 생겼을 때 버그를 잡는 것이 어렵다. 한번의 실수가 모든 시스템에 치명적인 영향을 미친다.

예를 들어 V↔ P순서가 바뀌는 실수를 하면 mutual exlusion이 깨질 수 있고, P연산하고 V연산이 아니라 실수로 P연산을 하면 deadlock에 빠진다.

그래서 synchronization을 위해 Monitor를 제공한다. 모니터는 특별히 프로그래밍 언어 차원에서 제공하기 때문에 high-level synchronization construct이다. 공유 데이터를 접근하기 위해서는 모니터라고 정의된 내부의 procedure를 통해서만 접근할 수 있도록 만든 것이다.


이렇게 되면 lock을 걸 필요가 없다. 세마포어의 경우 Lock을 걸고 푸는 일을 프로그래머가 해야하지만, 모니터는 기본적으로 모니터에 대한 동시접근을 허락하지 않기 때문에(모니터 내에서는 하나의 프로세스만 활동 가능) 프로그래머는 lock을 걸 필용 없지 그냥 shared data에 접근하면 된다. 나머지 프로세스들은 entry queue에 줄서서 기다리게 한다.

Condition Variable

모니터에서도 자원의 개수를 세는 것이 필요하다.
condition variable은 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 사용된다. 이는 wait와 signal 연산에 의해서만 접근할 수 있다. wait()는 여분이 없어서 기다려야 하면 그 프로세스를 suspend시켜 기다리는 줄에서 기다리도록 해주는 연산이다. signal은 기다리는 줄에 기다리는 프로세스가 있으면 resume시켜 빠져나가게 해주는 연산이다.


위 코드는 생산자 소비자 문제를 모니터 코드로 컨버전한 것이다.
모니터 안에 공유 버퍼가 정의되어 있기 때문에 생산, 소비 작업을 하기 위해선 모니터 내부 코드를 실행해야 한다. 생산자든 소비자든 하나의 프로세스만 모니터 내에서 활성화 되기 때문에 lock을 걸 필요가 없으며 이해하기도 쉽다.