고전적인 동기화 문제

세마포어와 같은 동기화 도구의 기능을 보여주기 위한 고전적인 동기화 문제들이 있습니다. 이 문제들은 컴퓨터 과학의 동기화 과제들을 추상화한 것으로, 새로운 동기화 기법이 나올 때마다 그 유효성을 검증하는 데 사용됩니다.

---

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

이 문제는 생산자(producer)와 소비자(consumer) 프로세스가 공유하는 유한 버퍼(bounded buffer)를 사용하는 예제입니다. 생산자는 아이템을 버퍼에 넣고, 소비자는 버퍼에서 아이템을 꺼냅니다. 이 해결책은 세 개의 세마포어를 사용합니다. mutex는 상호 배제를 제공하며 초기값은 1입니다. empty는 빈 버퍼의 개수를 세는 카운팅 세마포어로, 버퍼의 총 크기 n으로 초기화됩니다. full은 가득 찬 버퍼의 개수를 세는 카운팅 세마포어이며, 초기값은 0입니다.

---

독자-저자 문제 (The Readers-Writers Problem)

이 문제는 여러 프로세스가 공유 데이터베이스에 접근할 때 독자(readers)와 저자(writers) 간의 접근을 동기화하는 문제입니다. 여러 독자는 동시에 데이터를 읽을 수 있지만, 저자는 데이터를 독점적으로 사용해야 합니다. 해결책은 저자가 이미 공유 객체를 사용할 허가를 받은 경우가 아니라면, 독자는 기다리지 않는 것을 목표로 합니다. 이 때문에 저자가 기아 상태에 빠질 수 있습니다. 해결책은 rw_mutex와 mutex라는 두 개의 세마포어, 그리고 독자의 수를 세는 read_count 변수를 사용합니다.

---

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

다섯 명의 철학자가 원탁에 앉아 생각하거나 식사합니다. 식사를 하려면 양옆에 있는 두 개의 젓가락을 모두 잡아야 합니다. 이 문제를 해결하기 위해 각 젓가락을 세마포어로 표현하고, 철학자가 젓가락을 잡을 때 wait()를, 놓을 때 signal()을 호출하는 간단한 해결책이 가능합니다. 하지만 이 방법은 모든 철학자가 동시에 왼쪽 젓가락을 잡으면 아무도 오른쪽 젓가락을 잡지 못해 교착 상태(deadlock)가 발생할 수 있습니다.