Seungho Jeong

Backend Problem Solver (feat. Python)

게시:

본 포스팅은 Bounded-Buffer Problem(Producer-Consumer Problem), Readers & Writers Problem, Dining-Philosophers Problem의 내용과 솔루션에 대하여 다룬다.

Bounded-Buffer Problem (Producer-Consumer Problem)

순환하는 유한한 거공유 버퍼(Bounded Circular-Buffer)에 생산자 프로세스(Producer process)와 소비자 프로세스(Consumer process)에 대한 문제이다. 생산자는 데이터를 생산하여 Buffer에 집어넣는 프로세스이고, 소비자 프로세스는 Buffer에 있는 데이터를 꺼내 쓰는 프로세스를 의미한다.

Bounded-Buffer Problem

각 프로세스가 여러 개라고 가정할 때 공유 버퍼에는 다음과 같은 문제가 발생한다.

  1. 생산자의 공유 버퍼에 대한 데이터 입력 및 조작 경합(또는 소비자의 데이터 꺼내기 경합)
  2. 공유 버퍼의 유한함으로 인한 버퍼 Full 또는 Empty 문제
    • 버퍼에 데이터가 가득찬 상태에서 생산자 프로세스가 도착한 경우나, 공유 버퍼가 텅 빈 상태에서 소비자 프로세스가 도착한 경우가 이에 해당한다.

위의 문제는 세마포어(Semaphore)를 활용하여 다음과 같이 극복할 수 있다.

  1. 데이터 입력 및 조작 시 공유 버퍼 Lock 및 데이터 입력 또는 조작 후 Unlock.
    • Binary Semaphore를 활용하여 Shared Exclusion을 확보.
  2. 공유 버퍼가 Full 또는 Empty 상태일 때 가용 자원의 수를 Counting.
    • Integer Semaphore를 활용하여 남은 Full･Empty 버퍼의 수를 표시.
    • 공유 버퍼가 Full(또는 Empty)이면 생산자(또는 소비자)를 Block시켜 Queue로 보낸다.
Solution(Pseudo code)
생산자(Producer)와 소비자(Cunsumer)의 full, empty 변수에 대한 P, V 동작이 서로 반대다.

Readers and Writers Problem

데이터베이스(DB)에 대한 문제이다. 공유 자원은 DB이고 두 종류(Readers와 Writers)의 프로세스가 존재한다. Readers는 DB의 데이터를 읽고, Writer는 DB 데이터를 쓴다. 이 문제에서도 각 프로세스는 하나가 아닌 여러 개인 경우를 가정한다.

동시에 여러 개의 Readers 프로세스가 데이터를 읽는 것은 데이터의 무결성에 문제를 주지 않기 때문에 문제가 없지만 여러 개의 Writer 프로세스가 동시에 데이터를 쓰는 것은 문제가 된다. 또한 Readers 프로세스가 데이터를 읽고 있을 때 Readers 프로세스가 접근하는 것은 문제가 안되지만 Writers 프로세스가 접근하는 것은 문제가 된다.

이와 같은 문제는 다음 Pseudo code와 같이 해결할 수 있다.

Solution(Pseudo code)

Reader 프로세스가 mutex를 얻는 것은 readcount도 공유 데이터이기 때문에 상호 배제 조건을 만족시키기 위해서이다. 최초로 읽은(if (readcount == 1)) 프로세스이면 db를 얻는데 이 때 Reader 프로세스는 접근할 수 있고 Writer 프로세스만 차단한다.

모든 Readers 프로세스가 데이터를 읽은 이후 마지막으로 읽고 나가는(if (readcount == 0)) 프로세스는 db를 반납하여 Writer를 활성화 시킨다.

Dining Philosophers Problem

이 문제의 조건은 다음과 같다. 원탁에 \(n\)명(여기에서는 5명)의 철학자가 있고 철학자와 철학자 사이에는 젓가락(총 \(n\)개, 여기에서는 5개)이 있다. 철학자는 두 가지 동작을 할 수 있는데 참고로 젓가락 두 개를 동시에 들 수는 없다.

  1. 배고프면 양 쪽의 젓가락을 들어 밥을 먹는다.
  2. 밥을 먹었으면 젓자락을 놓고 생각한다.

위와 같은 조건과 동작을 Pseudo code로 나타내면 다음과 같다.

Dining Philosophers Problem
젓가락 두 개를 동시에 잡을 수 없다. 하나만 잡을 수 있다.

별 문제가 없어 보일 수도 있지만 이 코드는 Deadlock의 가능성이 있는 잘못된 코드이다. 만약 5명의 철학자가 모두 동시에 배가 고파지면(P 연산하면) 서로 상대방에 의해 충족될 수 있는 이벤트를 무한히 기다리게 되기 때문이다.

이를 해결할 수 있는 방법은 다음과 같다.

  1. n-1명(여기에서는 4명)의 철학자만 동시에 젓가락을 집을 수 있도록 제한한다.
  2. 젓가락을 양쪽 다 집은 수 있는 상황에서만 젓가락을 집을 수 있도록 한다.
  3. 홀수(또는 짝수) 철학자는 왼쪽, 짝수(또는 홀수) 철학자는 오른쪽을 먼저 집게 한다.

이중 2번 솔루션을 코드로 나타내면 다음과 같다.

Solution(Pseudo code)
semaphore self[5]=0;으로 초기화하였는데 이는 Semaphore에 맞지 않다.

semaphore self[5] = 0;[1] 변수는 젓가락을 집을 수 있는 권한을 의미하고 mutex는 상호 상태 변경에 영향을 줄 수 있는 문제를 막기 위하여(상호 배제 조건을 충족시키기 위하여) 선언된 변수이다.

젓가락을 들면 상태가 hungry로 바뀌고 테스트 함수(test(i))가 실행된다.

테스트 함수의 내용을 보면 내 상태가 hungry이고, 왼쪽 철학자의 상태가 eating이 아니고, 오른쪽 철학자의 상태가 eating이 아닌 경우에만 내 상태를 eating으로 바꾸고 젓가락을 집을 수 있는 권한을 준다. 테스트를 통과하면 젓가락(자원)을 내려놓고(P(self[i])) 함수가 끝난다.

만약 테스트에서 왼쪽 철학자 또는 오른쪽 철학자의 상태가 eating이라면 i는 젓가락을 집을 권한을 얻지 못하게 된다. 이러한 경우 P(self[i])하더라도 젓가락을 집을 권한이 없기(self[i]=0) 때문에 연산이 수행되지 않고 self[i] = 1이 될 때 까지 기다리게 된다.

젓가락을 집을 권리를 얻지 못하는 문제는 인접한 철학자가 밥을 먹고 있기 때문에 발생하는데 코드를 살펴보면 젓가락을 집을 권리 또한 인접한 철학자가 밥을 먹고 난 뒤에 주는 것을 확인할 수 있다.

철학자가 밥을 다 먹고 젓가락을 내려놓으면 상태를 thinking으로 바꾸고, 혹시 인접한 철학자 상태가 hungry 상태인데 내가 eating 상태인 바람에 젓가락을 못 집고 있는 상황이라면 집을 수 있도록 인접한 철학자에 대해 테스트 함수를 실행한다.

예를 들어 왼쪽 철학자에 대하여 테스트 함수를 실행하면, 왼쪽의 철학자 입장에서 인접한 철학자 중 적어도 한 명(오른쪽) 철학자는 eating 상태가 아니기 때문에 hungry 상태이면 나머지 한 명의 철학자만 eating 조건이 아니라면 젓가락을 집을 수 있도록 V(self[i]) 값을 주게 된다.

만약 P(self[i])를 못하고 있었다면 그제서야 P(self[i])를 빠져 나와서 \(1\)이던 값을 \(0\)으로 바꾸고 pickup 함수를 빠져나와 밥을 먹게 되는 것이다.

각주

1 : 보통 Binary semaphore는 자원의 값을 초기 값으로 갖고, 1 이상의 값으로 초기화하는데 이 경우 독특하게 0으로 초기화하고 테스트 하는 단계에서 권한을 주도록 독특하게 짜여져 있다. 이는 세마포어의 컨셉과 다른 부분이라고 한다.

Reference

반효경, “반효경 [운영체제] 14. Process Synchronization 3”. KOCW. 2014년 4월 8일. video, http://www.kocw.net/home/cview.do?lid=c5e572cd1319ca6b


OS 시리즈 모두보기 (펼치기)


댓글남기기