식사하는 철학자 문제(이진세마포어,계수세마포어,동기화,임계구역문제)

식사하는 철학자 문제

철학자들은 생각하거나, 밥을먹거나, 배가고프거나 3가지 상태를 가질 수 있다.

철학자들은 밥을 먹을때 왼쪽 포크와 오른쪽 포크를 각 손에 하나씩 들어야 식사를 할 수 있다.

하지만 사람이 5명인데 포크는 5개밖에 없다. 그래서 최대 2명만 동시에 밥을 먹을 수 있다.

프로세스가 어떤 공유자원(여기선 포크)을 가지고 아무한테도 주지 않으면서 다른 프로세스의 공유자원을 달라고 요구하게 되면 

데드락이 발생 할 수 있다.

이 문제가 그런데, 

이것을 해결하기 위해서 세마포어를 사용해야 한다.

mutex라는 이진 세마포어를 활용해서 포크를 손에 쥐는 행위를 하는것을 한 시점에 한 사람만 가능하게끔 해주고

각 프로세스 별로 세마포어를 또 따로 두어서 최대 2명까지 식사를 하게끔 해주어야 한다.(s[i])

첫번째 해결방법

왼쪽 포크들고, 오른쪽 포크들고, 식사하고, 왼쪽포크 내려놓고, 오른쪽 포크 내려놓는다.

이렇게 되면 모두가 동시에 왼쪽 포크를 든 상태에서 오른쪽 포크를 들려고 하지만 남은 포크가 없으므로 들 수 없고 결국엔 프로세스가

아무일도 할 수 없게 되면서 데드락이 발생하게 된다.

두번째 해결방법

왼쪽 포크를 들고나서 오른쪽 포크를 들 수 있나 보고 안되면 두 포크를 모두 내려놓는다.

->이런식으로 하면 모든 프로세스가 동시에 왼쪽 포크를 들었을때 남은 포크가 없어서 왼쪽 포크를 다시 내려놓고, 또다시 왼쪽 포크를 들고..

이런 행위가 반복 되게 되어서 결국엔 기아문제가 발생한다.(starvation)

세번째 해결방법

왼쪽 포크를 잡고나서 오른쪽 포크가 있나 봤는데 없으면 포크를 모두 내려놓고 랜덤한 시간동안 기다린 다음에 다시 방금 과정을 반복한다.

그러면, 모두가 동시에 왼쪽포크를 집는다고 하더라도 서로 기다리는시간이 다르므로 결국엔 어떤 한 사람은 식사를 할 수 있지만,

낮은 확률로 starvation이 발생할 수 있다. 

그렇기 때문에 원자력발전소나 비행기에 들어가는 프로그램처럼 완벽해야 하는 프로그램에는 사용할 수 없다.

네번째 해결방법

이진 세마포어로만 포크를 드는 행위(임계구역)를 하는곳을 감싼다. 그렇게 되면 포크를 드는 행위를 하려면 이진 세마포어의 제어를 받게 되므로

어느 한순간에는 한 프로세스만이 포크를 드는 행위를 할 수 있다.

하지만 이진 세마포어로만 감싸버리면 임계구역에 들어간 프로세스가 하나 있을때 다른 모든 프로세스들은 임계구역 밖에서 기다려야 한다.

즉, 한명이 식사중일때 반대편의 사람도 식사가 가능함에도 불구하고 임계구역에 프로세스가 들어가 있기 때문에 식사를 할 수 없다.

그렇기 때문에 우리는 mutex라는 이진 세마포어 이외에도 각 프로세스 별로 세마포어를 따로 두어서 최대한의 사람들이 식사를 할 수 있게끔 해야한다.

최종해결방법 -> 왼쪽 포크와 오른쪽 포크를 동시에 들게끔하고 그것을 세마포어들로 감싼다.

내 상태가 HUNGRY이며 양 옆의 사람의 상태가 EATING인지 아닌지 확인하는 행위는 한번에 한 프로세스만 

할수있다. (mutex로 제어한다)

확인해서 내가 포크를 들어도 되는 상황인 경우 그 이후에 블락이 되지 않고 포크를 못 들었다면 블럭된다.

(각 프로세스별 세마포어인 s[i]로 제어한다)

오른쪽 그림 처럼 각 사람에 번호를 지정했다고 가정하자.

1번 프로세스가 take_forks(1)을 호출했다.

mutex : 1->0  (뮤텍스가 0이 된순간 다른 프로세스는 임계구역에 접근할수없음)

state[1] : HUNGRY

test(1) -> 현재 내가 HUNGRY고 양옆이 식사를 안하고 있으므로 내 상태는 EATING이고 

세마포어 값을 1 증가시켜서 s[1] == 1 이다.

mutex : 0->1 (뮤텍스가 1이 된순간 다른 프로세스는 임계구역에 접근할수있음)

down(&s[1]) : s[1] : 1->0 만약 포크를 얻지 못한 상태에서 down을 호출하면 프로세스는 블락됨.

여기까지 실행하고 나서 스케쥴링이 일어나서 philosopher(2)가 실행 됬다고 가정하자.

take_forks(2)가 호출되고

mutex : 1->0 (뮤텍스가 0이 된순간 다른 프로세스는 임계구역에 접근할수없음)

state[2] = HUNGRY

test(2) : 1번 프로세스가 eating중이므로 아무 일도 하지 않고 리턴됨

mutext : 0->1 (뮤텍스가 1이 된순간 다른 프로세스는 임계구역에 접근할수있음)

down(&s[2]) : s[2] : test안에서 s[2]의 값을 1로 만들지 못했으므로 원래 들어있던 값인 0에서 down이 실행되기 때문에 2번 프로세스는 블락된다.

이상태에서 마찬가지로 0번프로세스가 실행된다 하더라도 0번프로세스도 마찬가지 이유로 블락 될 것이다.

즉, 1번이 식사하는 상태에서는 그 양옆의 프로세스는 실행되더라도 블락 되게 된다.

하지만 4번이나 3번 프로세스가 실행된다면 양옆이 식사를 하고 있지 않으므로 test 함수 안에서 s[3],s[4]를 up해주기 때문에 test 함수를 빠져나와서 down연산을 해주더라도 1->0이 되기때문에 블락 되지 않고 식사를 할 수 있게 된다.

이처럼 mutex라는 이진 세마포어로 포크를 내가 들수있나 확인하는 행위는 5개의 프로세스중 

한 시점에서 단 하나의 프로세스만이 가능하게 끔 도와주고 양옆 포크를 확인하는 행위 안에 또 카운팅 세마포어를 집어넣어서 만약 내가 배가고픈상태인데 양옆이 식사를 하지 않는 상황이면 각 프로세스의 카운팅 세마포어를 1 증가시켜서 마지막에 down연산을 하더라도 아무일이 안일어 나게끔 해준다. (포크를 들었으면 블락되지 않고 포크를 못들었으면 take_forks()마지막 부분에서 블락된다)

그후에 음식을 먹고 있던 프로세스가 put_forks를 호출하면 test(LEFT) test(RIGHT)연산을 통해서 자신의 왼쪽과 오른쪽 프로세스중 배가 고팠지만(HUNGRY상태에서 take_forks() 마지막 부분에서 잠든 프로세스) 내가 식사를 하고 있었기 때문에 잠들고 있었던 프로세스가 있으면 깨워준다.

1. Deadlock 정의

- 영원히 오지않는 이벤트를 기다리는 것 (응답없음 상태같은;)

- A라는 프로세스는 B가 가진 자원 있어야 동작 가능하다, 그래서 B 작업이 끝나서 자원을 넘겨주기를 기다리고 있는데

   B라는 프로세스 역시 A가 가진 자원이 있어야 있어야 하기 때문에 A작업이 끝나기만을 기다리는 상태.

즉 무한 교착 상태를 말한다. ( 두 작업은 영원히 끝날 수 없다)

교착 상태의 조건

1971년에 E. G. 코프만 교수는 교착상태가 일어나려면 다음과 같은 네 가지 필요 조건을 충족시켜야 함을 보였다.

1. 상호배제(Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.
2. 점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
3. 비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
4. 순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

이 조건 중에서 한 가지라도 만족하지 않으면 교착 상태는 발생하지 않는다. 이중 순환대기 조건은 점유대기 조건과 비선점 조건을 만족해야 성립하는 조건이므로, 위 4가지 조건은 서로 완전히 독립적인 것은 아니다.

식사하는 철학자 문제에서 왼쪽포크를 들고나서 오른쪽 포크를 보고 비어있으면 오른쪽 포크를 들고 식사를 하는 알고리즘은 데드락 상태에 빠질 수 있는 알고리즘이다.

1. 상호배제 : 기본적으로 포크를 드는 행위는 세마포어로 감싸있기 때문에 상호배제가 지켜진다.

2.점유대기 : 왼쪽 포크를 가진 상태에서 오른쪽 포크가 올때까지 기다린다.

3.비선점 : 오른쪽 포크를 가진 프로세스의 자원을 뺏을 수 없다.

4.순환대기 : 각 프로세스가 원형으로 꼬리를 문 상태로 다음 프로세스가 요구하는 자원(오른쪽 포크)를 가지고 있다.

이 4가지 조건이 식사하는 철학자 문제에서 만족되기 때문에 데드락이 발생 할 수있다.

 이 상황에서 철학자들이 동시에 오른쪽 포크를 집어든다면?

철학자들은 포크를 공유할 수 없고(상호 배제)

자신의 왼쪽에 앉은 철학자가 포크를 놓을 때까지 기다린다.(점유 대기) 

철학자들은 왼쪽 철학자의 포크를 빼앗을 방법도 없으며,(선점 불가) 

각 철학자들은 자신의 왼쪽 철학자의 포크를 대기한다.(순환대기)

 이러한 교착 상태를 회피하려면 발생조건 4가지 중 한가지만 해제하면 된다. 상호 배제와 선점 불가의 경우, 문제의 조건 때문에 해소가 불가능 하다. 

'점유 상태로 대기'(오른쪽 포크를 든 상태로 왼쪽 포크를 기다리는 상태)를 해제하려면 왼쪽 포크를 집을 수 없을 때, 오른쪽 포크를 식탁 위에 내려놓는 방법이 있다. '순환 대기'를 해소하려면 포크에 우선 순위를 매기는 방법이 있다.

보통 데드락을 해결할때 상호배제와 선점불가로는 해결하지 않는다. 이 두개는 없어서는 안되기 때문이다.

그래서 보통 2번이나4번으로 해결하게 되는데, 

식사하는 철학자문제에서 2번을 제거한것이 바로 오른쪽 포크를 들고나서 왼쪽 포크를 들 수 없으면 오른쪽 포크마저 식탁에 내려놓는 알고리즘이다. 하지만 이 문제 역시 기아문제가 발생할수 있다는 문제점이 있었다.

그래서 나온 완벽한 해결책은 2번과 4번을 제거한것이다. 

한번에 포크를 하나만 들 수 있게 하는게 아니라 동시에 왼쪽 오른쪽 포크를 들게 한다. 

그리고 나서 각 프로세스마다 세마포어를 하나씩 두게 한다. 동시에 2개의 포크를 들게 한다는것은 점유대기를 없앤다는것이다.

이렇게 하면 오른쪽 포크를 든 상태에서 왼쪽 프로세스의 포크를 얻을때 까지 기다리는 점유대기가 사라진다.

동시에 2개의 포크를 들면 또 다른 포크를 얻기 위해서 기다리는 일이 없어진다. 따라서 점유대기가 사라진다.(2번제거) 또한 각 프로세스는 자기가 포크를 들었으면 또 포크를 달라고 요구하지 않으므로 덩달아 순환대기도 제거 된다. (데드락은 포크를 2개 동시에 드는 행위로 제거 되었다.)

만약에 각 프로세스별로 세마포어가 없고 이진 세마포어로 포크를 들고 내려놓는 행위가 한번에 한 프로세스만 가능하게끔 해놨다고 가정해보자.

그렇게 될 경우 1번 프로세스가 포크를 들었을때 0번과 2번 프로세스가 take_forks를 호출하게 되면 아무일도 없이 함수 호출이 끝나게 된다.

그렇게 되면 eating()을 할꺼고 put_forks()를 차례로 호출하게 될텐데, 사실 1번 프로세스가 먹고있는 와중에 0번과 2번은 포크를 집을 수 없게 되서 1번이 식사를 마칠때까지 블락되어야 한다. 

그래서 각 프로세스별로 세마포어를 따로 두어서 1번이 식사중일때 양옆은 1번이 식사를 끝낼때 까지 기다리게끔 한 것이다.