교착 상태의 개요

교착 상태의 정의

2개 이상의 작업이 동시에 이루어지는 경우, 다른 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태 deadlock라고 한다.

교착상태는 아사 현상starvation과 비슷해 보이지만 차이가 있다. 아사 현상은 잘못된 정책으로 인해 프로세스 작업이 지연되는 문제인 반면, 교착 상태는 여러 프로세스가 작업을 진행하다 보니 발생하는 자연적인 현상이다. 

자원 할당 그래프

자원 할당 그래프 resource allocation graph는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프 directional graph로 표현한 것이다.

자원 할당 그래프에서 프로세스는 원으로, 자원은 사각형으로 표현한다. 자원을 사용하는 경우(할당된 경우)는 자원에서 프로세스로 향하는 화살표로 표시하고, 프로세스가 자원을 기다리는 경우(대기하는 경우)는 프로세스에서 자원으로 향하는 화살표로 표시한다.

https://blog.naver.com/doublebee1/220350605738

식사하는 철학자 문제의 자원 할당 그래프

(많은 책에 나오는 사례라서 설명을 하겠다.)

철학자 4명이 둥근 식탁에 앉아 식사를 하는데 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사가 가능하다는 조건이 있다. 철학자들은 음식을 먹기 위해 왼쪽의 포크를 잡은 뒤 오른쪽 포크를 잡으려고 옆을 볼 것이다. 그런데 옆에는 이미 왼손에 포크를 들고 있는 다른 철학자가 앉아있다. 이 문제의 결과는 오른쪽 포크를 잡지 못해 철학자가 모두 굶어 죽는다는 것이다. (비유가... 현실성이 없지만 오랫동안 사용된 예시다.)

 

위에 철학자 문제를 분석하자면

1. 철학자들은 서로 포크를 공유할 수 없다.

-> 자원을 공유하지 못하면 교착 상태가 발생한다.

2. 각 철학자는 다른 철학자의 포크를 빼앗을 수 없다.

-> 자원을 빼앗을 수 없으면 자원을 놓을 때까지 기다려야 하므로 교착 상태가 발생한다.

3. 각 철학자는 왼쪽 포크를 작은 채 오른쪽 포크를 기다린다.

-> 자원 하나를 잡은 상태에서 다른 자원을 기다리면 교착 상태가 발생한다.

4. 자원 할당 그래프가 원형이다. 

-> 자원을 요구하는 방향이 원을 이루면 양보를 하지 않기 때문에 교착 상태가 발생한다.

 

교착 상태 필요조건(중요)

상호 배제mutual exclusion, 비선점 non-preemption, 점유와 대기 hold and wait, 원형 대기 circular wait의 네 가지의 조건을 동시에 만족해야만 교착 상태가 발생한다. 이 네 가지 조건을 교착 상태의 필요조건이라 하며 네 가지 중 단 하나라도 충족하지 않으면 교착 상태가 발생하지 않는다. 

 

상호 배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. 

비선점: 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.

점유와 대기: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.

원형 대기: 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.

 

공부 마무리 문제

1) 2개 이상의 작업이 동시에 이루어져, 다른 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 무엇이라 하는가?

2) 교착 상태와 비슷해 보이지만 다른 현상을 무엇이라 하는가?

3) 잘못된 정책으로 인해 프로세스 작업이 지연되는 문제는 어떤 현상인가?

4) 여러 프로세스가 작업을 진행하다 보니 발생하는 자연적인 현상을 말하는 상태는 무엇인가?

 

5) 자원 할당 그래프에서 프로세스는 어떤 모형으로 나타내는가?

6) 자원은 어떤 모형으로 나타내는가?

7) 자원을 사용하는 경우(할당된 경우)는 화살표 방향이 어딜 가리키고 있는가?

8) 프로세스가 자원을 기다리는 경우(대기하는 경우)는 화살표 방향이 어딜 가리키고 있는가?  

 

9) 교착 상태 필요조건 4가지는 무엇인가?

10)  한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원은 무엇인가?

11) 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원은 무엇인가?

12) 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태는 무엇인가?

13) 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 하는것은 무엇인가?