데드락(Dead Lock)/교착상태

데드락(Dead Lock)/교착상태

• 두 개 이상의 프로세스나 쓰레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태이다.
• 무한히 다음 자원을 기다리게 되는 상태를 말한다.
• 시스템 적으로 한정된 자원을 여러곳에서 사용하려고 할 때 발생한다

데드락의 발생조건

• 4가지 모두 성립해야 데드락 발생(하나라도 성립하지 않으면 데드락 문제 해결 가능하다.)
  1. 상호 배제(Mutual exclusion)
     1. 자원은 한 번에 한 프로세스만 사용할 수 있다.
  2. 점유 대기(Hold and Wait)
     1. 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 한다.
  3. 비선점(No Preemption)
     1. 다른 프로세스에 할당된 자원은 사용이 끝날때까지 강제로 빼앗을 수 없다.
  4. 순환대기(Circular Wait)
     1. 프로세스 집합에서 순환 형태로 자원을 대기하고 있어야 한다.

데드락 처리

• 교착 상태를 예방&회피
  1. 예방(Prevention)
     • 교착 상태 발생 조건 중 하나를 제거하면서 해결한다.(자원낭비 심함)
       • 상호 배제 부정 : 자원들을 공유 가능하게 만들어주면 Mutual Exclusion이라는 조건을 만족시키지 않을 수 있다. 예를 들면 읽기 전용 파일(Read-only file)은 여러 프로세스가 동시에 접근할 수 있도록 허용해주는 방법 등이다. 하지만 Mutex lock과 같이 본질적으로 공유가 불가능한 자원들이 존재하기 때문에 일반적으로 사용하기는 어려운 면이 있다.
       • 점유 대기 부정 : 이 조건을 만족시키지 않기 위해, 프로세스가 어떤 자원을 점유하고 있다면, 다른 자원을 요청하지 못하게 만드는 방법을 사용할 수 있다. 이를 위해서 프로세스는 작업을 먼저 요청하고 할당을 받는 방법이나, 또는 자신이 가지고 있는 모든 자원을 방출하고 나서야, 새로운 자원을 요청할 수 있게 만드는 방법을 사용해야 한다.
         • 할당된 자원을 오랫동안 사용하지 않을 수 있기 때문에 자원의 이용도가 낮아질 수 있다.
         • 자주 쓰이는 자원들을 여러 개 필요로 하는 프로세스라면, 해당 자원들을 모두 모으지 못하면 실행할 수 없기 때문에 기아 문제(starcation)가 발생할 수도 있다는 것이다.
       • 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납한다.
       • 순환 대기 부정 : 모든 자원에 전체적인 순서를 부여하여, 각 프로세스들이 순서에 따라 오름차순으로만 자원을 요청할 수 있도록 만든다.
  2. 회피(avoidance)
     • 교착 상태 발생시 피해나가는 방법
       • 은행원 알고리즘
         • 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정상태로 남아있게 되는지 사전에 검사하여 교착상태를 회피한다.
         • 안정상태면 자원할당, 아니면 다른 프로세스들이 지원해지까지 대기한다.
• 교착상태를 탐지 & 회복
  • 교착 상태가 되도록 허용한 다음 회복시키는 방법
    1. 탐지(Detection)
       • 자원 할당 그래프를 통해 교착 상태를 탐지한다.
       • 자원 요청 시 , 탐지 알고리즘을 실행시켜 그에 대한 오버헤드가 발생한다.
    2. 회복(Recovery)
       • 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법이다.