[운영체제] 6. 프로세스 동기화 (4) - 식사하는 철학자 문제

 

그림과 같이 음식과 포크가 주어져있다.

이때 각 음식 앞에는 철학자들이 있고, 철학자들은 생각을 하거나 음식을 먹는다.

 

철학자들은 다음과 같은 순서로 식사를 진행한다.

 

1. 생각을 하다가 왼쪽 포크가 사용가능하면 집는다.

2. 생각을 하다가 오른쪽 포크가 사용가능하면 집는다.

3. 두 포크를 모두 집었다면 일정시간 식사를 한다.

4. 식사를 마치고 오른쪽 포크를 내려둔다.

5. 왼쪽 포크를 내려둔다.

6. 1~5반복

 

이를 코드로 구현하면 아래와 같다.

 

 

 

이때 만약 모든 철학자가 동시에 식사를 시작하면 모두 동시에 왼쪽 포크를 집어들고 오른쪽 포크를 서로가 영원히 기다리므로 식사를 할 수 없게 된다. 이렇게 서로가 이미 점유한 자원에 서로 의존하여 모든 프로세스가 동작을 멈추는 상황을 '데드락(교착 상태)' 이라고 한다.

따라서 위와 같은 코드는 식사하는 철학자 문제를 올바르게 해결하지 못한다.

 

교착 상태가 발생하려면 4가지 조건이 필요하다.

1. 상호 배제

2. 점유와 대기 (왼쪽 포크를 든 채로 대기)

3. 비선점 (다른 철학자의 포크를 뺏을 수 없다.)

4. 원형 대기 (서로가 서로의 자원을 요구하면서 고리 형태를 이루는 것)

 

이 4가지 중 하나라도 만족하지 않으면 데드락은 발생하지 않는다.

따라서 한가지씩 없애면서 데드락 문제를 해결해보자.

 

1. 상호 배제

상호 배제를 제거한다는 것은 두 철학자가 같은 포크로 식사를 한다는 것과 같다.

상호 배제는 레이스 컨디션을 방지하기 위해 필수적이므로 제거할 수 없다.

 

2. 점유와 대기

데드락이 발생한 근본적인 이유는 식사를 하기 전에 왼쪽 포크를 집은 채로 기다리는 것에 있다.

따라서 왼쪽 포크를 집고나서 오른쪽을 봤을 때 누군가 이미 집었다면 왼쪽 포크를 내려두고, 일정 시간이 지난 다음에 다시 확인한다.

 

하지만 이 문제도 완벽한 해결책은 될 수 없다.

5개의 프로세스가 동시에 왼쪽 포크를 집고, 확인하고 내려놓고를 반복할 수 있기 때문이다.

 

(다른 책에서는 점유와 대기로 문제를 해결할 수 있지만, 이 경우 특정 프로세스에게 자원을 몰아주는 효과를 주기 때문에 자원 활용률이 낮아지고, 필요한 자원을 기다리는 프로세스와 사용되지 않으면서 오랫동안 다른 프로세스에게 할당되는 자원을 양산할 수 있다. 마지막으로 각 프로세스마다 필요한 자원의 개수가 다를 텐데, 이 해결책은 많은 자원을 필요로 하는 프로세스에게 불리한 해결책이다. 따라서 많은 자원을 필요로 하는 프로세스 일수록 더 오래기다리는 기아 문제가 발생할 수 있다.)

 

3. 랜덤 시간 대기

데드락 발생 조건과 관련은 없지만, 위에서 말한 문제는 모든 철학자가 동시에 집고, 같은 시간을 기다렸다가 동시에 내려놓기 때문에 발생하였다.

그렇다면 왼쪽 포크를 집고나서 오른쪽 포크를 집기를 시도한 뒤 실패했을 때 다시 시도하기까지 기다리는 시간을 랜덤으로 두면 어떨까?

하지만 이것도 완벽한 해결책은 아니다. 정말 낮은 확률이지만 각자의 대기 시간이 우연히 모두 일치할 수도 있기 때문이다.

 

그럼에도 이런 확률은 매우매우 낮기 때문에 실제로는 이 알고리즘을 사용하기도 한다고 한다. (이더넷 등)

물론 원자력 발전소와 같이 낮은 확률이지만 발생했을 때 치명적인 문제를 일으킬 수도 있는 시스템에서는 사용할 수 없을 것이다.

 

4. 비선점

비선점 조건을 제거한다는 것은 다른 프로세스가 점유한 자원을 강제로 뺐을 수 있도록 한다는 말과 같다.

비선점 조건을 제거하면 데드락은 확실히 발생하지 않는다.

 

이 방식은 CPU 같이 일정 시간이 지난 뒤 강제로 내려와야 하는 선점형 자원의 경우에 대해서는 효과적이다.

하지만 한 프로세스의 작업이 끝날 때까지는 다른 프로세스가 점유할 수 없는 비선점형 자원도 존재한다.

따라서 이 해결책도 범용성이 떨어지는 해결책이다.

 

5. 원형 대기

모든 자원에 번호를 붙이고 오름차순으로만 자원을 할당한다.

이는 마치 철학자들이 일렬로 앉아서 식사를 하는 것과 같다.

(이러면 1번 포크를 집어야 하는 철학자는 영원히 식사를 못하지 않나?)

 

하지만 모든 자원에 번호를 매기는 것도 힘들고, 어떻게 번호를 매기는지에 따라서 특정 자원의 활용도가 떨어질 수 있기 때문에 쉬운 문제는 아니다.

 

6. 세마포

철학자들이 생각을 하고나서 포크를 집거나 내려놓는 과정을 바이너리 세마포로 감싼다.

그러면 누군가 포크를 집었을 때 다른 사람이 포크를 집으려고 하면 세마포에 의해 막혀서 Blocked 상태로 빠진다.

(다른 포크를 사용하는 것이라고 하더라도)

 

이 해결책 역시 데드락 문제는 해결하지만 한번에 최대 1명의 철학자만 식사할 수 있어서 성능 문제가 발생한다.

원형으로 둘러앉았을 때 나의 맞은편 사람과 함께 동시에 식사를 할 수 있음에도 일단 포크를 집기만 하면 모두가 포크를 집을 수 없게 되기 때문이다.

 

다음 코드는 이 문제를 해결한 코드이다.

 

 

 

각 철학자는 THINKING, HUNGRY, EATING 3가지 상태 중 하나를 가질 수 있다.

그리고 각 철학자의 상태와 mutex 라는 상호배제를 위한 변수를 둔다.

 

각 철학자 프로세스는 i 라는 번호를 가지며, 생각하고, 두 포크를 집고, 먹고, 포크를 내려놓는다.

(두 포크를 동시에 집어든다!)

 

 

 

먼저 2번 프로세스가 실행되었다고 해보자.

그러면 think(); 를 호출하여 생각을 하고, take_forks(2) 를 호출하면, 2번 철학자 기준 좌우의 포크를 집는다.

이 함수를 따라가보면 먼저 mutex 변수를 감소시켜 임계 구역에 진입하고, HUNGRY 상태로 들어온 뒤 test() 함수를 호출한다.

 

test() 함수는 이  철학자가 배고프며 좌, 우 철학자가 모두 EATING 이 아니라면 자신도 EATING 상태로 바꾼 뒤 s[2] 라는 세마포 변수를 up 시킨다. (처음에 s[i] 는 모두 0으로 초기화 되어있다.)

 

테스트 함수가 끝나면 up(&mutex); 를 통해 임계구역을 벗어나고, down(&s[2]); 를 호출하며 아까 올렸던 s[2] 를 다시 0으로 감소시킨다.

 

이때 1번 프로세스가 실행이 되면, 1번 프로세스는 임계 구역에 들어와서 (뮤텍스 변수는 풀려있으므로 들어올 수 있다.)

test(1) 을 호출한다.

이때 자신의 좌우 철학자 중 하나인 2번 프로세스가 EATING 이므로 조건을 만족하지 못하고 그대로 함수가 종료된다.

따라서 s[1] = 0 이므로, down(&s[1]) 을 호출하면 그대로 1번 프로세스는 Blocked 상태로 빠진다.

 

만약 3번 프로세스가 실행이 되면, 3번 프로세스도 마찬가지로 Blocked 상태로 빠질 것이다.

 

반면 4번 또는 5번 프로세스의 경우에는 좌우 철학자의 상태 s[i] 가 문제없이 1로 증가했다가 감소할 수 있으므로 식사가 가능하다.

따라서 위 코드는 한 번에 한명의 철학자만 식사가 가능하다는 기존의 세마포 문제를 해결했다.

 

만약 2번 프로세스의 식사가 끝나면 put_forks() 가 호출되면서 임계 구역에 들어가고, 자신의 좌, 우 철학자가 현재 식사가 가능한지 체크하여 식사가 가능하다면 가능한 철학자의 상태를 EATING 으로, s[i] 를 1로 만든다.

(만약 2번과 4번 프로세스가 동시에 식사를 하고 있었고, 2번 프로세스의 put forks() 이후 4번 프로세스의 put forks() 가 호출되면 3번 프로세스의 s[3] 은 2가 되지 않을까 생각했었지만, 이 문제에서 세마포는 '바이너리 세마포' 로서 0 아니면 1의 값만 가질 수 있으므로 2가 되진 않는다.)

 

up() 메서드는 잠든 프로세스를 깨우므로 1번과 3번 프로세스가 깨어나면 이 둘의 down() 오퍼레이션이 마저 실행되면서 s[i]를 0으로 만들고 take_forks() 를 빠져나온 뒤  eating() 에 돌입한다.