13-01 교착 상태란

식사하는 철학자 문제

• 식사하는 철학자 문제(dining philosophers problem):

  • 교착 상태를 설명하기 위한 아주 고전적이고 재미있는 문제 상황이다.

  • 이 유명한 문제는 교착 상태가 어떤 상황에서 왜 발생하는지, 나아가 교착 상태를 어떻게 해결할 수 있는지를 엿볼 수 있는 가상의 문제 시나리오이다.

    

  • 위에 상황에서 모든 한 두 명의 철학자가 식사를 하는 데에 있어서는 딱히 문제가 발생하지 않을 것이다. 다만, 만약 모든 철학자가 식사를 하게 된다면 1번에서 모든 철학자가 왼쪽 포크를 집어들기에 집어들 오른쪽 포크가 없어 계속 생각만 하게 되므로, 교착 상태가 일어난다.

  • 즉, **교착 상태(deadlock)**란 일어나지도 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 말한다.

  • 교착 상태를 해결하기 위해서는

    1. 교착 상태가 발생했을 때의 상황을 정확히 표현해보기
    2. 교착 상태가 일어나는 근본적인 이유 이해하기

자원 할당 그래프

• 자원 할당 그래프(resource-allocation graph):
  • 이를 그려보면 교착 상태 발생 조건을 파악할 수 있다.

    • 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능

    • 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능

    • 첫째 프로세스는 원으로 자원의 종류는 사각형으로 표현한다.

      

    • 둘째 사용할 수 있는 자원의 개수는 자원 사각현 내에 점으로 표현한다.

      

    • 셋째, 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.

      

    • 넷째, 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.

      

교착 상태 발생 조건

• 아래 네 가지 조건 중 하나라도 만족하지 않으면 교착 생태가 발생하지 않음
• 아래 네 가지 조건을 모두 만족하면 교착 생태가 발생할 수 있음
  1. 상호 배제(mutual exclusion):
     • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
  2. 점유와 대기(hold and wait):
     • 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
  3. 비선점(nonpreemptive):
     • 어떤 프로세스라도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
  4. 원형 대기(circular wait):
     • 프로세스들이 원의 형태로 자원을 대기하는 상태

13-02 교착 생태 해결 방법

교착 상태를 해결하는 방법에는 크게 예방, 회피, 검출 후 회복 이렇게 세 가지가 있다.

교착 상태 예방

• 애초에 교착 상태가 발생하지 않도록 함
• 교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애버리기
  • 상호 배제를 없애면?
    • 모든 자원을 공유 가능하게 만들기
    • 이는 이론적으로는 가능하나, 현실적인 방법은 아니다.
  • 점유와 대기를 없애면?
    • 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분하기
    • 자원의 활용률을 낮출 수 있는 방식이다.
    • 이론적으로는 가능하나, 자원의 활용도가 떨어질 수 있다는 점이 단점이다.
  • 비선점 조건을 없애면?
    • 선점이 가능한 자원에 한해 효과적인 방법이다.
    • 모든 자원이 선점 가능한 것은 아니다.
  • 원형 대기 조건을 없애면?
    • 자원에 번호를 붙이고 오름차순으로 할당하면 원현 대기는 발생하지 않는다.
    • 자원에 번호를 붙이는 것은 어려운 작업이다.
    • 어떤 자원에 어떤 번호를 붙이느냐에 따라서 활용률이 달라진다.

교착 상태 회피

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주한다.
• 교착 상태가 발생하지 않을 만큼 조심 조심 할당하기.
• 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원을 배분한다.
• 안전 순서열(safe sequence):
  • 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서