[Operating System] Deadlock and Starvation

 

 

 

데드락은 두 개 이상의 프로세스가 절대 발생할 수 없는 이벤트를 무한정 기다리는 상황을 의미한다.

 

 

 

 

프로세스 P는 A자원을 가지고 있고, B자원을 운영체제에게 요청했다.

프로세스 Q는 B자원을 가지고 있고, A자원을 운영체제에게 요청하는데...

 

운영체제는 현재 B자원이 사용할 수 없는 상태이기에 프로세스 A를 Block상태로 변경시키고, 프로세스 B도 같은 이유로 Block상태로 변경시킨다.

 

 

 

 

x축은 프로세스 P가 실행하는 시간을, y축은 프로세스 Q가 실행하는 시간을 의미한다.

나머지 루트로 진행하는 경우 아무 문제가 발생하지 않는데.. 3번, 4번 루트로 실행되는 경우 데드락이 발생한다. 

 

한 사람이 P와 Q 프로그램을 작성한다면 데드락이 발생하지 않는 방식으로 작성하겠지만.. P를 작성하는 사람과 Q를 작성하는 사람이 다른 경우가 많다.

개별 프로그램은 데드락이 발생하지 않는 온전한 프로그램이지만 해당 프로그램을 함께 사용할 경우 이렇게 데드락이 발생할 수 있다.

 

컴퓨터 시스템에서의 리소스는 두 가지로 구분된다.

 

Reusable Resource - 재사용 가능한 리소스로, 프로세스가 자원을 사용하더라도 없어지지 않고, 반환 시 다른 프로세스가 이어서 사용할 수 있는 자원이다.

Consumable Resource - 소비성 자원으로, 재사용 할 수 없는 자원이지만.. 데드락이 발생할 수 있다. 

 

 

 

 

Reusable Resource에서, 전체 메모리가 200KB인 시스템에서 여러 프로세스가 메모리를 요청한다고 생각해보자.

전체 메모리가 200이니.. P1과 P2가 각각 메모리를 요청하다 보면 어느 순간 메모리를 할당할 수 없는 순간이 찾아온다.

P1은 P2가 실행되고 메모리를 반환하기를 기다리고, P2는 P1이 실행되고 메모리를 반환하기를 기다려 데드락이 발생한다. 

 

Consumable Resource에서, P1은 P2가 메세지를 보내기를 기다리고 P2는 P1이 메세지를 보내기를 기다린다.

모두 Blocked상태에서 대기하게 돼 데드락이 발생한다.

 

 

 

 

데드락을 시각적으로 표현하기 위해 Resource Allocation Graph를 사용한다. 

프로세스는 원형으로, 컴퓨팅 리소스는 사각형으로, 리소스의 인스턴스는 사각형 내 검은 점으로 표현한다. 

 

그림처럼 리소스의 개수에 따라서 같은 형상이라도 데드락이 발생하지 않는 경우가 있다.

 

데드락은 아래 네 가지 조건을 동시에 만족하는 경우 발생한다.

 

1. Mutual Exclusion - 자원을 할당받은 프로세스가 해당 자원을 독점적으로 사용해야 한다. 

2. Hold and Wait - 데드락에 개입된 프로세스가 다른 컴퓨팅 리소스를 요청해야 한다. 

3. No Preemption - 모든 프로세스는 다른 프로세스의 컴퓨팅 리소스를 강탈할 수 없다. 

4. Circular Wait - Hold and Wait성질이 데드락에 개입된 모든 프로세스에게 적용될 때 Circular Wait 가 발생한다.

 

 

 

---

 

 

 

데드락이 발생한 경우 어떻게 해결해야 할까?

데드락이 발생하지 않도록 프로그램을 작성하거나, 운영체제가 데드락을 인식하고 복구하는 작업을 수행한다면 좋겠지만, 실제로 윈도우, 리눅스 등 여러 운영체제는 데드락이 발생했을 때 아무 작업도 처리하지 않고 관리자가 직접 데드락을 처리하도록 유도한다.

 

바로 전에 데드락이 발생하는 네 가지 조건을 다뤘는데, 반대로 말하면 네 가지 중 하나라도 만족하지 않는다면 데드락이 발생하지 않는다고 할 수 있다. 

 

1. Mutual Exclusion - 여러 프로세스가 하나의 자원을 동시에 사용하도록 해야 하는데.. 합리적이지 않다.

2. Hold and Wait - 특정 자원을 가진 상태에서 다른 자원을 요청하니, 프로세스가 시작 할 때 필요한 자원을 모두 가져가도록 하면 되는데... 아주 잠깐 동안만 사용되는 리소스도 프로세스의 전체 러닝타임동안 점유되기에 리소스를 효율적으로 사용할 수 없다.

3. No Preemption - 다른 프로세스가 가진 리소스를 강탈하는건 합리적이지 않다. 

4. Circular Wait - 그나마 고려해 볼 만한 방법이다.

 

 

프로세스 P4가 P1이 점유한 리소스를 기다리지 않으면 데드락이 발생하지 않는다. 

 

여기서 P4만 시작할 때 1번과 4번 리소스를 모두 가진 상태로 실행된다면? 

프로세스 P4에 대해서만 Hold and Wait을 못 하게 설정하는 경우 전체 프로세스에 대해 적용하는 것 보다는 낫지만.. 당연히 합리적이지는 않다.

 

그런데 개발자가 이 사실을 인지하지 못하고 코드를 작성하면.. 데드락을 피할 수 없다.

현실적으로 Circular Wait를 조작하는 방법도 힘들다.

 

데드락 발생 시 운영체제가 직접 해결하는건 굉장히 힘드니.. 운영체제는 관리자가 직접 데드락을 처리하도록 유도한다.

 

 

데드락이 발생했을 때, 데드락과 관계된 모든 프로세스를 죽이는 방식으로 데드락을 해결할 수 있지만, 오버헤드가 너무 크니 데드락에 관계된 프로세스들을 하나씩 죽이면서 데드락이 해결되는지 확인하는 방법을 사용한다.

 

 

 

 

Dining Philosophers Problem은 Deadlock과 Starvation 문제를 형상화한다.

Starvation은 자원 할당까지 시간이 오래 걸리는 상황을, Deadlock은 Starvation이 영원히 지속되는 상황을 의미한다.

 

철학자들은 음식을 담을 때 옆사람의 포크와 자신의 포크를 같이 사용해야 하고, 모든 사람들은 식사하는 시간이 다르다.

몇 시간 후 철학자들은 자신의 접시에 음식을 가져왔지만 음식을 먹은 사람은 아무도 없었다. 

 

 

 

왼쪽처럼 코드를 작성하면 데드락이 발생한다. 

모든 프로세스가 wait(fork[i]) 까지만 실행하고 CPU 시간이 만료된다면 wait(fork[(i+1) mod 5]) 를 아무도 실행하지 못하고 Block된다.

 

room 세마포어를 사용해 동시에 식사할 수 있는 철학자의 최대 수를 제한하자.

 

 

 

---

 

 

 

CPU를 프로세스에게 할당하기 전에 데드락으로부터 안전한 상태인지 판단하는 방법도 있는데.. 이 방법 중 하나가 Banker's Algorithm 이다.

 

알고리즘의 동작 방식이 은행에서 자금을 조달하는 방식과 비슷해 Banker's 라는 이름이 붙었다.

 

은행이 100을 대출해줄때, 금고에 70밖에 없다고 생각해보자.

미리 빌려간 사람이 돈을 갚으면 은행은 다른 사람에게 돈을 대출해 줄 수 있다. 

그러니 다른 사람이 돈을 갚아 금고에 100이 채워질 때 까지 돈을 빌리러 온 사람을 잠시 기다리게 한다.

 

프로세스는 고객 / 은행은 운영체제 / 돈은 컴퓨팅 리소스라고 생각하면 된다. 

 

Banker's 알고리즘이 제대로 작동하려면 컴퓨터 시스템 내 모든 프로세스들이 리소스를 얼마나 필요로 하는지 운영체제가 알고 있어야 한다.

 

사실 여기서부터 일반 컴퓨터에서는 불가능하다. 운영체제도 프로세스가 시작하면서 리소스를 얼마나 쓰는지 알 수 있어서.. 

그리고 Banker's 알고리즘은 프로세스가 리소스를 요청 할 때 마다 수행되어야 하는데, 이 부분도 오버헤드가 너무 크다.

 

이런 이유로 Banker's 알고리즘도 현실적으로 사용되지 않고 운영체제는 데드락을 운영자가 직접 처리하도록 유도한다.

 

 

 

 

 

프로세스들이 리소스를 얼마나 필요한지 알고 있으면 프로세스에게 CPU를 할당하기 전에 메모리를 계산해 해당 프로세스에게 CPU를 할당했을 때 데드락이 발생할지 안할지를 판단할 수 있다.