[OS] 동시성 (3) - 고전적인 동기화 문제

✅ Classical Problems of Synchronization

✔️ Producer-Consumer Problem (Bounded-Buffer Problem)

• 생산자 스레드들과 소비자 스레드들이 있고, 사이에 공유 버퍼가 있다고 가정, 둘 이상의 생산자가 비어있는 버퍼를 동시에 보고 데이터를 만들어 넣는다면 문제가 발생
• 마찬가지로 둘 이상의 소비자가 동시에 동일한 버퍼의 데이터를 사용한다면 문제 발생 ⇒ 따라서 동시에 버퍼에 접근할 수 없도록 락을 걸어줘야 함
  • 또 버퍼가 꽉 찬 상태에서 생산자는 반드시 소비자가 버퍼의 데이터를 사용하길 기다려야 하고, 버퍼가 빈 상태에서는 소비자는 생산자가 버퍼를 채우기를 기다려야 함
• 락을 걸고 푸는 용도, 자원의 개수를 카운팅하는 용도로 세마포어 변수를 사용

✔️ Readers-Writers Problem

한 프로세스가 데이터를 수정하는 작업을 수행할 때 다른 프로세스가 접근하면 안되고, 읽는 작업은 여러 프로세스가 동시에 수행 가능하도록 하는 문제

• 데이터에 대해 하나의 Lock을 사용하게 되면 데이터의 일관성은 지킬 수 있으나, 여러 프로세스가 동시에 읽을 수 있음에도 불구하고 한 프로세스만 읽도록 강제하는 것이므로 비효율적

따라서 현재 수정하려고 하는 프로세스가 없다면 모든 대기 중은 Reader들의 접근을 허용하고, Writer는 대기 중인 Reader가 하나도 없는 경우 접근하도록 함

• Writer가 접근 중이라면 Reader들은 접근할 수 없도록 함
• N개의 reader가 기다리고 있다면, 제일 처음인 reader만 wrt 세마포어에 넣고 나머지 n-1 개의 reader는 mutex 세마포어 큐에 넣어둠으로써 효율성을 높임
• Reader-Writers Problem의 해결책은 Starvation의 가능성이 존재
  • 계속해서 reader 혹운 writer가 들어오는 경우 한쪽이 수행되지 않을 수 있음
  • 큐에 우선순위를 부여한다거나, 일정 시간이 지나면 자동으로 write or read가 되도록 하여 해결

✔️ Dining-Philosophers Problem

5명의 철학자가 원탁에 둘러 앉아있고, 젓가락이 5개 놓여있을때

각 철학자는 식사를 하기를 원하고, 철학자가 식사하기 위해서는 양쪽 젓가락을 모두 집어야 함

• 이는 큰 규모로 동시성을 제어해야 하는 상황에 대한 비유이다.
• 여러 개의 자원을 다수의 프로세스 간에 Deadlock, Starvation 없이 잘 분배해야 한다.

해결법(세마포어)

• 이처럼 구현하면 이웃한 두 철학자는 동시에 먹는 경우가 없다는 것이 보장되지만 모두 왼쪽에 있는 젓가락을 들었다면 데드락 상태에 빠지게 됨

Mutual Exclusion을 만족하지만, Deadlock이나 Starvation을 방지할 수 없다.

개선 사항

• 데드락을 방지하기 위해 4명의 철학자가 테이블에 동시에 앉도록 함
• 젓가락을 두 개 집을 수 있을 때만 젓가락을 집도록 함
• 짝수/홀수 철학자는 왼쪽/오른쪽 젓가락을 먼저 집도록 함
  

위 방법으로 Mutual Exclusion과 Deadlock은 해결할 수 있지만, Starvation은 아직 발생할 수 있다.

Monitor Solution

• 철학자는 양쪽의 젓가락이 모두 사용가능할 때만 식사를 한다.
• 철학자는 3개의 상태를 갖는다.
  • thinking, hungry, eating
• 철학자는 양 옆의 철학자가 모두 eating 상태가 아닐 때만 식사를 할 수 있다.
• 철학자가 배고프지만 젓가락을 사용할 수 없을 때, 대기할 수 있도록하는 Condition Variable을 사용한다.