Deadlock?

교착 상태라고도 한다. 두개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태이다. 시스템 적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다. 아래 4가지 모두 성립해야 데드락이 발생한다

• 원형대기 : 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야한다
• 비선점 : 다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없다
• 점유와 대기 : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 한다
• 상호 배제 : 자원은 한번에 한 프로세스만 사용할 수 있다

식사하는 철학자

교착 상태를 설명하기 위한 문제
여러 프로세스(또는 스레드)가 동시에 돌아갈 때 교착 상태가 나타나는 원인을 직관적으로 알 수 있다.
기아 상태가 발생할 수 있다.

해결법

• 데드락이 발생하지 않도록 예방(prevention)하기

  • 한번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다. 그러나 추후 동기화 관련 문제가 발생할 수 있다

  • 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서 대기 조건을 성립하지 않도록 한다

  • 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다

  • 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 한다

    ⇒ 시스템의 처리량이나 효율성을 떨어트리는 단점이 발생할 수 있다.

• 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance)하기
  • 시스템의 프로세스들이 요펑하는 모든 자원을 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 안정 상태에 있다고 말한다. 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면 그것을 안전 순서라고 부른다
  • 자원을 할당한 후에도 시스템이 항상 안정 상태에 있을 수 있도록 할당을 허용한다는 뜻
  • 은행원 알고리즘
    • 다익스트라가 제안한 기법. 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션해서 안정 상태에 들 수 있는지 여부를 검사하는 것. 최대 자원 요구량과 할당할 수 있는 자원 수가 일정해야한다는 제약조건이 있다.
• 데드락 발생을 허용하지만 데드락을 탐지(detection)하여 데드락에서 회복하기
  • 탐지 기법
    • Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색하거나 자원 할당 그래프를 통해 탐지한다
  • 회복 기법
    • 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용한다
    • 단순히 프로세스를 1개 이상 중단 시킨다
      • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있음
      • 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있음
    • 자원 선점하기
      • 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에게 할당해주는 방법