[운영체제] 동기화 (2)

Bounded-Buffer 문제 (유한버퍼 문제)

---

소비자와 생산자가 유한 개의 버퍼 자원을 공유하는 상황에서, 다음 문제를 해결하고자 한다.

1. 소비자와 생산자가 버퍼에 상호 배타적으로 접근
2. 소비자는 버퍼에 원소가 한 개라도 있으면 버퍼를 소비해야 하고, 생산자는 버퍼에 원소가 없으면 원소를 생산해야 한다.

Bounded-Buffer 문제 해결을 위한 코드

위의 문제를 해결하기 위한 조건은 다음과 같다.

• 생산자가 먼저 실행된 적이 있어야 하고, 생산자의 실행 횟수가 소비자보다 많아야 한다.

위 문제를 해결하기 위해 사용하는 변수는 다음 세 가지이다.

• 세마포어 mutex(= 1): 생산자와 소비자의 상호배제를 위한 변수
• 세마포어 empty(= n): 비어있는 버퍼의 개수를 나타내는 변수
• 세마포어 full(= 0): 버퍼가 차있는 개수를 나타내는 변수

 

 

Reader-Writer 문제 (독자-저자 문제)

---

여러 개의 reader는 공유 데이터를 동시에 읽는 것이 가능한 반면에, writer는 reader가 공유 데이터를 읽는 동안 공유 데이터에 접근해서 수정할 수 없다.

Reader-Writer 문제는 2가지가 있다.

1. First reader-writer problem: writer가 대기하고 있다고 해서 reader가 다른 reader를 기다리면 안 된다. 마지막 reader가 공유자원을 release 하면 writer가 임계구역으로 진입한다.
2. Second reader-writer problem: 만약 writer가 대기하고 있다면, 어떠한 새로운 reader도 실행될 수 없다.

위 두 가지 모두 starvation의 가능성이 있다.

1. 새로운 reader가 계속 들어오면 writer는 계속 기다려야 한다.
2. 새로운 writer가 계속 들어오면 reader는 계속 기다려야 한다.

First reader-writer 문제 해결을 위한 코드

First reader-writer 문제 해결을 위해 사용하는 변수는 다음 세 가지이다.

• 세마포어 rw_mutex (= 1): reader와 writer의 상호배제를 위한 변수
• 세마포어 mutex (= 1): read_count를 갱신하기 위한 reader 간의 상호배제를 위한 변수
• 정수 read_count (= 0): 공유자원을 읽고 있는 reader의 개수를 나타내는 변수

위의 코드는 reader가 수행되는 동안 writer가 임계구역에 진입하는 것을 배제함으로써 First reader-writer 문제를 해결하지만, 이는 writer에게 starvation을 야기할 수 있다.

 

 

Dining-Philosophers 문제 (식사하는 철학자 문제)

---

철학자 5명이 원형 테이블에 앉아있다.

각 철학자들은 식사를 하기 위해서 젓가락 2개가 필요하며, 젓가락은 철학자의 왼쪽과 오른쪽에 위치한다.

각 철학자들은 한 번에 한 개의 젓가락만 집을 수 있다.

철학자가 식사를 하지 않는 동안에는 생각을 하는데, 생각을 하는 동안 다른 철학자들과 교류하지 않는다.

 

 

여기서 일반적인 해결법은 다음과 같다.

왼쪽의 코드는 각 철학자들이 자신의 왼쪽 젓가락을 먼저 집고, 오른쪽 젓가락을 집는다.

젓가락을 다 집은 후, 식사를 하고 다시 왼쪽 젓가락을 놓고 오른쪽 젓가락을 놓는다.

만약 한 명의 철학자가 젓가락을 모두 집어 든다면 그 철학자는 식사할 수 있고, 다른 철학자는 그 철학자의 식사가 끝날 때까지 대기한다.

하지만 모든 철학자가 동시에 자신의 왼쪽의 젓가락을 집어 드는 경우 Deadlock이 발생한다.

따라서 이 방법은 올바른 해결법이 아니다.

Deadlock 문제를 해결하기 위해 다음과 같은 3가지 방법이 존재한다.

• 5명의 철학자 중 4명만 식사를 할 수 있게 한다.
• 양쪽의 젓가락을 집을 수 있을 때, 동시에 그 젓가락을 집게 한다.
• 홀수번째 철학자는 왼쪽-오른쪽 순으로, 짝수번째 철학자는 오른쪽-왼쪽 순으로 젓가락을 집게 한다.