OS #7. 동기화(Synchronization) Part2

지난번 포스팅 동기화 Part1에 이어서 데드락과 동기화의 고전적 문제들에 대해서 정리를 해 보려고 한다.

데드락(교착상태, Deadlock)

데드락은 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만을 기다리며 작업을 더이상 수행하지 않는 상태를 의미한다. 교착상태가 발생하는 조건은 여러가지가 있는데 아래와 같다.

1. 상호 배제(mutual exclusion): 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다. 따라서 배타적인 자원을 사용하면 교착 상태가 발생한다.
2. 비선점(non-preemption): 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다. 어떤 자원을 빼앗을 수 있다면 시간 간격을 두고 자원을 공유할 수 있다. 하지만 자원을 빼앗을 수 없으면 공유할 수도 없으므로 교착 상태가 발생한다.
3. 점유와 대기(hold and wait): 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다. 다른 프로세스의 작업 진행을 방해하는 교착 상태가 발생하려면 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서 또 다른 자원을 기다리는 상태가 되어야 한다.
4. 원형 대기: 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다. 프로세스가 특정 자원에 대해 점유와 대기를 한다고 해서 모두 교착 상태에 빠지는 것은 아니다. 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이루면 프로세스들이 서로 양보하지 않기 때문에 교착 상태에 빠진다.

데드락을 해결하기 위해서는 크게 4가지 정도가 있다. 그들은 예방(prevention), 회피(avoidance), 검출(detection), 회복(recovery) 등이다. 예방은 위에서 기술한 교착 상태가 발생하는 조건들을 하나라도 막는 것이다. 회피는 프로세스에서 자원을 할당할 때 어느 수준 이상 자원을 나누어주면 교착 상태가 발생하는지 확인하여 그 수준 이하로 자원을 나누어 주는 방법이다. 회피 방법의 대표적인 예로 다익스트라가 제안한 은행원 알고리즘(banker's algorithms)이 있다. 검출과 회복은 예방과 회피가 현실적으로 어려운 경우 쓸 수 있는 방안으로, 교착 상태가 발생하는지 여부를 계속 주시하며 만약 교착 상태가 발생하면 이를 해결하기 위해 교착상태 회복 단계를 밟는 것을 의미한다.

그러면 동기화에서 발생하는 세 가지의 고전적인 문제들을 지금부터 살펴보도록 하자

---

Bounded-buffer problem

이 문제는 N개의 버퍼에 여러 생산자와 여러 소비자가 접근할 때 발생하는 문제이다. 여기에서 생산자(producer)는 하나의 아이템을 생산해 버퍼에 저장하는 역할을 하며, 동작 조건은 버퍼 내에 저장할 공간이 있어야 한다는 것이다. 반대로 소비자(consumer)는 버퍼에서 하나의 아이템을 가져오는 역할을 하며, 동작 조건은 버퍼 내에 소비할 아이템이 있어야 한다는 것이다. 생산자와 소비자가 충돌 없이 버퍼를 접근할 수 있도록 버퍼는 임계 영역(critical section)이어야 한다.

위의 Bounded-buffer 도식에서 우리가 주목해야 할 점은 생산자가 Write 하는 동안 다른 생산자는 Write 할 수 없고 어떤 소비자도 Read 할 수 없다는 점이다. 이 문제를 구현하기 위해서는 1차원 배열 Boolean Buffer[n] 으로 선언해서 각각의 배열값을 empty로 초기화 하고, 생산자가 empty인 index를 찾아 full로 바꾸는 방법을 생각해 볼 수 있다. 이 때 중복해서 Write가 선언되지 않게 하기 위해서 mutex 를 이용한 세마포를 생각해 볼 수도 있다. 

The structure of the comsumer process

---

Reader-writer problem

이 문제는 여러 reader와 writer가 하나의 공유 데이터를 읽거나 쓰기 위해 접근하는 상황이다. 여러 Reader가 동시에 데이터를 읽을 수 있다. writer는 공유 데이터에 쓸 수 있는데, 이 때 reader 또는 다른 writer가 작업을 하고 있지 말아야 한다. 즉 READ는 동시에 여럿이 가능하지만 WRITE는 한 번에 하나만 가능하다는 것이다. 아래의 도식을 살펴보자.

이 문제를 해결하기 위해서 필요한 자료구조와 세마포는 다음과 같다. 

• int read_count : 버퍼에 현제 접근하는 reader 숫자를 세는 정수형 변수
• semaphore mutex : writer간 동기화 세마포
• semaphore rw_mutex : read_count와 WRITE의 접근이 원자적으로 수행됨을 보장하기 위한 세마포

writer와 reader의 관점에서 발생하는 process 의사 코드(pseduo code)는 다음과 같다.

The structure ot a writer process

The structure of a reader process

이 해결 방법에는 한 가지 문제점이 존재하는데, 바로 writer가 기아 현상(starvation)을 겪을 수 있다는 점이다. read_count == 0 일 때만 signal(rw_mutex)가 수행되어 대기하고 있던 writer가 수행할 수 있다. 첫 번째 reader(read_count == 1)가 wait(rw_mutex)를 통과하면, 다른 reader들은 writer에 관계없이 계속 진입할 수 있는 구조이다. 여러 reader들이 계속 진입할 경우 read_count == 0 이 더이상 성립하지 않을 수 있고 그러면 writer는 WRITE를 수행할 수 없게 된다. 

---

Dining philosophers Problem(식사하는 철학자들 문제)

식사하는 철학자들 문제는 고전적인 동기화 문제이다. 5명의 철학자가 한 식탁에서 식사를 하는 상황이다. 젓가락은 다섯개 뿐이며, 철학자는 반드시 두 젓가락이 있어야 식사를 할 수 있다고 가정하자. 철학자는 반드시 자신의 왼쪽 또는 오른쪽에 있는 젓가락만 사용할 수 있으며, 식사를 마친 후에는 두 젓가락을 모두 내려놓는다. 우리는 이 상황에서 철학자가 굶지 않게 하는 방법을 고민해야 한다. 여기에서 철학자는 Actor를, 젓가락은 공유되는 data를 의미하는 것이며 우리는 Deadlock과 Starvation이 일어나지 않게 설계를 해야 한다.

Dining philosophers

첫 번째로 생각해 볼 수 있는 방법은 젓가락을 집을 때 동기화를 하는 방법이다. 철학자가 자신의 왼쪽 또는 오른쪽 젓가락부터 집도록 한다. 이 때 세마포는 chopstick[5] 이며 초기값은 1로 설정한다.

The structure of philosopher i

하지만 문제는 두 철학자가 동시에 chopstick[i]를 잡으면 데드락이 발생한다는 점이다. 그래서 이러한 상황이 일어나지 않게 다른 개선 방법을 고민해 보아야 한다. 한 번에 철학자를 4명만 식탁에 둘 수도 있고, 젓가락의 상태를 미리 검사해서 두 젓가락이 모두 사용 가능한 경우만 사용할 수 있게 하는 방법도 있을 수 있다. 또한 철학자에게 번호를 부여하여 홀수인 철학자는 왼쪽의 젓가락을, 짝수인 철학자는 오른쪽의 젓가락을 먼저 집도록 하는 방법도 있다. 하지만 이러한 방법들은 기아 현상까지 해결해 주지는 못한다.

그래서 이 문제를 데드락과 기아 현상까지 한 번에 해결할 수 있도록 하는 방법은, 양쪽의 젓가락을 한꺼번에 집는 방법으로 자료구조 및 세마포를 구현해 주는 것이다. 각 철학자의 상태를 state[5] 배열에 담고 이 배열에는 THINKING, HUNGRY, EATING 세 가지 상태가 들어간다. 문제해결을 위한 세마포에는 젓가락을 집거나 놓는 수행을 관리하기 위한 mutex(초기값 1)와 철학자 각각이 젓가락 두 개를 잡기를 기다리는 세마포 self[5](초기값 0)를 구성해 줄 수 있다. 

The process of a philosopher i

각각의 함수는 다음의 역할을 한다.

• take_chopsticks(int i) : mutex를 통해 진입하여, test(i)를 통해 양쪽의 철학자 상태를 검사한 후, 자신이 먹을 차례를 기다린다.
• put_chopsticks(int i) : mutex를 통해 진입하여, test(LEFT), test(RIGHT)를 통해 양쪽의 철학자 상태를 검사한 후, 먹을 차례를 기다리는 철학자에게 signal을 보내준다. -> test(i)에서 수행
• test(i) : test를 수행한 철학자 i가 HUNGRY 상태이고, 양쪽의 철학자가 모두 젓가락을 집지 않은 상태 not EATING이면 take_chopsticks()에서 wait 했던 자신의 세마포 self[i]에 signal을 보내 eating 상태로 진행

정리하면 이 솔루션은 철학자 좌우 젓가락이 사용 가능할 때 critical section에 진입하는데, i번째 철학자가 식사를 하기 위해서는 i-1 철학자와 i+1 철학자가 EATING 상태가 아니어야 한다. 동기화 알고리즘에서 체크할 요소들에는 다음 처럼 Data consistency가 확보되는지, 데드락이 발생하는지, 기아 현상의 가능성이 있는지, 그리고 동시성(Concurrency)을 얼마나 제공하는지 등을 종합적으로 고려해야 한다.

---

참고자료

1. 고려대학교 유혁 교수님 운영체제(COSE341) 수업 자료
2. <Operating System Concepts> 9th ed. by A. Silberschatz
3. <쉽게 배우는 운영체제> 조성호 저, 한빛아카데미