동기화 예제

Bounded Buffer Problem

• 문제점: 첫째로 count가 shared resource이지만 critical section이 보호되지 않으며, 둘째로 busy waiting을 사용해서 CPU Utilization이 떨어진다.

• 세마포어: 3가지의 세마포어를 사용해서 문제를 해결한다.

  • mutex는 lock을 걸기 위해 사용하는 바이너리 세마포어이다.
  • empty와 full은 카운팅 세마포어로 busy waiting을 사용하지 않도록 한다. Producer 프로세스가 큐 안에 데이터를 넣을 때 count가 N과 동일하면 busy waiting을 하도록 구현되었는데, wait(empty)를 통해 빈 공간의 개수를 의미하는 세마포어 empty의 티켓이 존재할 때만 진입할 수 있도록 한다. empty=0은 큐가 가득 찼다는 뜻이다.

• Producer는 empty에서 진입한 경우 mutex를 통해 lock을 걸고 shared resource에 접근하며 작업이 끝나고 signal(mutex)를 통해 mutex를 풀어주고 signal(full)을 통해 full 세마포어의 값을 1 증가시킨다.

• Consumer는 데이터가 들어가 있는 공간의 개수인 full이 1 이상일 때만 shared resource에 접근할 수 있으며, 만약 full이 0인 상황이라면 wait에서 기다리고 있다가 context switching되어 Producer에서의 signal이 실행되면 접근할 수 있게 된다.

  

Readers and Writers Problem

• 문제점: 여러 개의 동일한 프로세스들이 하나의 shared resource에 읽거나 쓰는 동작을 한다. 쓰는 작업은 mutually exclusive하게 동작해야 하지만, 읽는 작업은 여러 명이 접근해도 상관없다. Writer의 작업은 공유 자원을 오염시킬 수 있기 때문이다.

• Writer 프로세스는 exclusive하게 동작해야 하며, 다른 Reader, Writer 프로세스와 동시에 접근하면 안 된다. 문제를 해결하기 위해 3개의 세마포어를 사용한다:

  • wrt는 쓰기 작업 세마포어로 쓰기 작업을 할 수 있는 권한을 하나의 프로세스에만 준다. Writer의 작업을 mutually exclusive하게 만든다.
  • mutex 세마포어는 Reader가 읽기 작업을 하려면 wait(mutex)를 통해 세마포어가 있어야 허용함으로써 readcount를 보호한다. readcount 세마포어는 읽고 있는 프로세스의 개수를 나타낸다. readcount가 0이 되어야 쓰기 작업을 수행할 수 있다.

• readcount, wrt, mutex는 전역 변수로 선언이 되는데, 멀티스레드 환경에서 동작하기 위해 전역 변수로 사용할 수밖에 없지만 사용 시 주의가 필요하다. 쓰기 작업을 원하는 프로세스는 readcount 세마포어가 0이 될 때까지 wait한다.

• 읽기는 mutex 세마포어를 사용해서 readcount 값 증가시키는 critical section을 보호한다. 읽기가 끝나면 readcount를 감소시키고 readcount가 0이라면 Writer 프로세스는 wrt 세마포어를 획득하여 쓰기 작업을 진행한다.

  

Dining Philosopher Problem

• 정의: 다익스트라가 만든 데드락을 검증하기 위한 가상의 동기화 문제이다. 철학자들이 앉아 있는 원탁이 존재하고 사람 사이에 젓가락이 하나씩 놓여 있다. 철학자는 앉아서 생각하다가 배고프면 양쪽에서 젓가락을 잡아서 밥을 먹고 돌려놓은 다음 다시 생각한다. 철학자들은 왼쪽 젓가락이 사용 가능하면 왼쪽 젓가락을 먼저 잡고 오른쪽 젓가락이 사용 가능하면 가져와서 밥을 먹고 오른쪽 젓가락을 내려놓은 다음 왼쪽 젓가락을 내려놓는다. 만약 오른쪽 젓가락이 사용 중이면 기다린다.

• 여기서 철학자는 프로세스이고 젓가락은 shared resource이다. 만약 모든 철학자가 동시에 왼쪽 젓가락을 잡는다면, 모든 철학자들이 자신의 오른쪽 젓가락이 사용 가능해질 때까지 기다려야 한다. 이렇게 되면 모든 철학자가 영원히 굶는 상황이 되며, 여기서 나온 단어가 starvation이다. 모든 프로세스가 다른 프로세스가 사용 중인 자원을 기다리는 이런 상황을 deadlock이라고 한다.

• 해결 방법: 왼쪽과 오른쪽 젓가락을 한 번에 가져오는 것이 아니라 철학자들의 상태를 세마포어로 두고, 왼쪽과 오른쪽의 철학자가 먹고 있는지를 고려하고 두 개를 동시에 pickup하도록 한다.

  

  • mutex는 상호 배제를 위한 세마포어이고, s는 자신이 pickup 가능한 상태인지를 알려주는 세마포어이며, state는 철학자들의 상태를 저장한다. 철학자들은 thinking, hungry, eating 중 하나의 상태를 가진다.
  • 철학자가 젓가락을 가져오려면 hungry 상태가 되어야 하고, pickup을 수행할 때는 자신의 상태를 hungry로 변경하고 test를 수행한다. 왼쪽, 오른쪽의 철학자가 먹고 있는 상태가 아니면 eating으로 상태를 바꾸고 내가 먹을 수 있는지에 대한 세마포어인 s[i]를 signal로 반환한다. 그러면 pickup에 있는 wait을 수행할 수 있게 된다.
  • putdown을 수행할 때도 critical section을 보호하고 내 상태를 think로 바꾼 다음 왼쪽과 오른쪽에 test를 수행해서 가져가라고 알려준다. 중요한 점은 젓가락이 아닌 철학자들의 상태값을 세마포어로 잡는 것이다.

데드락

데드락의 정의

• 상황: 두 개 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다리며 무한히 대기하는 상태에 빠지는 것. 세마포어와 같은 동기화 툴을 사용하면서 발생하는 문제이다.

데드락 발생 조건

1. Mutual Exclusion: 한번에 한 프로세스만 리소스에 접근할 수 있다.