[운영체제] 14. 세마포어와 동기화 문제와 해결 (Bounded-Buffer, Readers-Writers Problem, 식사하는 철학자 문제)

1. Bouned-Buffer Problem 

공유 데이터에 관련한 고전적인 '동기화' 문제이다. producer-consumer 문제라고도 한다. 

문제점 

1) Producer 

발생 할 수 있는 문제 : 생산자는 데이터를 만들어서 집어 넣는 역할. 생산자 둘이 동시에 비어있는 버퍼에 도착하는 경우, 동시에 데이터를 생성하게 되면 문제가 발생한다. 

해결 방법 : 공유 데이터에 lock 을 걸어서 다른 producer 및 consumer 가 접근하지 못하도록 방지한다. 그 후, 데이터 입력 작업이 끝나면 Lock 을 해제 하여 다른 producer나 consumer가 접근할 수 있도록 한다. 그리고 full buffer를 하나 증가시킨다. (buffer count)

2) Consumer 

발생할 수 있는 문제 : consumer 여러명이 동시에 같은 데이터를 꺼내가려고 할 때 문제가 발생할 것이다. 

해결 방법 : buffer에 Lock 을 걸어서 데이터를 가져간 이후에 lock 을 해제한다. 그리고 비어있는 buffer 를 하나 증가시킨다. (buffer count)

3) 유한한 버퍼 (bounded-buffer) 여서 생기는 문제점 

생산자들이 한꺼번에 도착해서 버퍼가 full 인 상태에서 또 생산자가 오게 되면 문제가 생길 것이다. 생산자 입장에서는 '비어있는 Buffer'가 자원이며, 이 상태에서는 생산자가 사용할 수 있는 자원의 개수가 없는 것이기 때문이다. (buffer size == 0)

소비자가 나타나서 데이터를 꺼내가야만 생산자가 다시 와서 데이터를 집어넣을 수 있을 것이다. 

반면 소비자 입장에서도 꺼내갈 데이터가 없다면 문제가 발생할 것이다. 

문제 해결을 위한 변수들 

• int n;
• semaphore mutex = 1;
  공유 버퍼에 lock 을 걸기위한 semaphore (상호 배제)
• semaphore_empty = n;
  semaphore_full = 0;
  가용 자원의 개수를 count해야 한다. 

 

2. Readers-Writers Problem 

공유 데이터를 Database 라고 본다. 주로 reader와 writer 작업이 있는 상황이 DB이기도 하다. 

write 는 동시에 여럿이서 진행할 수 없지만, read 작업은 여럿이서 진행하여도 동기화와 관련하여 문제가 발생하지 않는다.

문제점

read작업을 수행 할 때, lock 을 걸어야 write 작업을 방지할 수 있을 것이다. 다만, 다른 read 작업 또한 허락해야 한다.  이러한 문제를 해결하기 위해서 등장한 것이 readcount라는 공유 변수이다. 이 변수 값을 변경하는 것은 모든 reader들이 할 수 있다. writer 의 경우에는 한 process가 DB에 write 중일 때 다른 Process가 접근하면 안된다.  

Shared Data

•  DB 그 자체 
•  readcount; (현재 DB에 접근중인 reader의 수)

위의 코드상에서 readcount 가 1 일때 lock 을 거는 것은 이미 다른 읽기 작업을 하는 reader들이 없으므로, lock 을 걸어도 괜찮다는 의미에서 writer 작업을 block 시키기 위함이다. 

한편, readcount가 0일 때는 읽기 작업이 모두 수행되었다는 의미이므로 다시 writer 작업을 할 수 있도록 lock 을 해제한다. 

동기화를 위한 변수 

• mutex : 공유변수인 readcount에 접근하기 위한 코드 (= critical section)의 상호배제 보장을 위해 사용
• db : reader와 writer가 공유 DB를 올바르게 접근하게 하는 역할 

Starvation 문제 발생 

writer의 입장에서 -> reader 가 lock 을 건 상황에서는 reader 들이 다 빠져나간 후에 lock 이 해제될 때까지 기다려야 한다. reader들이 작업을 다 끝날 때까지 writer가 지나치게 오래 기다리게 되는 경우(starvation)가 발생할 수도 있다

따라서 이를 해결하기 위해 위의 코드를 어느정도의 reader가 지나간 후에 writer에게 자원을 주는 방식으로 개선할 수 있다. 

 

3. 식사하는 철학자 문제 

5명의 철학자가 식사를 한다. 여기서 chopstick이 공유자원이 된다. 철학자는 왼쪽 젓가락과 오른쪽 젓가락을 집어서 식사를 하고싶다. 

문제 상황

위의 코드에서 5명의 철학자가 동시에 배고파서 왼쪽 젓가락을 집게되면, 오른쪽 젓가락을 집을 수 없다. 즉 영원히 식사를 할 수 없게 된다! -> deadlock 이 발생 

해결방안 

• 4명의 철학자만이 테이블에 동시에 앉을 수 있게 한다. 
• 젓가락을 두 개 모두 집을 수 잇을 때만 젓가락을 집을 수 있게 허용한다. 
• 짝수 철학자는 왼쪽 젓가락부터 집고 홀수 철학자는 오른쪽 젓가락부터 집도록 한다. (하나의 젓가락이 더 우선순위가 높게 설정)

세마포어로 해결한 식사하는 철학자들 문제

• 세마포어로 해결하는 방법에서는 각각의 젓가락을 세마포로 표현한다. 
• mutex 는 본인만이 상태를 바꿀 수 있는 것이 아니라 여러 철학자가 동시에 상태를 바꿀 수 있기 때문에 공유 변수로 둔다. 

pickup() 코드는 젓가락을 잡는 함수이다. test 단계에서 주변 철학자들이 밥을 먹고 있지 않으면서 && 나의 state가 hungry 라면 state를 eating으로 바꾸고 젓가락을 잡을 수 있도록 권한을 바꾼다. 

putdown() 코드는 젓가락을 내려놓는 함수이다. state를 바꾼 후 인접한 왼쪽 오른쪽 철학자들이 hungry 한 상황이었다면 밥을 먹게 할 수 있도록 한다. 

 

Semaphore의 문제점 

정확성의 입증, 코드 작성의 어려움, 한번의 실수가 모든 시스템에 치명적인 영향을 준다. 

Monitor 해결방법 

• 공유데이터를 접근하기 위해서는 Monitor 라고 정의된 내부 proceduer를 통해서만 접근할 수 있도록 만들어 놓은 방법 
• 세마포어와 달리 Monitor 방식에서는 lock 을 걸 필요가 없다. Monitor는 기본적으로 Monitor에 대한 동시접근을 허락하지 않는다. 
• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능함 
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없음 
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable을 사용 

condition variable 은 wait와 signal 연산에 의해서만 호출 가능하다. 

예시) Bounded-Buffer Problem