CHAPTER 13 교착상태

keyword : 교착상태, 식사하는 철학자 문제, 자원할당 그래프, 교착상태 발생조건

교착상태(DeadLock)란?

식사하는 철학자 문제

• 교착상태를 설명하는 사고실험이다.

• 철학자들은 포크를 가지고 식사할 때 다음의 규칙을 따른다고 한다.

  

  1. 식사는 두 개의 포크로만 가능하다.
  2. 철학자들은 왼쪽 포크가 사용가능하면 집는다.
  3. 철학자들은 오른쪽 포크가 사용가능하면 집는다.
  4. 식사가 끝나면 오른쪽 포크부터 내려놓는다.
  5. 식사가 끝나면 왼쪽 포크를 내려놓는다.
  6. 1부터 반복하며 식사한다.

• 이 사고 실험에서 한두명의 철학자만 식사하는 경우에는 문제가 없다.

• 하지만 모든 철학자가 동시에 식사하려고 왼쪽포크를 집는 순간 이들은 영원히 기다리기만 한다.

• 이런 상태를 **교착 상태(Dead Lock)**이라고 한다.

• 앞서 배운 뮤텍스 락에서도 교착상태는 발생할 수 있다.

• 두 개의 프로세스가 각각 lock1과 lock2를 잠구고 다시 각각 lock2와 lock1이 풀리길 기다리는 모습이 바로 교착상태임.

• 교착상태를 해결하기 위해선 다음의 두 가지가 필요하다.

  1. 교착상태를 정확히 묘사
  2. 교착상태가 일어나는 근본적인 이유를 알아야 함.

자원 할당 그래프(Resource allocation graph)

• 교착상태를 단순하게 표현하는 그래프. 자원할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 프로세스가 어떤 자원을 기다리고 있는지 표현하는 그래프임.
• 다음의 규칙을 따른다.
  1. 프로세스는 원, 자원은 사각형으로 표현한다.
  2. 사용가능한 자원 개수는 사각형 내 점(dot)으로 표현한다.
  3. 프로세스가 자원을 사용중이면, 자원에서 프로세스로 화살표를 표시한다.
  4. 프로세스가 자원을 기다리면 프로세스에서 자원으로 화살표를 표시한다.
• 이 규칙을 통해 교착상태의 자원 할당 그래프를 그려보면, 이들은 순환하는 원의 형태라는 것을 알 수 있다.

교착상태의 발생 조건(1971년 코프만 교수가 공개한 코프만 조건)

• 아래의 네가지 조건이 모두 만족될 때 교착상태가 일어날 가능성이 생긴다.
  1. 상호배제
  2. 점유와 대기
  3. 비선점
  4. 원형 대기